Planning Shortest Bounded--Curvature Paths for a Class of Nonholonomic Vehicles among Obstacles

This paper deals with the problem of planning a path for a robot vehicle amidst obstacles. The kinematics of the vehicle being considered are of the unicycle or car-like type, i.e. are subject to nonholonomic constraints. Moreover, the trajectories of the robot are supposed not to exceed a given bound on curvature, that incorporates physical limitations of the allowable minimum turning radius for the vehicle. The method presented in this paper attempts at extending Reeds and Shepp's results on shortest paths of bounded curvature in absence of obstacles, to the case where obstacles are present in the workspace. The method does not require explicit construction of the configuration space, nor employs a preliminary phase of holonomic trajectory planning. Successfull outcomes of the proposed technique are paths consisting of a simple composition of Reeds/Shepp paths that solve the problem. For a particular vehicle shape, the path provided by the method, if regular, is also the shortest feasible path. In its original version, however, the method may fail to find a path, even though one may exist. Most such empasses can be overcome by use of a few simple heuristics, discussed in the paper. Applications to both unicycle and car-like (bicycle) mobile robots of general shape are described and their performance and practicality discussed.