In this letter, we first theoretically prove the conditions and boundaries of resolution completeness for deterministic roadmap methods with a discretized workspace. A novel variant of such methods, the hierarchical dynamic roadmap (HDRM), is then proposed for solving complex planning problems. A unique hierarchical structure to efficiently encode the configuration-to-workspace occupation information is introduced and 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. A rigorous benchmarking shows that HDRM is robust and computationally fast compared with classical dynamic roadmap methods and other state-of-the-art planning algorithms. Experiments on the seven degree-of-freedom KUKA LWR robotic arm integrated with live perception further validate the effectiveness of HDRM in complex environments.

[ pdf] [ video] [ DOI: 10.1109/LRA.2017.2773669]