Path planning with incremental roadmap update for large environments

Research results suggest that one can incorporate motion-planning techniques into the control loop of 3D navigation or tele-operation for more efficient navigation. However, the motion planner with this approach may not scale up well for large workspaces. We propose an approach to overcome this scalability problem. We limit the region of interest for path-finding to a window around the current robot configuration and incrementally update the roadmap in this window as the robot moves. In order to make the roadmap update efficient enough for interactive applications, we adopt a data structure, called rapidly-exploring random tree, to reduce the run-time cost of building the connectivity roadmap. The incremental path planner has been implemented in Java and incorporated into a Java3D-based VRML browser. We compare the performance of this improved planner with the previous one for workspaces of various sizes and analyze the bottlenecks of maintaining such a roadmap. By extending the planning techniques to large work-spaces, we believe that this type of intelligent navigation or tele-operation control will inspire better user-interface design and further researches in planning for large or unbounded worlds.