Edinburgh Research Explorer

HDRM: A Resolution Complete Dynamic Roadmap for Real-Time Motion Planning in Complex Environments

Research output: Contribution to journalArticle

Original languageEnglish
Number of pages8
JournalIEEE Robotics and Automation Letters
StatePublished - 15 Nov 2017


We present the Hierarchical Dynamic Roadmap (HDRM), a novel resolution complete motion planning algorithm for solving complex planning problems. A unique hierarchical structure is proposed for efficiently encoding the configurationto-workspace occupation information that allows the robot to
check the collision state of tens of millions of samples on-the-fly—the number of which was previously strictly limited by available memory. The hierarchical structure also significantly reduces the time for path searching, hence the robot is able to find feasible motion plans in real-time in extremely constrained environments. The HDRM is theoretically proven to be resolution complete, with
a rigorous benchmarking showing that HDRM is robust and computationally fast, compared to classical dynamic roadmap methods and other state-of-the-art planning algorithms. Experiments on the 7 degree-of-freedom KUKA LWR robotic arm integrated with real-time perception of the environment further
validate the effectiveness of HDRM in complex environments.

ID: 47584596