Asymptoticcaly-Optimal Path Planning Using the Improved Probabilistic Road Map Algorithm - Muhammad Aria Pohan (Program Studi Teknik Elektro, Fakultas Teknik dan Ilmu Komputer, Universitas Komputer Indonesia., 2022)
A path planning algorithm is asymptotically optimal if it can guarantee that it will produce an optimal solution if given sufficient time. Path-planning algorithms that can provide optimal solutions are essential in many robotic applications. The objective of this study is to propose a new asymptotic optimal path planning algorithm. The method is to improve the probabilistic road map (PRM) algorithm through three strategies. The first strategy is to use an information-based sampling technique. The second strategy is that the search area starts from a small ellipsoid subset first. The third strategy is to improve the path using the wrapping process. We call this proposed algorithm the wrapping-based informed PRM (WIPRM) algorithm. Furthermore, the performance of the WIPRM algorithm was compared with the PRM algorithm, informed rapidly-exploring random tree* (RRT*), and informed PRM. The test results show that the WIPRM algorithm can build optimal paths for all test scenarios. The computational time needed by the WIPRM algorithm to build the optimal path is better than the informed RRT* and informed PRM algorithms. These results indicate that the WIPRM algorithm could be used in various robotic systems requiring optimal path planning algorithms, such as autonomous cars, unmanned aerial vehicles (UAV), and autonomous undersea vehicles (AUV).