Proceedings

AWA* - A Window Constrained Anytime Heuristic Search Algorithm

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2250-2254.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

This work presents an iterative anytime heuristic search algorithm called Anytime Window A* (AWA*) where node expansion is localized within a sliding window comprising of levels of the search tree/graph. The search starts in depth-first mode and gradually proceeds towards A* by incrementing the window size. An analysis on a uniform tree model provides some very useful properties of this algorithm.A modification of AWA* is presented to guarantee bounded optimal solutions at each iteration. Experimental results on the 0/1 Knapsack problem and TSP demonstrate the efficacy of the proposed techniques over some existing anytime search methods.

  1. [Dean and Boddy, 1988] T. Dean and M. Boddy. An analysis of time-dependent planning. In Proceedings of 6th National Confer- ence on Artificial Intelligence (AAAI 88), pages 49-54, St.
  2. Paul, MN, 1988. AAAI Press.
  3. [Furcy, 2006] D. Furcy. Itsa*: Iterative tunneling search with a*. In Proceedings of AAAI Workshop on Heuristic Search, Memory- Based Heuristics and Their Applications, pages 21-26, 2006.
  4. [Hansen et al., 1997] E. A. Hansen, S. Zilberstein, and V. A. Danilchenko. Anytime heuristic search: First results. Techni- cal Report 50, Univ. of Massachusetts, 1997.
  5. [Kitamura et al., 1998] Y. Kitamura, M. Yokoo, T. Miyaji, and S. Tatsumi. Multi-state commitment search. In Proceedings of 10th IEEE International Conference on Tools with Artificial In- telligence, pages 431-439, 1998.
  6. [Kumar et al., 1995] A. Kumar, A. Kumar, and M. Balakrishnan. Heuristic search based approach to scheduling, allocation and binding in data path synthesis. In Proceedings of 8th Interna- tional Conference on VLSI Design, pages 75-80, 1995.
  7. [Likhachev et al., 2004] M. Likhachev, G. J. Gordon, and S. Thrun. Ara*: Anytime A* with provable bounds on sub-optimality. In Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.
  8. [Pearl, 1984] J. Pearl. Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley Longman Publish- ing Co., Inc., Boston, MA, USA, 1984.
  9. [Pohl, 1970] I. Pohl. Heuristic search viewed as path finding in a graph. Artif. Intell., 1(3):193-204, 1970.
  10. [Sarkar et al., 1991] U. K. Sarkar, P. P. Chakrabarti, S. Ghose, and S. C. De Sarkar. Multiple stack branch and bound. Inf. Process. Lett., 37(1):43-48, 1991.
  11. [Zhang, 1998] W. Zhang. Complete anytime beam search. In Pro- ceedings of 14th National Conference of Artificial Intelligence AAAI'98, pages 425-430. AAAI Press, 1998.
  12. [Zhou and Hansen, 2002] R. Zhou and E. A. Hansen. Multiple se- quence alignment using anytime a*. In Proceedings of 18th Na- tional Conference on Artificial Intelligence AAAI'2002, pages 975-976, 2002.
  13. [Zhou and Hansen, 2005] R. Zhou and E. A. Hansen. Beam-stack search: Integrating backtracking with beam search. In Proceed- ings of the 15th International Conference on Automated Planning and Scheduling (ICAPS-05), pages 90-98, Monterey, CA, 2005.

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

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