The approach we have taken for abstract reasoning was originally inspired by earlier work involving a hierarchical behavior-space search where agents represent their planned behaviors at multiple levels of abstraction [Durfee Montgomery, 1991]. Distributed protocols are used to decide at what level of abstraction coordination is needed and to resolve conflicts there. This approach capitalizes on domains where resources can be abstracted naturally. This earlier work can be viewed as a very limited, special case of the work presented here. It is justified only intuitively and with limited experiments and analyses.
Corkill studied interleaved planning and merging in a distributed version of the NOAH planner corkill:79. He recognized that, while most of the conditions affected by an abstract plan operator might be unknown until further refinement, those that deal with the overall effects and preconditions that hold no matter how the operator is refined can be captured and used to identify and resolve some conflicts. He recognized that further choices of refinement or synchronization choices at more abstract levels could lead to unresolvable conflicts at deeper levels, and backtracking could be necessary. Our work is directed toward avoiding such backtracking by using summary information to guide search.
In closer relation to our approach, Pappachan shows how to interleave hierarchical plan coordination with plan execution for cooperative agents using an online iterative constraint relaxation (OICR) algorithm [Pappachan, 2001]. Like our approach, coordination can be achieved at higher levels of abstraction for more flexible execution, or the agents can decompose their tasks to lower levels for tighter coordination that can improve plan quality. The OICR approach is tailored toward interleaving coordination and flexible execution at the price of completeness while the coordination algorithm presented here is aimed at complete interleaved coordination and planning at the price of potentially delaying execution due to backtracking.
In planning research, hierarchical plans have often been represented as Hierarchical Task Networks (HTNs, erol:94), which planners such as NOAH [SacerdotiSacerdoti1977], Non, 1977], SIPE-2 [Wilkins, 1990], O-Plan [Currie Tate, 1991], UMCP [Erol, Nau, Hendler, 1994b], and SHOP2 [Nau, Au, Ilghami, Kuter, Murdock, Wu, Yaman, 2003] use to search through combinations of alternative courses of action to achieve goals within a particular context. These actions may be partially ordered, giving timing flexibility during execution [Wilkins, 1990, Currie Tate, 1991]. Our CHiP representation extends HTNs to include temporal extent and partial orderings can be expressed as constraints on the starting and ending timepoints of the action.
Yang presented a method (similar to our summarization) for
preprocessing a plan hierarchy in order to be able to detect
unresolvable conflicts at an abstract level so that the planner could
backtrack from inconsistent search spaces [Yang, 1990]. This
corresponds to the use of 
in Section
5.2. However, his approach requires that the
decomposition hierarchy be modeled so that each abstract operator have
a unique main subaction that has the same preconditions and
effects as the parent. We avoid this restriction by analyzing the
subplans' conditions and ordering constraints to automatically compute
the parent's summary conditions.
While our approach has focused on resolving conflicts among agents, cox:03 have used summary information to exploit synergistic interactions. The idea is that using summary information to identify overlapping effects can help agents skip actions whose effects are achieved by others. thang:03 have used summary information in rescheduling during execution. Their representations are actually subsumed by ours, and their work significantly postdates our first reporting of work in this paper [Clement Durfee, 1999].
DSIPE [desJardins Wolverton, 1999] is a distributed version of the SIPE-2 [Wilkins, 1990] hierarchical planning system. In the same way agents can use summary information to reduce communication to just those states for which they have common constraints, DSIPE filters conditions communicated among planners using irrelevance reasoning [Wolverton, desJardins, 1998].
The DPOCL (Decompositional Partial-Order Causal-Link) planner
[Young, Pollack, Moore, 1994] adds action decomposition to SNLP [McAllester, Rosenblitt, 1991].
Like other HTN planners, preconditions and high level effects can be
added to abstract tasks in order to help the planner resolve conflicts
during decomposition. In addition, causal links can be specified in
decomposition schemas to isolate external preconditions that DPOCL
must satisfy. However, because these conditions and causal links do
not necessarily capture all of the external conditions of abstract
tasks, the planner does not find solutions at abstract levels and
requires that all tasks be completely decomposed. In addition, DPOCL
cannot determine that an abstract plan has unresolvable conflicts
() because there may be effects hidden in the
decompositions of yet undetailed tasks that could achieve open
preconditions. By deriving summary conditions automatically and using
algorithms for determining causal link information
(e.g. must-achieve), our planning/coordination algorithm can find and reject abstract plans
during search without adding burden to the domain expert to specify
redundant conditions or causal links for abstract tasks.
Like DPOCL, TÆMS (a framework for Task Analysis, Environment Modeling, and Simulation) allows the domain modeler to specify a wide range of task relationships [Decker, 1995]. This work offers quantitative methods for analyzing and simulating agents as well as their interactions. While only some of these interactions can be represented and discovered using summary conditions, we discover this information through analysis rather than depending on the model developer to predefine the interactions.
Grosz and Kraus's shared plans model of collaboration [Grosz Kraus, 1995] presents a theory for modeling multiagent belief and intention. While the shared plans work is directed toward cooperative agents, it represents action hierarchies and provides mental models at a higher level than represented in this article. However, our use and analysis of summary information complements Grosz's work by providing a way to automatically represent and efficiently reason about the intentions of agents at multiple levels of abstraction. Future work is needed to understand how summary information can be bridged with mental states of agents to exploit the techniques employed in shared plans and other work based on BDI (belief-desire-intention) models of agents [Rao, Georgeff, 1995].
An analysis of hierarchical planning [Yang, 1997] explains that, in the case of interacting subgoals, certain structures of the hierarchy that minimize these interactions can reduce worst case planning complexity exponentially. However, the complexity analyses in Section 6 explain how using summary information can achieve exponential performance gains in addition to those achieved by restructuring plan hierarchies according to Yang's analysis by limiting the decomposition of task hierarchies and compressing the information manipulated by a coordinator, planner, or scheduler.
SHOP2 [Nau, Au, Ilghami, Kuter, Murdock, Wu, Yaman, 2003] is an HTN planner that uses a domain translation technique to reason about durative action. This however does not express temporal extent in the same way as the planner given here. Our model differs in that it supports ordering relationships on endpoints as well as conditions and effects during an action's execution. While there may be some domain translation that could achieve the expression of similar constraints and solutions for other systems, ours is the only formal model of such expressions in HTN planning.
SIADEX [Castillo, Fdez-Olivares, García-Pérez, Palao, 2006] is another HTN planner that handles temporal extent in the use of more expressive simple temporal networks [Dechter, Meiri, Pearl, 1991]. The performance improvement techniques reported for SIADEX are in temporal reasoning and not specific to HTNs. Thus, this work is complementary to ours. However, more work is needed to understand how summary information can be exploited in conjunction with the forward expansion approach that both SHOP2 and SIADEX use to perform competitively on planning competition problems.
Another class of hierarchical planners based on ABSTRIPS [Sacerdoti, 1974] introduces conditions at different levels of abstraction so that more critical conflicts are handled at higher levels of abstraction and less important (or easier) conflicts are resolved later at lower levels. While this approach similarly resolves conflicts at abstract levels, the planning decisions may not be consistent with conditions at lower levels resulting in backtracking. Summary information provides a means to make sound and complete decisions at abstract levels without the need to decompose and check consistency with lower levels. However, resolving conflicts based on criticality can still improve performance in complement to our approach.
Allen's temporal planner allen:91 uses hierarchical representations of tasks and could be applied to reasoning about the concurrent actions of multiple agents. However, it does not exploit hierarchy by reasoning about abstraction levels separately and generates a plan by proving the consistency of the collective constraints. Allen's model of temporal plans allen:83b and subsequent work on interval point algebra [Vilain, Kautz, 1986] strongly influenced our hierarchical task representation and algorithms that reason about them.
There are also many, many models and theories of concurrency. Some
older examples include automata representations, Petri nets and
Hoare's theory of communicating sequential processes
[Glabbeek, 1997]. There are also many temporal logics such as
computational tree logic (CTL, ctl) that allow modal
expressions about a proposition holding in some or all possible worlds
some of the time, all of the time, in the next state, eventually, or
until some other proposition holds. Another language for specifying
manufacturing processes has been in the process of being standardized
over 10 years [Bock, 1996, Schlenoff, Knutilla, Ray, 2006]. Many of these logics could have been
used to define summary conditions and relations like 
.
However, we found that these logics were awkward for representing
inconditions and defining summary conditions and that the terminology
used in this article simplifies the definitions.
Model checking uses temporal logics to verify different properties of system models, software, and hardware (such as correctness, deadlock-free, and convergence). In fact, model checking and planning algorithms can be used interchangeably on the same problems []<e.g.,>giunchiglia:99. In the context of model checking, summary information is a set of properties (akin to those specifiable in CTL) of a system model (as a planning domain) that summarize system variable requirements (conditions) and assignments (effects). Thus, a model checking algorithm could use this summary information to efficiently identify and resolve potential requirement violations/bugs (condition conflicts) or deadlock (resource conflicts) in a system model or its operation (planning/scheduling problem instantiations).