Journal of Artificial Intelligence Research, 28 (2007) 453-515. Submitted 8/06; published 4/07

© 2007 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

Abstract Reasoning for Planning and Coordination

Bradley J. Clement
Jet Propulsion Laboratory, Mail Stop: 301-260
Pasadena, CA 91109 USA
brad.clement@jpl.nasa.gov

Edmund H. Durfee
Electrical Engineering and Computer Science Department
University of Michigan,Ann Arbor, MI 48109 USA
durfee@umich.edu

Anthony C. Barrett
Jet Propulsion Laboratory, Mail Stop: 301-260
Pasadena, CA 91109 USA
tony.barrett@jpl.nasa.gov

Abstract:

The judicious use of abstraction can help planning agents to identify key interactions between actions, and resolve them, without getting bogged down in details. However, ignoring the wrong details can lead agents into building plans that do not work, or into costly backtracking and replanning once overlooked interdependencies come to light. We claim that associating systematically-generated summary information with plans' abstract operators can ensure plan correctness, even for asynchronously-executed plans that must be coordinated across multiple agents, while still achieving valuable efficiency gains. In this paper, we formally characterize hierarchical plans whose actions have temporal extent, and describe a principled method for deriving summarized state and metric resource information for such actions. We provide sound and complete algorithms, along with heuristics, to exploit summary information during hierarchical refinement planning and plan coordination. Our analyses and experiments show that, under clearcut and reasonable conditions, using summary information can speed planning as much as doubly exponentially even for plans involving interacting subproblems.

1 Introduction

Abstraction is a powerful tool for solving large-scale planning and scheduling problems. By abstracting away less critical details when looking at a large problem, an agent can find an overall solution to the problem more easily. Then, with the skeleton of the overall solution in place, the agent can work additional details into the solution [Sacerdoti 1974, Tsuneto, Hendler, Nau, 1998]. Further, when interdependencies are fully resolved at abstract levels, then one or more agents can flesh out sub-pieces of the abstract solution into their full details independently (even in parallel) in a ``divide-and-conquer'' approach [Korf, 1987, Lansky, 1990, Knoblock, 1991].

Unfortunately, it is not always obvious how best to abstract large, complex problems to achieve these efficiency improvements. An agent solving a complicated, many-step planning problem, for example, might not be able to identify which of the details in earlier parts will be critical for later ones until after it has tried to generate plans or schedules and seen what interdependencies end up arising. Even worse, if multiple agents are trying to plan or schedule their activities in a shared environment, then unless they have a lot of prior knowledge about each other, it can be extremely difficult for one agent to anticipate which aspects of its own planned activities are likely to affect, and be affected by, other agents.

In this paper, we describe a strategy that balances the benefits and risks of abstraction in large-scale single-agent and multi-agent planning problems. Our approach avoids the danger of ignoring important details that can lead to incorrect plans (whose execution will fail due to overlooked interdependencies) or to substantial backtracking when abstract decisions cannot be consistently refined. Meanwhile, our approach still achieves many of the computational benefits of abstraction so long as one or more of a number of reasonable conditions (listed later) holds.

The key idea behind our strategy is to annotate each abstract operator in a plan hierarchy with summary information about all of its potential needs and effects under all of its potential refinements. While this might sound contrary to the purpose of abstraction as reducing the number of details, in fact we show that it strikes a good balance. Specifically, because all of the possibly relevant conditions and effects are modeled, the agent or agents that are reasoning with abstract operators can be absolutely sure that important details cannot be overlooked. However, because the summary information abstracts away details about under which refinement choices conditions and effects will or will not be manifested, and information about the relative timing of when conditions are needed and effects achieved, it still often results in an exponential reduction in information compared to a flat representation.

Based on the concept of summary information, this paper extends the prior work summarized below and in Section 8 to make the following contributions:

1.0.0.1 A formal model of hierarchical plans with temporal extent, and of their execution.

While many planning systems have sophisticated temporal models []<e.g.,>laborie:95,muscettola:94 and some additionally use hierarchical representations of alternative courses of action [Allen, Kautz, Pelavin, Tenenberg, 1991, Currie Tate, 1991, Chien, Knight, Stechert, Sherwood, Rabideau, 2000a, Castillo, Fdez-Olivares, García-Pérez, Palao, 2006], we know of no other work that extends the hierarchical task network (HTN) formalization [Erol, Hendler, Nau, 1994a, Erol, Nau, Hendler, 1994b] to include temporal extent. We need such a formalism in order to clarify the semantics of summary information and concurrently executing agents.

1.0.0.2 Algorithms for deriving summary information about propositional and metric resource conditions and effects, and for using such information to determine potential and definite interactions between abstract tasks.

We prove that our summarization techniques are guaranteed to correctly capture all of the conditions and effects associated with an abstract operator appropriately, augmented with modal information about whether conditions must or may hold and whether they hold during the entire operation or only for some of the time. Because summary information captures all conditions and effects, our algorithms can reason with operators at different levels of abstraction to predict and often resolve operator interactions without fully detailing task hierarchies, even for operators that are executing asynchronously at different agents.

1.0.0.3 Sound and complete algorithms for hierarchical refinement planning and centralized plan coordination for actions with temporal extent, supporting flexible plan execution systems.

An agent can reduce backtracking during planning by selectively interleaving the refinement of its plan with predicting and resolving potential interdependencies between its evolving plan and the plans that will be asynchronously executed by other agents. Other research has also found benefit in guiding refinement with conditions specified at higher levels in the plan hierarchy to guide refinement [Sacerdoti, 1974, Young, Pollack, Moore, 1994, Tsuneto, Hendler, Nau, 1998]. We show that our algorithms improve on these capabilities by exploiting the hierarchical structure using summary information to more efficiently converge on coordinated plans, which can then be further refined individually and in parallel by the participating agents.

This ability to coordinate at abstract levels rather than over detailed plans allows each of the agents to retain some local flexibility to refine its operators as best suits its current or expected circumstances without jeopardizing coordination or triggering new rounds of renegotiation. In this way, summary information supports robust execution systems such as PRS [Georgeff Lansky, 1986], UMPRS [Lee, Huber, Durfee, Kenny, 1994], RAPS [Firby, 1989], JAM [Huber, 1999], etc. that interleave the refinement of abstract plan operators with execution.

Our approach also extends plan coordination (plan merging) techniques [Georgeff, 1983, Lansky, 1990, Ephrati Rosenschein, 1994] by utilizing plan hierarchies and a more expressive temporal model. Prior techniques assume that actions are atomic, meaning that an action either executes before, after, or at exactly the same time as another. In contrast, we use interval point algebra [Vilain Kautz, 1986] to represent the possibility of several actions of one agent executing during the execution of one action of another agent. Because our algorithms can choose from alternative refinements in the HTN dynamically in the midst of plan coordination, they support interleaved local planning, multiagent coordination, and concurrent execution.

1.0.0.4 Search techniques and heuristics, including choose-fewest-threats-first (CFTF) and expand-most-threats-first (EMTF), that take advantage of summary information to prune the search space.

When interdependencies run more deeply in agents' plans, resolving them at abstract levels, if possible at all, can lead to unacceptable losses in parallel activity. Fortunately, even when agents need to delve into the details of their plans to tease out interdependencies, summary information can still enable exponential speedups by guiding decomposition and by pruning refinement choices. The search efficiency of using summary information comes from ignoring irrelevant information, which in a distributed planning system also reduces communication overhead exponentially.

1.0.0.5 Complexity analyses and experiments showing potential doubly-exponential speedups in refinement and local search planning/scheduling using summary information.

Our algorithms demonstrate that exploiting summary information to guide hierarchical planning and scheduling can achieve exponential speedups, and resolving interdependencies at abstract levels can improve the performance of plan coordination algorithms doubly exponentially. While others have shown that abstraction can exponentially reduce search space size [Korf, 1987, Knoblock, 1991] when subproblem independence properties hold, we show that our techniques lead to exponential improvements if any of these broader conditions hold for the problem:

• solutions can be found at abstract levels;
• the amount of summary information is less at higher levels than at lower levels; or
• choices of decompositions lead to varying numbers of plan threats.

When none of these conditions hold, we show that generating and using summary information provides no benefit and can increase computation and communication overhead. Thus, care must be taken when deciding to use summary information, though it has proven to be extremely worthwhile in the types of problem domains we have examined, an example of which we next describe.

1.1 Manufacturing Example

As a running example to motivate this work, consider a manufacturing plant where a production manager, a facilities manager, and an inventory manager each have their own goals with separately constructed hierarchical plans to achieve them. However, they still need to coordinate over the use of equipment, the availability of parts used in the manufacturing of other parts, storage for the parts, and the use of transports for moving parts around. The state of the factory is shown in Figure 1. In this domain, agents can produce parts using machines M1 and M2, service the machines with a tool, and move parts to and from the shipping dock and storage bins on the shop floor using transports. Initially, machines M1 and M2 are free for use, and the transports (transport1 and transport2), the tool, and all of the parts (A through E) shown in their storage locations are available.

Figure 1: A simple example of a manufacturing domain

The production manager is responsible for creating a part H using machines M1 and M2. Either M1 and M2 can consume parts A and B to produce G, and M2 can produce H from G. The production manager's hierarchical plan for manufacturing H involves using the transports to move the needed parts from storage to the input trays of the machines, manufacturing G and H, and transporting H back to storage. This plan is shown in Figure 2. Arcs through subplan branches mean that all subplans must be executed. Branches without arcs denote alternative choices to achieving the parent's goal. The decomposition of $produce\_G\_on\_M1$ is similar to that of $produce\_G\_on\_M2$.

Figure 2: The production manager's hierarchical plan

The facilities manager services each machine by equipping it with a tool and then calibrating it. The machines are unavailable for production while being serviced. The facilities manager's hierarchical plan branches into choices of servicing the machines in different orders and uses the transports for getting the tool from storage to the machines (Figure 3). The decomposition of $service\_M2M1$ is similar to that of $service\_M1M2$.

Figure 3: The facilities manager's hierarchical plan

The parts must be ``available'' on the space-limited shop floor in order for an agent to use them. Whenever an agent moves or uses a part, it becomes unavailable. The inventory manager's goal is just to move part C to the dock and move D and E into bins on the shop floor (shown in Figure 4).

Figure 4: The inventory manager's hierarchical plan

To accelerate the coordination of their plans, each factory manager can analyze his hierarchical plan to derive summary information on how each abstract plan operator can affect the world. This information includes the summary pre-, post-, and in-conditions that intuitively correspond to the externally required preconditions, externally effective postconditions, and the internally required conditions, respectively, of the plan based on its potential refinements. Summary conditions augment state conditions with modal information about whether the conditions must or may hold and when they are in effect. Examples are given at the end of Section 3.2.

Once summary information is computed, the production and inventory managers each could send this information for their top-level plan to the facilities manager. The facilities manager could then reason about the top-level summary information for each of their plans to determine that if the facilities manager serviced all of the machines before the production manager started producing parts, and the production manager finished before the inventory manager began moving parts on and off the dock, then all of their plans can be executed (refined) in any way, or $CanAnyWay$. Then the facilities manager could instruct the others to add communication actions to their plans so that they synchronize their actions appropriately.

This top-level solution maximizes robustness in that the choices in the production and facilities managers' plans are preserved, but the solution is inefficient because there is no concurrent activity--only one manager is executing its plan at any time. The production manager might not want to wait for the facilities manager to finish maintenance and could negotiate for a solution with more concurrency. In that case, the facilities manager could determine that they could not overlap their plans in any way without risking conflict ($\neg CanAnyWay$). However, the summary information could tell them that there might be some way to overlap their plans ($MightSomeWay$), suggesting that a search for a solution with more concurrency (at the cost of perhaps committing to specific refinement choices) has hope of success. In this case, the facilities manager could request the production manager for the summary information of each of $produce\_H$'s subplans, reason about the interactions of lower level actions in the same way, and find a way to synchronize the subplans for a more fine-grained solution where the plans are executed more concurrently. We give an algorithm for finding such solutions in Section 5.

1.2 Overview

We first formally define a model of a concurrent hierarchical plan, its execution, and its interactions (Section 2). Next, we describe summary information for propositional states and metric resources, mechanisms determining whether particular interactions must or may hold based on this information, and algorithms for deriving the information (Section 3). Built upon these algorithms are others for using summary information to determine whether a set of CHiPs must or might execute successfully under a set of ordering constraints (Section 4). These in turn are used within a sound and complete multilevel planning/coordination algorithm that employs search techniques and heuristics to efficiently navigate and prune the search space during refinement (Section 5). We then show how planning, scheduling, or coordinating at abstract levels can exponentially improve the performance of search and execution (Section 6). We provide experimental results demonstrating that the search techniques also greatly reduce the search for optimal solutions (Section 7). Finally, in Section 8 we differentiate our approach from related work that we did not mention elsewhere and conclude.

2 A Model of Hierarchical Plans and their Concurrent Execution

A representation of temporal extent in an HTN is important not only for modeling concurrently executing agents but also for performing abstract reasoning with summary information. If an agent is scheduling abstract actions and can only sequentially order them, it will be severely restricted in the kinds of solutions it can find. For example, the agent may prefer solutions with shorter makespans, and should seek plans with subthreads that can be carried out concurrently.

In this section we define concurrent hierarchical plans (CHiPs), how the state changes over time based on their executions, and concepts of success and failure of executions in a possible world, or history. Because we later define summary information and abstract plan interactions in terms of the definitions and semantics given in this section, the treatment here is fairly detailed (though for an even more comprehensive treatment, see [Clement, 2002]). However, we begin by summarizing the main concepts and notation introduced, to give the reader the basic gist.

2.1 Overview

A CHiP (or plan $p$) is mainly differentiated from an HTN by including in its definition inconditions, $in(p)$, (sometimes called ``during conditions'') that affect (or assert a condition on) the state just after the start time of $p$ ($t_s(p)$) and must hold throughout the duration of $p$. Preconditions ($pre(p)$) must hold at the start, and postconditions ($post(p)$) are asserted at the finish time of $p$ ($t_f(p)$). Metric resource ($res$) consumption ($usage(p,res)$) is instantaneous at the start time and, if the resource is defined as non-consumable, is instantaneously restored at the end. The decompositions of $p$ ($d(p)$) is in the style of $and$/$or$ tree, having either a partial ordering ($order(p)$) or a choice of child tasks that each can have their own conditions.

An execution $e$ of $p$ is an instantiation of its start time, end time, and decomposition. That is, an execution nails down exactly what is done and when. In order to reason about plan interactions, we can quantify over possible histories, where each history corresponds to a combination of possible executions of the concurrently-executing CHiPs for a partial ordering over their activities and in the context of an initial state. A run ($r(h,t)$) specifies the state at time $t$ for history $h$.

Achieve, clobber, and undo interactions are defined in terms of when the executions of some plans assert a positive literal $\ell$ or negative literal $\neg\ell$ relative to when $\ell$ is required by another plan's execution for a history. By looking at the literals achieved, clobbered, and undone in the set of executions in a history, we can identify the conditions that must hold prior to the executions in the history as external preconditions and those that must hold after all of the executions in the history as external postconditions.

The value of a metric resource at time $t$ ($r(res,h,t)$) is calculated by subtracting from the prior state value the usage of all plans that start executing at $t$ and (if non-consumable) adding back usages of all that end at $t$. An execution $e$ of $p$ fails if a condition that is required or asserted at time $t$ is not in the state $r(h,t)$ at $t$, or if the value of a resource ($r(res,h,t)$) used by the plan is over or under its limits during the execution.

In the remainder of this section, we give more careful, detailed descriptions of the concepts above, to ground these definitions in firm semantics; the more casual reader can skim over these details if desired. It is also important to note that, rather than starting from scratch, our formalization weaves together, and when necessary augments, appropriate aspects of other theories, including Allen's temporal plans allen:83b, Georgeff's theory for multiagent plans georgeff:84, and Fagin et al.'s theory for multiagent reasoning about knowledge RAK.

2.2 CHiPs

A concurrent hierarchical plan $p$ is a tuple $\langle pre$, $in$, $post$, $usage$, $type$, $subplans$, $order\rangle$. $pre(p)$, $in(p)$, and $post(p)$ are sets of literals ($v$ or $\neg v$ for some propositional variable $v$) representing the preconditions, inconditions, and postconditions defined for plan $p$.¹

We borrow an existing model of metric resources [Chien, Rabideu, Knight, Sherwood, Engelhardt, Mutz, Estlin, Smith, Fisher, Barrett, Stebbins, Tran, 2000b, Laborie Ghallab, 1995]. A plan's $usage$ is a function mapping from resource variables to an amount used. We write $usage(p,res)$ to indicate the amount $p$ uses of resource $res$ and sometimes treat $usage(p)$ as a set of pairs $(res, amount)$. A metric resource $res$ is a tuple $\langle min\_value$, $max\_value$, $type\rangle$. The min and max values can be integer or real values representing bounds on the capacity or amount available. The $type$ of the resource is either consumable or non-consumable. For example, fuel and battery energy are consumable resources because, after use, they are depleted by some amount. A non-consumable resource is available after use (e.g. vehicles, computers, power).

Domain modelers typically only specify state conditions and resource usage for primitive actions in a hierarchy. Thus, the conditions and usage of a CHiP are used to derive summary conditions, as we describe in Section 3.4, so that algorithms can reason about any action in the hierarchy. In order to reason about plan hierarchies as and/or trees of actions, the $type$ of plan $p$, or $type(p)$, is given a value of either $primitive$, $and$, or $or$. An $and$ plan is a non-primitive plan that is accomplished by carrying out all of its subplans. An $or$ plan is a non-primitive plan that is accomplished by carrying out exactly one of its subplans. So, $subplans$ is a set of plans, and a $primitive$ plan's $subplans$ is the empty set. $order(p)$ is only defined for an $and$ plan $p$ and is a consistent set of temporal relations [Allen, 1983] over pairs of subplans. Plans left unordered with respect to each other are interpreted to potentially execute concurrently.

The decomposition of a CHiP is in the same style as that of an HTN as described by erol:94. An $and$ plan is a task network, and an $or$ plan is an extra construct representing a set of all methods that accomplish the same goal or compound task. A network of tasks corresponds to the subplans of a plan.

For the example in Figure 2, the production manager's highest level plan $produce\_H$ (Figure 2) is the tuple $$\langle\{\}, \{\}, \{\}, \{\}, and, \{produce\_G, produce\_H\_from\_G\}, \{before(0, 1) \}\rangle.$$ In $before$(0,1), 0 and 1 are indices of the subplans in the decomposition referring to $produce\_G$ and $produce\_H\_from\_G$ respectively. There are no conditions defined because $produce\_H$ can rely on the conditions defined for the primitive plans in its refinement. The plan for moving part A from bin1 to the first input tray of M1 using transport1 is the tuple $$\langle\{ \}, \{ \}, \{ \}, \{\}, and, \{start\_move, finish\_move\}, \{meets(0, 1)\}\rangle.$$ This plan decomposes into two half moves which help capture important intermediate effects. The parent orders its children with the $meets$ relation to bind them together into a single move. The $start\_move$ plan is $$\begin{array}{@{}l@{}l} \langle & \{at(A,bin1), available(A)... ...tray1) \},\\ & \{\}, primitive, \{\}, \{\}\rangle. \end{array}$$ The $finish\_move$ plan is $$\begin{array}{@{}l@{}l} \langle & \{\neg at(A, bin1), \neg a... ...tray1)\}, \\ & \{\}, primitive, \{\}, \{\}\rangle. \end{array}$$ We split the move plan into these two parts in order to ensure that no other action that executes concurrently with this one can use transport1, part A, or the input tray to M1. It would be incorrect to instead specify $\neg free$(transport1) as an incondition to a single plan because another agent could, for instance, use transport1 at the same time because its $\neg free$(transport1) incondition would agree with the $\neg free$(transport1) incondition of this move action. However, the specification here is still insufficient since two pairs of ($start\_move$, $finish\_move$) actions could start and end at the same time without conflict. We can get around this by only allowing the planner to reason about the $move\_plan$ and its parent plans, in effect, hiding the transition between the start and finish actions. So, by representing the transition from $free$ to $\neg free$ without knowing when that transition will take place the modeler ensures that another move plan that tries to use transport1 concurrently with this one will cause a conflict.²

A postcondition is required for each incondition to specify whether the incondition changes. This clarifies the semantics of inconditions as conditions that hold only during plan execution whether because they are caused by the action or because they are necessary conditions for successful execution.

2.3 Executions

Informally, an execution of a CHiP is recursively defined as an instance of a decomposition and an ordering of its subplans' executions. Intuitively, when executing a plan, an agent chooses the plan's start time and how it is refined, determining at what points in time its conditions must hold, and then witnesses a finish time. The formalism helps us reason about the outcomes of different ways to execute a group of plans, describe state transitions, and define summary information.

An execution $e$ of CHiP $p$ is a tuple $\langle d, t_s, t_f\rangle$. $t_s(e)$ and $t_f(e)$ are positive, non-zero real numbers representing the start and finish times of execution $e$, and $t_s < t_f$. Thus, instantaneous actions are not explicitly represented. $d(e)$ is a set of subplan executions representing the decomposition of plan $p$ under this execution $e$. Specifically, if $p$ is an $and$ plan, then it contains exactly one execution from each of the subplans; if it is an $or$ plan, then it contains only one execution of one of the subplans; and it is empty if it is $primitive$. In addition, for all subplan executions, $e'\in d$, $t_s(e')$ and $t_f(e')$ must be consistent with the relations specified in $order(p)$. Also, the first subplan(s) to start must start at the same time as $p$, $t_s(e')=t_s(e)$, and the last subplan(s) to finish must finish at the same time as $p$, $t_f(e')=t_f(e)$. The possible executions of a plan $p$ is the set $\mathcal{E}$$(p)$ that includes all possible instantiations of an execution of $p$, meaning all possible values of the tuple $\langle d, t_s, t_f\rangle$, obeying the rules just stated.

For the example in Section 1.1, an execution for the production manager's top-level plan $produce\_H$ would be some $e\in\mathcal{E}$$(produce\_H)$. $e$ might be $\langle\{e_1$, $e_2\}$, 2.0, 9.0 $\rangle$ where $e_1\in\mathcal{E}$$(produce\_G)$, and $e_2\in\mathcal{E}$$(produce\_H\_from\_G)$. This means that the execution of $produce\_H$ begins at time 2.0 and ends at time 9.0.

For convenience, the subexecutions of an execution $e$, or $subex(e)$, is defined recursively as the set of subplan executions in $e$'s decomposition unioned with their subexecutions.

2.4 Histories and Runs

An agent reasoning about summary information to make planning decisions at abstract levels needs to first be able to reason about CHiPs. In this section we complete the semantics of CHiPs by describing how they affect the state over time. Because an agent can execute a plan in many different ways and in different contexts, we need to be able to quantify over possible worlds (or histories) where agents fulfill their plans in different ways. After defining a history, we define a run as the transformation of state over time as a result of the history of executions. The formalization of histories and runs follows closely to that of RAK in describing multiagent execution.

A state of a world, $s$, is a truth assignment to a set of propositions, each representing an aspect of the environment. We will refer to the state as the set of true propositional variables. A history, $h$, is a tuple $\langle E, s_I\rangle$. $E$ is the set of all plan executions of all agents occurring in $h$, and $s_I$ is the initial state of $h$ before any plan begins executing. So, a history $h$ is a hypothetical world that begins with $s_I$ as the initial state and where only executions in $E(h)$ occur. In particular, a history for the manufacturing domain might have an initial state as shown in Figure 1 where all parts and machines are available, and both transports are free. The set of executions $E$ would contain the execution of $produce\_H$, $maintenance$, $move\_parts$, and their subexecutions.

A run, $r$, is a function mapping a history and time point to states. It gives a complete description of how the state of the world evolves over time, where time ranges over the positive real numbers.

Axiom 1   $$r(h,0) = s_I$$

Axiom 2   $$\begin{array}{@{}l@{}l@{}l} v \in r(h,t>0) \Leftrightarrow &... ...(\neg v \in post(p') \wedge t_f(e_{p'}) = t)) \par \end{array}$$

Axiom 1 states that the world is in the initial state at time zero. Axiom 2 states that a predicate $v$ is true at time $t$ if it was already true beforehand, or a plan asserts $v$ with an incondition or postcondition at $t$, but (in either case) no plan asserts $\neg v$ at $t$. If a plan starts at $t$, then its inconditions are asserted right after the start, $t+\epsilon$, where $\epsilon$ is a small positive real number. Axiom 2 also indicates that both inconditions and postconditions are effects.

The state of a resource is a level value (integer or real). For consumable resource usage, a task that depletes a resource is modeled to instantaneously deplete the resource (subtract $usage$ from the current state) at the start of the task by the full amount. For non-consumable resource usage, a task also depletes the usage amount at the start of the task, but the usage is restored (added back to the resource state) at the end of execution. A task can replenish a resource by having a negative $usage$. We will refer to the level of a resource $res$ at time $t$ in a history $h$ as $r(res,h,t)$. Axioms 3 and 4 describe these calculations for consumable and non-consumable resources, respectively.

Axiom 3   $$\begin{array}{@{}l@{}l@{}l} r(consumable\_res,h,t) = r(consu... ..._{e_p\in E(h), t_s(e_p)=t} usage(p,consumable\_res) \end{array}$$

Axiom 4   $$\begin{array}{@{}l@{}l@{}l} r(nonconsumable\_res,h,t) = &r(n... ..._p\in E(h), t_f(e_p)=t} usage(p,nonconsumable\_res) \end{array}$$

Now that we have described how CHiPs change the state, we can specify the conditions under which an execution succeeds or fails. As stated formally in Definition 1, an execution succeeds if: the plan's preconditions are met at the start; the postconditions are met at the end; the inconditions are met throughout the duration (not including the start or end); all used resources stay within their value limits throughout the duration; and all executions in the decomposition succeed. Otherwise, the execution fails.

Definition 1   $$\begin{array}{@{}l@{}l} succeeds(e_p, h) \equiv &pre(p) \sub... ...nd{array} \\ &\forall e \in d(e_p), succeeds(e,h) \end{array}$$

2.5 Asserting, Clobbering, Achieving, and Undoing

Conventional planning literature often speaks of clobbering and achieving preconditions of plans [Weld, 1994]. In CHiPs, these notions are slightly different since inconditions can clobber and be clobbered, as seen in the previous section. Formalizing these concepts and another, undoing postconditions, helps us define summary conditions (in Section 3.2). However, it will be convenient to define first what it means to assert a condition. Figure 5 gives examples of executions involved in these interactions, and we define these terms as follows:

Definition 2   $$\begin{array}{@{}l@{}l@{}l} asserts(e_p,\ell,t,h) \equiv &(&... ...ge t = t_f(e_p)) \wedge \\ &(&r(t,h) \vdash \ell) \end{array}$$

Definition 2 states that an execution $e_p$ in a history $h$ asserts a literal at time $t$ if that literal is an effect of $p$ that holds in the state at $t$. Note that that from this point on, beginning in Definition 3, we use brackets [ ] as a shorthand when defining similar terms and procedures. For example, saying ``[$a$, $b$] implies [$c$, $d$]'' means $a$ implies $c$, and $b$ implies $d$. This shorthand will help us avoid repetition, at the cost of slightly more difficult parsing.

Definition 3   $$\begin{array}{@{}l@{}l@{}l} [ach&ieves,clobbers] \_precondit... ...{p''},\neg\ell,t'',h)) \wedge t<t''\leq t_s(e_{p'}) \end{array}$$

Definition 4   $$\begin{array}{@{}l@{}l@{}l} clob&bers\_[in,post]condition(e_... ...] \wedge [t_s(e_{p'})<t<t_s(e_{p'}), t=t_f(e_{p'})] \end{array}$$

Definition 5   $$\begin{array}{@{}l@{}l@{}l} undo&es(e_p,\ell,e_{p'},t,h) \eq... ...'},\neg\ell,t'',h)) \wedge t_f(e_{p'}) \leq t'' < t \end{array}$$

So, an execution achieves or clobbers a precondition if it is the last (or one of the last) to assert the condition or its negation (respectively) before it is required. Likewise, an execution undoes a postcondition if it is the first (or one of the first) to assert the negation of the condition after the condition is asserted. An execution $e$ clobbers an incondition or postcondition of $e'$ if $e$ asserts the negation of the condition during or at the end (respectively) of $e'$. Achieving effects (inconditions and postconditions) does not make sense for this formalism, so it is not defined. Figure 5 shows different ways an execution $e$ achieves, clobbers, and undoes an execution $e'$. $\ell$ and $\neg\ell$ point to where they are asserted or required to be met.

Figure 5: Interval interactions of plan steps

2.6 External Conditions

As recognized by tsuneto:98, external conditions are important for reasoning about potential refinements of abstract plans. Although the basic idea is the same, we define them a little differently and call them external preconditions to differentiate them from other conditions that we call external postconditions. Intuitively, an external precondition of a group of partially ordered plans is a precondition of one of the plans that is not achieved by another in the group and must be met external to the group. External postconditions, similarly, are those that are not undone by plans in the group and are net effects of the group. Definition 6 states that $\ell$ is an external [pre, post]condition of an execution $e_p$ if $\ell$ is a [pre, post]condition of a subplan for which it is not [achieved, undone] by some other subplan.

Definition 6   $$\begin{array}{@{}l@{}l@{}l} exte&rnal\_[pre,post]condition(\... ...st]condition(e_{p''}, \ell, e_{p'},t,h)) \end{array}\end{array}$$

For the example in Figure 2, $available(G)$ is not an external precondition because, although G must exist to produce H, G is supplied by the execution of the $produce\_G$ plan. Thus, $available(G)$ is met internally, making $available(G)$ an internal condition. $available(M1)$ is an external precondition, an internal condition, and an external postcondition because it is needed externally and internally; it is an effect of $produce\_G\_on\_M1$ which releases M1 when it is finished; and no other plan in the decomposition undoes this effect.

3 Plan Summary Information

Summary information can be used to find abstract solutions that are guaranteed to succeed no matter how they are refined because the information describes all potential conditions of the underlying decomposition. Thus, some commitments to particular plan choices, whether for a single agent or between agents, can be made based on summary information without worrying that deeper details lurk beneath that will doom the commitments. While HTN planners have used abstract conditions to guide search []<e.g.,>sacerdoti:74,tsuneto:98, they rely on a user-defined subset of constraints that can only help detect some potential conflicts. In contrast, summary information can be used to identify all potential conflicts.

Having the formalisms of the previous section, we can now define summary information and describe a method for computing it for non-primitive plans (in Section 3.4). Because there are many detailed definitions and algorithms in this section, we follow the same structure here as in the previous section, where we first give a more informal overview of the key concepts and notation, into which we then subsequently delve more systematically.

3.1 Overview

The summary information of plan $p$ consists of summary pre-, in-, and postconditions ($pre_{sum}(p)$, $in_{sum}(p)$, $post_{sum}(p)$), summary resource usage ($usage_{sum}(p,res)$) for each resource $res$, and whether the plan can be executed in any way successfully ($consistent$).

A summary condition (whether pre, post, or in) specifies not only a positive or negated literal, but additional modal information. Each summary condition has an associated $existence$, whose value is either $must$ or $may$ depending on whether it must hold for all possible decompositions of the abstract operator or just may hold depending on which decomposition is chosen. The $timing$ of a summary condition is either $first$, $last$, $always$, or $sometimes$, specifying when the condition must hold in the plan's interval of execution. A plan $p_1$ must [achieve, clobber] summary precondition $c_2$ of $p_2$ if the execution of $p_1$ (or that of any plan with the same summary information) would [achieve, clobber] a condition summarized by $c_2$ (or any plan with the same summary information as $p_2$).

The algorithm for deriving summary conditions for plan $p$ takes as input the summary conditions of the immediate subplans of $p$ and the conditions defined for the CHiP $p$. The pre-, in-, and postconditions of $p$ become must first, must always, and must last summary conditions, respectively. The algorithm retains the existence and timing of subplan summary conditions in the parent depending on whether the conditions are achieved, clobbered, or undone by siblings, whether the decomposition is $and$ or $or$, whether the subplan is ordered first or last, and whether all subplans share the same condition. Subplan first, always, and last conditions can become sometimes conditions in the parent. The parent is computed as $consistent$ as long as all subplans are $consistent$, no subplan may clobber a summary condition of another, and summarized resources do not violate limits.

We represent summary resource usage as three value ranges, $\langle local\_min$, $local\_max$, $persist \rangle$, where the resource's local usage occurs within the task's execution, and the persistent usage represents the usage that lasts after the task terminates for depletable resources. The summarization algorithm for an abstract task takes the summary resource usages of its subtasks, considers all legal orderings of the subtasks, and all possible usages for all subintervals within the interval of the abstract task, to build multiple usage profiles. These profiles are combined with algorithms for computing parallel, sequential, and disjunctive usages to give the summary usage of the parent task.

3.2 Summary Conditions

The summary information for a plan $p$, $p_{sum}$, is a tuple $\langle pre_{sum}$, $in_{sum}$, $post_{sum}$, $usage_{sum}$, $consistent\rangle$, whose members are sets of summary conditions, summarized resource usage, and a $consistent$ flag indicating whether the plan will execute consistently internally. $pre_{sum}(p)$ and $post_{sum}(p)$ are summary pre- and postconditions, which are the external pre- and postconditions of $p$, respectively. The summary inconditions of $p$, $in_{sum}(p)$, contain all conditions that must hold within some execution of $p$ for it to be successful. A condition $c$ in one of these sets is a tuple $\langle\ell,existence, timing\rangle$. $\ell(c)$ is the literal of $c$. The $existence$ of $c$ can be $must$ or $may$. If $existence(c)=must$, then $c$ is called a $must$ condition because $\ell$ must hold for every successful plan execution. For convenience we usually write $must(c)$. $c$ is a $may$ condition ($may(c)$ is $true$) if $\ell(c)$ must hold for some successful execution.

The $timing$ of a summary condition $c$ can either be $always$, $sometimes$, $first$, or $last$. $timing(c)$ is $always$ for $c\in in_{sum}$ if $\ell(c)$ is an incondition that must hold throughout all potential executions of $p$ ($\ell$ holds always); otherwise, $timing(c)=sometimes$ meaning $\ell(c)$ holds at one point, at least, within an execution of $p$. So, an $always$ condition is $must$, and we do not define $may$ $always$ inconditions because whether it is $may$ because of existence or timing, it is not significantly different from $may$ $sometimes$ in how a planner reasons about it. Whether a condition is $may$ $always$ (however defined) or $may$ $sometimes$, another plan can only have a $may$ $clobber$ relationship with the condition (as defined in Section 3.3). Note also that the incondition of a CHiP has the restricted meaning of a $must$ $always$ summary incondition. The $timing$ is $first$ for $c\in pre_{sum}$ if $\ell(c)$ holds at the beginning of an execution of $p$; otherwise, $timing=sometimes$. Similarly, $timing$ is $last$ for $c\in post_{sum}$ if $\ell(c)$ is asserted at the end of a successful execution of $p$; otherwise, it is $sometimes$. Although $existence$ and $timing$ syntactically only take one value, semantically $must(c)\Rightarrow may(c)$, and $always(c)\Rightarrow sometimes(c)$.

We considered using modal logic operators to describe these concepts. While a mix of existing temporal logic and dynamic logic [Pratt, 1976] notation could be forced to work, we found that using our own terminology made definitions much simpler. We discuss this more at the end of Section 8.

Definitions 7, 8, and 9 give the formal semantics of $existence$ and $timing$ for a few representative condition types. Summary conditions of a plan are defined recursively in that they depend on the summary conditions of the plan's immediate subplans instead of its complete decomposition. Because a single description of summary information could represent many different plan hierarchies, we quantify over plans $p'$, whose subplans have the same summary information as those of the plan $p$ being summarized. We could have defined the existence and timing properties of conditions based on the entire hierarchy, but in doing so, deriving summary conditions would be as expensive as solving the planning problem, and one of the main purposes of summary information is to reduce the computation of the planning problem. The reason why it would be so expensive is that in the worst case all legal orderings of all plan steps must be explored to determine whether a condition is $must$ or $may$. We will discuss an example of this at the end of this subsection.

Definition 7   $$\begin{array}{@{}l@{}l@{}l} [mu&st,may]\_first\_precondition... ...}) \wedge \ell \in pre(p'') \end{array} \end{array}\end{array}$$

Definition 8   $$\begin{array}{@{}l@{}l@{}l} must&\_always\_incondition(\ell,... ...{p''}) \wedge \ell\in in(p'') \end{array}\end{array}\end{array}$$

Definition 9   $$\begin{array}{@{}l@{}l@{}l} [mus&t,may]\_sometimes\_incondit... ... \ell\in post(p'') \end{array}\end{array}\end{array}\end{array}$$

Definition 7 states that a $first$ precondition of $p$ is an external precondition that is always required at the beginning of the execution of any $p'$ that has the same conditions as $p$ and the same summary information and ordering for its subplans as $p$. A last postcondition is always asserted at the end of the execution (substitute ``pre'' with ``post'' and $t_s$ with $t_f$ in the last two lines of Definition 7). A [must,may] sometimes precondition is a [must,may] external precondition that is not a $first$ precondition. A sometimes postcondition is defined similarly. Definition 8 states that a literal $\ell$ is a $must$, $always$ incondition of a plan $p$ if at any time during any isolated execution of any $p'$ with the same summary information as $p$, some executing plan $p''$ has incondition $\ell$. Definition 9 states that a [must, may] sometimes incondition of plan $p$ is a condition that is required during [any, some] execution of [any, some] plan $p'$ that has the same summary information and ordering for its subplans as $p$.

The $consistent$ flag is a boolean indicating whether the plan (or any plan with the same summary information and ordering for subplans) would execute successfully no matter how it was decomposed and no matter when its subplans were executed. Definition 10 says that all possible executions will succeed for a consistent plan. This is very similar to the $CanAnyWay$ relation that will be defined in Section 4. We do not include whether the plan will definitely not succeed in the summary information because it requires an exponential computation to see whether all conflicts in the subplans can be resolved. This computation can wait to be done during planning after summary information is fully derived.

Definition 10   $$\begin{array}{@{}l@{}l@{}l} cons&istent(p) \equiv \\ &\for... ...p'} \in \mathcal{E}(p'), e_{p'} succeeds \end{array}\end{array}$$

We show a subset of the summary conditions for the production manager's top-level plan (of Figure 2) below. Following each literal are modal tags for $existence$ and $timing$ information. ``Mu'' is $must$; ``Ma'' is $may$; ``F'' is $first$; ``L'' is $last$; ``S'' is $sometimes$; and ``A'' is $always$.

Production manager's $produce\_H$ plan:
Summary preconditions:
available(A)MuF, available(M1)MaS, available(M2)MaS
Summary inconditions:
$\neg$available(A)MuS, available(M1)MaS, available(M2)MuS, available(G)MuS,
available(A)MuS, $\neg$available(M1)MaS, $\neg$available(M2)MuS, $\neg$available(G)MuS,
available(H)MuS, $\neg$available(H)MuS
Summary postconditions:
$\neg$available(A)MuS, available(M1)MaS, available(M2)MuS, $\neg$available(G)MuS,
available(H)MuL

The $available(M1)$ summary precondition is a $may$ condition because the production manager may end up not using M1 if it chooses to use M2 instead to produce G. $available(A)$ is a $first$ summary precondition because part A must be used at the beginning of execution when it is transported to one of the machines. Because the machines are needed sometime after the parts are transported, they are sometimes (and not first) conditions: they are needed at some point in time after the beginning of execution.

Because the production manager may use M1 to produce G, $\neg available(M1)$ is a summary incondition of $produce\_H$. Having both $available(M1)$ and $\neg available(M1)$ as inconditions is consistent because they are $sometimes$ conditions, implying that they hold at different times during the plan's execution. In contrast, these conditions would conflict if they were both $must$ and $always$ (meaning that they must always hold throughout every possible execution of the plan).

The summary condition $\neg available(A)$ is a $must$ postcondition of the top-level plan because A will definitely be consumed by $make\_G$ and is not produced by some other plan in the decomposition of $produce\_H\_from\_G$. Even though $available(G)$ is an effect of $produce\_G$, it is not an external postcondition of $produce\_H$ because it is undone by $produce\_H\_from\_G$, which consumes G to make H. $available(H)$ is a $last$ summary postcondition because the production manager releases H at the very end of execution. $available(M2)$ is not $last$ because the manager finishes using M2 before moving H into storage.

Notice that $available(M2)$ is a $may$ summary precondition. However, no matter how the hierarchy is decomposed, M2 must be used to produce H, so $available(M2)$ must be established externally to the production manager's plan. Because summary information is defined in terms of the summary information of the immediate subplans, in the subplans of $produce\_H$, we only see that $produce\_G$ has an $available(M2)MaS$ precondition and an $available(M2)MaS$ postcondition that would achieve the $available(M2)MuF$ precondition of $produce\_H\_from\_G$. This summary information does not tell us that the precondition of $produce\_G$ exists only when the postcondition exists, a necessary condition to determine that the derived precondition of $produce\_H$ is a $must$ condition. Thus, it is $may$. If we augmented summary information with which subsets of conditions existed together, hunting through combinations and temporal orderings of condition subsets among subplans to derive summary conditions would basically be an adaptation of an HTN planning algorithm, which summary information is intended to improve. Instead, we derive summary information in polynomial time and then use it to improve HTN planning exponentially as we explain in Section 6. This is the tradeoff we made at the beginning of this section in defining summary conditions in terms of just the immediate subplans instead of the entire hierarchy. Abstraction involves loss of information, and this loss enables computational gains.

3.3 Summary condition relationships and algorithms

In order to derive summary conditions according to their definitions, we need to be able to recognize achieve, clobber, and undo relationships based on summary conditions as we did for basic CHiP conditions. We give definitions and algorithms for these, which build on constructs and algorithms for reasoning about temporal relationships, described in Appendix A.

Achieving and clobbering are very similar, so we define them together. Definition 11 states that plan $p_1$ must [achieve, clobber] summary precondition $c_2$ of $p_2$ if and only if for all executions of any two plans, $p_1'$ and $p_2'$, with the same summary information and ordering constraints as $p_1$ and $p_2$, the execution of $p_1'$ or one of its subexecutions would [achieve, clobber] an external precondition $\ell(c_2)$ of $p_2'$.

Definition 11   $$\begin{array}{@{}l@{}l@{}l} must&\_[achieve,clobber] \_preco... ...ndition(\ell(c_2),e_{p_2'}) \end{array} \end{array}\end{array}$$

Achieving and clobbering in- and postconditions are defined the same as Definition 11 but substituting ``in'' and ``post'' for ``pre'' and removing the last line for inconditions. Additionally substituting $\exists$ for $\forall$ gives the definitions of may achieve and clobber. Furthermore, the definitions of must/may-undo are obtained by substituting ``post'' for ``pre'' and ``undo'' for ``achieve'' in Definition 11. Note that, as mentioned in Section 2.5, achieving inconditions and postconditions does not make sense for this formalism.

Algorithms for these interactions are given in Figure 6 and Figure 7. These algorithms build on others (detailed in Appendix B) that use interval point algebra to determine whether a plan must or may assert a summary condition before, at, or during the time another plan requires a summary condition to hold. Similar to Definition 3 of must-achieve for CHiP conditions, Figure 6 says that $p'$ achieves summary condition $c$ if it must asserts the condition before it must hold, and there are no other plans that may assert the condition or its negative in between. The algorithm for may-achieve (in Figure 7) mainly differs in that $p'$ may assert the condition beforehand, and there is no plan that must assert in between. The undo algorithms are the same as those for achieve after swapping $c$ and $c'$ in all $must$/$may$-$assert$ lines.

Figure 6: Algorithm for whether a plan must achieve or clobber a summary condition

Figure 7: Algorithm for whether a plan may achieve or clobber a summary condition

The complexity of determining must/may-clobber for inconditions and postconditions is simply $O(c)$ to check $c$ conditions in $p'$. If the conditions are hashed, then the algorithm is constant time. For the rest of the algorithm cases, the complexity of walking through the summary conditions checking for $p''$ and $c''$ is $O(nc)$ for a maximum of $c$ summary conditions for each of $n$ plans represented in $P_{sum}$. In the worst case, all summary conditions summarize the same propositional variable, and all $O(nc)$ conditions must be visited.

Let's look at some examples of these relationships. In Figure 8a, $p' = equip\_M2\_tool$ may-clobber $c$ = $available$(M2)MaS in the summary preconditions of $p = produce\_G$ because there is some history where $equip\_M2\_tool$ ends before $produce\_G$ starts, and $calibrate\_M2$ starts after $produce\_G$ starts. In Figure 8b, $p' = build\_H$ must-achieve $c$ = $available$(H)MuF in the summary preconditions of $p = move\_H$. Here, $c'$ is $available$(H)MuL in the summary postconditions of $build\_H$. In all histories, $build\_H$ attempts to assert $c'$ before the $move\_H$ requires $c$ to be met, and there is no other plan execution that attempts to assert a condition on the availability of H. $equip\_M2\_tool$ does not may-clobber $c$ = $available$(M2)MuF in the summary preconditions of $build\_H$ even though $equip\_M2\_tool$ asserts $c'$ = $\neg available$(M2)MuL before $c$ is required to be met. This is because $calibrate\_M2$ must assert $\neg available$(M2)MuA between the time that $equip\_M2\_tool$ asserts $c'$ and when $c$ is required. Thus, $calibrate\_M2$ must-undo $equip\_M2\_tool$ 's summary postcondition. Because $calibrate\_M2$ cannot assert its postcondition $available$(M2)MuL before $build\_H$ requires $available$(M2)MuF, $calibrate\_M2$ must-clobber the summary precondition.

Figure 8: The production and facilities managers' plans partially expanded. a) The managers' plans unordered with respect to each other. b) $equip\_M2\_tool$ must clobber $available$(M2)MaL of $produce\_G$, and $calibrate\_M2$ must clobber $available$(M2)MuF of $build\_H$.

3.4 Deriving Summary Conditions

Now that we have algorithms that determine interactions of abstract plans based on their summary conditions, we can create an algorithm that derives summary conditions according to their definitions in Section 3.2. Figure 9 shows pseudocode for the algorithm. The method for deriving the summary conditions of a plan $p$ is recursive. First, summary information is derived for each of $p$'s subplans. Then conditions are added based on $p$'s own conditions. Most of the rest of the algorithm derives summary conditions from those of $p$'s subplans. Whether $p$ is $consistent$ depends on the consistency of its subplans and whether its own summary conditions and resource usages are in conflict. The braces '{' '}' used here have slightly different semantics than used before with the brackets. An expression {$x$,$y$} can be interpreted simply as ($x$ or $y$, respectively).

Figure 9: Algorithm for deriving summary information

Definitions and algorithms for temporal relationships such as $always$-$first$ and covers are in Appendix A. When the algorithm adds or copies a condition to a set, only one condition can exist for any literal, so a condition's information may be overwritten if it has the same literal. In all cases, $must$ overwrites $may$; and $first$, $last$, and $always$ overwrite $sometimes$; but, not vice-versa. Further, because it uses recursion, this procedure is assumed to work on plans whose expansion is finite.

3.5 Summary Resource Usage

In this section, we define a representation for capturing ranges of usage both local to the task interval and the depleted usage lasting after the end of the interval. Based on this we introduce a summarization algorithm that captures in these ranges the uncertainty represented by decomposition choices in $or$ plans and partial temporal orderings of $and$ plan subtasks. This representation allows a coordinator or planner to reason about the potential for conflicts for a set of tasks. We will discuss this reasoning later in Section 4.2. Although referred to as resources, these variables could be durations or additive costs or rewards.

3.5.1 Representation

We start with a new example for simplicity that motivates our choice of representation. Consider the task of coordinating a collection of rovers as they explore the environment around a lander on Mars. This exploration takes the form of visiting different locations and making observations. Each traversal between locations follows established paths to minimize effort and risk. These paths combine to form a network like the one mapped out in Figure 10, where vertices denote distinguished locations, and edges denote allowed paths. Thinner edges are harder to traverse, and labeled points have associated observation goals. While some paths are over hard ground, others are over loose sand where traversal is harder since a rover can slip.

Figure 10: Example map of established paths between points in a rover domain

Figure 11 gives an example of an abstract task. Imagine a rover that wants to make an early morning trip from point $A$ to point $B$ on the example map. During this trip the sun slowly rises above the horizon giving the rover the ability to progressively use soak rays tasks to provide more solar power (a non-consumable resource³) to motors in the wheels. In addition to collecting photons, the morning traverse moves the rover, and the resultant go tasks require path dependent amounts of power. While a rover traveling from point $A$ to point $B$ can take any number of paths, the shortest three involve following one, two, or three steps.

Figure 11: $and$/$or$ tree defining a rover's tasks and their resource usages

A summarized resource usage consists of ranges of potential resource usage amounts during and after performing an abstract task, and we represent this summary information for a plan $p$ on a resource $res$ using the structure $$usage_{sum}(p, res) = \langle local\_min(p,res),local\_max(p,res),persist(p,res)\rangle,$$ where the resource's local usage occurs within $p$'s execution, and the persistent usage represents the usage that lasts after the execution terminates for consumable resources.

Definition 12   $$\setlength{\arraycolsep}{0in} \begin{array}[t]{lll} usage_{... ...p\in E(h)}(-r(res,h,t_f(e_p)))]& \rangle \end{array}\end{array}$$

The context for Definition 12 is the set of all histories $H$ where the value of $res$ is 0 in the initial state, and $E(h)$ only contains the execution of $p$ and its subexecutions. Thus, the $-r(res,h,t)$ term is the combined usage of $res$ at time $t$ of all executions in the hierarchy as defined in Section 2.4. So, the maximum of the $local\_min$ is the highest among all histories of the lowest point of usage during $p$'s execution. The usage ranges capture the multiple possible usage profiles of a task with multiple decomposition choices and timing choices among loosely constrained subtasks. For example, the high path task has a $\langle$[4,4],[6,6],[0,0]$\rangle$ summary power use over a 40 minute interval. In this case the ranges are single points due to no uncertainty - the task simply uses 4 watts for 15 minutes followed by 6 watts for 25 minutes. The $move$(A,B) task provides a slightly more complex example due to its decompositional uncertainty. This task has a $\langle$[0,4],[4,6],[0,0]$\rangle$ summary power use over a 50 minute interval. In both cases the $persist$ is [0,0] because solar power is a non-consumable resource.

As an example of reasoning with resource usage summaries, suppose that only 3 watts of power were available during a $move$(A,B) task. Given the [4,6] $local\_max$, we know that there is not enough power no matter how the task is decomposed. Raising the available power to 4 watts makes the task executable depending on how it gets decomposed and scheduled, and raising to 6 or more watts makes the task executable for all possible decompositions.

This representation of abstract (or uncertain) metric resource usage can be seen as an extension of tracking optimistic and pessimistic resource levels [Drabble Tate, 1994]. Computing only the upper and lower bounds on resource usage for an abstract plan gives some information about whether lower or upper bound constraints on a resource may, must, or must not be violated, but it is not complete. By representing upper and lower bounds as ranges of these bounds over all potential histories, we can certainly know whether bounds may, must, or must not be violated over all histories. For the example above, if we only tracked one range for the local usage, [0,6], we would not know that there is definitely a conflict when only 3 watts are available. Knowing this extra information can avoid exploration of an infeasible search space.

3.5.2 Resource Summarization Algorithm

The state summarization algorithm in Section 3.4 recursively propagates summary conditions upwards from an $and$/$or$ hierarchy's leaves, and the algorithm for resource summarization takes the same approach. Starting at the leaves, the algorithm finds primitive tasks that use constant amounts of a resource. The resource summary of a task using $x$ units of a resource is $\langle[x$,$x]$,$[x$,$x]$,$[0$,$0]\rangle$ or $\langle[x$,$x]$,$[x$,$x]$,$[x$,$x]\rangle$ over the task's duration for non-consumable or consumable resources respectively.

Moving up the $and$/$or$ tree, the summarization algorithm either comes to an $and$ or an $or$ branch. For an $or$ branch the combined summary usage comes from the $or$ computation $$\setlength{\arraycolsep}{0in} \begin{array}[t]{lllll} \lang... ... & max_{c \in children}(ub(persist(c)))]&\ \rangle, \end{array}$$ where $lb()$ and $ub()$ extract the lower bound and upper bound of a range respectively. The $children$ denote the branch's children with their durations extended to the length of the longest child. This duration extension alters a child's resource summary information because the child's usage profile has a zero resource usage during the extension. For instance, in determining the resource usage for $move$(A,B), the algorithm combines two 40 minute tasks with a 50 minute task. The resulting summary information describes a 50 minute abstract task whose profile might have a zero watt power usage for 10 minutes. This extension is why $move$(A,B) has a [0,4] for a $local\_min$ instead of [3,4]. Planners that reason about variable durations could use [3,4] for a duration ranging from 40 to 50.

Computing an $and$ branch's summary information is a bit more complicated due to timing choices among loosely constrained subtasks. The take $x$ path examples illustrate the simplest sub-case, where subtasks are tightly constrained to execute serially. Here profiles are appended together, and the resulting summary usage information comes from the SERIAL-AND computation $$\setlength{\arraycolsep}{0in} \begin{array}[t]{lllll} \lang... ...a_{c \in children}(ub(persist(c)))] & \ \rangle,\\ \end{array}$$ where $\Sigma_{lb}^{pre}(c)$ and $\Sigma_{ub}^{pre}(c)$ are the respective lower and upper bounds on the cumulative persistent usages of children that execute before $c$. These computations have the same form as the $\Sigma$ computations for the final $persist$.

The case where all subtasks execute in parallel and have identical durations is slightly simpler. Here the usage profiles add together, and the branch's resultant summary usage comes from the PARALLEL-AND computation $$\setlength{\arraycolsep}{0in} \begin{array}[t]{lllll} \lang... ...a_{c \in children}(ub(persist(c)))] & \ \rangle,\\ \end{array}$$ where $\Sigma_{ub}^{non}(c)$ and $\Sigma_{lb}^{non}(c)$ are the respective sums of the $local\_max$ upper bounds and the $local\_min$ lower bounds for all children except $c$.

To handle $and$ tasks with loose temporal constraints, we consider all legal orderings of child task endpoints. For example, in the rover's early morning tasks, there are three serial solar energy collection subtasks running in parallel with a subtask to drive to location $B$. Figure 12 shows one possible ordering of the subtask endpoints, which breaks