Motion planning using dynamic roadmaps

Abstract

We evaluate the use of dynamic roadmaps for online motion planning in changing environments. When changes are detected in the workspace, the validity state of affected edges and nodes of a precompiled roadmap are updated accordingly. We concentrate in this paper on analyzing the tradeoffs between maintaining dynamic roadmaps and applying an on-line bidirectional rapidly-exploring random tree (RRT) planner alone, which requires no preprocessing or maintenance. We ground the analysis in several benchmarks in virtual environments with randomly moving obstacles. Different robotics structures are used, including a 17 degrees of freedom model of NASA's Robonaut humanoid. Our results show that dynamic roadmaps can be both faster and more capable for planning difficult motions than using on-line planning alone. In particular, we investigate its scalability to 3D workspaces and higher dimensional configurations spaces, as our main interest is the application of the method to interactive domains involving humanoids.