The Statistical Inference Method in Heuristic Search Techniques
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, ) ,
- Pearl, J., "Heuristic Search Theory : Survey of Recent Results ," Proceedings of 7-th IJCAI, 1981, pp . 554-562 . IJCAI
- Pearl , J., "Probabili tic Analysis of the comple- xity of A* ," A.I., Vol, 15, No, 3, 1980, PP • 241- 254 .
- Pearl , J, , "Asymptotic Properties of Minimax Tree and Game-searching Procedures," A.I., Vol,14, No , 2 , 1980 , pp.113-138.
- Nilsson, N. J,, Principles of artificial Intel- ligence, Palo Alto, CA : Tioga Publishing Compary , 1980.
- Baudet , G, M,, "On the Branching Factor of the Alpha-Beta Pruning Algorithm," A.I., Vol. 10, 1978 , pp.173-199.
- Knuth, D. E, and R. W, Moore , "An Analysis of Alpha-Beta Ptunine;." A.I., Vol. 6, 1975, PP • 293- 326 .
- 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.
- Zacks, S,, The Theory of Statistic Inference, John Wiley & Sons, Inc,, New York, 1971.
- Degoot , M. H., Probability and Statistics , Menlo Park, California, 1975,
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. INTRODUCTION
The heuristic search theory has been investigat ed by many researchers (1)-(9). All results obtain ed can't completely avoid . the exponential explosion of searching complexity. We improve it by applying statistic inference method (s, i. m.) to heuristic search. The results we obtain are that the mean complexity of SA* is CN 2 and the maximal storage space is CN.
2. ALGORITHM SA* IN TREE G
2 .1. Statistic a(n)
For simplicity, we assume the following search space: A .uniform m-ary tree G has an initial node S,(root) and a unique goal node SHat depth N. Let l=(So oSI o··tSH) be the ShOrtest-path frOm So tO SHo The subtrees having foo1 Sc ar~ called Ti-type subtrees. They are T,,T,, ··· ,T,, i=0,1,... Assume that T is an T;-subtree, If n is a node cf T, the generation(depth) of the node is n, and T doesn't contain 1. We have
f ,f ol ' ' ' cnl =- n-t,~-t +It-t -=-Nt2.Cn-t ) .
(We use the same symbols as thoes used in most books,e.g, (4)).
h(n) is a heuristic estimate of h*(n), so a(n) is an estimate of a*(n). While n tl, f*(n)=N, Zhang , Bo Dept . of Computer ~ngineering & Science Tsinghua University Bei j ing , Chir.a
a*(n)= f*c~>;N =1- f. Given i, We have a*(n)=l,· In a word, for any node the statistic a( n) can~-be computed from h(n). (If N i s ur.known, we may replace a(n) with some other statistic , For example , Jet t he number of all nodes being expanded be k( n), the number of all nodes beinp; expanded in T:-subtree be k~(n). We redace a(n) with b( n)= ...&...!..!!.1. as the statistic of T~-~ubtree,a.nd so on.) i<-e>tJ
Hypothesis I: Assume(a(n)\is an independent and identically distribution random variable . The mean of a( n) ir. the solution path 1 is .Po · 'fhe mean of a(n) off 1 is .A1 · .),1 1 >.).I., Under this hypothesis, when h(n) of each node is computed using A*, an a(n) is obtained, This {a(n) l forms a random sample, using testing statistical hypo theses(t.s,h,)l10)(11) , we exercise the statisti cal inference method.(s.i,m.) over it, Under a given significance level of the test, whether a subtree contain 1 is decided . If not, the subtree is pruned off. otherwise, algorithm A* and t.s,h. will be continued until the goal node is found,
The sampling of statistics in subtree T
LetT be a subtree, a 1 be the statistic of the root in T. Ass~me T is expanded by A*, and in some stage the corresponding statistics { a 1 , a 2 ,,., ,a(l have been obtained. We say "observing T is conti nued." It means expanding node pat which f(n) is minimal among all nodes not being expanded in T. (If there exist several such nodes, choose one which has maximal generation, If there still exist several nodes, choose any one at your op tion,) Thus we obtain m successors of p and corresponding a ( n)'s, Let at·l be the minimal value among these a(n)'s, then a(, 1is r eferred to a new observed value during the observation of T, we say "exercising some t.s.h, overT." It means exercis ing some t.s.h. over the statistics {a~l corres ponding to T.
2 . 2 . Al gorithm SA*
Given a testing hypotheses method S. Applying this method to A*, We obtain algorithm SA*:
Step 1: From initial states., m T0 -type sub trees are expanded, A set U1 is composed by these subtrees, Let t+-1. go to Step 2.
Step 2: Exercise the statistical inference over Ut·
(1) If Ut is an empty set , stop.
- If there is only one T{-type subtree Tin
Ut, expand the (i+1)- th generation nodes in T and obtaj n m T,,1- type subtrees . Merging the T;.,- type subtrees i'lto Un obtain Ut·to Let t --- t +1 , go to Step 2.
(3) If there is more than one subtree , expand node p at which f(n) is the minimum among all nodes not being expanded in a l l subtrees( If there still exist several nodes , choose any one . )
(3 . 1) If there exists a p;oal node amonl'; the successors of p , stop.
(3 . 2) Assume pis , i n subtree T', observ1ng T' and exerci sing the t , s , h. S over it are continued , If the hypothesis is rejected , let Ut,,._Ut-T', t + t +1, f':O to Step 2. otherwise , let Ut-1- ut -T'+T" ( T" is a subtree formed by adding the successors of p to T' ) , t +- t +1 , go to Step 2 .
Proposition 1: SA* is superior to A* . Assume A* and SA* both are directed by the same h(n) . Fi ndin~ an optimal solution path by SA* , every node expanded by SA* i s also expanded by A* ,
Proof : SA* is a n algorithm formed by only adding an additional pruning subtrees stage to A*, so the nodes expanded by SA* are not more than the nodes expanded by A* ,
It must be pointed out that the results obtain ed by SA* have some error probabilities , because of the application of s . i .m, · We 'll discuss later on ,
SPRT testing hypotheses method in algorithm SA* ( denited by SPA*)
SPRT (Sequential Probability Rat i o Test) was decribed in many books (e .g , t1 0J ) . We use SPRT as testing hypothese here . Let fa(n) } be / Xn} , ha ine: anN( .,«, ,.2) distributi.on . Gi ven a significance level ( 0( , ;3) and two simple hypotheses H. : fi =,4J ·· H 1 : A=fl 1 , ,/l/1 i fl,.
Where f( x ; M )= dJr .R.:xp {- ± ( x -_)A ), } ·
Let l: 4 ( t o. ; A , J _ .. ,ddL:L~{q~ t 1.. AJ; -...<It == 0 9 f (X . A ) - If' :z. lf'i .5 ~ .!.1 ~ . -~ !1. X · ..... ..11. ...<~:-&t n - "'T' t - <r f ~ ' 2. ~ >- A ~ ¥ , B tE ~ , a g f og A , b ~ foJ 13.
The stopping rules of SPRT are as follows :
If n o a
_,u, +,;()o
' Hypothesis H 0 is rejected ,
L: xi ~ A,-:;a. + n ,;. a-
Hypothesis H0 is accepted .
Because parameters If , J), , )1 0 are unknown, we ~sually use Sn : ~ f ( x..: _ ~ ll to estimate d" , where x=*~ Xi· Let a * be the minimum va]ue of a( n ) 's am ong ~11 k-th generation nodes which a(n) 's have been computed in G. Let the mean of { a 11 } be the estimate of )1 0 , and the mean of al l a( n) 's , which have been computed in G, be A 1·
Otherwise , observing Xn~J is continued .
If in SA* as testing hypotheses S, SPRT is exercised over m T< - type subtrees , using a level ( ,,Ji+1 ~) ·-o 1 d f' th' SA* as ""' , m- l , 1-, , ·· ,, we e 1ne 15 SPA* under level ( Ol, ~) , denoted by SPA* for s hort ,
2 . 3 . The Mean Complexit y of SPA*
From t he approximation of t he mean of ping variable (sampl e size) N i n SPRT (10 ) , stop ifN

~ The mean complexity (asymptotic) for deciding m Ti- type subtrees in SPA* is
2 6').
"'mbl log rj, l·(i +1 ) , where b = <AJ, -,),1 0 )' Proof : From SPRT we know tha.t dec;iding m T~ - type subtrees under level ( O(i~l, ';:.'_+,' ) , , t he mean complexity (asymptotic) is ""mbllog 0(. " 1 mb / lop; ()l..l·(i+1 ) ,
Theorem 1: Let lX.=min( 1 ~6z. , ~. ) . Using SPA* , under level ( IX.~) t he mean compl exity of finding an optimal sol ution path in G is "'-CN ~ , where C= mbl £oorJ.l · The err or pr obabilities of Type I P 1 ~ ~o. The error probabilities of Type JL pl ~(.:l ··
Proof : Deciding m Ti-type subtrees there are m- 1 subtrees not containing 1 but one . Due to the probability r,= *~", ' , (m-1) Dfn.:_.,' = "' '+' s~btrees not c9ntaining 1 are left . Because of P 1 = ()1.. " + 1 , ( 1-()1..~,. 1 ) subtrees containing 1 are left . Totally oci· 1 +(1- 0(..:" 1 )=1 subtree is left. The mean complexity for deciding one T{- type subtree is "- b l log ot l (i+1 ) (lemma) , Thus usi ng SPA* , the mean complexity of finding an optimal path is
""''¥ 1 m h I R..oJ Ol I ( it I ) = m b I .R..oJ rj, ) N(~ + 1 ) "' rnb I !o1 ci I "'). = c N".
The pr obability P 1 (P2. ) is as follows : Deciding m T0 - type subtrees P, = <X. · . In general Totally
decidingmT.;- type subtrees .P 1 ~tf..t-. l "' {, !11·1 < / - 0(.''1 Ol .
Analogously, P2 ~ fSo ·
Corollary: Using SPA* , under l evel ( ~ , ~ ) ) the maximal storage- space ~ mb llog cL I N=C1N.
Proof : Deciding m Ti-type subtrees , al l in formation about these subtr ees is s toraged at most , That is , "- mb llog r/... J N.
Note : Due to the process of pr uning subtrees , the stor age- space requir ed by SPA* is not more than A* .
2 .4 . Compar son to r ecent r esul ts
Pearl (2 ) defined a n es timate h(n) of ~(n) - type error and pr oved that when !F. ( n )=n t he complexity of A* is O(e 111 ) . We 'l l pr ove t hat i n t he same case the complexity of SPA* i s CN 2 ·
Theor em 2 : Assume h( n) i s an admissibl e esti mate , having ~(n)=n type er ror , P( l h*~h l <h*)>O . Then the mean complexi t y of SPA* i s CN ·
Proof: If ,;{)1 >~. is proved (the proof is omitted) , according to Theorem 1, we obtatn Theorem 2 .
Coroll ary: Ass ume h(n) i s an admissible es ti mate having ~( n) - type error , lim~ ?1-"" ~ 1 P( I h*-h I < ~( h*)) > 0, t hen the mean complexity of SPA* directed by h(n) is CNL, Notet In SPA*,~ ,)A,and;U.are unknown, They are replaced with their estimators. This will cause some error. For elimilating this disadvan tage, we may use t-test as testing hypotheses S in SA* .The searching complexity is a little more than SPA* . But we may prove that Theorem 1 also holds and the mean complexity is 1'-CN 2 , Theorem 2 also holds for {x"l having some sorts of distribution except N(~, ~·).
3, ALGORITHM SA* IN GENERAL GRAPH
Assume h(n) is an admissible estimate , then using b(n)= ~~~l (see 2.1) as the statistic of
Tf-subtree (subgraph), and so on, we may obtain algorithm SA* for a general ~raph .
4.ALCORITHM SA* IN GAME TREE
We'll apply SA* to game-searching . A stand ard 2n-level game tree of degree m is indicated by (n ,m,F)-tree where F(v) is a distribution function of terminal value (the symbols used are the same as in (J) ), In (1),(5),(6),(7), it has been proved that any known algorithm which evalu ates a (n ,m,F )-tree must evaluate at least mn terminal positions , We'll apply SA* to a (N,m,F) tree, and conclude that the mean complexity of SA* in game-searching is C1Nl,
The Sampling of Statistics in Game-Tree
In a game-tree , the value f*(n) of each node is obtained by searching backward from terminal values (for example , from the standpoint of Max) , Assume that for each node an estimate f(n) of f*(n) can be computed, Let statistic a(n) be
[ ax ( f( n i ) , · i =1 , 2, ·· , , m) Q(np ni is th~_successor of n, n is an even node min (f(nd , ~-1,2, ... ,m) ni is the successor of n, n is an o.dd node,
Let T be an T<-type subtree, The sampling its statistics is as follows: of
Let a.=f(s.), s . is the root ofT.
Expanding S0 ,Assume a 1 =f(S 1 )=max(f(n,)), ni, S 1
are the successors of S0 , Expanding S1 , Assume a,=f(S2 )=min(f(n,)), ni, Sz are the successors of S1 ·
In general, we obtain [a., a 1 , ··· , ai}. k=2j, let . If
a t+t =f(S >t-tl )=max (f(ni)), ni, S*+l successors of S*, l.si~m are
If k=2j+1, let a.t+t=f(S*.-tl )=min. (f(nc:)), n,:, S~-tl are successors of S~, l~t..$:ort
Assume the statistic {a(n)l satisfies the Hypothesis I, Similar to tree search we apply SA* to game-searching, and the following theorem holds,
Theorem 1't In an (n ,m,F)-game tree, the mean complexity of SPA* under the level (ex. , -#:,- ) is ""'CN 1 C= mbl.laj~l .. l/.=2mbllogcx.l t ' I 2 · The P1 (P2 ) is d 0 ( (.3. ). where ()(.=min(~ , ~J o Corollarv: The maximal storage-space of SPA* in game-tree searching is C2 N, Cfmbllog ex. I · Note: The storage-space required by SSS* is at least mn ( 7]. (The proof of Theorem 1' is omitted),
@inproceedings{ijcai1983p182,
title = {The Statistical Inference Method in Heuristic Search Techniques},
author = {Zhang, Ling and Zhang, Bo},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {757--758},
year = {1983},
note = {Planning and Search},
url = {https://ijcai.org/proceedings/1983/182},
}
TY - CPAPER TI - The Statistical Inference Method in Heuristic Search Techniques AU - Zhang, Ling AU - Zhang, Bo T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 757 EP - 758 UR - https://ijcai.org/proceedings/1983/182 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: