Planning shortest bounded-curvature paths for a class of nonholonomic vehicles among obstacles

Abstract

This paper describes a technique for path planning in environments cluttered with obstacles for mobile robots with nonholonomic kinematics and bounded trajectory curvature (i.e., limited turning radius). The method is inspired by the results of Reeds and Shepp (1990) regarding shortest paths of bounded curvature in absence of obstacles. It is proved that, under suitable assumptions, the proposed technique provides the shortest path of bounded curvature among polygonal objects for a particular class of vehicles (circular unicycles of radius h and minimum turning radius /spl rho//sub min//spl les/h). Although the class of vehicles this theoretical result is restricted to is rather narrow, the proposed planner can be satisfactorily applied to other nonholonomic vehicles yielding good practical results.