Hybrid RRT: A Semi-Dual-Tree RRT-Based Motion Planner

Abstract

Rapidly-exploring Random Trees (RRTs) have been widely used for motion planning problems due to their ability to efficiently find solutions. Informed RRT* is an optimized version of RRT, which not only implements the rewiring process to optimize the tree but also limits the search area to a subset of the state space to return near-optimal solutions faster. However, limiting the state space is a function of the obtained shortest path so that before a solution is found, the planner cannot limit the state space to a subset. Moreover, unidirectional RRTs such as Informed RRT* take more time to find initial solutions in comparison to the bidirectional RRTs. In this paper, we propose Hybrid RRT, which divides the planning process into three parts: finding initial solutions by a dual-tree search, combining two trees into one, and optimizing the solution. In order to obtain an initial solution, Hybrid RRT implements a dual-tree search, which helps it find solutions faster than unidirectional searches. Then, it combines the start tree and the goal tree of the dual-tree search into one so as to implement informed sampling for a single tree to optimize the current solution. The simulation carried out in Open Motion Planning Library (OMPL), which shows that Hybrid RRT achieved outstanding improvement over RRT* and Informed RRT*.

Keywords

• Motion planning
• path planning
• RRT
• informed sampling
• path optimization