A double-phase search algorithm for sub-optimal path finding
Zhipeng Gao, Junmeng Huang, Chen Zhao · 2021
Traditional optimal path finding algorithms are usually too complex for real world problems, motivating the need to find path with sub-optimality. Typically suboptimal algorithms use a single admissible heuristic value to decide how to find a path and bound the cost. Algorithms like Weighted A*(WA*), Convex upward parabola(XUP) and Convex downward parabola(XDP) have overcome the node re-expansion problem during search. However, this re-incur a balance between the quality of path and the speed of search. In this paper, we research the process of extending and put forward an algorithm that would more efficiently operate the search while on the same time not lower the quality of path. This algorithm includes two phase of search, the first phase is to fasten the process of path finding, while the second phase is to guarantee the quality of path. In most maps we choose from Dragon Age Origins(DAO), our algorithm performs better than WA*.