Application of coevolution strategy to solve the problem of autonomous navigation trough the maze

Abstract

This study explores the use of coevolutionary methods to address the challenge of navigating through complex mazes using autonomous agents controlled by artificial neural networks (ANNs). It underscores a critical impediment to algorithmic optimization: the close interdependence between the task's goal and the objective function used for optimal solution discovery. The task's goal is clear—identify the most efficient route through the maze. However, the objective function's formulation is more complex. In complex maze layouts, numerous deceptive areas may appear proximate to the exit but culminate in dead ends. Consequently, an elementary objective function that merely gauges the proximity to the exit can encounter numerous local optima within this deceptive search space, hindering the search for optimal solution. As maze complexity increases, such an objective function inevitably becomes ensnared in a local optimum, rendering the navigation issue unsolvable. To counteract this, the study proposes a coevolution strategy involving a population of decision-making agents and a population of objective function candidates. This approach diverges from prior research by incorporating the NEAT algorithm to steer the coevolution of both populations. Additionally, the Novelty Search (NS) method was suggested to optimize the search within the potential solution space, favoring the most novel solutions. The paper details the mathematical framework for crafting the objective function template, which integrates the novelty value of the discovered solution and its distance from the maze's exit. This framework serves as the foundation for defining the genomes of the organisms — candidates for the objective functions. For comparison with preceding works, an experiment was conducted to evaluate the efficacy of the proposed coevolution method in resolving the problem of navigation within a complex maze environment.

Prombles in programming 2024; 2-3: 263-270