TABLE OF CONTENTS Howie Chos, Carnegie Mellon University, Pittsburgh, PA, USA
Joel Burdick, California Institute of Technology, Pasadena, CA, USA
Abstract The hierarchical generalized Voronoi graph (HGVG) is a roadmap that can serve as a basis for sensor based robot motion planning. A key feature of the HGVG is its incremental construction procedure that uses only line of sight distance information. This work describes basic properties of the HGVG and the procedure for its incremental construction using local range sensors. Simulations and experiments verify this approach.
Sensor based motion planning incorporates sensor information, reflecting the current state of the environment, into a robot's planning process, as opposed to classical planning, which assumes full knowledge of the world's geometry prior to planning. Sensor based planning is important, for realistic deployment of robots because: (1) the robot often has no a priori knowledge of the world; (2) the robot may have only a coarse knowledge of the world because of limited computer memory; (3) the world model is bound to contain inaccuracies which can be overcome with sensor based planning strategies; and (4) the world is subject to unexpected occurrences or rapidly changing situations.
This work addresses two primary problems in sensor based motion planning for static environments. The first problem deals with the case of when a robot is given a target location and...
