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

Yiming Yang, Wolfgang Merkt, Vladimir Ivan, Zhibin Li, Sethu Vijayakumar

Research output: Contribution to journalArticlepeer-review


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
configuration-to-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.
Original languageEnglish
Pages (from-to)551-558
Number of pages8
JournalIEEE Robotics and Automation Letters
Issue number1
Early online date15 Nov 2017
Publication statusPublished - Jan 2018


Dive into the research topics of 'HDRM: A Resolution Complete Dynamic Roadmap for Real-Time Motion Planning in Complex Environments'. Together they form a unique fingerprint.

Cite this