Path planning algorithm using informed rapidly-exploring random tree*-connect with local search

Author

Muhammad Aria Rajasa Pohan, M.T

Abstrak

The objective of this study is to propose a path planning algorithm using the Informed RRT*-Connect algorithm and a RRT*- based local search algorithm. The Informed RRT*-Connect algorithm is a two-way version of RRT* where sampling is limited to the area that is predicted to provide a better solution. The proposed local search algorithm uses the idea of an informed RRT* where the sampling process is carried out at a certain distance from the best path obtained from the previous path planning algorithm. The performance of the proposed algorithm with the RRT*, Informed RRT*, and RRT*-Connect algorithms using several benchmark cases, namely clutter, trapping, and narrow, respectively, were compared. The test results showed that the use of the Informed RRT*-Connect algorithm with a local search algorithm can increase the convergence rate and final solution quality compared to other algorithms. The Informed RRT*-Connect algorithm can have a high convergence speed because it uses two search trees and performs searches only in a limited area. The local search algorithm can improve the quality of the final solution because it performs exploitation searches along the previous final path. So, the Informed RRT*-Connect algorithm with a local search algorithm has the potential to be used in systems that require fast and optimal path planning algorithms such as robots and autonomous vehicles. Keywords: Informed RRT*, Informed RRT*-Connect, Local search, Path planning, RRT*-Connect.