Research on the A Star Algorithm for Finding Shortest Path
DOI:
https://doi.org/10.54097/hset.v46i.7697Keywords:
Artificial intelligence; Robot walking route; Manhattan Distance Formula; Matlab.Abstract
With the rapid development of artificial intelligence technology, the problem of intelligent path finding is gradually important, which can optimize the robot walking route and the movement problem of NPCs in the game is improved. Among many shortest path algorithms, A-star algorithm to find the path is one very classic way. In this thesis, the authors mainly study the principle of A star algorithm and compare it with Dijkstra algorithm, and conclude that A-star algorithm is more effective and convenient. In this essay, writer used Raster Method to simulate the environment with obstacle, the distance between every two grids is calculated using Manhattan Distance Formula, which regulate the convenient way of moving is from top to bottom and move around. Through the outcome of the simulation of A star algorithm in Matlab, it shows that it is a better way to search the shortest path.
Downloads
References
Xiong, R., & LIU, Y. (2015). Improvement and parallelization of A* algorithm. Journal of Computer Applications, 35(7), 1843.
Jing, X., & Yang, X. (2018). Application and Improvement of Heuristic Function in A* Algorithm. In 2018 37th Chinese Control Conference (CCC) IEEE.
Faisal, M., & Zamzami, E. M. (2020). Comparative analysis of inter-centroid K-Means performance using euclidean distance, canberra distance and manhattan distance. In Journal of Physics: Conference Series, 1566(1), 012112.
Candra, A. (2021). Application of A-Star Algorithm on Pathfinding Game. Journal of Physics: Conference Series, 1898(78), 012047.
Duchoň, F., Babinec, A., Kajan, M., Beňo, P., Florek, M., Fico, T., & Jurišica, L. (2014). Path planning with modified a star algorithm for a mobile robot. Procedia Engineering, 96, 59-69.
Yao, J., Lin, C., Xie, X., Wang, A. J., & Hung, C. C. (2010). Path planning for virtual human motion using improved A* star algorithm. In 2010 Seventh international conference on information technology: new generations IEEE.
Ghaffari, A. (2014). An energy efficient routing protocol for wireless sensor networks using A-star algorithm. Journal of applied research and technology, 12(4), 815-822.
Bell, M. G. (2009). Hyperstar: A multi-path Astar algorithm for risk averse vehicle navigation. Transportation Research Part B: Methodological, 43(1), 97-107.
Cheng, L., Liu, C., & Yan, B. (2014). Improved hierarchical A-star algorithm for optimal parking path planning of the large parking lot. In 2014 IEEE International Conference on Information and Automation (ICIA) IEEE.
Rousseau, G. L. A., Bostel, J., & Mazari, B. (2005). Star recognition algorithm for APS star tracker: Oriented triangles. IEEE Aerospace and Electronic Systems Magazine, 20(2), 27-31.
Attoyibi, M. M., Fikrisa, F. E., & Handayani, A. N. (2019). The Implementation of A Star Algorithm (A*) In the Game Education about Numbers Introduction. In 2nd International Conference on Vocational Education and Training (ICOVET 2018) Atlantis Press.
Kim, H. Y., & Junkins, J. L. (2002). Self-organizing guide star selection algorithm for star trackers: thinning method. In Proceedings, IEEE Aerospace Conference IEEE.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
