Abstract
X. Sun, W. Yeoh and S. Koenig. Dynamic Fringe-Saving A*. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 891-898, 2009.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.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.