Preprocessing Search Spaces for Branch and Bound Search

1 Introduction

Heurist ic search procedures ·are useful in a large number of problem domains. Most. heuristic search procedures (for example, A* , SSS*, B* , AO* , and alpha-beta) have been shown to be special cases of best-first Branch-and­ Bound search [ V. Kumar and L. Kana! , 1983, Nau eta/., J 984] . T hese procedures search several solution paths at t he sanw time, expanding some paths more qui ckly than others dPpending on which paths look most promising.

One source of computational overhead during such search is the time spent keeping track of the alternate partial solutions that the procedure is examining. Typi­ cally. t hP search algorithm stores these parti al solutions on a I ist called the agenda, open list , or active list , in order of their estimated cost. Any time anew partial so­ lution is generated , its est imated cost must be compared with tlw estimated cost.s of the other partial solutions already on the list. , in order to find t.he appropriate place Dana S. Nau*

*This work was supported in part by an NSF Presidential Young Investigator award , with matching funds provided by Texas l nstrument.s and General Motors Research Laborato­ ri es, a.uJ iu pa.rt by NSF Graut. NSFD CDR-8800.3012 to t.he Systems Research Center.

Computer Science Department, Institute for Advanced Computer Studies, and Systems Research Center University of Maryland College Park, Maryland 207 42

to put it on the list. Thus, significant computational overhead is required just to maintain the active list .

Certain problem domains have special properties which allow us to eliminate this overhead. In particu­ lar, in some problem domains it is possible to do auto­ matic preprocessing or "compiling" of the search space, to extract control knowledge which can be used to do the heuristic search without having to maintain the ac­ tive list explicitly. In this paper , we discuss what kind of domains allow us to do such preprocessing, how to do the preprocessing, how to use the information gath­ ered from the preprocessing, and how much time can be saved by doing this preprocessing. We also present an example from a. problem domain of particul a r interest to us: generative process planning for the manufacture of machined parts.

2 Problem Characteristics

Preprocessing of the search space is possi hiP wherwver the following conditions are satisfied:

1. With the exception of feasibility /infeasibility of nodes, the search space has the same shape regard­ less of the parti cul ar problem instance being con­ sidered . Thus, if P and P' are two problt>m in­ stances , t.hPn there is a one-to-onP mapping betwPen the nodes of t.hei r search spaces S and S', such that if somP feasible node a in S has 11 childrPn b;, i = 1 .. . 11 , then its corresponding nodP a' inS' will either havP 11 childwn o; , fori= I . . . 11 such t.hat. b; corresponds too; , or be infPasible.
2. Corresponding nodes need not. have t.hP same cost. but. if two nodes a and bin .)'1 have cost( a) > cost(b) , then for tlw corn~sponding nodes a' and b' in S'' , WP must have cost(a') > cosL(b').

Nearly a ll heuristi c search probl ems sat isfy t.lw first condition abovP, but fpwer satisfy the second one. How­ ever , there are still many problems whi ch do satisfy it .. One example is generative process pl anning for the man­ ufacture of machined parts. Jn our genPrat.ivP process planning system SIPS[Na.u , 1987], a mach inable part is considered to be a coll('dion of ma.chinabiP features. For each feature , SIPS finds an opt imal pl an for that feature via a. best-first. Branch- and-Bound search in its knowl­ edge base. SIPS's knowl0dgf' base consists of informa­ tion on a. larg<' n umlwr of different. machining processes.

organized in a taxonomic hierarchy. For two different machinable features, different machining processes may have different costs- but if process a costs more than pro­ cess b on feature /, it generally also costs more than process b on feature f' as well .

Robotic route planning[T. A. Linden and J . Glicks­ man , 1987] is another problem domain which also sat­ isfies the second condition . In this domain, a route map corresponds to a graph, in which a node represents a region and an arc represents connectivity between two regions. The cost of a node can be the time needed to pass through the region it represents , and the feasibility of a node indicates whether or not the region is pass­ able. In general, although the passability of a region may change from one problem instance to another , the relative costs of the regions stay the same. In such cases, preprocessing is possible.

3 Threaded Decision Graphs

Suppose that. for a given problem instance the search space is as shown in Figure 1. The goal is to search for the cheapest leaf node for which all the nodes along the path from the root are feasible . In Figure 1, suppose the problem solver is checking the conditions associated with node c. If c succeeds, we know that. the next node to check will be/, since c must be the current minimum costly node to be checked, and f's cost is the same as c's. Similarly, if c fails, the next. node to check in the search space must be j . This is because at the time c is being checked, nodes a, b, d, e, h and k must. all have been checked, since they all have costs less than that of c's. Control information like this is independent of the particular problem instances, and can be gathered before the problem solving process starts. Therefore, we can assign a success thread from node c to node f, and failur·e thread from c to j. During the course of finding the cheapest actions to achieve a given goal, once we reach node c, if all the conditions are satisfied, we can follow the success thread of c to get to the next node to be checked . On the other hand, if they are not satisfied, then the failure thread a.t c can be followed to get to the next node to be checked. Figure 2 shows such a. structure.

If all the deterministic control information is gath­ ered, it is no longer necessary to maintain an active list for storing control information. Before problem solving starts, the information can be used to construct a data structure that contains one or more occurrences of each action, and for each action occurrence there is a suc­ cess pointer and a failure pointer. We will call such a data structure a threaded decision graph of the original search space. Problem solving can then be completely guided by its threaded decision graph. Figure 3 shows the threaded decision graph for the search space in Fig­ ure 1.

Two special nodes in Figure 3 are worth noting. The node marked "success" is called a success node. If this node is reached through the success threads, the search process terminates with success. The path from the root node to success in the threaded decision graph contains the solution path which should ·be returned. The node marked "fail" is called a failure node, which marks the termination of the search process without success.

In the following, we first discuss in detail how problem solving is done with the help of threaded decision graphs. We then consider how such a data structure could be automatically constructed.

4 Search with the Threaded Decision Graphs

Given a search space, assume that we have constructed its threaded decision graph. A request to solve the prob­ lem would correspond to finding out the cheapest path in the tree. For the given threaded decision graph, this is done by checking the conditions associated with each node, starting from the root node. The success thread of the current node should be followed if the node is tested to be feasible, and the failure thread should be followed if it is infeasible. Each node is also marked as "success" or "failure'' depending on the result. of its feasibility test.

If, during the traversal process, a. success node is reached via a. success thread, then the search ends with success.

If a failure node is reached through failure thread, then no actions satisfying the criteria exist . In this case, search is terminated with failure.

After tracing down the failure thread of some node, it is possible to reach some other node whose ancestor in the original search tree failed the feasibility test . For ex­ ample, suppose node b in figure 3 is infeasible and node f is being checked . Iff is infeasible then the next node to be checked should be j . Since b is an ancestor of j which failed , no feasibility test need be done at j , and the failure thread of it should automatically be followed . In general , whenever a node n is reached via some fail­ ure thread, it should always be checked to see if n has any ancestor m which failed the feasibility test . If so, the failure thread of node n should be followed , without conducting its feasibility test.

To check if a given node has any infeasible ancestor is straightforward: we can retrieve the traversal informa­ tion associated with the parent node of the given node in the original search space. It has an infeasible ancestor if its parent node is unvisited or marked as infeasible.

5 The Construction of Threaded Decision Graphs

In this section , we consider the problem of how the threaded decision graphs are constructed . For simpli c­ ity, we assume the search space is finite. Later we will discuss cases where the search space is not finite.

With the above rest rictions, the following algorithm generates the threaded decision graph. This algorithm is a. mod ified version of best-first search.

procedure Construct A := { ao } (A is the actit·e list, and ao is the root of the search space) While A is not empty do bPgin n := pop(A) ; Jf A is empty, then FailurP-t.hread( n) :=Failure-node else FailurP-thread(n):= head(A) ; If n is a. leaf node, t.hen Success-t.hrPa.d( n) :=SurcPss-nodP Plse begin A:=insert.(A, Children(n)) ; Suw~ss-t. hread( n ):=head( A) end {else} end{whil e} end Con.s lru.ct

Du ring prPprocessing of the search space, each node in the trf'e appears at. the head of the act ive list. once and only once , and the resultant threaded decision graph has t he same number of nodes as the original search space. Since every node has only two threads , the suc­ cess and the failure threads, the number of threads of t.he threaded decision graph is twice the number of nodes a.s t.hat. of the search space. The same a.rg11ment. a lso guar­ antees t.he absence of cycles of t.hrea.ds.

6 Very Large or Infinite Search Spaces

If the search space is very large, the time it. takes to pre­ process it may be prohibitive. In such cases, and in cases when the search space is infinite, we can preprocess a. fi­ nite portion of it. This partial threaded decision graph can be created by running the algorithm Construct for a finite number of iterations, until one or more goal states appear in the graph.

During the problem solving process , the threaded deci­ sion graph can be used in the same manner as described in the previous sections , until a node which has no suc­ cess and failure threads is reached. At this point, con­ ventional Branch-and-Bound search can be utilized as follows: An active list is constructed by incl~ding all of the successor nodes of the current node and the children of the feasible nodes along the path back to the root node in the state space. This list. is sorted according to the costs of its nodes, and least costly of these is expanded.

The construction of the threaded decision graph may also be done with the following strategy: During search through the search space for each particular problem in­ stance, every time a node is tested we will look for its success or failure threads . If they do not exist, we will use the search procedure to fi~d out whi ch node we should test next. The success or failure threads can then be assigned to this node. In other words, the threaded de­ cision graph is partially built. on the job.

7 Analysis

By gathering all tlw possible stat. ir control informat ion beforehand , preprocessing oft.he search space can great ly improve problem solving effi ciPncy. In order t.o see this claim more quantitat. iw'ly, cons id 1~ r a simplified Pxample. Assume that. the search spaef' is in the shape of a tree with a branching factor of m a.nd dep th k (t.he root of the tree has a depth of I) . To Sf'f' how much time the problem solver spends on manipulating the list of incom­ plete paths using conventional Sf'arch methods , consider the following two extn·me casf's.

In the best. case, the search procedure expands only one path down the tree. The t.ime for manipulat ing the act. i ve I ist. is 0( km log m) .

In t.he worst. cast>, tlw search procedure expands the tree in a breadth first manner. T lw t.ot.al t.inw spent on manipul a ting t.he list in this case is hounded hy m x IH(k - 1) L i= l log(i x m) = O(mk log n/) .

On t.hf' ot her hand , Sf' arch with a threaded decision graph is guided completely by the success and fail ­ ure threads , and no add itional computational effort is needed for manipul at ing the search control information. Therf'fore, the time saved by using the threaded deci­ sion graph to guide t.he search procedure can be bPt.ween 0( km log m) and 0( mk log mk ) , where k is the dept.h of the tree and m is the branching factor.

8 Discussion

In t. his paper we presented a technique for preprocessing Sf'arr h spaces in order t.o gather control informat ion for problem solving. We also discussed a number of condi­ tions under which the method works. Through complex­ ity analysis, we demonstrated that by using preprocess­ ing, a great deal of computational effort is saved during the search process.

Our idea of preprocessing search spaces has some similarity to that of threading of binary trees for tree traversal[Knuth, 1968]. However, the way such thread­ ing is done , and the way it is used, are both clearly different from our threaded decision graphs.

As described in the paper , our technique only works on state-space graphs. An extension of the work is to allow the search space to be an AND/OR graph. When AND branches are allowed, the problem can be very compli­ cated depending on how the costs are assigned its nodes. In the worst case, the threaded decision graph can con­ tain an exponential number of the occurrences of nodes in the original search space. An example of this situa­ tion is given in Figure 4. The problem is that the ith and i + 1 1 h best paths , fori= 1, 2, ... , are not next to each other, but on the left and right subtrees respectively. One way to tackle this problem is to partially preprocess the search space. For example, we can assign success and failure threads only to the nodes which are in the first. k best paths.

Another problem which needs more attention is that the relative costs of some nodes in different problems may not be the same, but may change with different situations. However, if the cost of nodes change with different situations in some predictable manner, and if the number of such changes is finite , the preprocessing technique can still be made to work. For example, it may be possible to divide the situations into separate classes , each with a different. threaded decision graph. Many domains satisfy this property, including process planning in automated manufacturing and robotic path planning.