A-star algorithm

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Revision as of 16:53, 29 November 2021 by Arielbarboza (talk | contribs)
Jump to navigation Jump to search

Authors: Andres E. Blanco, Ariel Barboza, Grace Soto, Idan Mika, Lauren Moore (SYSEN 5800)

Introduction


Theory, Methodology, and Algorithmic Discussions

From its start as a path finding algorithm for a robot, A* Algorithm has grown to be a staple in modern optimization of shortest path algorithms. An early study of the algorithm was done in Beijing university of Technology in 2011 where the algorithm was used to track the fastest path through a maze. Three A* Algorithms were used with different heuristics based on distance from start and end, difference from farthest point (where the last decision was made) and angle from current position to the goal. On all occasions at least one of the A* Algorithms out performed a depth search with the second heuristic performing the best (Liu & Gong). Through this early experiment the strength of the A* Algorithm is truly shown, allowing for multiple heuristics to adjust the algorithm to the needs of the problem.


A modern example of the A* Algorithm can be found from the Chengdu University of Information and Technology and their study of the A* Algorithm’s viability in tracking meteorological paths for ships. Whether it be the accident in the Suez Canal or the current supply chain issues in the world, ship travel is a key issue in need of optimization. The study accounts for “All hydrological and meteorological conditions are considered in the route planning before and after the voyage.” and “Navigation safety is the prerequisite for route planning, and weather navigation can plan different routes for ships with different sailing goals”. A spatial model of the path is then made and used as the grounds on which the algorithm will travel. An A* Algorithm was then used and compared to other tools such as Dijkstra’s and BFS algorithms. Again a heuristic was used in simple situations (ones with no obstacles) to calculate the cost of moving from current node to the target. In more complicated cases (where weather obstacles were introduced) a heuristic based on Dijkstra algorithm is used “ according to the 0020 position of the target point relative to the starting point, the algorithm’s search direction at each node is restricted. Taking a square grid map with 8 search directions as an example, after the preprocessing of the global route planning”. This improvement of A* Algorithm for ship tracking decreased the number of nodes searched by nearly 30%. (Chen, Ge, et al).

A* Algorithm is a strong tool in use of optimization and AI machine learning. The algorithm is strong as heuristics can be used to further optimize the problem without changing the basis of the code structure. Additionally the algorithm, if possible, will always find the optimal solution with a proper, admissible heuristic. While A* Algorithm has many pros in its adaptability to the situation and reliability. It has one large drawback, its memory, usage and processing power. If a heuristic is implemented improperly the algorithms speed and completion will be hindered. In conclusion, A* is a powerful catch all solution that builds on its predecessors to develop a reliable optimal path algorithm.

There are a lot of discussions revolving on the best use of the A* Algorithm and also where it is mostly used. One of them being the game industry, mainly used to find the shortest path. There are a lot of different shortest path algorithms but A* is one of the preferred methods.[4]

Numerical Example


Application Illustration


Conclusion


References

1. Chen, Ge, et al. “Research on Ship Meteorological Route Based on A-Star Algorithm.” Mathematical Problems in Engineering, vol. 2021, 2021, pp. 1–8., https://doi.org/10.1155/2021/9989731.

2. Liu, Xiang, and Gong, Daoxiong. “A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze.” 2011 International Conference on Electric Information and Control Engineering, 2011, https://doi.org/10.1109/iceice.2011.5777723.

3. C. Wang et al., "Path planning of automated guided vehicles based on improved A-Star algorithm," 2015 IEEE International Conference on Information and Automation, 2015, pp. 2071-2076, doi: 10.1109/ICInfA.2015.7279630.

4. P. O. N. Saian, Suyoto and Pranowo, "Optimized A-Star algorithm in hexagon-based environment using parallel bidirectional search," 2016 8th International Conference on Information Technology and Electrical Engineering (ICITEE), 2016, pp. 1-5, doi: 10.1109/ICITEED.2016.7863246.