Dynamic fringe-saving A*

ABSTRACT

Fringe-Saving A* is an incremental version of A* that repeatedly finds shortest paths from a fixed start cell to a fixed goal cell in a known gridworld in case the traversability of cells changes over time. It restores the content of the OPEN and CLOSED lists of A* at the point in time when an A* search for the current search problem could deviate from the A* search for the previous search problem. Thus, Fringe-Saving A* reuses the beginning of the previous A* search that is identical to the current A* search. In this paper, we generalize the correctness proof of Fringe-Saving A* to cover the case where the goal cell changes over time in addition to the traversability of cells. We then apply Fringe-Saving A* to the problem of moving an agent along a shortest path from its current cell to a fixed destination cell in a known gridworld, where the shortest path is replanned whenever the traversability of cells changes. Our experimental results show that the resulting Dynamic Fringe-Saving A* algorithm can outperform both repeated A* searches and D* Lite (a state-of-the-art incremental version of A*) in highly dynamic gridworlds, with runtime savings of up to a factor of about 2.5.

REFERENCES

• 1: R. C. Holte , T. Mkadmi , R. M. Zimmer , A. J. MacDonald, Speeding up problem solving by abstraction: a graph oriented approach, Artificial Intelligence, v.85 n.1-2, p.321-361, Aug. 1996 [doi>10.1016/0004-3702(95)00111-5]
• 2: S. Koenig and M. Likhachev. Fast replanning for navigation in unknown terrain. Transaction on Robotics, 21(3):354--363, 2005.
• 3: Sven Koenig , Maxim Likhachev , David Furcy, Lifelong planning A*, Artificial Intelligence, v.155 n.1-2, p.93-146, May 2004 [doi>10.1016/j.artint.2003.12.001]
• 4: Sven Koenig , Maxim Likhachev , Yaxin Liu , David Furcy, Incremental heuristic search in AI, AI Magazine, v.25 n.2, p.99-112, Summer 2004
• 5: Sven Koenig , Craig Tovey , Yuri Smirnov, Performance bounds for planning in unknown terrain, Artificial Intelligence, v.147 n.1-2, p.253-279, July 2003 [doi>10.1016/S0004-3702(03)00062-6]
• 6: Judea Pearl, Heuristics: intelligent search strategies for computer problem solving, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 7: X. Sun and S. Koenig. The Fringe-Saving A* search algorithm - a feasibility study. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 2391--2397, 2007.
• 8: Xiaoxun Sun , Sven Koenig , William Yeoh, Generalized Adaptive A*, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Experimentation, Theory

Keywords:
A*, D* lite, fringe-saving A*, incremental heuristic search, path planning