This
work was sponsored in part by the National Science Foundation's Course,
Curriculum and Laboratory Improvement -- Adaptation and Innovation Program, DUE- 9980999.
This
work was sponsored in part by the National Science Foundation's Course,
Curriculum and Laboratory Improvement -- Adaptation and Innovation Program, DUE- 9980999.Printable (pdf) version
Mapper II is the most recent autonomous robot mapper developed at the Bonaventure Robotics Laboratory. Its predecessor, Mapper I, used rectilinear objects in its world to maintain its alignment, thereby rendering accurate, grid-based maps of an unknown environment using odometry. Mapper II adds a supervising module that monitors its progress in mapping a world. In particular, it is capable of recognizing and escaping cycles, determining if a region is unexplorable, and terminating mapping once a world is explored completely.
We have also introduced a world class, gridWorld, that encapsulates a map, a display mechanism, a search strategy and an initialization function for worlds defined by a two-dimensional coordinate system.
The robots Mapper I and Mapper II were designed to experiment with the problem of generating an accurate and complete map of an unknown world containing randomly placed obstacles. The world is defined by a coordinate system. In our experimentation the world is divided into 140 cells approximately the size of the Khepera robots we use for experimentation (80 mm2). Each cell has a row and column address. Obstacles (or objects, we use the terms as equivalent) are blocks that occupy one cell. As the robot moves forward it maps the cells to the left, right and in front. Sensor data are used to indicate if the cells are occupied objects.
 |
| Figure 1: Mapper II exploring a world. |
The problem posed by this task is the problem of localization: how can the robot determine whether or not its representation of where it is in the world is accurate? A robot can use odometry to track its position: given both the direction and number of wheel rotations, the robot can calculate its position in the world. This strategy, however, fails over time owing to both drift, caused by unequal torque on the drive wheels, and slippage, caused by bumps on the surface or unequal wheel traction. In a very short order (12 to 16 cm) the robot's internal representation of its position varies from its actual position in the world, rendering its mapping inaccurate. Click here for a video of a drifting robot.
Mapper I used obstacles in the world to eliminate the problems of drift and slippage. Because objects are rectilinear, which is characteristic of many man-made environments such as office buildings, Mapper I could check its alignment with any obstacle it encountered. If it was either too close or too far away from an obstacle it would adjust its alignment. We were able to show that given an environment where at least 25% of the space was occupied by obstacles the robot could generate an accurate map of the environment.
Mapper I was subject to two problems, however, that forced the addition of a higher-level supervisory module to monitor its progress in mapping an environment. First, Mapper I could be caught in cycles where it would explore the same set of cells repeatedly. Though we added a randomizing function to try to avoid this problem there were specific configurations of objects that would lead to cycles.
The second problem was that Mapper I was unable to determine when a world had been mapped completely.
Mapper II has a supervisory module that solves these two problems. It stops mapping once the world has been explored completely. It also recognizes and breaks cycles by moving the robot to an unexplored region of the world. In addition, the supervisor enables the robot to recognize if a region is unexplorable.
 |
| Figure 2: Mapper II Architecture |
Mapper II is built on top of Mapper I. Mapper I consisted of a sequencer function, wander(), which guided the robot's meandering through the world and mapping. It managed low-level behaviors avoidObject(), drawMap() and move(), which guided the robot through a world mapping as it went, and correctDrift(), which maintained the robot's alignment with objects in the world.
Mapper II adds a super-ordinate, planner/supervisor module that is responsible for monitoring the wander() sequencer (figure 2), thereby making Mapper II's architecture a three-layer architecture (Gat, 1998). The planner/supervisor checks for cycles in the exploration of the world. If found, it moves the robot to some unexplored region of the world where it can recommence mapping. It also terminates the behavior once all of the world is explored and is capable of marking regions that cannot be reached as unexplorable.
The Planner/Supervisor Module
The planner/supervisor module uses three functions, isChanging(), findUnexplored() and gotoUnexplored() to carry out the monitoring and management of the wander() sequencer (figure 3). These have been added to the navigation class developed for Mapper I.
IsChanging() is used to recognize cycles: if the robot moves five times with no new cells updated, isChanging() returns false, signaling that the robot should move to some other, unexplored region of the world.
FindUnxplored() finds the cell closest to the current location of the robot that has not been explored. If there are no non-explored cells the function returns the cell (-1,-1) to signal that all cells have been explored.
GotoUnexplored() finds a path to the unexplored cell generated by findUnexplored() based upon the robot's current map of the world and the search strategy associated with the world, and manages the movement of the robot to the cell. GotoUnexplored() can have three different outcomes:
A path to the cell is found and the robot moves to the cell;
A path to the cell is found but the robot is blocked by an unknown obstacle from reaching the cell;
There is no path to the cell;
begin planner/supervisor gridWorld w(aStar, text) nRobot r while there are cells to explore
end planner/supervisor *************************************** begin gotoUnexplored(cell) if no unexplored cells
path = w.search(current, goal) if no path to cell
else move to cell if path to cell blocked
else return end gotoUnexplored(cell) |
| Figure 3: Planner/Supervisor Algorithm |
In the first case, the cell can resume wandering and mapping at its new location. In the third case, the robot has discovered that the cell cannot be reached. It is marked as unexplorable and findUnexplored() is asked for the next unexplored cell closest to the robot. GotoUnexplored() is called again with this new goal cell.
The second case is the most interesting. If the current map shows that the cell can be reached but an unknown obstacle blocks the way, the goal cell is abandoned and a new goal is generated by findUnexplored(). This new goal is the unexplored cell closest to the current position of the robot, not its original position. The robot resumes wandering at this point with the assumption that the former goal cell will eventually be explored.
This strategy implements the intuition that a cell we currently don't know how to get to will be explored eventually. The robot has moved to a new part of the world and can resume wandering in this area. It proves efficient because the robot does not jump repeatedly to unexplored regions of the world: it picks the first unexplored region it can get to and resumes wandering and mapping at that point.
GotoUnexplored() uses whatever search strategy is passed to the world when it is created, as described below. The experimentation described below used the version of the A* algorithm described here.
The gridWorld Class
The worlds explored by Mapper I and Mapper II are defined by a two-dimensional coordinate systems where movement is restricted to four directions, north, south, east and west. Each cell has a location, and may be occupied, empty, unexplored or unexplorable. A world is shown in figure 1 above and abstractly in figures 4 and 5.
Mapper I used a matrix to represent the status of each cell. In Mapper II we have encapsulated in the class world a matrix representing the status of each cell together with functions for initializing the world, searching the world and displaying the world.
There are various strategies for planning a route between two cells in the grid-based worlds explored by our robots. We have defined a family of search classes (e.g., breadth-first, best-first, A*), each of which is derived from the abstract class Search. When a world is defined, the search to be used in planning routes between cells is passed as a parameter . The search method returns a path between the two if one exists, an indication that no such path exists otherwise.
We have also parameterized the map display function: map displays can be either text-based or graphical.
Experimentation
We have run Mapper II on different worlds with at least 25% of the cells occupied by objects, a density established by Mapper I to be sufficient to enable the robot to overcome the problems of drift and slippage. Some maps included cells that could not be reached by the robot.
In all cases the robot mapped accurately 100% of the world and terminated once the mapping was complete. Areas that were not reachable were marked as unexplorable.
We ran Mapper II on the world (figure 4 below) mapped by Mapper I to compare the behavior of the two. Mapper II was able to map the world in seven minutes, the amount of time at which we halted Mapper I. Mapper I had mapped about two-thirds of the world in the same amount of time it took Mapper II to complete a map of the entire world.
Conclusion
The development of Mapper I demonstrated that rectilinear objects in a world could be used to maintain an accurate representation of the location of a robot using dead reckoning in navigating and mapping an unknown world provided there were a sufficient number of objects in the world. However, experimentation showed that a higher-level, supervisor function was needed to recognize when the robot had completed mapping a world and to make sure that it was making progress towards completing a map.
Mapper II is the result of the development of this supervisory module. It exhibits a three-layer architecture consisting of low-level behaviors that govern robot-environment interaction, a sequencer that manages the low-level behaviors, and a planner that supervises the execution of the sequencer. Testing has shown that Mapper II is capable of generating accurate maps of complex worlds and is even capable of recognizing regions of a world that cannot be explored.
Maps generated by and videos of Mapper II
| Robot Map Generated by Mapper I | Actual Map |
 |
 |
| Figure 4: Mapper I failed to explore the areas in dark gray. Mapper II generated an accurate and complete map in seven minutes. |
Click here for our Mapper II code (zip file)
updated 07/12/2005