Path Planning Algorithm for Autonomous Vehicles Based on Hybridization of BFS and Path Smoothing Algorithm
Abstract - In this paper an alternative algorithm is designed for autonomous vehicle path planning. The proposed algorithm is a hybridization of the Breadth First Search algorithm (BFS) and the path smoothing algorithm (BFS - path smoothing). Based on observations from the test results, the advantage of the BFS algorithm is that it can provide solutions that lead to optimal solutions, but has the disadvantage of high computational time. In order to obtain an optimal solution, then the path produced by the BFS algorithm will be further processed by the path smoothing algorithm. Although the BFS - path smoothing algorithm has a high computational time, but for the purpose of getting an optimal solution, the BFS - path smoothing computation time is still lower than the RRT* algorithm to get the optimal solution. RRT* algorithm is one algorithm that is commonly used for autonomous vehicles path planning. This hybridization process is carried out by first running the BFS algorithm to provide an initial solution. The initial solution is then improved by using the path smoothing algorithm to obtain an optimal solution. The BFS-path smoothing algorithm is tested in simulations using several existing benchmark cases, namely narrow, maze, trap and clutter environments. The optimality criteria that are compared are path costs and computational time. In testing, the performance of the BFS-path smoothing algorithm is compared with the performance of the RRT* algorithm. We show that the proposed algorithm can produce path output with higher quality than the path produced by RRT *.
Keywords : Breadth First Search, path smoothing, path planning, simulation testing, RRT*