Dynamic Map Pathfinding Using Hierarchical Pathfinding Theta-Star (HPT*) Algorithm - Irfan Darwin; Suryadiputra Liawatimena (Doctorate Program of Engineering Science, Faculty of Engineering, Udayana University, 2021)
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.