Path Planning Using Combined Informed Rapidly- Exploring Random Tree Star and Particle Swarm Optimization Algorithms

Abstract

This study proposes a path planning algorithm that combines an informed rapidly-exploring random tree (RRT*) and particle swarm optimization (PSO) algorithms. The informed RRT* algorithm can build optimal pathways quickly. However, in some cases, the informed RRT* strategy cannot help increase the convergence rate. Meanwhile, the PSO algorithm can be combined with other algorithms to improve algorithm performance. The proposed algorithm will combine the advantages of informed RRT* and PSO algorithms. The proposed algorithm is called the RRT-PSO algorithm. The RRT-PSO algorithm’s performance was compared to the informed RRT*, RRT*, RRT-ACS, and informed RRT*-connect algorithms using eight benchmark scenarios. The test results on benchmark scenarios with known optimal values demonstrate that the RRT-PSO algorithm achieves those optimal values. The statistical analysis shows that the RRT-PSO algorithm has a fast convergence rate compared to other comparison algorithms. The test results also demonstrate the RRT-PSO algorithm’s stability and robustness compared to other comparison algorithms. Our test results also show the RRT-PSO algorithm’s advantages over other PSO-based and traditional path planning algorithms. The results show that the RRT-PSO algorithm is suitable for applications requiring a fast and optimal path planning algorithm, such as self-driving cars and unmanned aerial vehicles (UAV).

Keywords

• Path planning
• convergence rate
• optimal path
• informed rapidly-exploring random tree
• particle swarm optimization