An Enhancement of A* Algorithm Applied in Automated Vehicle Parking - Mary Janelly S Borbon; Rovia Zhen M Indol; Raymund M Dioses; Khatalyn E. Mata (Asosiasi Riset Teknik Elektro dan Informatika Indonesia, 2024)
The A* Algorithm is a path-finding algorithm that primarily uses weighted graphs and focuses on the heuristic values of nodes. However, while effective in generating a near-optimal path in a static environment, the traditional algorithm faces limitations in navigating dynamic environments, often resulting in collisions due to its inability to recognize dynamic and moving obstacles. This limitation makes it inefficient especially in complex environments with real-world scenarios. To address these limitations, an Enhanced A* Algorithm is proposed. This algorithm utilizes Navigation Mesh data structure to generate a more optimal route with local path planning and to dynamically adjust the parameters in two-dimensional non-grid environments. The performance of the algorithms was evaluated using 12 benchmarks, each corresponding to a distinct test case and levels of complexity. Then, in terms of dynamic obstacle avoidance, a comparison between the Enhanced A* Algorithm and the traditional algorithm was conducted. Statistical analyses were also performed to assess the consistency and validity of the findings. The results demonstrated that the Enhanced A* Algorithm successfully avoided all dynamic obstacles and moving objects encountered along the path in all distinct test cases. In contrast to the traditional algorithm, which achieved an average obstacle avoidance rate of 8.33%, the enhanced algorithm consistently demonstrated a 100% average obstacle avoidance rate. The enhanced algorithm outperformed the traditional A* algorithm in generating a path in a complex environment by exhibiting optimal dynamic obstacle recognition and avoidance. The Enhanced A* Algorithm is subsequently applied to autonomous vehicle parking, following standard parking restriction laws.