Proceedings

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

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2391-2396.

© 2007 International Joint Conferences on Artificial Intelligence

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

  1. [Corman et al., 1990] T. Corman, C. Leiserson, and R. Rivest. In- troduction to Algorithms. MIT Press, second edition, 1990.
  2. [Hart et al., 1968] P. Hart, N. Nilsson, and B. Raphael. A formal ba- sis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 2:100-107, 1968.
  3. [Koenig and Likhachev, 2005] S. Koenig and M. Likhachev. Fast replanning for navigation in unknown terrain. Transaction on Robotics, 21(3):354-363, 2005.
  4. [Koenig and Likhachev, 2006] S. Koenig and M. Likhachev. A new principle for incremental heuristic search: Theoretical results. In Proceedings of the International Conference on Autonomous Planning and Scheduling, pages 402-405, 2006.
  5. [Koenig et al., 2004a] S. Koenig, M. Likhachev, and D. Furcy. Lifelong planning A*. Artificial Intelligence Journal, 155(1- 2):93-146, 2004.
  6. [Koenig et al., 2004b] S. Koenig, M. Likhachev, Y. Liu, and D. Furcy. Incremental heuristic search in artificial intelligence. Artificial Intelligence Magazine, 25(2):99-112, 2004.
  7. [Pearl, 1985] J. Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1985.
  8. [Stentz, 1995] A. Stentz. The focussed D* algorithm for real-time replanning. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1652-1659, 1995. IJCAI
  9. [Trovato and Dorst, 2002] K. Trovato and L. Dorst. Differential A*. IEEE Transactions on Knowledge and Data Engineering, 14:1218-1229, 2002.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards