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.