SHORTEST PATHS FOR A CAR-LIKE ROBOT TO MANIFOLDS IN CONFIGURATION-SPACE

Reeds and Shepp (1990) studied the problem of finding the shortest fea sible path for a car-like robot between two points in configuration sp ace. We extend their results to find the shortest feasible path betwee n 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 numer ical discretization techniques. In addition to providing insight into the underlying structure of Reeds and Shepp paths, this research has m any applications in path planning. Planning algorithms often rely on t he notion of clearance from obstacles, and for car-like mobile robots, clearance is closely related to the length of the shortest feasible p ath to an obstacle. In addition, one may want to bring the robot to a predefined path (such as a skeleton,). Skeletonization and potential f ield methods are two examples of planning paradigms where our algorith m would prove useful.