Multilevel Path Planning for Nonholonomic Robots Using Semiholonomic Subsystems

We present a new and complete multilevel approachfor solving path- planning problems for nonholonomic robots. At the first level, a path is found that disrespects (some of) the nonholonomic constraints. At each of the next levels, a new path is generated by transformation of the path generated at the previous level. The transformation is such that more nonholonomic constraints are respected than at the previous level. At the final level, all nonholonomic constraints are respected. We present two techniques for these transformations. The first, which we call the pick and link technique, repeatedly picks pieces from the given path, and tries to replace them by more feasible ones. The second technique restricts the free configuration space to a "tube" around the given path, and a road map that captures the free-space connectivity within this tube is constructed by the prob abilistic path planner. From this road map we retrieve a new, more feasible path. In the intermediate levels, we plan paths for what we refer to as semiholonomic subsystems. Such systems are obtained by taking real (physical) systems, and removing some of their nonholonomic constraints. In this paper, we apply the scheme to carlike robots pulling trail ers, that is, tractor-trailer robots. In this case, the real system is the tractor-trailer robot, and the ignored constraints in the semiholo nomic subsystems are the kinematic ones on the trailers. These are the constraints of rolling without slipping, on the trailer's wheels. Experimental results are given that illustrate the time efficiency of the resulting planner. In particular, we show that using the multilevel scheme leads to significantly better performance (in computation time and path shape) than direct transformations to feasible paths.