The Application of Graph Neural Networks in Maze Problem
DOI:
https://doi.org/10.54097/gq83vf96Keywords:
Graph Neural Network; Maze Problem; Shortest Path.Abstract
Graph Neural Network (GNN) shows significant applications in many fields these days, being a possible strong solution for Maze Problem, like finding paths and predicting distance. This paper attempts to apply Graph Neural Network with traditional algorithms as solutions. First, this paper built a generator to construct mazes as the data set for later experiments. Then, this paper proposes two methods. One is GNN-ShortestPath, that predicts distance to the target position by aggregating messages along the graph. The other one is GNN-Policy, which generates distribution of actions in steps. This paper performs experiments based on the methods and evaluates the results on Successful Rate and Optimal Rate. Finally, this paper analyses results and discusses limitation and possible improvements. Despite of many limitations in the experiments, this paper shows that application of Graph Neural Network in solving Maze Problem has great advantages and traditional algorithms can assist in the performance of Graph Neural Network.
References
[1] Wu Z, Pan S, Chen F, Long G, Zhang C, Yu PS. A comprehensive survey on graph neural networks. IEEE Trans Neural Netw Learn Syst. 2021;32(1):4–24. doi:10.1109/TNNLS.2020.2978386.
[2] Kaur NKS. A review of various maze solving algorithms based on graph theory. IJSRD. 2019;6(12):431–4.
[3] Ji X, Li H, Pan Z, Gao X, Tu C. Decentralized, unlabeled multi-agent navigation in obstacle-rich environments using graph neural networks. In: Proceedings of the 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2021. p. 8936–43.
[4] Shah MSH, Mohite MJM, Musale AG, Borade JL. Survey paper on maze generation algorithms for puzzle solving games. Int J Sci Eng Res. 2017;8(2):1064–7.
[5] Ji X, Li H, Pan Z, Gao X, Tu C. Decentralized, unlabeled multi-agent navigation in obstacle-rich environments using graph neural networks. In: Proceedings of the 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2021. p. 8936–43.
[6] Khan A, Ribeiro A, Kumar V, Francis AG. Graph neural networks for motion planning. arXiv preprint arXiv:2006.06248. 2020.
[7] Coremen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 3rd ed. Prentice Hall of India; 2009. p. 587–748.
[8] Wang Q. Comparative analysis of maze solving algorithms based on OCaml. In: AIP Conference Proceedings. AIP Publishing LLC; 2024. Vol. 3194, No. 1, p. 040001.
[9] Biju A, Gayathri MP, Jayapandian N, Chris A, Thaleeparambil NR. Efficient pathfinding in a maze to overcome challenges in robotics and AI using breadth-first search. In: Proceedings of the 2025 IEEE 14th International Conference on Communication Systems and Network Technologies (CSNT). IEEE; 2025. p. 727–32.
[10] Mahmud MS, Sarker U, Islam MM, Sarwar H. A greedy approach in path selection for DFS based maze-map discovery algorithm for an autonomous robot. In: Proceedings of the 2012 15th International Conference on Computer and Information Technology (ICCIT). IEEE; 2012. p. 546–50.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
