Skip to search boxSkip to navigationSkip to main content

K-order surrounding roadmaps path planner for robot path planning

  • Yueqiao Li
    ,
  • Dayou Li
    ,
  • Carsten Maple
    ,
  • Yong Yue
    ,
  • John O. Oyekan
Research Output: Contribution to journal Article Peer-review

Abstract

Probabilistic roadmaps are commonly used in robot path planning. Most sampling-based path planners often produce poor-quality roadmaps as they focus on improving the speed of constructing roadmaps without paying much attention to the quality. Poor-quality roadmaps can cause problems such as poor-quality paths, time-consuming path searching and failures in the searching. This paper presents a K-order surrounding roadmap (KSR) path planner which constructs a roadmap in an incremental manner. The planner creates a tree while answering a query, selects the part of the tree according to quality measures and adds the part to an existing roadmap which is obtained in the same way when answering the previous queries. The KSR path planner is able to construct high-quality roadmaps in terms of good coverage, high connectivity, provision of alternative paths and small size. Comparison between the KSR path planner and Reconfigurable Random Forest (RRF), an existing incremental path planner, as well as traditional probabilistic roadmap (PRM) path planner shows that the roadmaps constructed using the KSR path planner have higher quality that those that are built by the other planners.

Publication Information

Output type

Research Output: Contribution to journal Article Peer-review

Original language

English

Pages from-to (Number of pages)

Pages 493-516

Journal (Volume, Issue Number)

Journal of Intelligent and Robotic Systems: Theory and Applications (Volume 75, Issue 3-4)

Publication milestones

  • Published - 01/09/2014

Publication status

Published - 01/09/2014

ISSN

0921-0296

External Publication IDs

  • handle.net: 10547/336162
  • Scopus: 84906249994

Access to documents

Publication metrics