The fringe-saving A* search algorithm: a feasibility study
Xiaoxun Sun, Sven Koenig · 2007
In this paper, we develop Fringe-Saving A* (FSA*), an incremental version of A * that repeat-edly 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 dur-ing the subsequent searches faster than A * because it reuses the beginning of the immediately preceed-ing 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 de-viate from the A * search for the immediately pre-ceeding search problem. We present first experi-mental results that demonstrate that FSA * can have a runtime advantage over A * and Lifelong Planning A * (LPA*), an alternative incremental version of A*. 1