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.