IBPF-RRT*: An improved path planning algorithm with Ultra-low number of iterations and stabilized optimal path quality

Abstract

Due to its asymptotic optimality, the Rapidly-exploring Random Tree star (RRT*) algorithm is widely used for robotic operations in complex environments. However, the RRT* algorithm suffers from poor path quality, slow convergence, and unstable generation of high-quality paths in the path planning process. This paper proposes an Improved Bi-Tree Obstacle Edge Search Artificial Potential Field RRT* algorithm (IBPF-RRT*) to address these issues. First, based on the RRT* algorithm, this paper proposes a new obstacle edge search artificial potential field strategy (ESAPF), which speeds up the path search and improves the path quality simultaneously. Second, a bi-directional pruning strategy is designed to optimize the bi-directional search tree branch nodes and combine the bi-directional search strategy to reduce the number of iterations for convergence speed significantly. Third, a novel path optimization strategy is proposed, which enables high-quality paths to be generated stably by creating an entirely new node between two path nodes and then optimizing the paths using a pruning strategy based on triangular inequalities. Experimental results in three different scenarios show that the proposed IBPF-RRT* algorithm outperforms other methods in terms of optimal path quality, algorithm stability, and the number of iterations when compared to the RRT*, Q-RRT*, PQ-RRT*, F-RRT* and CCPF-RRT* algorithms, and proves the effectiveness of the proposed three strategies.

Keywords

• Rapidly-exploring Random Tree star (RRT*)
• Optimal path planning
• Barrier edge sampling