MACHINE LEARNING

Machine Learning

The Wall Following Robot

The goal of a wall-following robot is to navigate through open spaces until it encounters a wall, and then navigate along the wall at some fairly constant distance. The successful wall-follower should traverse the entire circumference of its environment at least once without straying either too close, or too far from the walls.

Figure 1 - The four room configurations used to develop the wall-following behavior.

A two-dimensional simulated environment is used to test the navigation algorithms developed by GP. The environment consists of four completely enclosed rooms with wall contours of varying complexity. Each individual algorithm from the GP population is tested in each of the four rooms, and scored on how well it performs the wall-following behavior. By testing each individual in a number of different environments GP is encouraged to develop general-purpose solutions rather than simply memorize a set of movements, or capitalize on insignificant coincidental properties of the simulator.

A screen display of the simulation environment is shown in figure 1. The dark shaded areas represent the walls of the environment. The lightly shaded areas represent the desired path of the robot. The desired path is for display only - the robot has no visibility of these areas. All sensory input to the robot comes through the use of simulated range finders. The robot has eight range finders positioned at 45 increments about its center. The solid square in the center of each room designates the starting point of the robot in that room.

Each room in the simulated environment consists of a 40 by 40 array of grid locations that are each 10 pixels square. The pixel size is used as the basic unit of movement. The navigation algorithms are scored on how many of the lightly shaded "corridor" grid locations they can pass through - the more the better. The robot is allowed to wander between 10 and 20 units from the wall (the width of a corridor grid) without any performance demerits. GP calculates fitness based on the number of corridor grids that are not visited during the course of a run, and attempts to minimize the following fitness equation:

1000 * NumberOfCorridorGridsNotVisited +

100 * DistanceOfEndingPointFromCenterOfCorridor +

TotalDistanceTravelled

NumberOfCorridorGridsNotVisited is the most significant aspect of fitness. A weighting factor of 1000 ensures that GP will remain motivated to navigate through corridor grids, even when there are only a few unvisited grid points remaining.

DistanceOfEndingPointFromCenterOfCorridor is the distance from the final resting point of the robot to the center of the nearest corridor grid (i.e., 15 units from the nearest wall). This term is used to "kick-start" the GP process. Without it, a robot that does not move at all (travels zero distance) will score higher than a robot that moves towards a wall but does not quite reach the corridor grids, and GP will often suffer premature convergence on these solutions. In other words, this term encourages initial exploration by rewarding algorithms that move towards walls, even if they do not reach ...