Layered path planning for an autonomous mobile robot

Abstract

In order to continue to improve the usefulness of robots, it is becoming increasingly important to have them act as autonomous agents. A significant step toward this object is autonomous motion planning. This research was conducted as part of a broader effort to empower Yambico-11, a mobile robot under development at the Naval Postgraduate School, with ability to move autonomously. We believe that this problem is best attacked in layers. This thesis is our proposal for the initial layer. Given a robot's current location and its goal location, we use the homotopy relation to reduce the infinite set of path choices into a more manageable and smaller set of path classes. Specifically, we solve the problem of how to enable a robot to autonomously identify and label these classes of paths. We begin by decomposing the robot's operating environment into a collection of convex pieces called cells. The cells are transformed into a graph by adjacency. We show that every simple path on the graph corresponds to a unique simple homotopy class in the robot's world. We then search the graph to give each class a symbolic representation which also provides intermediate path planning clues. Subsequent layers can use these clues to form a more detailed plan. We implement the cell decomposition, graph transformation, and path class labeling as C programs, and preprocess them on a Unix workstation. This resulting data structures are then compiled and linked into the robot's kernel. All implementation has been integrated into the model- based mobile robot language (mml) used by Yamabico-11