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


An Efficient Algorithm to Find a Shortest path for a Car-like Robot


We study the problem of finding a shortest path for a car-like mobile robot with a minimal turning radius constraint. This vehicle can move either forward or backward in an unconstrained environment. First, using a geometrical approach, we establish necessary conditions on the lengths of the segments of shortest paths. We then apply these conditions to partition the configuration space into elements such that a single path type is associated with 150 elements and two path types are associated with the other 11 elements. A shortest path from a fixed initial configuration to any final configuration in an element can always be found among the paths of types associated with that element. Finally, we present an algorithm based on this partition and we give results showing that our algorithm is 15 times faster on average than the Reeds-Shepp algorithm.

, 36 pages