SCIENCE@home

Dynamic fringe-saving A*

Xiaoxun Sun,W. Yeoh,Sven Koenig

Published 2009 in Adaptive Agents and Multi-Agent Systems

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-10 of 10 references · Page 1 of 1

CITED BY

Showing 1-22 of 22 citing papers · Page 1 of 1