6.5.1. Graph Search
Algorithm SA can formally be extended to graph search.
First, graph-search needs to be transferred into some sort of tree search. There are several strategies dealing with the problem. For example, the procedure presented in
Nilsson (1980) is one of the strategies. It generates an explicit graph
G and a subset
T of graph
G called the search tree.
Second, since the branching factor is not a constant, and there is not only one solution path, the depth N at which the goal is located is generally unknown, etc. There is no threshold to be given in the graph-search algorithm. One of the formal algorithm may be given as follows.
Assume that
T is a search tree of
G, and has
m 0-subtrees
. The evaluation function
(or
) defined in
is chosen as the local statistic of each individual node in
T. The global statistic of each 0-subtree
is defined as follows:
Confidence probability γ(0<γ<1) and the width
of confidence intervals are given. Algorithm
SAA is performed on
. Then we have intervals
.
Assume that
is the left most one in real axis. If
does not intersect with
, then choose
, prune
, and the search continues. If
intersects with one of
, letting
and replacing the width
of confidence intervals by
, restart
SAA,…
Similarly, perform SAA on i-subtrees, i=1,2,…
When N is unknown and T is an infinite tree, SAA might not terminate. In order to overcome the difficulty, an upper bound B, the estimate of depth N, may be chosen. If the search reaches the bound, then a new round of SA search starts.
On the other hand, in
SAA, the chosen width of confidence intervals is
, where
, but
is unknown beforehand generally. Thus, we may choose a monotonically decreasing series
. At the beginning,
is chosen as the width of confidence intervals, if
(the left most one in
i-subtrees) intersects with one of
, then replace
by
and restart
ASM test. In order to prevent the search from not being terminated, a lower bound
may be chosen. When
if
still intersects with
, the current search stops and a new round of
SAA starts. Of course, at the beginning a proper
should be chosen as the width of confidence intervals and perform
SAA search, where
is chosen according to previous experience and domain knowledge.
6.5.2. AND/OR Graph Search
The statistical inference methods can be applied to AND/OR graph search as well. Now, we take the combination of
ASM test and
GBF search (
Pearl, 1984a, 1984b, 2000) as an example to show the
SA search in AND/OR graphs.
G is an AND/OR graph and
is a sub-graph generated from
G when search reaches a certain stage.
is a sub-graph of
and satisfies (1)
contains starting node
, (2) if an expanded
AND node
p is in
, then all sub-nodes of
p are in
, (3) if an expanded
OR node
p is in
, then just one of its sub-nodes is in
, (4) there is no ‘
UNSOLVABLE’ node in
, (5)
n is a node in
. In this case,
is called a solution base of
G containing node
n.
In
GBF search, a graph evaluation function
is used to judge the most promising solution base. Then the graph (base) is expanded according to node evaluation function
.
Assume that
is a solution base of
G containing
n.
is a sub-graph of
G rooted at
n.
is an expanded part of
and has
k nodes. For
, let
be a graph evaluation function of a solution base containing node
q (
Fig. 6.9). Thus,
reflects some property of a set of solution graphs that potentially generated from
.
Figure 6.9 AND/OR Graph Search , where
F is a combination function of
. Assume that
is a unique optimal solution graph of
G. For any solution base
containing
n, when expanding
rooted at
n in order to search
, the observation
from sub-graph
of
reflects the possibility of seeking out
. Thus, observation
can be used as the statistic of
ASM test for discriminating the most promising solution base. Therefore, we have a corresponding statistic
AND/
OR graph search algorithm-
SGBF.Assume that
G is a
-game tree and has a unique optimal solution. Statistic
satisfies a hypothesis similar to Hypothesis I. Using
ASM as hypothesis testing method
S, in the
2n-th level let the confidence probability be
, the width of confidence intervals be
, where
is a constant, and the threshold be
, where
c is a constant and independent of
n. If the complexity of
SGBF is defined as the average number of frontier nodes tested by the algorithm (
Pearl, 1984a, 1984b), then we have the following theorem.
Theorem 6.14
When
SGBF searches a
- double game tree, it can find the goal with probability one and its upper bound of complexity is
.
Theorem 6.15
When
SGBF searches a
- double game tree, if there is a
MAX win strategy by letting the threshold be
,
c is a constant, in the
2n-th level, then
MAX will win with probability
, and its upper bound of complexity is
.