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

# A Shortest Path Algorithm for a Car-Like Robot in a Polygonal Environment

## Guy Desaulniers, François Soumis et J-C Laurent

We study the problem of finding a shortest collision-free path for a point car-like robot maneuvering around polygonal obstacles in a room bounded by a polygonal line. We assume that the workspace is decomposable into convex polygonal cells. First, we introduce a sufficient set of 56 subpath types similar to that presented by Reeds and Shepp (1990) for the no-obstacle case, where a subpath is defined as a piece of a path which starts and ends either at the initial position, the final position, or any position on a cell boundary. We prove that, whenever a shortest collision-free path exists in an environment decomposable into convex cells, then such a path exists that is a sequence of subpaths whose types belong to the set of 56 subpath types. Next, we propose a near-optimal algorithm to solve this problem. Basically, this algorithm consists of finding a shortest path in a search graph where the arcs represent subpaths whose types belong to the sufficient set. Testing results show the efficiency of the algorithm, which computes a solution in less than 1 second on average. We then study a relaxation of the problem in which the robot is allowed to turn on the spot at a certain cost. This relaxed problem can be solved by a modified version of the algorithm. Its solutions can be approximated as closely as needed by collision-free paths and, therefore, can lead to shorter paths than those produced by the original version of the algorithm. Finally, we compare the solutions derived from both algorithms. These comparisons show the high quality of the solutions produced by the original version of the algorithm.

, 43 pages

Ce cahier a été révisé en décembre 1996