PLANNING SHORTEST BOUNDED-CURVATURE PATHS FOR A CLASS OF NONHOLONOMICVEHICLES AMONG OBSTACLES

This paper deals with the problem of planning a path for a robot vehic le amidst obstacles. The kinematics of the vehicle being considered ar e of the unicycle or car-like type, i.e. are subject to nonholonomic c onstraints. Moreover, the trajectories of the robot are supposed not t o exceed a given bound on curvature, that incorporates physical limita tions of the allowable minimum turning radius for the vehicle. The met hod presented in this paper attempts at extending Reeds and Shepp's re sults on shortest paths of bounded curvature in absence of obstacles, to the case where obstacles are present in the workspace. The method d oes not require explicit construction of the configuration space, nor employs a preliminary phase of holonomic trajectory planning. Successf ull outcomes of the proposed technique are paths consisting of a simpl e composition of Reeds/Shepp paths that solve the problem. For a parti cular vehicle shape, the path provided by the method, if regular, is a lso the shortest feasible path. In its original version, however, the method may fail to find a path, even though one may exist. Most such e mpasses can be overcome by use of a few simple heuristics, discussed i n the paper. Applications to both unicycle and car-like (bicycle) mobi le robots of general shape are described and their performance and pra cticality discussed.