Analyzing and comparing routing algorithms to find the shortest path in graph transformable problems

Document Type : Original Article

Author

Faculty of Industrial Engineering, Islamic Azad University – South Tehran Branch, Tehran, Iran

10.22034/ijwg.2023.405659.1062

Abstract

Objective: Search is a problem solving technique in artificial intelligence. Graph search problems are often modeled as graph games between multiple agents. Graph search algorithms are designed with two main applications of graph traversal and finding the shortest path between two vertices of a graph.
Method: In this article, first a comprehensive study on search methods has been conducted and then, various route search algorithms have been investigated and compared in order to achieve the most optimal algorithm in finding the shortest route.
Findings: These algorithms include Dijkstra, A*, and IDA* search algorithms, which have been compared with each other using the three parameters of execution time, time complexity, and space complexity.
Conclusion: To carry out investigations, a hypothetical game state (field) was used in two conditions, with and without obstacles, and programming was done using Python programming language. The results show that the Dijkstra algorithm and the A* algorithm have relatively the same time complexity, and the IDA* algorithm is faster than both; Also, the IDA* method occupies less memory than the A* method.

Keywords

Main Subjects

References

  • Bhadoria, A., & Singh, R. K. (2014). Optimized angular a star algorithm for global path search based on neighbor node evaluation. International Journal of Intelligent Systems and Applications, 6(8), 46.
  • Candra, A., Budiman, M. A., & Pohan, R. I. (2021). Application of A-Star Algorithm on Pathfinding Game. Journal of Physics: Conference Series, 1898(1), 012047. https://doi.org/10.1088/1742-6596/1898/1/012047
  • Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. https://doi.org/10.1007/BF01386390/METRICS
  • Duchon, F., Babinec, A., Kajan, M., Beno, 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. https://doi.org/10.1016/J.PROENG.2014.12.098
  • Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3), 596–615. https://doi.org/10.1145/28869.28874
  • Gibert, F., & Nofrarias, M. (2021). Application of A-Star Algorithm on Pathfinding Game Application of A-Star Algorithm on Pathfinding Game. https://doi.org/10.1088/1742-6596/1898/1/012047
  • Goyal, A., Mogha, P., Luthra, R., & Sangwan, N. (2014). Path finding: A* or Dijkstra’s? International Journal in IT & Engineering, 2(1), 1–15.
  • Gross, J. L., & Yellen, J. (2005). Graph theory and its applications. CRC press.
  • Guruji, A. K., Agarwal, H., & Parsediya, D. K. (2016). Time-efficient A* Algorithm for Robot Path Planning. Procedia Technology, 23, 144–149. https://doi.org/10.1016/J.PROTCY.2016.03.010
  • Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136
  • Hassan, F., Sunar, N., Mohd Basri, M. A., Mahmud, M. S. A., Ishak, M. H. I., & Mohamed Ali, M. S. (Eds.). (2023). Methods and Applications for Modeling and Simulation of Complex Systems. 1912. https://doi.org/10.1007/978-981-99-7243-2
  • Jindal, P., & Kumar, A. (2010). Analysis of shortest path algorithms. Global Journal of Computer Science and Technology, 10(8).
  • Kapi, A. (2020). A Review on Informed Search Algorithms for Video Games Pathfinding. International Journal of Advanced Trends in Computer Science and Engineering, 9, 2756–2764. https://doi.org/10.30534/ijatcse/2020/42932020
  • Keshuai, Z., & Pingqing, F. (2021). Improved A~* algorithm and artificial potential field algorithm for mobile robot path planning [J]. Electronic Devices, 44(02), 368–374.
  • Lanning, D. R., Harrell, G. K., & Wang, J. (2014). Dijkstra’s Algorithm and Google Maps. Proceedings of the 2014 ACM Southeast Regional Conference, ACM SE 2014. https://doi.org/10.1145/2638404.2638494
  • Li, Y., Harms, J., & Holte, R. (2007). No Title. IEEE International Conference on Communications, 123–130. https://doi.org/10.1109/ICC.2007.29
  • Meng, Q., & Zhang, J. (2019). Optimization and application of artificial intelligence routing algorithm. Cluster Computing, 22(4), 8747–8755. https://doi.org/10.1007/s10586-018-1963-z
  • Pemmaraju, S., & Skiena, S. (2003). Computational discrete mathematics: Combinatorics and graph theory with mathematica®. Cambridge university press.
  • Peng, J., Huang, Y., & Luo, G. (2015a). Robot path planning based on improved A* algorithm. Cybernetics and Information Technologies, 15(2), 171–180.
  • Peng, J., Huang, Y., & Luo, G. (2015b). Robot path planning based on improved A* algorithm. Cybernetics and Information Technologies, 15(2), 171–180.
  • Phaneendhar Reddy Vanam. (2011). Shortest path using A∗ Algorithm. http://cs.indstate.edu/~pvanam/phani.pdf
  • Qiong, W., Meiwan, L., Weijian, R., & Tianren, W. (2019). Overview of common algorithms for UAV path planning. Journal of Jilin University (Information Science Edition), 37(01), 58–67.
  • Russell, S. J., & Norvig, P. (2009). Artificial Intelligence A Modern Approach (M. Pompili, Ed.). Alan Apt.
  • Sharma, Cs. K. (2015). Shortest path searching for road network using a* algorithm.
  • Sinthamrongruk, T., Mahakitpaisarn, K., & Manopiniwes, W. (2013). A Performance Comparison between A* Pathfinding and Waypoint Navigator Algorithm on Android and iOS Operating System. International Journal of Engineering and Technology, 5(4), 498.
  • Skiena, S. (1991). Implementing discrete mathematics: combinatorics and graph theory with Mathematica. Addison-Wesley Longman Publishing Co., Inc.
  • Song, Y., & Ma, P. (2021). Research on mobile robot path planning based on improved A-star algorithm. 2021 International Conference on Electronic Information Engineering and Computer Science (EIECS), 683–687.
  • Tang, G., Tang, C., Claramunt, C., Hu, X., & Zhou, P. (2021). Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment. IEEE Access, 9, 59196–59210. https://doi.org/10.1109/ACCESS.2021.3070054
  • Vamja, H., Shaikh, A., & Rami, S. (2017). Comparative Analysis of Different Path Finding Algorithms to Study Limitations and Progress. The Fourteenth International Conference on Networks, 7(9), 68–75.
  • Wang, H., Qi, X., Lou, S., Jing, J., He, H., & Liu, W. (2021). An Efficient and Robust Improved A* Algorithm for Path Planning. Symmetry 2021, Vol. 13, Page 2213, 13(11), 2213. https://doi.org/10.3390/SYM13112213
  • Wang, H., Yin, P., Zheng, W., Wang, H., & Zuo, J. (2020). Mobile robot path planning based on improved A* algorithm and dynamic window method. Robot, 42(03), 346–353.
  • Wang, Q., Hao, Y., & Chen, F. (2021). Deepening the IDA* algorithm for knowledge graph reasoning through neural network architecture. Neurocomputing, 429, 101–109. https://doi.org/https://doi.org/10.1016/j.neucom.2020.12.040
  • Whiting, P. D., & Hillier, J. A. (1960). A method for finding the shortest route through a road network. Journal of the Operational Research Society, 11, 37–40.
  • Yu, X., Huahua, L., Mingbo, D. U., Tao, M., & Zhiling, W. (2014a). An improved A* algorithm that can search infinite neighborhoods [J]. Robot, 36(05), 627–633.
  • Yu, X., Huahua, L., Mingbo, D. U., Tao, M., & Zhiling, W. (2014b). An improved A* algorithm that can search infinite neighborhoods [J]. Robot, 36(05), 627–633.
  • Zhang, C., Ao, L., Yang, J., & Xie, W. (2020). An Improved A* Algorithm Applying to Path Planning of Games. Journal of Physics: Conference Series, 1631(1), 012068. https://doi.org/10.1088/1742-6596/1631/1/012068
  • Zikky, Moh. (2016). Review of A* (A Star) Navigation Mesh Pathfinding as the Alternative of Artificial Intelligent for Ghosts Agent on the Pacman Game. EMITTER International Journal of Engineering Technology, 4(1), 141–149. https://doi.org/10.24003/EMITTER.V4I1.117

 

Iranian Journal of Wargaming
Volume 6, Issue 12 - Serial Number 12
September 2023
Pages 85-114

Files

Share

How to cite

Statistics