Multilevel Path Planning for Nonholonomic Robots Using Semiholonomic Subsystems
- 1 August 1998
- journal article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 17 (8), 840-857
- https://doi.org/10.1177/027836499801700803
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- Motion Planning for Carlike Robots Using a Probabilistic Learning ApproachThe International Journal of Robotics Research, 1997
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Flatness and defect of non-linear systems: introductory theory and examplesInternational Journal of Control, 1995
- A motion planner for nonholonomic mobile robotsIEEE Transactions on Robotics and Automation, 1994
- Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstaclesAlgorithmica, 1993
- Singularities and Topological Aspects in Nonholonomic Motion PlanningPublished by Springer Science and Business Media LLC ,1993
- Optimal Nonholonomic Motion Planning for a Falling CatPublished by Springer Science and Business Media LLC ,1993
- Optimal paths for a car that goes both forwards and backwardsPacific Journal of Mathematics, 1990