We are considering three different approaches to achieving full coverage for a given room. One approach utilizes genetic programming to generate an algorithm that effectively vacuums the room, while the other two focus on designing behaviors for the robot to traverse the floor in a pre-specified pattern (the North/South and Concentric Squares methods). We plan on comparing all three approaches in a variety of room environments to measure their relative utilities.
North/South. The robot begins in the southwest corner of the room, facing north. The robot then traces a path of north-south lines through the room, while avoiding large obstacles (see Figure 1). When the robot is in its North behavior, it simply travels north in a straight line until it either senses an obstacle directly in front of it or senses that it has just passed an object immediately on its left. If it senses an obstacle directly in front of it, the robot moves east one robot's width, turns to face south, and enters its South behavior. During North, if the robot senses that it has just passed an object immediately on its left, the robot switches to a TraverseObstacle behavior in which it turns to face east and follows the top edge of the object on its left. When the robot senses that this edge has dropped off, it turns to face north and returns to the North behavior, vacuuming the area of the room that lies north of the piece of furniture. During South, the robot moves due south until it senses an obstacle in front of it, in which case it moves east one robot's width, faces north, and changes to the North behavior. In designing this algorithm, we attempted to rely as little as possible on computing the robot's estimated position within a map. Instead, we used only the robot's sensor readings as criteria for determining the robot's path.
Figure: Illustrations of the North/South (left) and Concentric Square
(right) approaches.
Concentric Squares. The first step of this method is to represent the structure of a room in the internal coordinate system of the Saphira interface. The next step is to locate a series of goals in the coordinate system. The goals should be positioned so that, if the robot were to move in a straight line from each goal to the next goal in the series, it would cover all the space in the room (see Figure 1, note that the goals are depicted as small squares). There are four behaviors that characterize the robot's action as it moves through the series of goals: Avoid turns the robot away from objects before it hits them, Straight turns the robot back to the straight line between its last goal and its next goal, Seek turns the robot toward its current goal and replaces the current goal with the next goal when the current goal is achieved, and Wander is the default behavior.
The combination of these behaviors leads to the following action sequence in the case of an obstacle: first, the robot slows and turns to avoid collision; next, it wanders until it is free of the obstacle; finally, it resumes the course it was following before it encountered the obstacle. This sequence of behaviors has the advantage that the space on the opposite side of an obstacle is not neglected once the obstacle has been avoided. The approach as a whole, however, is risky because of the inaccuracy of the robot's dead reckoning system.
Genetic Programming. In GP (Koza 1994), the idea is to first generate a collection of random programs, building from a pool of relatively simple functions, to control the robot's behavior. Each program is given a fitness--a measure of how well it performs. Akin to natural evolution, this population of random programs undergoes a simulated version of natural selection and reproduction to produce a new and hopefully better population of programs. In GP, the computer generates the programs rather than human designers. It is our hope that this approach may create innovative control strategies.