Dynamic Map Pathfinding Using Hierarchical Pathfinding Theta-Star (HPT*) Algorithm

Irfan Darwin; Suryadiputra Liawatimena

Irfan Darwin Bina Nusantara University
Suryadiputra Liawatimena Bina Nusantara University

Abstract

Theta-Star is an efficient algorithm that can be used to find an optimal path in a map with better performance compared to the A-Star algorithm. Combining the Theta-Star with Hierarchical Pathfinding further enhances its performance by abstracting a large map into several clusters. What this combination lacks is the capability to handle a dynamic element in the map. Without that capability, the agent could potentially collide with elements in the map that is undesirable in certain conditions, while adding that capability might reduce the pathfinding algorithm's performance. The proposed algorithm aims to provide the capability to handle dynamic elements without severe negative impact on the performance of the algorithm. The effectiveness of the proposed algorithm is verified in terms of execution time, number of nodes explored, final path length, and the number of collisions that occurred.

Downloads

Download data is not yet available.

References

L. van Elswijk, “Hierarchical Path-Finding Theta*,” pp. 11–13, 2013.

S. J. Russell and P. Norvig, in Artificial intelligence: a modern approach, Upper Saddle River: Prentice-Hall, 2010, pp. 42–44.

X. Cui and H. Shi, “A*-based Pathfinding in Modern Computer Games,” International Journal of Computer Science and Network Security, pp. 125–130, 2011.

K. Daniel, A. Nash, S. Koenig, and A. Felner, “Theta*: Any-Angle Path Planning on Grids,” Journal of Artificial Intelligence Research, vol. 39, pp. 533–579, 2010.

A. Nash, S. Koenig, and C. Tovey, “Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D.,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 24, no. 1, 2010.

P. Mendonca and S. Goodwin, “C-Theta*: Cluster Based Path-Planning on Grids,” 2015 International Conference on Computational Science and Computational Intelligence (CSCI), 2015.

В. Г. Михалько and І. В. Круш, “Effective pathfinding for four-wheeled robot based on combining Theta* and hybrid A* algorithms,” ScienceRise, vol. 7, no. 2 (24), p. 17, 2016.

N. B. Abdul Latip, R. Omar, and S. K. Debnath, “Optimal Path Planning using Equilateral Spaces Oriented Visibility Graph Method,” International Journal of Electrical and Computer Engineering (IJECE), vol. 7, no. 6, p. 3046, 2017.

V.-H. Dang, N. D. Thang, H. H. Viet, and L. A. Tuan, “Batch-Theta* for path planning to the best goal in a goal set,” Advanced Robotics, vol. 29, no. 23, pp. 1537–1550, 2015.

R. E. Korf, “Recent Progress in the Design and Analysis of Admissible Heuristic Functions,” Lecture Notes in Computer Science, pp. 45–55, 2000.

F. A. Raheem and U. I. Hameed, “Heuristic D* Algorithm Based on Particle Swarm Optimization for Path Planning of Two-Link Robot Arm in Dynamic Environment,” Al-Khwarizmi Engineering Journal, vol. 15, no. 2, pp. 108–123, 2019.

Yan Li, Wenju Zhao, Zhenhua Zhou, and Cai Chen, “Hierarchical and Dynamic Pathfinding Algorithms in Game Maps,” International Journal of Advancements in Computing Technology, vol. 5, no. 11, pp. 87–98, 2013.

A. Kring, A. Champandard, and N. Samarin, “Dhpa* and shpa*: Efficient hierarchical pathfinding in dynamic and static game worlds,” Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, vol. 5, no. 1, 2010.

W. Zhu, D. Jia, H. Wan, T. Yang, C. Hu, K. Qin, and X. Cui, “Waypoint Graph Based Fast Pathfinding in Dynamic Environment,” International Journal of Distributed Sensor Networks, vol. 11, no. 8, p. 238727, 2015.

A. Botea, M. Muller, and J. Schaeffer, “Near-optimal hierarchical pathfinding,” Journal of Game Development, vol. 1, no. 1, pp. 1–30, 2004.

N. R. Sturtevant, “Benchmarks for Grid-Based Pathfinding,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 2, pp. 144–148, 2012.