Fast Path Planning Based on Bi-Directional RRT^* for Mobile Robot in Complex Maze Environments

Abstract

The Rapidly-exploring Random Tree (RRT) algorithm and various improved algorithms are being used for path planning in many different environments. Because of the probabilistic completeness of the RRT algorithm, if there is a feasible path, the RRT algorithm should be able to find it. However, in maze environments, the cost of computation and computation time will increase. There, in this paper, a new algorithm Exploration and Exploitation RRT (EE-RRT) based on Bi-directional RRT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> (B-RRT*) is proposed for path planning in maze environments. During the initial stage of path planning, two trees with starting point and ending point as root nodes grow at the same time, exploring the global environment. Once all feasible areas are discovered, the algorithm stops searching and begins to exploit the feasible areas to find better paths. The simulation results verify the effectiveness and superiority and of our proposed algorithm which has the fastest speed of path planning and shorter path length than RRT*-connect and Bi-directional RRT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> algorithms.