Shortest paths for a car-like robot to manifolds in configuration space

Reeds and Shepp (1990) studied the problem of finding the shortest feasible path for a car-like robot between two points in configuration space. We extend their results to find the shortest feasible path between a point and a manifold in configuration space. Our approach is based on the Lagrange method for optimizing a function while constrained to a manifold. Solving the problem analytically is much faster than numerical dis cretization techniques. In addition to providing insight into the underlying structure of Reeds and Shepp paths, this research has many applications in path planning. Planning algorithms often rely on the notion of clearance from obstacles, and for car-like mobile robots, clearance is closely related to the length of the shortest feasible path to an obstacle. In addition, one may want to bring the robot to a predefined path (such as a skeleton). Skeletonization and potential field methods are two examples of planning paradigms where our algorithm would prove useful.