Abstract

Abstract: In this paper, we develop Fringe-Saving A* (FSA*), an incremental version of A* that repeatedly finds shortest paths in a known gridworld from a given start cell to a given goal cell while the traversability costs of cells increase or decrease. The first search of FSA* is the same as that of A*. However, FSA* is able to find shortest paths during the subsequent searches faster than A* because it reuses the beginning of the immediately preceeding A* search tree that is identical to the current A* search tree. FSA* does this by restoring the content of the OPEN list of A* at the point in time when an A* search for the current search problem could deviate from the A* search for the immediately preceeding search problem. We present first experimental results that demonstrate that FSA* can have a runtime advantage over A* and Lifelong Planning A* (LPA*), an alternative incremental version of A*.

Download the paper in pdf.

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.