An enhancement of A* algorithm applied to automated vehicle parking

By: Borbon, Janelly S.; Indol, Rovia Zhen M
Language: English Publisher: . . c2025Description: Undergraduate Thesis: (Bachelor of Science in Computer Science) - Pamantasan ng Lungsod n g Maynila, 2025Content type: text Media type: unmediated Carrier type: volumeGenre/Form: academic writingDDC classification: . LOC classification: QA76.9 A43 B67 2025
Contents:
ABSTRACT: 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 is a static environment, the traditional algorithm faces limitations in navigating dynamic environments, often resulting in collisions with obstacles and generating a path with unnecessary sharp turns. These limitations make 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, penalties and Box Blur Algorithm to create a safer distance around the obstacles, and NavMesh Raycast element to make the generated path smoother. The performance of the algorithms was evaluated using three versions of the parking lot environment, 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 effects 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% and 13.33% in all maps, the enhanced algorithm consistently demonstrated a 100% average obstacle avoidance rate. The average obstacle clearance and maximum turning angle were also evaluated, showing an increase in distance of 1 to 4 units and an improvement rate of 14.44% to 27.78%, respectively. The enhanced algorithm outperformed the traditional A* algorithm in generating a path in a complex environment by exhibiting optimal dynamic obstacle recognition and avoidance.
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)

ABSTRACT: 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 is a static environment, the traditional algorithm faces limitations in navigating dynamic environments, often resulting in collisions with obstacles and generating a path with unnecessary sharp turns. These limitations make 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, penalties and Box Blur Algorithm to create a safer distance around the obstacles, and NavMesh Raycast element to make the generated path smoother. The performance of the algorithms was evaluated using three versions of the parking lot environment, 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 effects 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% and 13.33% in all maps, the enhanced algorithm consistently demonstrated a 100% average obstacle avoidance rate. The average obstacle clearance and maximum turning angle were also evaluated, showing an increase in distance of 1 to 4 units and an improvement rate of 14.44% to 27.78%, respectively. The enhanced algorithm outperformed the traditional A* algorithm in generating a path in a complex environment by exhibiting optimal dynamic obstacle recognition and avoidance.

Filipiniana

There are no comments for this item.

to post a comment.

© Copyright 2024 Phoenix Library Management System - Pinnacle Technologies, Inc. All Rights Reserved.