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

August 2006

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

Authors:

Hamidreza Chitsaz, Steven M. LaValle, Devin J. Balkcom, and Matthew T. Mason

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.
@conference{Chitsaz-2006-121295,
author = {Hamidreza Chitsaz And Steven M. LaValle And Devin J. Balkcom And Matthew T. Mason},
title = {An Explicit Characterization of Minimum Wheel-Rotation Paths for Differential-Drives},
booktitle = {Proceedings of IEEE 12th International Conference on Methods and Models in Automation and Robotics (MMAR '06)},
year = {2006},
month = {August},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.