Explanation and Speedup Comparison of Advanced Path-planning Algorithms Presented on Two-dimensional Grid
Abstract
Path planning or network route planning problems are an important issue in AI, robotics, or computer games. Appropriate implementation and knowledge of advanced and classical path-planning algorithms can be important for both autonomous navigation systems and computer games. In this paper, we compare advanced path planning algorithms implemented on a two-dimensional grid. Advanced path planning algorithms, including pseudocode, are introduced. The experiments were performed in the Python environment, thus with a significant performance margin over C++ or Rust implementations. The main focus is on the speedup of the algorithms compared to a baseline method, which was chosen to be the well-known Dijkstra's algorithm.
All experiments correspond to trajectories on a two-dimensional grid, with variously defined constraints. The motion from each node corresponds to a Moore neighborhood, i.e., it is possible in eight directions.
In this paper, three well-known path planning algorithms are described and compared: the Dijkstra, A* and A* /w Bounding Box. And two advanced methods are included, namely Jump Point Search (JPS), incorporated with the Bounding Box variant (JPS+BB), and Simple Subgoal (SS). These advanced methods clearly show their advantage in the context of the speed up of solution time.
References
Abd Algfoor, Z., Sunar, M. S., and Kolivand, H. A comprehensive study on pathfinding techniques for robotics and video games. International Journal of Computer Games Technology 2015 (2015).
Bjornsson, Y., and Halld´orsson, K. Improved heuristics for optimal path-finding on game maps. AIIDE 6 (2006), 9–14.
Botea, A. Ultra-fast optimal pathfinding without runtime search. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (2011), vol. 6.
Botea, A., Muller, M., and Schaeffer, J. Near optimal hierarchical path-finding. J. Game Dev. 1, 1 (2004), 1–30.
Brewka, G. Artificial intelligence—a modern approach by stuart russell and peter norvig, prentice hall. series in artificial intelligence, Englewood cliffs, nj. The Knowledge Engineering Review 11, 1 (1996), 78–79.
Bulitko, V., Bjornsson, Y., and Lawrence, R. Case-based subgoaling in real-time heuristic search for video game pathfinding. Journal of Artificial Intelligence Research 39 (2010), 269–300.
Cazenave, T. Optimizations of data structures, heuristics and algorithms for path-finding on maps. In 2006 IEEE symposium on computational intelligence and games (2006), IEEE, pp. 27–33.
Costa, M. M., and Silva, M. F. A survey on path planning algorithms for mobile robots. In 2019 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC) (2019), IEEE, pp. 1–7.
Dijkstra, E. W., et al. A note on two problems in connexion with graphs. Numerische Mathematik 1, 1 (1959), 269–271.
Galceran, E., and Carreras, M. A survey on coverage path planning for robotics. Robotics and Autonomous systems 61, 12 (2013), 1258–1276.
Hagberg, A., Swart, P., and S Chult, D. Exploring network structure, dynamics, and function using networkx. Tech. rep., Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
Hamed, O., and Hamlich, M. Hybrid formation control for multi-robot hunters based on multi-agent deep deterministic policy gradient. MENDEL 27, 2 (Dec. 2021), 23–29.
Harabor, D., and Botea, A. Breaking path symmetries on 4-connected grid maps. In Sixth Artificial Intelligence and Interactive Digital Entertainment Conference (2010).
Harabor, D., and Grastien, A. Online graph pruning for pathfinding on grid maps. In Proceedings of the AAAI Conference on Artificial Intelligence (2011), vol. 25.
Harabor, D., Hechenberger, R., and Jahn, T. Benchmarks for pathfinding search: Iron harvest. In Proceedings of the International Symposium on Combinatorial Search (2022), vol. 15, pp. 218–222.
Harabor, D. D., and Grastien, A. The jps pathfinding system. In SOCS (2012).
Harabor, D. D., Uras, T., Stuckey, P. J., and Koenig, S. Regarding jump point search and subgoal graphs. In IJCAI (2019), pp. 1241–1248.
Hart, P. E., Nilsson, N. J., and Raphael, B. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4, 2 (1968), 100–107.
Hernandez, C., and Baier, J. A. Fast subgoaling for pathfinding via real-time search. In Twenty-First International Conference on Automated Planning and Scheduling (2011).
Klobusnıkova, Z. Mobile robot path planning. Master thesis, Brno University of Technology, Brno, 2018.
Korf, R. E. Depth-first iterative-deepening: An optimal admissible tree search. Artificial intelligence 27, 1 (1985), 97–109.
LaValle, S. M. Planning algorithms. Cambridge university press, 2006.
Lee, J.-Y., and Yu, W. A coarse-to-fine approach for fast path finding for mobile robots. In 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (2009), IEEE, pp. 5414–5419.
Lozano-Perez, T., and Wesley, M. A. An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM 22, 10 (1979), 560–570.
Manakova, L. Advanced methods of mobile robot path planning. Master thesis, Brno University of Technology, Brno, 2020.
Nobes, T. K., Harabor, D., Wybrow, M., and Walsh, S. D. The jps pathfinding system in 3d. In Proceedings of the International Symposium on Combinatorial Search (2022), vol. 15, pp. 145–152.
Pochter, N., Zohar, A., Rosenschein, J. S., and Felner, A. Search space reduction using swamp hierarchies. In Twenty-Fourth AAAI Conference on Artificial Intelligence (2010).
Rabin, S., and Silva, F. Jps+: An extreme a* speed optimization for static uniform cost grids. In Game AI Pro 360. CRC Press, 2019, pp. 95–108.
Sankaranarayanan, J., Alborzi, H., and Samet, H. Efficient query processing on spatial networks. In Proceedings of the 13th annual ACM international workshop on Geographic information systems (2005), pp. 200–209.
Sturtevant, N. Benchmarks for grid-based pathfinding. Transactions on Computational Intelligence and AI in Games 4, 2 (2012), 144 – 148.
Sturtevant, N., and Buro, M. Partial pathfinding using map abstraction and refinement. In AAAI (2005), vol. 5, pp. 1392–1397.
Sturtevant, N. R., Felner, A., Barrer, M., Schaeffer, J., and Burch, N. Memory-based heuristics for explicit state spaces. In Twenty-First International Joint Conference on Artificial Intelligence (2009).
Uras, T., and Koenig, S. Subgoal graphs for fast optimal pathfinding. In Game AI Pro 360. CRC Press, 2019, pp. 109–124.
Uras, T., Koenig, S., and Hernandez, C. Subgoal graphs for optimal pathfinding in neightneighbor grids. In Twenty-Third International Conference on Automated Planning and Scheduling (2013).
VanRossum, G., and Drake, F. L. The python language reference. Python Software Foundation Amsterdam, Netherlands, 2010.
Copyright (c) 2023 MENDEL
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
