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.