Citation: Xin, P.; Wang, X.; Liu, X.;
Wang, Y.; Zhai, Z.; Ma, X. Improved
Bidirectional RRT* Algorithm for
Robot Path Planning. Sensors 2023, 23,
1041. https://doi.org/10.3390/
s23021041
Academic Editors: Luis Payá, Oscar
Reinoso García and Helder Jesus
Araújo
Received: 22 November 2022
Revised: 31 December 2022
Accepted: 5 January 2023
Published: 16 January 2023
Copyright: © 2023 by the authors.
Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and
conditions of the Creative Commons
Attribution (CC BY) license (https://
creativecommons.org/licenses/by/
4.0/).
Article
Improved Bidirectional RRT* Algorithm for Robot Path Planning
Peng Xin, Xiaomin Wang *, Xiaoli Liu, Yanhui Wang , Zhibo Zhai and Xiqing Ma
Key Laboratory of Intelligent Industrial Equipment Technology of Hebei Province, School of Mechanical and
Equipment Engineering, Hebei University of Engineering, Handan 056038, China
* Correspondence: ztds8579390@163.com
Abstract:
In order to address the shortcomings of the traditional bidirectional RRT* algorithm, such
as its high degree of randomness, low search efficiency, and the many inflection points in the planned
path, we institute improvements in the following directions. Firstly, to address the problem of the
high degree of randomness in the process of random tree expansion, the expansion direction of the
random tree growing at the starting point is constrained by the improved artificial potential field
method; thus, the random tree grows towards the target point. Secondly, the random tree sampling
point grown at the target point is biased to the random number sampling point grown at the starting
point. Finally, the path planned by the improved bidirectional RRT* algorithm is optimized by
extracting key points. Simulation experiments show that compared with the traditional A*, the
traditional RRT, and the traditional bidirectional RRT*, the improved bidirectional RRT* algorithm
has a shorter path length, higher path-planning efficiency, and fewer inflection points. The optimized
path is segmented using the dynamic window method according to the key points. The path planned
by the fusion algorithm in a complex environment is smoother and allows for excellent avoidance of
temporary obstacles.
Keywords:
artificial potential field method; improved bidirectional RRT* algorithm; dynamic window
method; fusion algorithm; temporary obstacles avoidance
1. Introduction
Mobile robots have a wide range of applications in industry, agriculture, and daily
life. To enable robots to quickly reach their target point and complete a designated task in a
complex environment, an excellent path-planning algorithm should be employed to plan
an effective path. Therefore, a path-planning algorithm is a core facet of the development
of mobile robots [
1
,
2
]. Common path-planning algorithms include the artificial potential
field method [
3
], ant colony algorithms [
4
], the A* algorithm [
5
], the dynamic window
method [6], etc.
The RRT algorithm is a classical path-planning algorithm [
7
]. The main idea of the
algorithm is to find an effective path by growing a random tree continuously until the
target point is also on the random tree. The defects of the RRT algorithm are obvious. The
RRT algorithm randomly obtains sampling points when looking for a path, which makes
its search efficiency low, and there are many redundant nodes and redundant sections
in the planned path. RRT* [
8
] and bidirectional RRT* are commonly used to improve
the RRT algorithm. At present, scholars have carried out in-depth research on the RRT
algorithm. Mashayekh et al. [
9
] proposed Informed RRT*-Connect, which improved the
sampling of RRT*-Connect and provided better solutions. In [
10
], the author proposes
EB-RRT, which facilitates a robot’s movement in dynamic environments using heuristics to
plan a global path and the EB method to optimize the heuristic path. In [
11
], the authors
propose a new rewiring method based on triangulation to improve the RRT algorithm.
The planning time is closer to the optimum than the traditional RRT algorithm. In [
12
],
a regression mechanism is added to RRT to prevent over-searching. The algorithm uses
adaptive expansion to avoid duplicate searches and improve search efficiency by refining
Sensors 2023, 23, 1041. https://doi.org/10.3390/s23021041 https://www.mdpi.com/journal/sensors
