The statistical inference methods can also be applied to weighted heuristic search. Weighted techniques in heuristic search have been investigated by several researchers (
Nilson, 1980; Field et al., 1984). They introduced the concept of weighted components into evaluation function
. Thus, the relative weights of
g(
n) and
h(
n) in the evaluation function can be controlled by:
where
is a weight.
In statically weighted systems, a fixed weight is added to the evaluation functions of all nodes. For example, Pearl investigates a statically weighted system
and showed that the optimal weight is
(the definition of
and more details see Pearl (1984b)). But even the optimal weight is adopted; the exponential complexity still cannot be overcome.
For dynamic weighting, for example, the weight
may vary with the depth of a node in the search tree, for example,
, where
e is a constant and
N is the depth that the goal is located. But the dynamic weighting fails to differentiate the nodes: which are on the solution path (
), whereas the others (
) are not. Thus, neither static nor dynamic weighting can improve the search efficiency significantly.
As stated in Section
6.1.1, under certain conditions we regard heuristic search as a random sampling process. By using the statistic inference method, it can tell for sure whether a path looks more promising than others. This information can be used for guiding the weighting.
For example, the Wald sequential probability ratio test (
SPRT) is used as a testing hypothesis in
SA search. In some search stage if the hypothesis that some subtree
T in the search tree contains solution path is rejected, or simply, subtree
T is rejected, then the probability that the subtree contains the goal is low. Rather than pruning
T as in
SA, a fixed weight
is added to the evaluation function of the nodes in
T, i.e. the evaluation function is increased by
,
. If the hypothesis that the subtree
T′ contains the goal is accepted, the same weight is added to evaluation functions of all nodes in the brother-subtrees of
T′, whose roots are the brothers of the root of
T′. If no decision can be made by the statistic inference method, the searching process continues as in
SA search. We call this new algorithm as the weighted
SA search, or
WSA. It is likely that the search will focus on the most promising path due to the weighting. We will show that the search efficiency can be improved by the
WSA significantly.
For clarity and brevity, we assume that the search space is a uniform 2-ary tree,
, in the following discussion. The
SPRT (or
ASM) is used as a testing hypothesis and the given significance level is
, where
. The complexity of an algorithm is defined as the expected number of the nodes expanded by the algorithm when a goal is found.
Definition 6.9
A subtree is called a completely weighted, if all its subtrees have been judged to be rejected or accepted.
The subtree
shown in
Fig. 6.8 is completely weighted (where the rejected subtrees are marked with sign ‘
’ ). But subtree
is not completely weighted.
We imagine that if a subtree is not completely weighted, the testing hypothesis is continued until it becomes a completely weighted one. 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 obtained, it certainly is an upper estimate of the mean complexity in general.
Figure 6.8 A Completely Weighted and Incompletely Weighted Subtree We now discuss this upper estimate.
Let
T be a completely weighted 2-ary tree and
be a set of nodes at depth
d. For
, from initial node
to
n there exists a unique path consisting of
d arcs. Among these
d arcs if there are
i arcs marked by ‘
’, node
n is referred to as an
i-type node, or
i-node.
So
can be divided into the following subsets:
0-node: there is only one such node.
1-node: the number of such nodes is
i-node: the number of such nodes is
d-node: the number of such nodes is
In considering the complexity for finding a goal, we first ignore the cost of the statistic inference. Assume that the goal of the search tree belongs to 0-node so that its evaluation is
, where
N is the depth at which the goal is located. From algorithm
, it's known that every node which
must be expanded in the searching process.
If node
n is an
i-node, its evaluation function is
. All nodes whose evaluations satisfy the following inequality will be expanded.
From
, it’s known that the complexity corresponding to the evaluation function
is
. The mean complexity of each
i-node (the probability that an
i-node is expanded) is
On the other hand, 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 a 0-node, the upper bound of the mean complexity for computing all
d-th depth nodes is the following (ignoring the complexity for making statistic inference).
On the other hand, when
is a constant, from Section
6.2 it’s known that the mean computational cost of
SPRT is a constant
Q for making the statistic inference of a node. When the goal is an 0-node, accounting for this cost, the mean complexity for computing all
d-th depth nodes is
Similarly, if the goal belongs to
i-node, its evaluation is
. Then the computational complexity of each node in the search tree is increased by a factor of
. Thus when the goal is an
i-node, the mean complexity for computing all
d-th nodes is
From algorithm
SA, the probability that the goal falls into an
i-node is
if the given level is
,
. At depth
N, there are
i-nodes, so the probability that the goal belongs to
i-node is
Accounting for all possible cases of the goal node, the mean complexity for computing all
d-th depth nodes is
Let
. There is an optimal weight
such that
is minimal. The optimal weight
and
.
The upper bound of mean complexity of
WSA is
Letting
, we have
(6.23)
where,
is a constant.
Theorem 6.12
If
,
is a constant, letting the significance level for
i-subtrees be
, where
b is a constant, then
Alterable weighting: When the type of the order of
is unknown, we uniformly adopt weight function
. Next, we will show that when
,
, if the weight function
is used what will happen to the complexity of
WSA.
Since
the ‘additive’ weight
s can be regarded as ‘multiplicative’ weight
but
is no long a constant. So we call it the alterable weighting.
Assume that
. When a node is a 0-node,
. For any node
, it is assumed to be an
i-node. The evaluation function of
after weighting is
, where
are the weights along the path from starting node
to node
.
According to the heuristic search rules, when
, i.e.,
, node
will be expanded.
It’s known that the goal locates at the
N level, so the evaluation
may be adopted.
Thus, when s fixed,
satisfies
.
Since
, the mean complexity for testing each
i-tree is
When the goal is a
t-node,
. The mean complexity for testing each
i-node is
Similar to Theorem 6.10, we have
(6.26)
When
,
. Thus, when
is sufficiently small, the asymptotic estimation of the above formula can be represented as
Let
. When
is sufficiently small, from the above formula we have
. Substitute
into Formula
(6.26), we have
Then, we have the following theorem.