A-star algorithm

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Revision as of 17:49, 6 December 2021 by Lam397 (talk | contribs)
Jump to navigation Jump to search

Authors: Andrés E. Blanco, Ariel Barboza, Grace Soto, Idan Mika, Lauren Moore [SYSEN 5800, Fall 2021]

Introduction

Algorithms have many purposes in the world of optimization, from Gradient Descent to Belman-Ford, algorithms have been used widely in the world of optimization. Hoping to create better pathing for their new robot, the Shakey project of DARPA created the A-star (A*) algorithm a shortest path algorithm that uses heuristics as part of the algorithm to navigate a terrain. Since then, A* has many modern applications in computer science. A common modern application is the optimal travel path between two locations based on travel time or distance. Optimal path traveled is increasingly important throughout society


Today more than ever Americans see the importance of the transportation infrastructure. Whether it is the supply chain pipeline or personal travel, transportation is a key part of everyday life. This is extenuated by the climate impacts of travel with the National Geographic society stating “Globally, transportation accounts for between 15 and 20 percent of emissions each year. Motor vehicles are the leading cause of air pollution in the United States, though other modes of travel, such as planes and cruise ships, create greater emissions per voyage per person.” (National Geographic Society) Air pollution, time spent traveling, cost of transportation and the safety associated with transportation impacts individuals every day. Reliable and fast transportation is especially important in the United States where access to transportation can be a barrier to economic and social success.


A* Algorithm can optimize this travel through finding the shortest, cheapest, and most efficient path between two points helping to lower the travel time of everyday travelers, more efficiently conduct cross country shipments and lower the emission production of cars as they travel. By creating a heuristic for and minimizing the travel distance, time and fuel usage while still resulting in a completed trip. This document will introduce the situation of an optimized trip from Cornell University to Harvard University using the A* Algorithm impacted by the travel distance, time and fuel usage parameters.


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] A* Algorithm is an implementation of heuristic search, a process that will give an estimation value from current node to goal node. This implementation will always find the smallest value from f(n) = g(n) + h(n) where n is a node, g(n) is the distance from starting node to n node, and h(n) is a heuristic value of estimation distance from node n to finish node. [4] One of the methods of using the A* Algorithm in the gaming industry is when creating automated movement for non playable characters, the challenge being that they need to move in a realistic way. The combination of using a hexagon based environment versus a grid based environment is one of the discussions seen today.

Numerical Example

The A* Algorithm is a great approach for finding the lowest-cost path between two points. In the figure below, we are seeking to find the shortest distance between two nodes.

Representation of Mapped Locations


The above image is a representation of mapped locations. Each node is a location, and the lines between the nodes is the path between their respective nodes. The numbers on the paths are the distance between each node, g(x). The numbers next to each node represents the straight-line distance between their respective node and the objective node, h(x), and these shall be our heuristic value. Here, the objective is to find the shortest path between our starting node, Node A, and our objective node, Node K. Thus, the A* algorithm will be employed below, where f(x) is the objective function.



Starting from Node A, we can choose to go to either Node C or Node B; we want to choose the best path by applying the A* Algorithm below:



Since f(C) yields the smaller value, we'll choose taking the path between Node A and Node C. This path is highlighted yellow in the figure below.

Map Highlighting the Chosen Path from Node A to Node C


Now, we employ the A* algorithm to chose the next path from Node C. Here, we can chose to go to either Node D or Node H.



Since f(H) yields a smaller value than f(D), we shall chose the path between Nodes C and H. Once again, the path is highlighted yellow in the figure below.

Map Highlighting the Chosen Path from Node A through Node H

Next step applies A* algorithm from Node H to either Nodes I or J.


Since F(I) yields a smaller value than F(J), we shall choose the path between Nodes H and I. The path continues to be highlighted yellow in the figure below.

Map Highlighting the Chosen Path from Node A through Node I

Next step applies A* algorithm from Node I to either Nodes G or K.


Since F(K) is the smaller value, and K is the objective Node we want to arrive at, the A* Algorithm has found the shortest path between Nodes A and K. The path is highlighted in the image below.

Map Highlighting Shortest Path from Node A through Node K

Application

Public Transportation in Cities Optimal routes are essential in creating successful transportation systems. Transportation systems affect entire societies and their quality of life. Minimizing transportation time and distance, effectively reduces time spent traveling, traffic, risk of death or injury while traveling, air pollution and costs incurred from traveling. Transportation is also considered a barrier to impoverished communities, affecting access to employment and other essential services, directly impacting economies. The objective of applying the A* algorithm to transportation challenges is to minimize cost and travel time for transportation.

Pathfinding in Video Games

Pathfinding algorithms are increasingly used in video game development globally. Artificial Intelligence issues are prevalent as these games increase in complexity. Decision-making, movements and strategy are instances where pathfinding algorithms, such as the A* algorithm, are utilized to find optimal solutions. In video games where users make decisions, path finding may increase with complexity as decisions are dynamic according to the user's input. Pathfinding uses up CPU power and memory. The objective is to optimize paths between characters and their endpoints to minimize CPU power and memory used to maximize game performance.

Conclusion

Through the use of a serpentine node map system, using each road and intersection as an edge and node respectively and scoring each based on our characteristics, a basis was built on which to run the A* algorithm. The algorithm was then able to traverse the map finding the shortest, fastest, and most fuel-efficient path in order to minimize the inconvenience to the traveler and the environmental impact. Through the A* algorithm on the node map travel can be optimized to be more efficient and faster for both commercial and pedestrian travel.

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, pp.2071-2076, 2015, https://doi.org/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), pp. 1-5, 2016, https://doi.org/10.1109/ICITEED.2016.7863246.