Choosing Good Distance Metrics and Local Planners for Probabilistic Roadmap Methods

Abstract

This paper presents a comparative evaluation of different distance metrics and local planners within the context of probabilistic roadmap methods for planning the motion of rigid objects in three-dimensional workspaces. The study concentrates on cluttered three-dimensional workspaces typical, e.g., virtual prototyping applications such as maintainability studies in mechanical CAD designs. Our results include recommendations for selecting appropriate combinations of distance metrics and local planners for such applications. Our study of distance metrics shows that the importance of the translational distance increases relative to the rotational distance as the environment becomes more crowded. We find that each local planner makes some connections than none of the others do --- indicating that better connected roadmaps will be constructed using multiple local planners. We propose a new local planning method we call {\em rotate-at-s} that often outperforms the common straight-line in C-space method in crowded environments.

To appear in IEEE Transactions on Robotics and Automation (conditionally accepted). Full Paper (postscript)