Abstract
X. Sun, W. Yeoh and S. Koenig. Dynamic Fringe-Saving A*. In 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. Unfortunately, our experimental results show that the resulting Dynamic Fringe-Saving A* algorithm tends to be dominated by either repeated A* searches or D* Lite (a state-of-the-art incremental version of A*).
Errata: We updated the experimental results after we noticed a problem in the implementation of our experiments: We performed the experiments in gridworlds of size 1000 x 1000. After each move of the agent from its current cell to a neighbor, we intended to block a certain number of randomly chosen unblocked cells and unblock the same number of randomly chosen blocked cells. We had ported code to a different operating system and, in the process, changed the random number generator. The new random number generator used to determine these cells generated random numbers in the range from 0 to 32,767 only, which is too small to choose among all cells. Our experimental results after fixing this programming mistake show that our algorithm (Dynamic Fringe-Saving A*) is now completely dominated by either A* or D* Lite (depending on how many cells change their blockage status) for the experimental setup in the paper. Two papers were affected by this programming mistake but, fortunately, the experimental results in the other paper did not change dramatically.
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.