Efficient Robot Motion Planning Using Bidirectional-Unidirectional RRT Extend Function

In this article, based on the rapidly-exploring random tree (RRT), we propose a novel and efficient motion planning algorithm using bidirectional RRT search. First, a RRT extend function is used to organize the sampled states under kinodynamic constraints. Meanwhile, the bidirectional search strategy is implemented to grow a forward tree and backward tree simultaneously in the tree extension process. When these two trees meet each other, the backward tree will act as a heuristic to guide the forward tree to continuously grow toward the goal state, where the algorithm switches to unidirectional search mode. Therefore, the two-point boundary value problem (BVP) in the connection process is avoided, and the extension process gets much accelerated. We also prove that probabilistic completeness is guaranteed. Numerical simulations are conducted to demonstrate that the proposed algorithm performs much better than the state-of-the-art algorithms in different environments. Note to Practitioners—The motivation of this work is to develop an efficient sampling-based motion planning algorithm for mobile robots. Conventional sampling-based algorithms are time-consuming to find a feasible solution under differential constraints. When applying bidirectional search strategy to improve them, the complex 2-point BVP is required to solve. In this article, the backward free is regarded as a heuristic to guide the tree growth. On the one hand, the advantage of bidirectional search is retained. On the other hand, the 2-point BVP is avoided. Therefore, the bidirectional-unidirectional technique can achieve efficient robot motion planning. The proposed algorithm can be extended to other specified sampling-based algorithms to further improve their performance. Besides, it can be also applied to autonomous driving, service robot and medical robots to achieve efficient motion planning.

I. Introduction

Robot motion planning is to plan collision-free motions for a robot from a start to a goal state among a set of obstacles [1]. Although it can be considered as a geometric path planning problem for simplicity, the computation is still complex [2]. When taking into account differential constraints and sensing uncertainties, this problem becomes further complicated. In the past few decades, many algorithms have been presented to address the motion planning problem, such as combinatorial roadmap [3], potential fields [4] and sampling-based methods [5], [6]. Combinatorial roadmap and potential field algorithms can efficiently solve a series of motion planning problems. However, both of them do not scale well in the general case since they rely on the complex construction of configuration space. Sampling-based algorithms can avoid the precise geometric modeling of configuration space and efficiently search the whole state space. Therefore, they have become relatively popular for a very general class of problems. They implement a random sampling strategy to organize collision-free states concerning robot kinematics and dynamics. Probabilistic roadmap (PRM) [5] utilizes a graph to store the sampled states while rapidly-exploring random tree (RRT) [6] utilizes a tree. Then a feasible solution can be computed by querying the constructed graph or tree. PRM is suitable for multi-query problems, while RRT for single-query problems. Single-query approaches have seen a significant advance in recent years and have been widely applied into many robotic applications. In this article, we also focus on the single-query motion planning problem.