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.