The Fringe-Saving A* Search Algorithm — A Feasibility Study

Xiaoxun Sun, Sven Koenig

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*.