Adaptive probabilistic roadmap construction with multi-heuristic local planning

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Doctoral thesis (article-based)
Checking the digitized thesis and permission for publishing
Instructions for the author
Degree programme
62, [38]
Helsinki University of Technology Industrial Information Technology Laboratory publications, 1
The motion planning problem means the computation of a collision-free motion for a movable object among obstacles from the given initial placement to the given end placement. Efficient motion planning methods have many applications in many fields, such as robotics, computer aided design, and pharmacology. The problem is known to be PSPACE-hard. Because of the computational complexity, practical applications often use heuristic or incomplete algorithms. Probabilistic roadmap is a probabilistically complete motion planning method that has been an object of intensive study over the past years. The method is known to be susceptible to the problem of "narrow passages": Finding a motion that passes a narrow, winding tunnel can be very expensive. This thesis presents a probabilistic roadmap method that addresses the narrow passage problem with a local planner based on heuristic search. The algorithm is suitable for planning motions for rigid bodies and articulated robots including multi-robot systems with many degrees-of-freedom. Variants of the algorithm are described for single query planning, single query planning on a distributed memory parallel computer, and a preprocessing type of learning algorithm for multiple query planning. An empirical study of the effect of balance between local and global planning reveals that no universal optimal balance is likely to exist. Furthermore, it appears that many traditional simple local planners are too weak for efficient solving of problems with a narrow passage. The empirical results show that local planners based on backtracking search are more efficient than the more traditional local planners when a motion through a narrow passage is to be planned. The parallel variant has acceptable scalability on a parallel computer built from commodity components. It is also observed that run-time adjustment of the parameters of the search can reduce the variance of the run-cost. The run-cost variance is a known, but little studied deficiency of randomized motion planning methods. It is suggested that the future research in randomized motion planning algorithms should address run-cost variance as an important performance characteristic of the algorithm. The results are obtained with empirical methods and established procedures from design and analysis of experiments. The algorithms are assessed with a number of test problems including known benchmark problems from the literature.
motion planning, robotics, heuristic algorithms, empirical algorithmics
Other note
  • Isto P., 1996. Path planning by multiheuristic search via subgoals. Proceedings of the 27th International Symposium on Industrial Robots. CEU, Milan, pages 712-726. [article1.pdf] © 1996 by author.
  • Isto P., 1997. A two-level search algorithm for motion planning. Proceedings of the 1997 IEEE International Conference on Robotics and Automation. IEEE Press, pages 2025-2031. [article2.pdf] © 1997 IEEE. By permission.
  • Isto P., 2001. A parallel motion planner for systems with many degrees of freedom. Proceedings of the 2001 International Conference on Advanced Robotics, pages 339-344. [article3.pdf] © 2001 by author.
  • Isto P., 2002. Constructing probabilistic roadmaps with powerful local planning and path optimization. Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE Press, pages 2323-2328. [article4.pdf] © 2002 IEEE. By permission.
  • Isto P., Tuominen J. and Mäntylä M., 2003. Adaptive strategies for probabilistic roadmap construction. Proceedings of the 2003 International Conference on Advanced Robotics, pages 682-687. [article5.pdf] © 2003 by authors.
  • Isto P., Mäntylä M. and Tuominen J., 2003. On addressing the run-cost variance in randomized motion planners. Proceedings of the 2003 IEEE International Conference on Robotics and Automation. IEEE Press, pages 2934-2939. [article6.pdf] © 2003 IEEE. By permission.
Permanent link to this item