A Weighted Technique in Heuristic Search

Zhang, Bo

Dept. of Computer Science

Tsinghua University

Beijing, China

ABSTRACT

As shown in (1), we examine search as a statis­ tic sampling proces s. Based on some statistical inference method the probability that a subtree in search tree conteins the goal can be decided. Thus some weight is intentionaly added to the evaluation function of those nodes which are un­ likely in the solution path so that the search will concentrate on the most promising path. It results in a new weighted algorithm-WSA.

In a uniform m- ary tree, we show that a goal can be found by WSA in the polynomial time, although tßN computational complexity of A (or A*) may be O(e ) for searching the same space. Where N is the depth at which the goal i s loc ated .

INTRODUC TION

Weighted techniques in heuristic search have been investigated by several researchers (e.g., see (2]- (4)). Al though thoes methods made the search more efficiency, the improvement is rather limitted because weights are usually added to all nodes undicriminally, for example, in(2)the same weight ~ 0 is applied to each node.

The alternative weighted technique presented here is the following . According to decisions made by some statistic inference method during A (or A*) search a weight will only be added to the evaluation of some nodes which are unlikely in the solution path. It results in a new weighted technique that will provide better results .

A NEW WEIGHTED METHOD

As shown in (1), under certain conditions we examine search as a statistic sampling process so that statistic inference method can be used dur­ ing the search . Assurne the v/ald sequential probabilityradio test (SPRT) is used as a test­ ing hypotheses. In some searching stage, if the hypothesis that some subtree T contains solution path is rejected, from (1) i t' s known that subtree T contains the goal with lower probability.

Rather than pruning T (as in(1) ) a fixed weight w is added to the evaluation function of nodes in T, i.e., f 1 (n)=f(n)+w. If the hypothesis that the

subtree T' contains the goal is accepted, the same weight i ·s added to all nodes in the brother­ subtrees of T' which roots are the brothers of the root ofT'. If no decision can be made the search process is continued as in A search. Thus Zhang, Ling Dept . of Mathematics Anqing Teachers' College Anqing, Anhui, China the search will concentrate on the subtrees which contain the goal with higher probability due to the weighting. This new algorithm is called the weighted SA search--WSA.

THE COMPLEXITY OF WSA

Assurne the search space is a uniform m-ary tree, the SPRT is used as the testing hypotheses and the given significance level is ( ()(., ß) , d. + ß =b. The complexi ty of an algori thm is defined as the expected nurnber of nodes expanded by the algorithm when a goal is found. We have proved the following theo.rems ( the proof is presented in the Appendix).

Theorem 1: Assurne P(A)"'O(eCN), C>O a:1i Cis a known constant, N is the depth at whi ch the goal is located, P(A) is the complexity of algo­ rithm A when it searches the same space. Using

the weighted function f (n)=f{n)+w , where 1 1-b 1 0 ' w 0 = 2C ln -b- ( the optimal weight) the complexity of algorithm WSA is

Theorem 2: If P(A)"'O(Na), a-;>1, using the 2aJ-b weighted function f 1 (n)= ).. 0 f(n) where ).. 0 = b' then the complexity of WSA is

Obviously, the new weighted method can improve the computational complexity greatly.

Generally, P(A) is either ...... o(eCN) or-v(Na), and it's unknown. When an arbitrary weight w~w is used in WSA search, how about its complexi~y?

Theorem 3: If P{A)"'O(eCN), C >O and C is unknown, using the weighted function f 1 (n)=f(n)+

w, wi'w 0 , and ce level b = i a monotonously decreased significan­ ~ is used for testing T 1 .-subtrees, i "

then

Theorem 4: If P( A)"' 0( Na), a >1, using the same weighted function f 1 (n)=f(n)+w, the complexity of WSA search remains in the polynomial time.

ALGORITHM WSA

Given an evaluation function (statistic) f(n) and a testing hypotheses method, the WSA search procedure as follows:

(1) Create a list called OPEN, Expand initial node S , generatinJ its m successors, put them on oPEIV.

Create a list CLOSED , It's initially empty, Create a list R OOTS. Put m successors of S on it, The node in ROOTS is called a, 0

(2) LOOP: If OPEN is empty, exit with failure (It's impossible that OPEN is empty when there exists a goal in the search tree),

(3) Select the first node on OPEN, remove it from OPEN, and put it on CLOSED, Call this node n.

(4) If n is a goal, exit successfully with the solution obtained by tracing a path along the poin­ ters which are established in step 5.

(5) Expand node n, generating its m successors, Put them on OPEN.Establish apointer to n from these successors .

(6) If some subtree T(a) is accepted according to some testing hypothese, add a weight w to the statistics of all nodes in the brother-subtree of T(a), remove the root nodes of T(a) and its bro­ ther-subtrees from ROOTS and put their successors on ROOTS,

(7) Reorder the list OPEN according to statis­ tics, Go LOOP,

CONCLUSIONS

A new weighted technique is incorporated in A (or A*) search. While the algorithm A searches a space using evaluation function f(n), some weight w is added to f(n) (f 1 (n)=f(n)+w) of the nodes which are unlikely in the solution path according to decisions made by some statistic inference method. Thus the paths that contain the goal with higher probabilitywill be expanded more due to the weighting.

In a uniform m-ary tree, we show that a goal can be found by WSA in the polynomialc~ime, al­ though the complexity of A may be O(e ) for searching the same space,

Both algori thm A (3 J and SA are special cases of this more general algorithm WSA, Note that when w eO algori thm WSA is idential to A search. While w = + oo algori thm WSA degenerates into SA search.

APPENDIX

The proof of Theorem 1:

For simplicity, we assume the search space is a uniform 2-ary tree, m=2, in the following discussion. There is no loss of generality in

as suming that P(A)=ecN.

If a statistic decision is made in some search

staee,a weight w is added to evaluation of nodes of the rejected subtrees, A subtree is called a completely weighted if all its subtrees have been decided to be rejected or accepted. The subtree shown in Fig.1 is completely weighted (Where the rejected subtrees are marked with sign "X" ).

Obviously, a completely weighted subtree has more expanded nodes than the incompletely weighted one. Thus if an upper estimate .of the mean complexity of the completely weighted subtree is computed, it certainly is an upper estimate of the mean complexity in general cases.

We now discuss this upper estimate,

arcs marked by "X", node n is referred to as an

Let Pd be a set of nodes at depth d. Given n EPd. From initial node S to n there exists a uniqug path consisting of d arcs. Among these arcs if there are i(o~i~d) i-type node or i-node.

So Pd can be divided into the following sub­ sets:

1 0-node: there is only one, 1-node: Cd=d , ···· , i-node: c~····· d-node: c~~1.

In considering the complexity for finding a goal, we first ignore . the cost of the statistic inference. Assurne that the goal belongs in 0-node so that its eva1uation is f (n)=N, From algori­ thm A, it's known that everf node which f(n)< N must be expanded in the searching process.

If node n is an i-node, its evaluation func­ tion is f 1 (n)=f(n)+iw.All nodes which evaluation satisfy the following inequation will be expand­ ed.

Using evaluation function f(n) ~Re complexity of A search is known to be P(A)=e , thus the complexity correspondin~(g~.t~e evaluation func­ tion f 1 (n)=f(n)+iw is e lW. The mean comple­ xity of each i-node (the possibility that an

The mean complexity for finding a goal at depth N is at least N. Thus the mean complexity of each i-node is

When the goal is an 0-node, the upper estirnate of the mean complexity for computing all d-th depth nodes is the following: CN

On the other hand, if ol.+ J3 =b is a constant, from (1) for making the statistic inference of a node, the mean computational cost of SPRT is a constant Q. When the goal is an 0-node, account­ ing for this cost, the mean complexity is

Similarly, if the goal belongs in i-node, the mean complexity for computing all d-th nodes is

From algori thm SA (1) , theNE~:q fall s int"o s.n i-node with probability (1-b) b , if the given leve:::. is ( oc,ß), c/..+(3 =b. At depth N there are c 1 i-nodes, so the probability that the goal N belongs in 1-node is

Accounting for all possiblP cases of the goal node, the mean complexity for computing all d-th depth nodes is

-Cw Cw Let F(w)=(1 +e ).(1-b+be ) (1) F(w) a t tains i ts minimum for a value of w given by

Under tße optimal weight, the upper bound of the mean complexi ty of algori thm '!ISA is

Assurne 0 < C < ln2, we shall Show tha t there exists an b such that C < ln( 1 + 2 fb ( 1 _b ) ) ·

Let C=lnf<ln2, i.e., f<2.

0

"' 0

0

If 4h 2 :> 1 , gi ven any 0 < b < 1 , Form ( 3)

2

( 3) holds

If 4h -1 ~o, as long as o<. b 0 <. 2

Similarly, Theorem 2 can be proved.

The proof of Theorem 3:

We discuss P(A)-'VO(eCN) and C is unknown. So the optimal weight w 0 is also unknown.

,

° 1-~

holds.

Form In order to obtain P(WSA)"-O( N), value b rnust be so small that

But C is unknown, it is unable to select a fixed b so that Form (6) is satisfied. If we use a rnonotonously deceased value bi for testing Tisubtrees as we did in (1)[6). Due to the gradual decrement of b = d. . + (3 i, in sorne search s tage,

Form (6) rnust ~old!

making the statistic inference(SPRT) once, the mean complexity Q is O(ln N) at most. Frorn (5) obtain P(WSA)"-' O(N.lnN).

The proof of Theorem 4 is omitted.