Proceedings

Heuristic Search Theory: Survey of Recent Results

Download BibTeX Cite

Proceedings of the Seventh International Joint Conference on Artificial Intelligence. Search. Pages 554-561.

© 1981 International Joint Conferences on Artificial Intelligence

Abstract

This paper summarizes recent analytical investigations of the mathematical properties of heuristics and their influence on the performance of common search techniques. The results are reported without proofs, together with discussions of motivations and interpretations. Highlights include the following: relations between the precision of the heuristic estimates and the average complexity of the search, comparisons of the average complexities of A* and BACKTRACKING, procedures for comparing and combining non-admissible heuristic functions, the influence of the weight ul [in f = (1-w)g + wh] on the complexity of A*, determination of the branching factors of alpha-beta and SSS*, and the effects of successor ordering on the complexity of alpha-beta and of search depth on the quality of decisions.

  1. Hart, P., N. Nilsson, and B. Raphael. "A For- mal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Trans. on Systems Science and Cybernetics, Vol. SSC-4, No. 2, July 1968, pp . 100-107.
  2. Pohl, I. "First Results on the Effect of Error in Heuristic Search." In B. Meltzer and D. Michie (Eds.), Machine Intelligence 5, Edin- burgh: Edinburgh University Press, 1970.
  3. Munyer, J. "Some Results on the Complexity of Heuristic Search in Graphs." Technical Report HP-76-2, Information Sciences Department, University of California, Santa Cruz, Septem- ber 1976.
  4. Vanderbrug, G. "Problem Representation and Formal Properties of Heuristic Search." Infor- mation Sciences, Vol. ll, No. 4, 1976.
  5. Pohl, I. "Practical and Theoretical Consider- ations in Heuristic Search Al9orithms." In E. Elcock and D. Michie (Eds.), Machine Intel- ligence 8, Chichester, England: Ellis Horwood Ltd . , 1977.
  6. Gaschnig, J. "Performance Measurement and Analysis of Certain Search Algorithms." Ph.D. Dissertation, Department of Computer Science, Carnegie-Mellon University, 1979.
  7. Gelperin, D. "On the Optimality of A*." Arti- ficial Intelligence, Vol. 8, No.1, 1977,-- pp. 69-76.
  8. Huyn, N., R. Dechter, and J. Pearl. "Prob- abilistic Analysis of the Complexity of A*." Artificial Intelligence, Vol. 15, No. 3, 1980, pp. 241-254.
  9. Pearl, J. "The Utility of Precision in Search Heuristics." UCLA-ENG-CSL-8065, Cognitive Systems Laboratory, University of California, Los Angeles, October 1980.
  10. Nilsson, N. Principles of Artificial Intelli- gence. Palo Alto, CA: Tioga Publishing Com- pany, 1980.
  11. Pearl, J. "The Complexity of Non-Admissible Search Heuristics." In preparation.
  12. Pohl, I . "Heuristic Search Viewed as Path 562
  13. Finding in a Graph." Artificial Intelligence, Vo 1 . 1 , 1970, pp. 193-204.
  14. Pearl, J. "Asymptotic Properties of Minimax Trees and Game-Searching Procedures." Artifi- c i a 1 Intelligence, Vo 1 . 14, No. 2, 1980-,-- pp. ll3-138.
  15. Slagle, J. R., and J. K. Dixon. "Experiments with Some Programs that Search Game Trees . " Journal of the ACM, Vol. 2, 1969, pp. 189-207.
  16. Fuller, S. H., J. G. Gaschnig, and J. J. Gillogly. "An Analysis of the Alpha-Beta Pruning Algorithm." Department of Computer Science Report, Carnegie-Mellon University, 1973.
  17. Knuth, D. E., and R. N. Moore. "An Analysis of Alpha-Beta Pruning." Artificial Intelli- gence, Vol. 6, 1975, pp. 293-326.
  18. Baudet, G. M. "On the Branching Factor of the Alpha-Beta Pruning Algorithm." Artificial Intelligence, Vol. 10, 1978, pp. 173-199.
  19. Pearl, J. "The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm." UCLA-ENG-CSL-8019, Cognitive Systems Labora- tory, University of California, Los Angeles, April 1980. To be published in Communications of the ACM.
  20. Pearl, J. "A Space-Efficient On-Line Method of Comput1ng Quantile Estimates." UCLA-ENG- CSL-8018, Cognitive Systems Laboratory, Univer- sity of California, Los Angeles, December 1980. To be published in Journal of Algorithms .
  21. Stockman, G. "A Minimax Algorithm Better Than Alpha-Beta?" Artificial Intelligence, Vol. 12, 1979, pp. 179-196.
  22. Roizen, I., and J. Pearl. "A Minimax Algorithm Better Than Alpha-Beta?: Yes and No." In preparation.
  23. Tarsi, M. "Optimal Searching of Some Game Trees." UCLA-ENG-CSL-8108, Cognitive Systems Laboratory, University of California, Los Ange 1 es, 11ay 1981 .
  24. Nau, D. S. "Pathology on Game Trees: A Sum- mary of Results . " Proceedings of the first National Conference on Artificial Intelligence, August 1980, pp. 102-104.
  25. Nau, D. S. "Pearl's Game is Pathological." Technical Report TR-999, Computer Science Department, University of Maryland, January 1981.

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

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