Time Optimal Trajectories for Bounded Velocity Differential Drive Vehicles

Abstract

This paper presents the time optimal trajectories for differential drive vehicles in the unobstructed plane. The wheel angular velocities are bounded, but may be discontinuous. The paper proves the existence of optimal controls, derives the structure of optimal trajectories, and develops an algorithm for producing a time optimal trajectory between any two configurations. Every nontrivial optimal trajectory is composed of straight segments alternating with turns about the robot's center. Optimal trajectories may have as many as five actions, but four actions are sufficient—for every optimal trajectory of five actions, there is an equally fast trajectory with four actions.

Keywords

Pontryagin's maximum principle time optimal trajectories differential drive robots steered cars Dubins Reeds and Shepp optimal control

Get full access to this article

View all access options for this article.

References

Balkcom, D.J. , and Mason, M.T. 2000. Time optimal trajectories for bounded velocity differential drive robots. In Proc. 2000 IEEE International Conference on Robotics and Automation, pp. 2499-2504.

Dubins, L.E. 1957. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents . American Journal of Mathematics 79:497-516.

Pontryagin, L.S. , Boltyanskii, V.G. , Gamkrelidze, R.V. , and Mishchenko, E.F. 1962. The Mathematical Theory of Optimal Processes. John Wiley.

Reeds, J.A. , and Shepp, L.A. 1990. Optimal paths for a car that goes both forwards and backwards . Pacific Journal of Mathematics 145(2):367-393.

Reister, D.B. , and Pin, F.G. 1994. Time-optimal trajectories for mobile robots with two independently driven wheels. International Journal of Robotics Research 13(1):38-54.

Renaud, M. , and Fourquet, J.-Y. 1997. Minimum time motion of a mobile robot with two independent acceleration-driven wheels. In Proc. 1997 IEEE International Conference on Robotics and Automation, pp. 2608-2613.

Souères, P. , and Boissonnat, J.-D. 1998. Optimal trajectories for nonholonomic mobile robots. In Robot Motion Planning and Control , ed. J.-P. Laumond , 93-170. Springer .

Souères, P. , and Laumond, J.-P. 1996. Shortest paths synthesis for a car-like robot. IEEE Transactions on Automatic Control 41(5):672-688.

Sussmann, H. , and Tang, G. 1991. Shortest paths for the reeds-shepp car: a worked out example of the use of geometric techniques in nonlinear optimal control. SYCON 91-10 , Department of Mathematics, Rutgers University, New Brunswick, NJ 08903.