Using Skeletons for Nonholonomic Path Planning among Obstacles

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 Euclidean 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 With an abundance of theoretical results and algorithms already existing for solving the classical piano mover's problem, research ..