Anytime rectangle expansion A∗ algorithm for time-limited pathfinding

Anytime algorithms are well suited for time-limited pathfinding problems, which find a feasible sub-optimal solution quickly and then continually work on improving it until time runs out. In this paper, a new anytime algorithm is introduced, called Anytime Rectangle Expansion A∗ (AREA∗), which is the anytime variant of basic Rectangle Expansion A∗ (REA∗). AREA∗ runs an accelerated sub-optimal search and then an incomplete REA∗ will repair the sub-optimality. AREA∗ can not only return the first feasible solution much faster than existing anytime algorithms but also converge to the optimal solution in almost the same speed with REA∗, which is an order of magnitude and more faster than A∗. AREA∗ also provides narrower and more accurate sub-optimality bounds of its solutions. Experimental results for typical benchmark problem sets show that, compared with the existing anytime techniques and the basic REA∗, the new algorithm shows a significant improvement in performance for time-limited pathfinding problems.