Industrial Applications of Genetic Algorithms:Development of Mobile Robot Wall-following Algorithms Using Genetic Programming

Previous | Table of Contents | Next

The GP process initially creates a number of computer programs by randomly combining functions and terminals into complete tree structures. This collection of programs, or individuals, is called a population. The GP engine evaluates and assigns a fitness value to each of the individuals in the population. Not surprisingly, the performance of the individuals in this initial, randomly created population can be quite poor. Nevertheless, there is variance in the performance levels: some individuals perform less poorly than others. The population is ranked according to fitness. A new population is generated by selecting individuals from the previous generation to participate in creative operations. Individuals are selected for inclusion in the creative process based on their fitness - the higher the fitness, the higher the likelihood of inclusion. Three basic creative operations are used in GP: reproduction, crossover, and mutation. Reproduction is simply the copying of an individual from the previous generation into the next generation without any modification of its structure (Figure 14.2).

Figure 14.2 The reproduction operation.

Mutation is performed by randomly selecting a node in an individual tree structure, and removing that node along with any sub-tree that may exist below it. A new sub-tree is then generated randomly and “grafted in” at the position where the original node was removed. Figure 14.3 shows an example of mutation.

Figure 14.3 The mutation operation.

Crossover involves selecting two individuals from the previous generation and selecting a node at random in each of them. The selected nodes, along with any sub-trees that exist below them, are exchanged between the two individuals, as shown below in Figure 14.4.

Figure 14.4 The crossover operation.

As successive populations are created by applying these genetic operators, the average performance of the population tends to improve, and the performance of the best individual in the population can improve quite dramatically. There is no guarantee that GP will find an optimal solution (in less than infinite time), but a well thought out set of functions and terminals with a reasonable fitness test will usually produce good results.

PROBLEM DESCRIPTION

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 without either staying too close, or straying too far from the walls.

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 variety 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 [2].

A screen display of the simulation environment is shown in Figure 14.5. 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.

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

Each room in the simulated environment consists of a 40 by 40 array of grid locations which are each 10 pixels square. The pixel size is used as the basic unit of movement.2 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 which are not visited during the course of a run, and attempts to minimize the following fitness equation:

> 2Robot position is displayed at the nearest pixel, but is not constrained to pixel centers.

  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 pixels 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. In other words, this term encourages initial exploration by rewarding algorithms that move towards walls, even if they do not reach those walls. This provides the necessary scoring gradient in the early generations to encourage GP to develop individuals that leave their starting location and move towards the walls. A weighting factor of 100 is applied to this term so that it will eclipse TotalDistanceTravelled any time the robot does not reach the corridor grids.3

> 3This term can also eclipse (or at least compete with) TotalDistanceTravelled if a robot moves away from the walls after passing through one or more corridor grids. While that is not the intent of this term, the effect does not seem to hinder performance and may even be beneficial.

TotalDistanceTravelled is the least significant term in the fitness equation. It is included to discourage the navigation algorithms from traversing the corridor grids by spiraling haphazardly through the open spaces of the environment. A robot that navigates directly through the center of the corridor grids will score higher than one that meanders back and forth across the grids.

Previous | Table of Contents | Next

Copyright © CRC Press LLC