Generalizing the dubins and reeds-shepp cars: Fastest paths for bounded-velocity mobile robots

Abstract

What is the shortest or fastest path a mobile robot can follow between two configurations in the unobstructed plane? The answer to this fundamental question is only known analytically for a few planar mobile robots: the Dubins and Reeds-Shepp steered cars, the differential drive, and a particular omnidirectional robot. This paper explores the optimal trajectories for a general parameterized model of a mobile robot that includes each previously-studied vehicle as a special case. The model also allows characterization of the optimal trajectories for several other mobile robot designs for which the optimal trajectories have not been previously explored. The paper applies Pontryagin's Maximum Principle to the generalized robot to find necessary conditions that optimal trajectories must satisfy, and gives geometric interpretations of the conditions. We also present an algorithm that generates and classifies all optimal trajectories for a given design.