Groupe d’études et de recherche en analyse des décisions


On Shortest Paths for a Mobile Robot in a Convex Cell


We consider the problem of finding a shortest path for a car-like robot maneuvering in a convex cell. This robot, capable of forward and backward motion, is without slippage of the rear wheels and subject to a maximal steering angle constraint. We first establish that no shortest path exists between certain initial and final configurations. To prove this result, we find a strict, tight lower bound on the length of any path between these configurations. This lower bound is the length of a pseudo-path that contains at least one turn on the spot and, consequently, violates the requirement that there be no slippage of the rear wheels. We also show that such a pseudo-path can be approximated as closely as necessary by a path satisfying all constraints and containing a number of segments that increases with the accuracy of the approximation. The second part of the paper concerns shortest pseudo-paths. We establish that, when searching for a shortest pseudo-path, there is no need to consider pseudo-paths containing a turn on the spot in the interior of the convex cell. We also show that, except in one case, there is always a turn on the spot between two line segments in a shortest pseudo-path.

, 30 pages