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

Abstract

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.