Proceedings

The Statistical Inference Method in Heuristic Search Techniques

Download BibTeX Cite

Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Planning and Search. Pages 757-758.

© 1983 International Joint Conferences on Artificial Intelligence

Abstract

In this paper we present a new heuristic searching algorithm by introducing statistical inference method on the basis of algorithm A*, It's called al g orithm SA*, The followin g results have been proved. (1) Al gorithm SA* is super .Lor to al g orith m A*. ( 2 ) The mean complexity of SA* is CN 2 , but in some case A* exhibits exponential complexity (e N) , (J) In a (N ,d,F ) -ga me tree , the mean complexity o f S A* is CN 1 , b ut t~e complexity of other known gamesearching algori thm (-~, SSS* etc.) is at least d>l. (4)The maximal storage-space required by SA* is c,N. Thishows that under a given significance l evel S A* is superior to other known algorithm (e . g , A*, B* , ct..fJ , SS S* etc, ) ,

  1. Pearl, J., "Heuristic Search Theory : Survey of Recent Results ," Proceedings of 7-th IJCAI, 1981, pp . 554-562 . IJCAI
  2. Pearl , J., "Probabili tic Analysis of the comple- xity of A* ," A.I., Vol, 15, No, 3, 1980, PP • 241- 254 .
  3. Pearl , J, , "Asymptotic Properties of Minimax Tree and Game-searching Procedures," A.I., Vol,14, No , 2 , 1980 , pp.113-138.
  4. Nilsson, N. J,, Principles of artificial Intel- ligence, Palo Alto, CA : Tioga Publishing Compary , 1980.
  5. Baudet , G, M,, "On the Branching Factor of the Alpha-Beta Pruning Algorithm," A.I., Vol. 10, 1978 , pp.173-199.
  6. Knuth, D. E, and R. W, Moore , "An Analysis of Alpha-Beta Ptunine;." A.I., Vol. 6, 1975, PP • 293- 326 .
  7. Stockman, G. C., "Is a M inimax Algorithm Beter Than Alpha-Beta? " A.I., Vol. 12, 1979, pp .179 -1 96 . ( l'l ) Kanal, L, and Kumar V. , "Bra nch & Bound Formu- lation for Sequential and Parallel Game Tree Sear- chi.ng: Preliminary Results ," Proceedings of 7-th IJCAI, 1981, pp .569-571, ( 9 J Ber 1 i ner, H, , "The B* Tree Search Algorithm : A Best-first Proof Procedure," Readin!'; in Artifi- cial Intelligence, edited by B. L. Webber , 1981, pp.79-87.
  8. Zacks, S,, The Theory of Statistic Inference, John Wiley & Sons, Inc,, New York, 1971.
  9. Degoot , M. H., Probability and Statistics , Menlo Park, California, 1975,

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

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