Adaptive Sampling for PRM using Workspace Information

Although Probabilistic Roadmap (PRM) performs well in solving path planning problems involving high DOFs robot, its performance degrades significantly when the robot's configuration space contain narrow passages. Narrow passages are small regions of the configuration space that are critical for capturing the connectivity of the configuration space. Unfortunately, as the robot's DOF's increases, the narrow passage problem becomes more severe due to the curse of dimensionality. Nevertheless, sampling history provides hints on the connectivity of the configuration space. Furthermore, in many real world application, the robot's workspace, the space where the robot works, provide hints on the location of narrow passages in the configuration space.

In this project, we develop a new probabilistic path planner called Workspace-based Connectivity Oracle (WCO). WCO uses workspace information and reinforcement learning technique to adapt the sampling distribution of PRM, dynamically. WCO is an ensemble sampler composed of many component samplers, each based on a geometric feature of a robot. Each component sampler adapts its sampling distribution using information about the connectivity of the workspace and the current roadmap being constructed. These component samplers are combined through a reinforcement learning technique, based on their sampling history. WCO is able to solve a simulation of bridge inspection problem involving a 35 DOFs mobile manipulator.


H. Kurniawati and D. Hsu. Workspace-based connectivity oracle: An adaptive sampling strategy for PRM planning. In S. Akella and, editors, Algorithmic Foundations of Robotics VII. Springer-Verlag, 2006.
bib | .pdf ]

H. Kurniawati and D. Hsu. Workspace importance sampling for probabilistic roadmap planning. In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, pages 1618-1623, 2004.
bib | .pdf ]

Last updated: 15 September 2008