Augmenting RRT-planners with local trees

During the last few years, Rapidly-exploring Random Trees, RRTs, has been recognized as a very useful tool for designing efficient single-shot path planners. Another benefit is that RRTs can easily handle planning problems involving non-holonomic systems. However, it has also been noted that the narrow passage problem can become even more severe compared to other randomized methods. To reduce that problem, we suggest augmenting RRT-planners with local trees. Furthermore, using local trees, the planner is able to explore several difficult regions in parallel, something that has proved to be very effective for problems where the solution trajectory repeatedly has to pass difficult regions. We present powerful heuristics for when to create such trees and how often they should be allowed to grow, such that the RRT-planner will improve its qualities as an efficient single-shot path planner. The resulting algorithm, RRTLocTrees, is implemented in a newly developed object-oriented framework for path planning and tested on four different path planning problems, with excellent results.

I. Introduction

Being able to efficiently compute collision-free trajectories is one of the main goals in the pursuit of a truly autonomous robot. The path planning problem also appears in several other contexts, some of them rather unexpected. In virtual prototyping, assembly/disassembly problems often have to be solved to, e.g., guarantee efficient maintenance, see Sundaram et al. [1]. In computer animation, there is also a growing need for efficient path planning, allowing the animator to specify only important key frames. Work in this area can be found in, e.g., Kuffner [2] and Nieuwenhuisen [3]. There is also a great potential for motion planning in drug-design, where it is used to study the folding of complex protein molecules, see Song and Amato [4].