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.