Autonomous Maze Navigation

The maze navigation is a classic computer science problem related to the autonomous navigation domain. In this chapter, you will learn how neuroevolution-based methods can be used to solve the challenge of maze navigation. Also, we will explain how to define a goal-oriented fitness function using the fitness scores of the navigator agent calculated as a derivative of the agent's distance from the final goal. By the end of this chapter, you will understand the basics of training an autonomous navigation agent using neuroevolution methods and will be able to create the more advanced maze solver that will be introduced in the next chapter. You will become familiar with advanced visualization techniques that will make it easier to understand the results of algorithm execution. Also, you will obtain hands-on experience of writing simulators of maze-navigating...

Technical requirements

The following technical requirements should be met to complete the experiments described in this chapter:

• Windows 8/10, macOS 10.13 or newer, or modern Linux
• Anaconda Distribution version 2019.03 or newer

The code for this chapter can be found at https://github.com/PacktPublishing/Hands-on-Neuroevolution-with-Python/tree/master/Chapter5

Maze navigation problem

The maze navigation problem is a classic computer science problem that is closely related to creating autonomous navigation agents that can find a path through ambiguous environments. The maze environment is an illustrative domain for the class of problems that have a deceptive fitness landscape. This means that the goal-oriented fitness function can have steep gradients of fitness scores in dead ends in the maze that are close to the final goal point. Such areas of the maze become the local optima for objective-based search algorithms that may converge in these areas. When the search algorithm converges in such deceptive local optima, it cannot find an adequate maze-solver agent.

In the following example, you can see a two-dimensional maze with local optima dead ends, which are shaded in:

The two-dimensional maze configuration

The maze configuration in...

Maze simulation environment

The environment for the maze simulation consists of three major components that are implemented as separate Python classes:

• Agent: The class that holds information related to the maze navigator agent that is used by simulation (see the agent.py file for the implementation details).
• AgentRecordStore: The class that manages the storage of records relating to evaluations of all the solver agents during the evolutionary process. The collected records can be used to analyze the evolutionary process after its completion (see the agent.py file for the implementation details).
• MazeEnvironment: The class that contains information about the maze simulation environment. This class also provides methods that manage the simulation environment, control the position of a solver agent, perform collision detection, and generate the input data for sensors of the agent...

Objective function definition using the fitness score

In this section, you will learn about the creation of successful maze-solver agents using a goal-oriented objective function to guide the evolutionary process. This objective function is based on the estimation of the fitness score of the maze solver by measuring the distance between its final position and the maze exit after executing the 400 simulation steps. Thus, the objective function is goal-oriented and solely depends on the ultimate goal of the experiment: reaching the maze exit area.

In the next chapter, we will consider a different approach for solution search optimization, which is based on the Novelty Search (NS) optimization method. The NS optimization method is built around exploring new configurations of the solver agent during evolution and doesn't include proximity to the final goal (in this case, the...

Running the experiment with a simple maze configuration

We start our experiments related to the creation of the successful maze navigation agent with a simple maze configuration. The simple maze configuration, while having the deceptive local optima cul-de-sacs discussed earlier, has a relatively straightforward path from the start point to the exit point.

The following diagram represents the maze configuration used for this experiment:

The simple maze configuration

The maze in the diagram has two specific positions marked with filled circles. The top-left circle denotes the starting position of the maze navigator agent. The bottom-right circle marks the exact location of the maze exit that needs to be found by the maze solver. The maze solver is required to reach the vicinity of the maze exit point denoted by the specific exit range area around it in order to complete the task...

Exercises

1. Try to increase the compatibility_disjoint_coefficient parameter in the maze_config.ini file and run the experiment with new settings. What impact does this modification have on the number of species produced during the evolution? Is the neuroevolution process able to find a successful maze solver?
2. Increase the population size by 200% (the pop_size parameter). Was the neuroevolution process able to find a solution in this case, and if so, how many generations did it take?
3. Change the seed value of the random number generator (see line 118 of the maze_experiment.py file). Does the neuroevolution process succeed with this new value?

Running the experiment with a hard-to-solve maze configuration

The next experiment in this chapter is to run the neuroevolution process to find an agent that can solve a maze with a more complex configuration of walls. This hard-to-solve maze configuration introduces powerful local fitness optima traps and does not have a straightforward route from the start position of the agent to the exit area of the maze. You can see the maze configuration in the following diagram:

The hard-to-solve maze configuration

The maze configuration has its start position in the bottom-left corner, marked with a green circle, and the position of the maze exit point is in the top-left corner, marked with a red circle. You can see that, to solve the maze, the navigator agent must develop a complex control strategy that allows it to avoid the local fitness optima traps around the starting point. The...

Exercises

1. Try to increase the population size by tweaking the pop_size parameter in the maze_config.ini file. Did this help the neuroevolutionary process to evolve a successful maze solver?

This may take a long time to execute.

Summary

In this chapter, you have learned about a class of planning and control problems that use goal-oriented fitness functions that have a deceptive definition landscape. In this landscape, there are multiple traps created by the local optima areas of the fitness function that mislead the solution search process, which is based only on the fitness score calculated as a derivative of the distance from the agent to the goal. You have learned that the conventional goal-oriented fitness function can help the search process to create a successful maze navigator agent for a simple maze configuration, but failed with a more complex maze due to the local optima traps.

We presented a useful visualization method that allowed us to visualize the final positions of all evaluated agents on the maze map. With this visualization, you can make assumptions about the performance of the evolutionary...