Triple RRTs: An Effective Method for Path Planning in Narrow Passages

Although Rapidly-exploring Random Trees (RRTs) have been successfully applied in path planning of robots with many degrees of freedom under non-holonomic and differential constraints, rapidly identifying and passing through narrow passages in a robot's configuration space remains a challenge fo...

Full description

Saved in:
Bibliographic Details
Published in:Advanced robotics 2010-01, Vol.24 (7), p.943-962
Main Authors: Wang, Wei, Xu, Xin, Li, Yan, Song, Jinze, He, Hangen
Format: Article
Language:English
Subjects:
Corridors
Degrees of freedom
Joints
Mathematical analysis
MULTI-D.O.F
NARROW PASSAGES
PATH PLANNING
RAPIDLY-EXPLORING RANDOM TREES
ROBOT
Robots
Sampling
Strategy
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Although Rapidly-exploring Random Trees (RRTs) have been successfully applied in path planning of robots with many degrees of freedom under non-holonomic and differential constraints, rapidly identifying and passing through narrow passages in a robot's configuration space remains a challenge for RRTs-based planners. This paper presents a novel two-stage approach to address the problem of multi-d.o.f. robot path planning in high-dimensional configuration space with narrow corridors. The first stage introduces an efficient sampling algorithm called Bridge Test to find a global roadmap that identifies the critical region. The second stage presents two varieties of RRTs, called Triple-RRTs, to search for a local connection under the guidance of the global landmark. The two-stage strategy keeps a fine balance between global heuristics and local connection, resulting in high performance over the previous RRTs-based path planning methods. We have implemented the Triple-RRTs planners for both rigid and articulated robots in two- and three-dimensional environments. Experimental results demonstrate the effectiveness of the proposed method.
ISSN:0169-1864
1568-5535
DOI:10.1163/016918610X496928