Finding narrow passages with probabilistic roadmaps: the small step retraction method

The efficiency of probabilistic roadmap (PRM) planners drops dramatically in spaces with narrow passages. This paper presents a new method - small-step retraction - that helps PRM planners find paths through such passages. The method consists of slightly fattening the robot's free space, constr...

Full description

Saved in:
Bibliographic Details
Main Authors: Saha, M., Latombe, J.-C.
Format: Conference Proceeding
Language:English
Subjects:
Artificial intelligence
Computational geometry
Costs
Laboratories
narrow passages
Orbital robotics
Path planning
probabilistic roadmap
Road accidents
Robots
small-step retraction
Solid modeling
Testing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The efficiency of probabilistic roadmap (PRM) planners drops dramatically in spaces with narrow passages. This paper presents a new method - small-step retraction - that helps PRM planners find paths through such passages. The method consists of slightly fattening the robot's free space, constructing a roadmap in the fattened free space, and repairing colliding portions of this roadmap by retracting them out of collision. The fattened free space is not explicitly computed. Instead, the robot links and/or obstacles are thinned around their medial axis. A robot configuration lies in fattened free space if the thinned objects do not collide at this configuration. Two repair strategies are used. The "optimist" strategy waits until a complete path has been found in fattened free space before repairing it. The "pessimist" strategy repairs the roadmap as it is being built. The former is faster, but the latter is more reliable. A simple combination yields an integrated planner that is both fast and reliable.
ISSN:2153-0858
2153-0866
DOI:10.1109/IROS.2005.1545606