language: en

Using Skeletons for Nonholonomic Path Planning among Obstacles

Brian Mirtich John Canny
Computer Science Division University of California
Berkeley, CA 94720

Abstract This paper describes a practical path planner for nonholonomic robots in environments with obstacles. The planner is based on building a one-dimensional, maximal clearance skeleton through the configuration space of the robot. However rather than using the Eu-clidean metric to determine clearance, a special metric which captures information about the nonholonomy of the robot is used. The robot navigates from start to goal states by loosely following the skeleton; the resulting paths taken by the robot are of low "complexity." We describe how much of the computation can be done off-line once and for all for a given robot, making for an efficient planner. The focus is on path planning for mobile robots, particularly the planar two-axle car, but the underlying ideas are quite general and may be applied to planners for other nonholonomic robots.

1 Introduction