On Shortest Paths for a Car-Like Robot Maneuvering around Obstacles

摘要

We consider the problem of finding a shortest path for a car-like robot (approximated by a point) maneuvering around obstacles. This robot is capable of forward and backward motion, subject to a maximal steering angle constraint. We first establish that no shortest path exists between certain initial and final configurations. Then, similarly to the work of Reeds and Shepp, we introduce a set of path types that contains the type of any subpath of a shortest path such that all contacts with obstacles are avoided, except possibly at the endpoints of the subpath. Necessary conditions on the segment lengths of these subpaths are also provided. These results greatly reduce the set of paths to consider when searching for a shortest path among obstacles, since such a path can be seen as a sequence of subpaths without contact, except possibly at their endpoints.