RESULTS

The genetic programming engine was, indeed, able to organize the functions and terminals described above into fairly proficient wall-following algorithms. This section describes a typical evolutionary cycle. The initial generations of each run, as expected, performed quite poorly. The robot paths in Figure 14.6 (shown as dotted lines) are typical of early generations. The robot manages to maneuver into the wall-following corridor and claim a few grid points, but has not yet figured out how to turn and follow the corridor. (The target corridor shading has been removed for clarity.)

Figure 14.6  Typical result of early generations in a GP run.

The GP-generated code that produced the behavior displayed in Figure 14.6 is shown below. The line numbers are for reference only, and the indentation represents the calling hierarchy. This particular solution capitalizes on the hysteresis band in the WhileTooFarFromWall function to skim the edge of a wall following corridor in the upper right room.

It begins with a WhileTooFarFromWall loop, with a Do2 function as the body. The robot starts in a too-far-from-wall position, so the Do2 is evaluated. The first argument of the Do2 is a TurnAwayFromClosestWall terminal which sets the direction of the robot to the left in all cases. The second argument of the Do2 is another WhileTooFarFromWall loop with a MoveForward terminal as its body. This loop repeats until the too-far-from-wall test fails (i.e., the robot ends up within allowable wall-following range). The inner WhileTooFarFromWall loop terminates at that point. The Do2 is complete, so the outer WhileTooFarFromWall loop evaluates the position of the robot. Finding that the robot is not too-far-from-wall, this loop terminates and the program ends with a total of 13 hits out of the possible 933.

0	WhileTooFarFromWall
1		Do2
2			TurnAwayFromClosestWall
3			WhileTooFarFromWall
4				MoveForward
END

GP soon begins to develop solutions that exhibit rudimentary wall-following behavior, as shown in Figure 14.7. These solutions typically perform reasonably well in the square room, and claim a few corridor grids in the more complex rooms by ricocheting around the environment.

The code for the individual displayed in Figure 14.7 is shown below. It begins with a WhileTooFarFromWall loop with a Do2 as its body. The arguments of the Do2 are a MoveForward and a Do2 with two WhileInCoridorRange loops as arguments. While the robot is out of corridor range the WhileInCoridorRange tests will fail. The result is that the robot will move forward until it finds itself within corridor range of a wall. When the MoveForward on line 2 moves the robot into a wall-following corridor, the WhileInCoridorRange functions are able to execute. The first (on line 4) turns the robot away from the closest wall repeatedly until the maximum loop counter is exceeded.⁴ The second (on line 6) employs a Do2 to turn the robot parallel to the closest wall and move forward. These two steps are repeated until the robot moves out of range, or the loop times out.⁵ When either of those conditions occurs, another iteration of WhileTooFarFromWall (on line 0) is made. If the robot is out of range and the loop counter is not maximized, the process repeats. This algorithm passes through a total of 275 corridor grids.

---

⁴Actually these loops terminate immediately if the robot does not move during the course of evaluating the function body. This feature was added to improve the performance of the simulator.
⁵The instruction pair, TurnParallelToClosestWall and MoveForward, are capable of navigating a concave turn because the robot gets closer to the wall it is approaching than the wall it is following before it goes out of corridor range. The instruction pair is not capable, however, of negotiating a convex corner - the robot simply moves out of range. This is the reason the robot follows the walls briefly and then loses them.

---

0	WhileTooFarFromWall
1		Do2
2			MoveForward
3			Do2
4				WhileInCoridorRange
5					TurnAwayFromClosestWall
6				WhileInCoridorRange
7					Do2
8						TurnParallelToClosestWall
9						MoveForward
END

Figure 14.7  Typical result of a GP run as it begins to learn the wall-following behavior.