Layered path planning for an autonomous mobile robot
By: Timothy A. Haight
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1994
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 111
Description: 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.
Notes: Thesis advisor(s): Yutaka Kanayama, Craig W. Rasmussen.

"September 1994."

Thesis (M.S. in Computer Science and M.S. in Mathematics) Naval  Postgraduate School, September 1994.

Bibliography: p. 43-44.

Approved for public release; distribution unlimited.

Also available online.

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

US Army (USA) author.