Workspace importance sampling for probabilistic roadmap planning

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but they behave poorly when a robot's configuration space contains narrow passages. This paper presents workspace importance sampling (WIS), a new sampling strategy for PRM planning. Our main idea is to use geometric information from a robot's workspace as "importance" values to guide sampling in the corresponding configuration space. By doing so, WIS increases the sampling density in narrow passages and decreases the sampling density in wide-open regions. We tested the new planner on rigid-body and articulated robots in 2-D and 3-D environments. Experimental results show that WIS improves the planner's performance for path planning problems with narrow passages.

Authors

• Hanna Kurniawati
• David Hsu

Keywords

• Monte Carlo methods
• Sampling methods
• Orbital robotics
• Path planning
• Testing
• Robots
• Computer science
• Application software
• Design automation
• Computer graphics
• Degrees Of Freedom
• Configuration Space
• Geometric Information
• Many Degrees Of Freedom
• Running Time
• Sample Distribution
• Tetrahedral
• Free Space
• Rigid Body
• Position Of Point
• Total Run Time
• Complex Shapes
• Robot Motion
• Collision Detection
• Position Of The Robot
• Computational Geometry
• Narrow Opening
• Medial Axis
• Orientation Of The Robot