An Explicit Characterization of Minimum Wheel-Rotation Paths for Differential-Drives

Abstract

This paper characterizes shortest paths for differential-drive mobile robots by classifying solutions in the spirit of Dubins curves and Reeds-Shepp curves for car-like robots. Not only are optimal paths for mobile robots interesting with respect to the optimized criteria, but also they offer a family of motion primitives that can be used for motion planning in the presence of obstacles. A well-defined notion of shortest is obtained by optimizing the total amount of wheel rotation. This paper extends our previous characterization of the minimum wheel-rotation trajectories that are maximal with respect to sub-path partial order in [2]. To determine the shortest path for every pair of initial and goal configurations, we need to characterize all of the minimum wheel-rotation trajectories regardless of whether they are maximal with respect to sub-path partial order. In this paper we give all 52 minimum wheel-rotation trajectories. We also give the end-point map in terms of the path parameters for every shortest path. Thus, finding the shortest path for every pair of initial and goal configurations reduces to solving systems of equations for the path parameters. As in [2], the Pontryagin Maximum Principle as a necessary condition eliminates some non-optimal paths. The paths that satisfy the Pontryagin Maximum Principle (called extremals) are presented in this paper by finite state machines. Level sets of the cost-to-go function for a number of robot orientations are finally presented.