Localized Search for Multiagent Planning

1 Introduction

The focus of this paper is the use of locality - the in­ herent structural qualities of a domain - to control the explosive cost of planning and other forms of reasoning. The use of localized reasoning, while quite intuitive and natural, has not been a fundamental aspect of most AI systems. A localized domain description is one that is explicitly decomposed into a set of regions. Each region may be viewed as a subset of potential domain activity with an associated set of requirements or "constraints" that pertain only to the activities within that region. We refer to this delineation of constraint applicability as constraint localization. (Throughout this paper we use the term "constraint" very broadly to refer to any type of goal or domain property that the planner must fulfill.)

Localized planning is the process of creating a valid domain plan by searching a set of smaller, regional plan­ ning search spaces rather than a single large "global" space. Each G EMPLAN search space may be visualized as a plan-construction search tree, where each tree node is associated with a region plan and each arc is associated with a plan modification that transforms the preceding plan into a new plan in order to satisfy some region con­ straint. Localized search is a powerful technique for re­ ducing the size and cost of the entire planning search space. Although this paper discusses localized search as applied to planning, the technique is generally ap­ plicable to any form of decomposable reasoning search.

This research has been made possible in part by the National Science Foundation, under Grant IRI-8715972.

Localized Search for Multiagent Planning

AmyL. Lansky

Sterling Federal Systems NASA Ames Research Center (AI Research Branch) MS 244-17, Moffett Field, CA 94035 U.S.A

In addition to GEMPLAN, a scheduler, an ~bduction­ based planner, and an image understanding system have already incorporated aspects of GEMPLAN's localized search method.

The GEMPLAN domain representation allows for a myriad of decompositional strategies, including the use of regions that overlap, are disjoint, are organized hi­ erarchically, or form any combination thereof. The al­ lowance for overlap, in particular, renders our localized search method quite useful for realistic domains. Crite­ ria for decomposition are usually suggested by the innate characteristics of a domain- e.g., its physical structure, its behavioral processes, its functional elements, and its abstraction hierarchies. A good decomposition typically reflects several such criteria. Consider, for example, a building-construction domain. Viewed globally, the do­ main may be described by a set of constraints, some of which describe the structure and requirements for a specific building, some that encode the characteristics of contractors and physical resources, and those that describe construction "rules of thumb." Clearly, most of these constraints apply only to a subset of the con­ struction activities to be planned. One way to decom­ pose the domain is according to the physical structure of the building - e.g., to utilize separate regions to model each room. Other regions could model the individual building processes - e.g., the contractors. In most cases, physically-motivated regions and process-based regions will overlap. Figure 1 depicts a possible decomposition for a small construction domain.

The primary goal of localization is to cluster activities into regions so that constraints are applied as narrowly as possible. The actual decomposition chosen will de­ termine the exact scope of applicability of domain con­ straints - i.e., each region's constraints are assumed to apply only to the activities within that region. How­ ever, different localization decompositions will incur dif­ ferent planning costs. As we will show, there is a trade­ ?ff between increased decomposition and the resulting mcreased costs necessary for coping with regional over­ lap. While most of our empirical tests have utilized user-provided decompositions, we are currently develop­ ing a technique for automatically learning good decom­ position strategies. This work bears some similarity to Knoblock's learning of domain abstractions [4]; however, Knoblock's abstractions must be strictly hierarchical.

The use of localized reasoning has several benefits. From a representational point of view, locality provides a solution to aspects of the frame problem; constraint localization may be viewed as a frame rule which limits interaction among domain actions and properties. Most importantly, locality provides a rationale for partition­ ing a potentially explosive global planning space into a set of smaller, localized planning spaces. This has three interrelated benefits: ( 1) The absolute size of the union of a set of localized planning spaces is usually smaller than that of a non-localized space; (2) At each node in the search space, expensive planning algorithms need be applied to much smaller regional plans. Thus, search cost is cheaper, even if search space size is unaffected; (3) Since a localized domain description provides infor­ mation about how constraints and activities interact, it serves as a heuristic for constraint application. In par­ ticular, localized search enables the application of con­ straints only to relevant segments of the overall emerging plan and causes constraints to be applied only when then actually need to be. All of these factors facilitate scaling up to large domains.

The notion of localized search is related to several other research efforts. The consistency maintenance techniques used in localized search for dealing with re­ gional overlap, for example, are similar to data consis­ tency methods used by shared, distributed databases. Other planning researchers have looked at methods of problem decomposition in order to reduce search com­ plexity [1, 5), but they have focused primarily on goal reduction and operator reformulation rather than search space decomposition. The goals of controlling the scope of constraint applicability and constraint triggering are shared by work in truth maintenance and constraint propagation. Our use of locality, however, generally produces a much coarser-grained connectivity than that found in a TMS or CSP net. GEMPLAN regions record constraint interrelatedness without the need for incre­ mental update or truth checking; they are thus less ex­ pensive. Semantically, however, localization can provide significant information. For instance, even if a constraint syntactically appears relevant to a broader fragment of the overall plan, its inclusion within a region will limit its application to within that region. Localized search also imposes an explicit control over constraint applica­ tion that is distinct from anything intrinsically provided by a TMS or CSP net. Recent work in discovering "tex­ tures" in CSP networks [3) to control constraint prop­ agation bears some similarity to localization, although CSP constraints are usually extensional and proposi­ tional, whereas GEMPLAN constraints are broader in content and usually intensional. One interesting use of locality is deKleer's work on localizing or merging clauses in a TMS [2]. In deKleer's case, merging is done to gain completeness. In localized search, partitioning is done to gain efficiency, but with no loss of completeness.

The rest of this paper is organized as follows. Section 2 provides an overview of the GEMPLAN architecture and a description of the localized search algorithm. This discussion is made concrete in Section 3, which describes a simple planning scenario. Section 4 discusses various tradeoff's inherent in localized search, and then substan­ tiates these intuitions with a complexity analysis. This is followed by the empirical results of Section 5.

2 The GEMPLAN Planner

GEMPLAN is a planner designed for multiagent do­ mains that require complex coordination. It has been applied to multiagent blocks-world problems, the Tower of Hanoi, and several versions of a construction domain. The system includes an execution facility, and has the ability to apply constraints before or during execution. It may thus be viewed as a combined pre-planner/dynamic­ planner. While the existing system is primarily designed for pre-planning, we have begun implementation of a next-generation GEMPLAN system, called COLLAGE, that will span the pre-planning/dynamic-planning spec­ trum in a more seamless fashion.

G EMPLAN differs from standard hierarchical plan­ ners in several ways. Besides its use of localized search, GEMPLAN has the ability to satisfy a broad range of domain "constraint forms," not simply the attainment and maintenance of state conditions. Note that we use the term "constraint" in a very broad sense - i.e., to refer to any sort of property that the planner knows how to test and make true. The system includes a set of general-purpose constraint satisfaction algorithms for a set of constraint forms, which may be further aug­ mented by user-supplied constraint-satisfaction meth­ ods. The default constraint algorithms are fully gen­ eral for partially-ordered plans and perform the task of plan construction by introducing actions, action interre­ lationships, and variable bindings. GEMPLAN's current constraint repertoire includes: (1) The attainment and maintenance of goal conditions and preconditions - i.e., the traditional planning algorithms used by STRIPS­ based planners. Actions may have conditional effects, and established conditions are protected; (2) Action de­ composition. GEMPLAN allows for reasoning about ac­ tions at mixed levels of detail, rather than confining itself to reasoning "one level at a time," as do some hierarchi­ cal planners [10]; (3) A variety of temporal and causal constraints; (4) Required patterns of behavior expressed as regular expressions; (5) CSP constraints on potential values of plan variables.

More details on GEMPLAN appear elsewhere [6, 7, 8]. The rest of this paper focuses on GEMPLAN's localized search mechanism. A detailed account of GEMPLAN's localized search implementation can be found in [9].

2.1 Localized Search Overview

Part of GEMPLAN's domain specification input is an explicit decomposition of domain action and constraint information into regions. GEMPLAN uses this informa­ tion to create a search space for each region, rather than utilizing a single global search space. Each search space is concerned with building a plan for its region that sat­ isfies all regional constraints. The planner may thus be viewed as a set of "mini-planners," tied together by the structural relationships between regions.

The localized search algorithm has two basic functions: ( 1) controlling the flow of constraint application - in par­ ticular, shifts between regional search spaces; and (2) maintaining the consistency of the overall search space. Besides assuring that all regions are searched at least once (to satisfy goal constraints), localized search typi­ cally shifts from one regional search space to the search space for a region R only if previous plan modifications have impacted R's plan. That is, search will flow only to those regions whose plans have been affected and whose constraints truly need to be checked. Planning for a region can impact the plan for another region only if they share a common portion of the overall plan (i.e., they overlap). And because the search spaces of over­ lapping regions reason about shared subplans, localized search must make sure that they share a consistent view of these subplans.

2.2 Region Description

Let us assume that a domain is specified as a set of re­ gions. Each region R is defined by a region description: < actions{R}, subregions{R), constraints(R), tree(R)>. The set actions(R) consists of action types, instances of which may occur directly within R (but not within a subregion of R). The set subregions(R) consists of subregions belonging to R. For each such subregion Q, we use the notation Q C R. The set constraints(R) in­ cludes constraints that pertain to activities within Rand its subregions. Finally, each region is associated with a plan-construction search tree tree(R).

Consider the construction domain of Figure 1. It has been partitioned into regions corresponding to the ac­ tivities of an electrician, plumber, and general contrac­ tor. These regions are further decomposed to include subregions that contain the activities of the electrician and plumber at various walls as well as their respective "control" activities (these might include communication actions between contractors). Each wall region would be associated with constraints that are relevant only to the actions taking place at that wall; e.g., wallA might in­ clude constraints relating to coordination the plumber and electrician. The electrician, plumber, and gc region constraints, which apply to all their subregions, describe more global requirements; e.g., the gc constraints might describe how the contractors communicate instructions.

2.3 Plan Representation

The focus of regional search is to incrementally construct a region plan. Each region plan consists of a local region plan and a set of subplans (the region plans of its subre­ gions). For example, if Rl C Rand R2 C R, the region plan for R will include a local region plan for R and re­ gion plans for Rl and R2. GEMPLAN associates all plan information with the smallest region that encompasses that information. This assures that plan information is visible to all relevant regions. The region plans of Rl and R2 will thus include all plan information that deals exclusively with Rl and R2, respectively. The local re­ gion plan of R will include plan information that deals specifically with activities in R or that pertains to rela­ tionships among R, Rl, and R2 (and therefore cannot be associated strictly with Rl or R2).

2.4 Region Search Trees

Figure 2 depicts portions of planning search trees for the electrician and waiiB regions of our sample domain. Each tree reflects search through a space of "plan construc­ tion" operations - i.e., it is a plan-construction search space (rather than a state search space). Each tree node is associated with the region plan constructed Up to that point in the search, and each tree arc is associated with a plan modification or "fix" that transforms a region plan into a new region plan. Upon reaching a node, the plan­ ner must choose which region constraint to check next. (Thus, an implicit branching factor in the search space is the set of all relevant constraints at each node.) If the chosen constraint is not satisfied by the plan associ­ ated with that node, constraint satisfaction algorithms or "fixes" must be applied (there may be several fix al­ gorithms for each constraint, as well as many possible solutions or "fixes" per fix algorithm), resulting in a set of new region plans at the next level down in the tree. A GEMPLAN fix typically adds new actions, relations, and variable bindings to a region plan, and may also generate new subregions. Deletion of plan information can only be accomplished by backtracking (this restriction will be lifted in the COLLAGE system). GEMPLAN uses, by default, a depth-first search strategy. It tries constraints in the order supplied by the domain specification, fixes in the order supplied by GEMPLAN's internal constraint mechanism, and backtracks only if all fixes fail for a par­ ticular constraint. However, since search should opti­ mally be driven by domain-dependent information and the structure of the growing plan, GEMPLAN allows for flexible tuning of tree search. The order in which con­ straints and fixes are applied, as well as backtracking schemes, can be made context dependent.

2.5 Transfer Between Trees

In the current GEMPLAN system, transfer of control flow between regions occurs according to a fixed algo­ rithm. Aside from assuring that each region is visited at least once to address goal constraints, transfer be­ tween regions generally occurs in response to informa­ tion transmitted to the search mechanism by a fix. Sup­ pose we are in tree(R). After applying a fix for one of R's constraints to R's region plan, the fix must re­ turn a subset of R's subregions, Rl, ... , Rm, whose plans have been affected by the fix. The GEMPLAN search algorithm will then inhibit further search within tree(R) until tree(Rl) ... tree(Rm) are all satisfactorily searched. As depicted in Figure 2, if electrician affects the sub­ plan for region waiiB via the introduction of new actions there, search within tree( electrician) cannot safely pro­ ceed until wallS's tree is searched and its constraints are rechecked and satisfied.

Notice how shifts between parent and child regions induce a partitioning on the child's search tree. We call these search fragments incarnations - search within the child is reinvoked or "reincarnated" each time the child's plan is modified in some way by a parental fix. Each time a child's tree is reincarnated, all of its af­ fected constraints must be rechecked. One restriction on GEMPLAN's search control mechanism is that all search strategies (e.g., alternative backtracking schemes) must be applied within the confines of an individual incar­ nation. This greatly simplifies the problem of search consistency.

2.6 Global Correctness and Consistency

Two important challenges of localized search are mak­ ing sure that all regional constraints are checked when they need to be (global correctness) and assuring that all regional search tree information is consistent (global consistency). This would be fairly straightforward if domain structure were strictly hierarchical. However, since we allow for regional overlap, added effort is re­ quired. For example, if a fix in tree( electrician) affects region wallA's plan, it is not enough to simply recheck wallA's constraints and return to tree( electrician). Re­ gion plumber's representation of wallA's subplan must also be updated within tree(plumber), and search must also eventually occur within tree(plumber) to recheck its constraints. We call this overall process completion.

Let us consider completion in more detail. When search within an incarnation for region R is terminated, all changes for that region must be reflected within the tree of every ancestor region A of R. This will involve update of subplans and other information relating to R at relevant nodes in tree(A). Assuming that the final plan for R's preceding incarnation was Rplan, the nodes to be updated will be precisely those that have information about Rplan. Next, some method must be used to ensure that A's search space is eventually reincarnated. This could be done via an auxiliary facility that keeps track of which regions must be checked. We are taking this approach in COLLAGE; the facility will fully con­ trol region incarnation and will also allow for parallel incarnation of regions.

In the current GEMPLAN system, the DAG formed by the inclusion relation C must be completed by a span­ ning tree. This tree is then used as a guideline for con­ trolling regional transfer. Each region, except some des­ ignated "top" region must have a parent via the C rela­ tion or be artificially "assigned" a parent via the span­ ning tree. For example, gc, electrician, and plumber are not subregions of any enclosing region. Although they do not logically belong to another region as far as con­ straint applicability, we must make sure that each has a "parent" for search control purposes. We denote this pseudo-parental relationship by Cp and choose gc as the "top" region, with electrician Cp gc and plumber Cp gc. Search initiates at the "top" region and transfers from parent to child only if C or Cp holds and if the child's region needs to be checked.

3 Example

We now clarify the preceding discussion with a simple planning scenario. Let us assume that the electrician, plumber, and wallA regions are associated with the fol­ lowing constraints: 1

ELECTRICIAH CONSTRAINTS: (1) action(install-socket(vallA,locA1)) (2) decompose(install-socket(W,L), {W.electprep(L) => W.insertsocket(L)}) PLUMBER CONSTRAINTS: (1) action(install-pipe(vallA,locA1)) (2) decompose(install-pipe(W,L), {W.plumbprep(L) ·> W.insertpipe(L)}) WALLA CONSTRAINTS: (1) (forall L) [(forall prep:{electprep(L),plumbprep(L)}) pattern((prep)·=>)] (2) fcfs([[electprep,insertsocket], [plumbprep,insertpipe]])

The first electrician constraint requires a socket to be installed in wallA. An action constraint simply results in the addition of an action to the plan. 2 The second constraint requires that each install-socket(W ,L) ac­ tion be decomposed into an electprep action followed by an insertsocket action at wall W, location L. The plumber constraints are similar. In this case, one pipe is to be installed in wallA. The two wallA constraints per­ tain to the coordination of the electrician and plumber actions at that wall. The first constraint states that all electprep and plumbprep actions at the same loca­ tion must follow a certain pattern - they must be to­ tally ordered by the temporal relation =>. The second constraint additionally requires that the electrician and plumber have access to the same locations of wallA on a first-come-first-serve basis. The constraint provides a set of action pairs and has the following semantics: any required execution ordering of the first actions in each pair (in this case, required orderings between prep ac­ tions) will determine the ultimate ordering of the second actions in each pair (the ordering of insertsocket and insertpipe actions). Since a total ordering is forced on all prep actions at the same location, this will force elec­ tricians and plumbers to insert their devices in common locations on a first-come-first-serve basis.

1 This informal description is intended for didactic purposes only. A full GEMPLAN domain description requires specification of regional action types and domain structure, allows for specifi­ cation and instantiation of region types, may include many more types of constraints, and may include various search heuristics. Capitalized tokens denote variables. Each variable has a scope limited to the constraint in which it is found. An action of form I. Y denotes an action Y occurring at location I .

2 One way to introduce actions into the plan might have been via STRIPS-based goal conditions or preconditions. In this domain, it is more convenient to add the actions explicitly, since only one type of action is available for attaining the desired effect.

We now describe the construction of the plan in Fig­ ure 3. Reasoning begins at the "top" region gc, which, in this case, has no constraints of its own, but is responsible for invocation of the electrician and plumber search trees. In this case, electrician is invoked first and its first con­ straint adds the specified install-socket action into the electrician plan. Constraint 2 then decomposes this action into electprep and insertsocket actions at wallA, causing changes in the wallA subplan of electrician. Before search continues within tree( electrician), search within tree(waiiA) must occur. Both wallA constraints are checked, but both are satisfied at this point. The newly completed incarnation of wallA therefore does not add any new information to the subplan for wallA as­ sociated with electrician, but the process of completion causes the new version of the wallA plan (that includes the changes made by electrician) to be inserted appropri­ ately into nodes of tree(plumber).

All electrician constraints are now satisfied. Search returns to gc, which invokes search in tree(plumber). The plumber constraints cause the addition of the install-pipe action and its decomposition into the appropriate subactions at wallA. Search must now oc­ cur for the affected wallA region. This causes the actions electprep(locAl) and plumbprep(locA1) to be forced into some total order ( electprep(locA1) => plumbprep(locA1) is chosen) and then, as a result of the second wallA constraint, a similar ordering is imposed on insertsocket(locA1) and insertpipe(locA1). The new wallA plan is appropriately inserted into both tree( electrician) and tree(plumber) (due to completion). All plumber constraints are now satisfied and search re­ turns to gc. The constraints within electrician are then rechecked (due to the changes at wallA), but they are still satisfied. Search then terminates· successfully.

4 Complexity Analysis

It is clear that no general complexity result can be given for localized search- the size and complexity of the plan­ ning search trees for a particular problem will depend on the structure of the domain, the constraints associated within each region, the complexity of their satisfaction algorithms, the domain search heuristics, and the specific domain problem being solved. In order to provide some theoretical estimate of the benefits of localized search, however, we present a complexity analysis that compares search of a non-localized domain with search of a simple localized version of the same domain. We provide best­ and worst-case search costs, assuming that constraint algorithms are either all constant, linear, quadratic, or exponential in cost (obviously, most domains will have a mixture of these).

Although our analysis is quite idealized, it is corrobo­ rated by the empirical results of Section 5 and jibes with our basic intuitions about the tradeoffs inherent in local­ ized search. In particular, it is clear that the completion costs necessary for dealing with overlap are nontrivial. These include search-tree update of ancestral regions to maintain consistency, and possibly wasteful rechecking of affected regional search trees (for example, the recheck­ ing of the electrician constraints at the end of the pre­ ceding scenario). The problem of needless rechecking of regional trees can be mitigated by maintaining tighter relevancy hooks between actions and constraints (which GEMPLAN optionally provides) to inhibit unnecessary constraint checking. However, the problem is impossi­ ble to avoid completely. On the other hand, needless rechecking would be worse in global search.

Our analysis is based on the non-localized and local­ ized domain configurations depicted in Figure 4. For both domains, we assume a total of ne constraints, n 1 possible fixes for each constraint, and a final plan con­ sisting of s actions. The cost of checking any constraint on a plan of size j is c(j) and the cost of fixing a plan of size j is f(j). For the localized case, we assume the domain consists of m regions R1 ·· · Rm and a region G. The actions in the final plan are divided equally among the regions R1 ··· Rm, so that each builds a plan of size ,;-. Each of the R1 ··· Rm regions also contains a sub­ region consisting of k actions that overlaps with region G. Thus, G's region plan consists of mk actions. The nc constraints of the original problem are evenly distributed among G, R11 ··· Rm so that each region is associated with ,:'.; 1 constraints. (Note that the "k" regions have nolo­ cal constraints associated with them.)

Let us now consider the cost of a generic region search tree. For a region i, we _assume there are ne; constraints, that each constraint has n 1 fixes, and that the final size of the region plan is Si. Because a constraint fix may violate previously satisfied constraints, constraints may need to be repeatedly checked and fixed. We call the number of times the search must cycle through the con­ straints the search "repeat factor." Assuming that are­ gion i has a repeat factor of ri, its tree depth is rinc., with average depth to adding an action being r;~·; · (Thus, we assume that at most one action is added per fix. In most domains, many actions may be added per fix.) We then assume an implicit search space that alter­ nately branches due to choice of a constraint (the costs c(j) accumulated due to constraint testing) and choice of a fix (the costs f(j) accumulated due to constraint fix­ ing) . By "best-case search" we mean depth-first search without backtracking - i.e., the cost of one path from the root to the leaves of the search space. The cost of best-case search for region i is

In contrast, worst-case search cost measures the cost of searching the entire space:

To compare the complexity of these formulae for the non-localized and localized cases, we must set the repeat factot r i for each region. For this analysis, we let ri be ...u.. - that is, we assume that exactly one action is added n ci per fix, that the size of the plan is larger than the number of constraints, and that the depth of the region tree is equal to the number of actions in the region plan. The complexities of all cases are summarized in Table 1. For all of the localized search cases, we must also add to the total cost of the search trees an additional completion cost C. Assuming that completion occurs each time an action is added within a region of overlap and that the cost of each completion operation is a function of the plan data structures that must be updated, Cis 0( m 2 k ).

As can be seen, localized search is nearly always better than non-localized search - in most cases much better. The only exceptions are constant-complexity best-case search (when there is no reduction of search space size nor constraint algorithm cost) or when the cost of com­ pletion overshadows the cost of the search. The amount by which localized search wins over non-localized search is proportional to the amount by which s dominates both ,;- (the plan size of each of the subregions R1 ... Rm) and mk (the plan size of G). Thus, increased decomposition is always worthwhile, except for the cost of increased overlap (reflected in the size of mk and the cost of com­ pletion C). The gains of localized search become ex­ ponential as the complexity of the constraint algorithms increases and the bushiness of the search space increases. These gains come from three sources:

1. The size of the search space. This size reduction be­ come more significant as the bushiness of the search space (the amount of backtracking) increases.
2. The cost at each node. Even if the absolute size of the non-localized and localized search spaces are the same, expensive constraint algorithms need be applied to much smaller plans in the localized case.
3. The search heuristics provided by localization. Be­ cause of the semantic information provided by a lo­ calized domain description, the most relevant con­ straints tend to be applied at the right time, en­ abling a reduction in search space bushiness.

5 Empirical Results

All of our empirical experiences with GEMPLAN bear out the efficacy of localized search. Our largest appli­ cation thus far is a building-construction domain which requires both resource allocation and temporal coordi­ nation. The application was used to test and compare a variety of localization configurations. In our study, all of the localized configurations were superior to the non­ localized configuration. Even though planning for this domain manifested best-case search in both the local­ ized and non-localized cases (there was no backtracking), GEMPLAN attains speedups of greater than 50% using the best decomposition. This speedup can be attributed to a reduction in the cost of the constraint algorithms rather than a decrease in search space size. Exponen­ tial speedups can be expected for domains with bushier search spaces and more complex constraint algorithms.

Table 2 provides a variety of statistics about the tested decompositions (the system is written in Prolog and runs on a SPARC workstation). The "number of regions" column gives the total number of regions that have at least one constraint and one action in the final plan (this number corresponds to the m+ 1 factor in the complexity analysis). The "overlap" column gives two figures: an overlap count and an overlap size. The overlap count is the sum, over all regions of overlap, of how many parents each region of overlap has. To obtain overlap size, we additionally multiply the count for each region of overlap by the number of actions it contains. Overlap count and size provide good estimates of completion cost and are related to the mk factor in the complexity analsysis. The "weighted sum" column gives a pair of numbers: total and overlap. The total weighted sum is the sum, over each constraint check and fix that was performed, of the product of plan size and a constraint-difficulty weighting (ranging from 1 to 4). It thus gives a good measure of the constraint checking and fixing cost. The overlap weighted sum is the same sum over constraints belonging to regions of overlap. Finally, the "timing" column gives three numbers: the total CPU time in seconds, which is a sum of the time spent dealing with constraint application and the remaining time, spent mostly in search.

The table provides results for the creation of a 49action construction plan and for a 97 -action construction plan. Results are included for four domain decomposi­ tional strategies, with the 97-action plan simply hav­ ing more walls, contractors, etc. The first strategy is non-localized. The localized( 1) configuration is highly decomposed but also has significant amounts of overlap between regions. The localized(2) case has less local­ ization and much less overlap. Case localized(3) has an intermediate level of both localization and overlap, and attains the best results in both cases.

As with our formal analytical results, these results show that increased localization provides increased bene­ fit, except for the added expense due to regional overlap. However, notice that, in the 97-action case, localized(!) is faster than localized(2). This shows that, as plan size increases, the cost of dealing with overlap is overshad­ owed by search and constraint costs. Even though the size of the search space was not significantly different among the various decompositions (because there was no backtracking), search cost still increased with decreased localization. This is because the plan structures become unwieldy as plans become large and the search imple­ mentation is affected by the size of these structures.

6 Conclusion

This paper has described an algorithm for localized search, as well as complexity and empirical results that illustrate how localized search can provide substantial gains in performance. The idea is quite intuitive and natural, but has, surprisingly, not been a fundamental aspect of most AI systems. Its application to automated reasoning is vital if such systems are to meet the require­ ments of large, complex domains.

Acknowledgments

Lode Missiaen helped design and implement GEMPLAN's local­ ized search algorithm and Anna Karlin assisted with the complex­ ity results. John Bresina, Mark Drummond, Megan Eskey, Andrew Philpot, Monte Zweben, and the IJCAI reviewers provided useful comments.