A concurrent hierarchical plan is a tuple , , , , , , . , , and are sets of literals ( or for some propositional variable ) representing the preconditions, inconditions, and postconditions defined for plan .1
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 is a function mapping from resource variables to an amount used. We write to indicate the amount uses of resource and sometimes treat as a set of pairs . A metric resource is a tuple , , . The min and max values can be integer or real values representing bounds on the capacity or amount available. The 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 of plan , or , is given a value of either , , or . An plan is a non-primitive plan that is accomplished by carrying out all of its subplans. An plan is a non-primitive plan that is accomplished by carrying out exactly one of its subplans. So, is a set of plans, and a plan's is the empty set. is only defined for an plan 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 plan is a task network, and an 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 (Figure 2) is the tuple In (0,1), 0 and 1 are indices of the subplans in the decomposition referring to and respectively. There are no conditions defined because 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 This plan decomposes into two half moves which help capture important intermediate effects. The parent orders its children with the relation to bind them together into a single move. The plan is The plan is 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 (transport1) as an incondition to a single plan because another agent could, for instance, use transport1 at the same time because its (transport1) incondition would agree with the (transport1) incondition of this move action. However, the specification here is still insufficient since two pairs of (, ) 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 and its parent plans, in effect, hiding the transition between the start and finish actions. So, by representing the transition from to 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.2
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.