---
title: "The Fringe-Saving A* Search Algorithm - A Feasibility Study"
authors:
  - "Xiaoxun Sun"
  - "Sven Koenig"
doi: ""
url: "https://ijcai.org/proceedings/2007/385"
pdf: "https://ijcai.org/proceedings/2007/0385.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "2391-2396"
track: ""
keywords:
---

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

Xiaoxun Sun, Sven Koenig

*Proceedings of the Twentieth International Joint Conference on Artificial Intelligence*, pages 2391-2396.

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