Depth-bounded Discrepancy Search

1 Introduction

On backtracking, depth-first search explores decisions made against the branching heuristic (or "discrepan­ cies"), starting with decisions made deep in the search tree. However, branching heuristics are more likely to be wrong at the top of the tree than at the bottom. We would like therefore to direct search to discrepancies against the heuristic high in the tree - precisely the op­ posite of depth-first search. To achieve this aim, depth­ bounded discrepancy search (or Dns) combines together limited discrepancy search [Harvey and Ginsberg, 1995] and iterative deepening search [Korf, 1985]. DDS ap­ pears to perform better than both limited discrepancy search, Los and the improved version, ILDS [Korf, 1996]. Unlike ILDS, Dns does not need an upper limit on the maximum depth of the tree (that is, the maximum num­ ber of branching points down any branch). This will be an advantage in many domains as we often only have a loose limit on the maximum depth because of constraint propagation and pruning.

2 Discrepancies

A discrepancy is any decision point in a search tree where we go against the heuristic. For convenience, we assume that left branches follow the heuristic . Any other branch

*T he author is supported by EPSRC award GR/K/65706. I wish to thank members of the APES group for their help.

3 Depth-bounded discrepancy search

Depth-bounded discrepancy search (Dos) biases search to discrepancies high in the tree by means of an iterat­ ively increasing depth bound. Discrepancies below this bound are prohibited. On the Oth iteration, Dos ex­ plores the leftmost branch. On the i+ lth iteration, Dos explores those branches on which discrepancies occur at a depth of i or less. As with ILOS, we are careful not to re-visit leaf nodes visited on earlier iterations . This is surprisingly easy to enforce. At depth i on the i + lth iteration, we take only right branches since left branches would take us to leaf nodes visited on an earlier itera­ tion. At lesser depths, we can take both left and right branches. And at greater depths, we always follow the heuristic left . Search is terminated when the increasing bound is greater than the depth of the deepest leaf node. As the i + lth iteration of Dos on a balanced tree with branching factor b explores O(bi) branches, the cost of each iteration grows by approximately a constant factor.

As an example, consider a binary tree of depth 4. On the Oth iteration, we branch left with the heuristic and visit the leftmost leaf node. On the 1st iteration , we branch right at the root and then follow the heuristic left. On the 2nd iteration, we branch either way at the root, just right at depth 1, and left thereafter. Branching left at depth 1 re-visits leaf nodes visited on earlier iterations. On the 3rd iteration, we branch either way at the root and depth 1, just right at depth 2, then left thereafter. On the 4th and final iteration, we branch either way up to and including depth 2, and just right at depth 3. This takes us to the remaining leaf nodes and completes the search of the tree. Note that we did not re-visit any leaf nodes. The following pseudo-code describes Dos for binary trees. Note that, unlike ILOS, the maximum depth does not need to be given as it is computed during search as the second argument returned by PROBE.

function DDS k=O repeat (goal, depth)= PROBE(root ,k) k=k+1 until goal or k > depth return goal

function PROBE( node ,k) if leaf( node) then return (goal-p( node) , 0) if k = 0 then (goal , depth)= PROBE(Ieft(node), O) return (goal , 1 +depth) if k = 1 then (goal , depth) = PROBE(right(node),O) return (goal, 1 +depth) if k > 1 then (goal1,depth1) = PROBE(left(node) ,k- 1) if goai : then return (goal1, 1 + depth1) else (goal2, depth2) = PROBE(right(node),k- 1) return (goal2, 1 + max( depth 1 , depth2))

Dos visits all the leaf nodes of a search tree, but never re-visits leaf nodes at the maximum depth. To prove this, consider the depth j of the deepest right branch on the path to any leaf node at the maximum depth. Only the jth iteration of Dos will visit this leaf node. Dos re-visits leaf nodes above the maximum depth of the tree when the depth bound k exceeds the depth of the shallowest leaf node. This typically occurs late in search when much of the tree has been explored. Indeed, as search is usually limited to the first few iterations, we often do not re-visit any leaf nodes. ILOS also re-visits leaf nodes that occur above (the upper limit on) the maximum depth of the tree. However, ILDS can re-visit leaf nodes from the first iteration onwards. For example, if the leftmost leaf node is above the maximum depth of the tree, it is re-visited on every iteration.

Given a limited amount of search, Dos explores more discrepancies at the top of search tree than Los or ILOS. At the end of the first iteration of ILOS on a binary tree of height d, we have explored branches with at most one discrepancy. By comparison, Dos is already on ap­ proximately its log2 (d)-th iteration, exploring branches with up to log 2 (d) discrepancies. And at the end of the second iteration of ILDS , we have explored branches with at most two discrepancies. Dos is now on approximately its 2log 2 ( d)-th iteration, exploring branches with up to 2log2 ( d) discrepancies.

DDS is a close cousin of iterative-deepening search [Korf, 1985]. There are, however, two significant dif­ ferences . First , when the depth bound is reached, we do not immediately backtrack but follow the heuristic to a leaf node. Second , by always going right immediately above the depth bound , we avoid re-visiting any nodes at the depth bound.

4 Asymptotic complexity

For simplicity, we consider just balanced binary trees of depth d. The analysis would generalize with little dif­ ficulty to trees with larger branching rates. Korf has shown that in searching the tree completely, Los vis­ its 0(~2d) leaf nodes [Korf, 1996]. By comparison, Dos , DFs and ILOS all visit the 2d leaf nodes just once. ILDS and Dos are less efficient than DFS as they re-visit interior nodes multiple times . However, they have a sim­ ilar overhead. DFs visits 2d+l- 1 nodes in searching the tree exhaustively. By comparison, ILOS visits approximately 2d+ 2 nodes [Korf, 1996], as does DDS. Let DDs(d) be the number of nodes visited by DDS in searching a tree of depth d completely. On the Oth iteration, DDS explores the d nodes below the root ending at the leaf node on the leftmost branch . On the ith iteration, DDS explores completely a subtree of depth i -1. In addition, DDS branches right at the 2'- 1 nodes at depth i -1, and then left down the (d- i) nodes to a leaf node. Thus, ford large,

Expanding only right nodes at the depth bound con­ tributes significantly to this result. On the last and most expensive iteration, the depth bound reaches the bottom of the tree, yet DDS explores just the 2d-l out of the 2d leaf nodes that have not yet been visited. Without this efficiency, DDS would explore approximately 2d+3 nodes.

5 A Small Improvement

By increasing the space complexity of DDS, we can avoid most of the interior node overhead. For instance, we could search to the depth bound using breadth-first search instead of iterative-deepening as present. We can then start successive iterations from the frontier at the depth bound, saving the need to re-visit all the interior nodes above the depth boumd. The only overhead now is that of re-visiting the approximately 2d interior nodes that lie along the left paths followed beneath the depth bound. The dominating cost is that of breadth-first search which visits approximately 2d+l nodes. Unfortu­ nately, this improvement increases the space complexity at the kth iteration from O(k) to 0(2k). Provided search is limited to the first few iterations, this may be accept­ able and offer improvements in runtimes. We can achieve lesser savings but at linear cost in the space complexity using recursive best-first search with the depth as the cost function [Korf,· 1993]. This will perform breadth­ first search using space that is only of size 0( k) but will re-visit some interior nodes. We might also consider searching up to depth bound using ILDS. Such a strategy would not explore the tree completely. For example, it would not explore the branch which goes left at the root , right at depth 1, and left thereafter. For completeness, we would need to search to the depth bound using Los . But this search strategy would re-visit many more nodes than necessary.

6 A Simple Theoretical Model

To analyse iterative broadening and limited discrepancy search theoretically, Harvey and Ginsberg introduce a simple model of heuristic search with a fixed probabil­ ity of a branching mistake [Ginsberg and Harvey, 1992; Harvey and Ginsberg, 1995]. Nodes in a search tree are labelled "good" and "bad". A good node has a goal be­ neath it. A bad node does not. The mistake probability, m is the probability that a randomly selected child of a good node is bad. This is assumed to be constant across the search tree. See [Harvey, 1995] for some experimental justification of this assumption.

The heuristic probability, pis the probability that at a good node, the heuristic choses a good child first . If the heuristic choses a bad child, then since the node is good, the other child must be good. If the heuristic makes choices at random then p = 1 - m. If the heuristic does better than random then p > 1-m. And if the heuristic always makes the wrong choice, p = 1 - 2m. Figure 3, adapted slightly from Figure 3.3 in [Harvey, 1995], lists what can happen when we branch at a good node, and gives the probabilities with which each situation occurs.

In order to simplify the analysis, Harvey and Ginsberg assume that p is constant throughout the search tree, though they note that it tends to increase with depth in practice. At the top of the tree, heuristics are less informed and have to guess more than towards the bot­ tom of the tree. This simplifying assumption will bias results against Dos . Harvey and Ginsberg also restrict their analysis to the first iteration of Los. The com­ binatorics involved in computing exactly the probability of success of later iterations are very complex and have defeated analysis. To study later iterations, we simply estimate probabilities by searching an ensemble of trees constructed to have a fixed depth and a given heuristic and mistake probability. Since search will be limited to the first few iterations of the algorithms, the nodes in the trees can be generated lazily on demand. Trees with billions of nodes can easily be analysed by this method.

As in Figure 4 of [Harvey and Ginsberg, 1995], Figure 4 gives the probability of finding a goal when searching trees of height 30 with a mistake probability of 0.2 com­ puted from an ensemble of 100,000 trees. Such trees have approximately a billion leaf nodes, of which just over a million are goals. With about 1 in 1000 leaf nodes being goals, such problems are relatively easy. Nev­ ertheless, the probability of success for DFs rises only slightly above pd, the probability that the first branch ends in a goal. As in [Harvey and Ginsberg, 1995], DFs is given the highest heuristic probability in this and all subsequent experiments but still performs poorly. ILDS , which is omitted from the graphs for clarity, performs very similarly to Los. On these small and easy problems, Dos offers a small advantage over Los at each value of p. The discontinuities in the gradients of the graphs for DDS correspond to increases in the depth bound. They do not seem to disappear with even larger samples.

"

Figure 4: Probability of success on trees of height 30 and mistake probability, m = 0.2.

We next consider more difficult search problems. As in Figure 5 of [Harvey and Ginsberg, 1995], Figure 5 gives the probability of finding a goal when searching trees of height 100 with a mistake probability of 0.1 computed from an ensemble of 10,000 trees. Such trees have ap­ proximately 10 30 leaf nodes, of which about 1 in 38,000 are goals. This graph covers the Oth, 1st and part of the 2nd iteration of Los. Previously, Harvey and Ginsberg restricted their theoretical analysis to the 1st iteration of Los as it is intractable to compute the probabilit­ ies exactly for later iterations. As predicted in [Harvey and Ginsberg, 1995], at the start of the 2nd iteration, the probability of success for Los "rise[s] steadily once again" as we explore fresh paths at the top of the search tree. However, Dos appears to be more effective at ex­ ploring these paths and offers performance advantages over Los at every value of heuristic probability.

'"'

Figure 5: Probability of success on trees of height 100 and mistake probability, m = 0.1.

Finally, we vary the heuristic probability with depth. In Figure 6, p varies linearly from 1 - m at depth 0 (i .e. random choice) to 1 at depth d (i.e. always cor­ rect). This may provide a better model for the behavior of heuristics in practice. Dos appears to offer greater performance advantages over Los in such situations.

'""'

Figure 6: Probability of success on trees of height 100 and m = 0.1 with heuristic probability, p varying linearly from 1 - m (random choice) at the root to 1 (correct choice) at leaf nodes. At depth i, p = (1-m)+ im/100.

7 Early mistakes

We attribute the success of Dos to the ease with which it can undo early mistakes. Such mistakes can be very costly for DFS. For instance, Crawford and Baker identi­ fied early mistakes as the cause of poor performance for a Davis-Putnam procedure using DFS on Sadeh's schedul­ ing benchmarks [Crawford and Baker , 1994]. On some problems, a solution was found almost immediately. On other problems, an initial bad guess would lead to search­ ing a subtree with the order of 2 70 nodes. Recent phase transition experiments have also identified early mistakes as a cause of occasional exceptionally hard problems (or ehps) in under-constrained regions. For example, Gent and Walsh found ehps in soluble propositional satisfiab­ ility problems [Gent and Walsh, 1994]. They report that ehps often occur after an early mistake when the heur­ istic branches into an insoluble and difficult subprob­ lem. Similarly, Smith and Grant found ehps in soluble constraint satisfaction problems with sparse constraint graphs [Smith and Grant, 1995]. Again they report that they often occur after an early branching mistake into an insoluble and difficult subproblem .

Dos may undo early mistake at much less cost than DFs . To test this hypothesis, we generated satisfiable problems from the constant probability model using the same parameters as [Gent and Walsh, 1994]. Each prob­ lem has 200 variables and a ratio of clauses to variables of 2.6 . Literals are included in a clause with probab­ ility 3/400, giving a mean clause length of approxim­ ately 3. Unit and empty clauses are discarded as they tend to make problems easier. This problem class is typically much easier than the random 3-SAT model but generates a greater frequency of ehps [Gent and Walsh, 1994]. To solve these problems, we use the Davis­ Putnam procedure, branching on the first literal in the shortest clause. Table 1 demonstrates that DDS reduces the severity of ehps compared to DFS. Other methods to tackle ehps include sophisticated backtracking pro­ cedures like conflict-directed backjumping [Smith and Grant, 1995] and learning techniques like dependency­ directed backtracking [Bayardo and Schrag, 1996] which identify quickly the insoluble subproblems after an early mistake.

8 Adding bounded backtracking

Whilst early mistakes are not necessarily costly for DDS, mistakes deep in the tree will be very costly. Bounded backtrack search (BBs) allows quick recovery from mis­ takes deep in the tree for little additional cost [Harvey, 1995] . A backtrack bound of depth l adds at most a factor of 2 1 to the search cost. For small/, this is likely to be cheaper than the cost of additional iterations of DDS. An alternative view is to consider bounded backtracking as strengthening the branching heuristic to avoid choices which fail using a fixed lookahead.

DDS combines very naturally with BBS to give the al­ gorithm DDs-BBs. DDS explores early mistakes made at the top of the tree whilst BBS identifies failures rap­ idly at the bottom of the tree . The two search s~rategies therefore join together without overlap. Harvey has also combined LDS with BBs to give LDS-BBs . See the Ap­ pendix for details and for a correction of a small error in the specifications ofthe algorithm given in [Harvey, 1995; Harvey and Ginsberg, 1995]. On the ith iteration, LDs­ BBs re-visits all those leaf nodes with less than i dis­ crepancies. One improvement is to combine ILDS with BBS so that the discrepancy search does not re-visit leaf nodes. However, even with such a modification, bounded backtracking still re-visits leaf nodes visited on earlier it­ erations. By comparison, the bounded backtracking in DDs-BBs only visits leaf nodes with a greater discrep­ ancy count that have not yet been visited. The following pseudo-code describes DDs-BBs for binary trees.

function Dos-BBs( l) k=O repeat (goal, depth)= PROBE(root ,k,l) k=k+1 until goal or k + l > depth return goal function PROBE( node,k,l) if leaf( node) then return (goal-p( node ),0) if k = 0 then (goah, depth1) = PROBE(left(node),O,l) if goal1 or depth1 ~ l then return (goah, 1 + depth1) else (goal2, depth2) = PROBE(right(node),O,l) return (goal2, 1 + max( depth 1 , depth2))) if k = 1 then (goal, depth)= PROBE(right(node),O,l) return (goal, 1 + depth) if k > 1 then (goal1, depth1) = PROBE( left( node) ,k - 1 ,l) if goah then return (goal1, 1 + depth1) else (goa/2 , depth2) = PROBE(right(node),k- 1,/) return (goa/2, 1 + max( depth1, depth 2 ))

9 Experiments

A phase transition is often seen when we vary the constrainedness of randomly generated problems and they go from being under-constrained and soluble to over-constrained and insoluble [Cheeseman et a/., 1991]. Discrepancy search strategies like DDS, LDS and ILDS are designed for under-constrained and soluble prob­ lems, where we expect to explore just a small fraction of the search tree. Harvey and Ginsberg report that such problems are common in areas like planning and scheduling [Harvey and Ginsberg, 1995]. Discrepancy search strategies offer no advantage on insoluble prob­ lems where the tree must be traversed completely. In­ deed, for a balanced binary tree, our asymptotic results, along with those of [Korf, 1996], show that we explore ap­ proximately double the number of nodes of DFs . When the tree is unbalanced, as a result of constraint propaga­ tion and pruning, the overhead can be even greater. We therefore restricted the experiments in this section to soluble and under-constrained problems, on which dis­ crepancy search strategies can offer advantages.

As in [Harvey, 1995], we use the random 3-SAT model. A phase transition occurs for this model at a clause to variable ratio, L/ N of approximately 4.3 [Mitchell et al., 1992]. We generated 10,000 satisfiable problems from the soluble region with L/ N = 3.5 and from 50 to 250 vari­ ables. Each problem is solved using the Davis-Putnam procedure, branching as before on the first literal in the shortest clause. Results are given in Table 2. As expec­ ted, on such under-constrained and soluble problems, DDS and ILDS are superior to DFs, with DDS offering an advantage over ILDS especially on larger and harder problems. By comparison, on "critically constrained" problems at L/N = 4.3, DFs gave the best performance, with little to chose between ILDS and DDS .

10 Related work

Los was proposed by Harvey and Ginsberg in [Harvey, 1995; Harvey and Ginsberg, 1995]. They showed that it outperformed existing strategies like DFS and iterative sampling on large, under-constrained scheduling prob­ lems . ILDS, Korf's improved version of Los appeared in [Korf, 1996]. Ari Jonsson (personal communication reported on page 94 of [Harvey, 1995]) has proposed a related search strategy to Dns in which we perform iterative-deepening search followed by bounded back­ tracking from nodes at the depth bound. Like Los, such a strategy re-visits leaf nodes multiple times. For ex­ ample, the leftmost leaf node is visited on every iteration of the search. By comparison, Dns visits only half the nodes at the depth bound, and never re-visits any leaf node at the maximum search depth.

11 Conclusions

For many problems, the search tree is too large to explore completely. As a consequence, we often want to increase the chance of finding a solution in a limited amount of search. We have shown both theoretically and experi­ mentally that depth-bounded discrepancy search is an effective means of exploring large and under-constrained search trees. By focusing on branching decisions at the top of the search tree, where heuristics are most likely to be wrong, depth-bounded discrepancy search outper­ forms depth-first and limited discrepancy search.