An Zhang, Chong Li, and Wenhao Bi
Time-limited pathfinding, heuristic algorithms, grid maps, A algorithm, anytime algorithms
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.
Important Links:
Go Back
