Appendix B: Algorithms for Must/May Asserting Summary Conditions

Here we describe algorithms for determining temporal plan relationships based on summary information. They are used to build other algorithms that determine whether plan must or may achieve, clobber, or undo the condition of another under particular ordering constraints.

The definitions and algorithms throughout this section are given within the context of a set of plans

with a corresponding set of summary information $P_{sum}$ , a set of ordering constraints

, and a set of histories

including all histories where

only includes an execution

of each plan in

and

's subexecutions, and

satisfies all constraints in

. They are all concerned with the ordering of plan execution intervals and the timing of conditions. By themselves, they do not have anything to do with whether conditions may need to be met or must be met for a plan execution.

First, in order to determine whether abstract plan executions can achieve, clobber, or undo conditions of others, an agent needs to be able to reason about how summary conditions are asserted and required to be met. Ultimately, the agent needs to be able to determine whether a partial ordering of abstract plans can succeed, so it may be the case that an agent's action fails to assert a summary condition that is required by the action of another agent. Therefore, we formalize what it means for an action to attempt to assert a summary condition and to require that a summary condition be met. These definitions rely on linking the summary condition of a plan to the CHiP conditions it summarizes in the subplans of the plan's decompositions. Thus, we first define what it means for a summary condition to summarize these conditions.

Definition 14

A summary condition summarizes a condition $\ell$ in condition set of plan iff was added by the procedure for deriving summary information to a summary condition set of ; $\ell=\ell(c)$ ; and either was added for $\ell$ in a condition set of , or was added for a summary condition of a subplan of that summarizes $\ell$ in of .

For example,

(bin1, A) is a precondition of the $start\_move$ plan for moving part A from bin1 to machine M1 (as given in Section 2.2). When deriving the summary conditions for $start\_move$ ,

(bin1, A) is added to the summary preconditions. Thus, the summary precondition

(bin1, A)MuF summarizes

(bin1, A) in the preconditions of $start\_move$ .

Definition 15

An execution of requires a summary condition to be met at iff is a summary condition in 's summary information; there is a condition $\ell$ in a condition set of that is summarized by ; if , ; if , ; if , is within ; and if , there is an execution of a subplan of in that requires a summary condition to be met at , and summarizes $\ell$ in of .

So, basically, an execution requires a summary condition to be met whenever the conditions it summarizes are required. The execution of $build\_G$ has a summary precondition

(A,M1_tray1). This execution requires this summary condition to be met at

( $build\_G$ ) because

(A, M1_tray1) is a precondition of $build\_G$ 's first subplan that is summarized by $build\_G$ 's summary precondition.

Definition 16

An execution of attempts to assert a summary condition at iff is a summary condition in 's summary information; there is a condition $\ell$ in a condition set of that is summarized by ; $\neg first(c)$ ; if , is in the smallest interval after and before the start or end of any other execution that follows ; if , ; and if , there is an execution of a subplan of in that attempts to assert a summary condition at ; and summarizes $\ell$ in of .

We say that an execution ``attempts'' to assert a summary condition because asserting a condition can fail due to a simultaneous assertion of the negation of the condition. Like the example above for requiring a summary condition, the executions of $build\_G$ , $produce\_G\_on\_M1$ , and $produce\_H$ all assert summary postconditions that M1 becomes available at

( $build\_G$ ).

In order for agents to determine potential interactions among their abstract plans (such as clobbering or achieving), they need to reason about when a summary condition is asserted by one plan in relation to when it is asserted or required by another. Based on interval or point algebra constraints over a set of abstract plans, an agent specifically would need to be able to determine whether a plan would assert a summary condition before or by the time another plan requires or asserts a summary condition on the same state variable. In addition, to reason about clobbering inconditions, an agent would need to determine if a summary condition would be asserted during the time a summary incondition

was required (asserted in

). Agents also need to detect when a summary postcondition would be asserted at the same time as another summary postcondition

(asserted when

We do not consider cases where executions attempt to assert a summary in- or postcondition at the same time an incondition is asserted because in these cases, clobber relations are already detected because executions always require the summary inconditions that they attempt to assert. For example, if $equip\_M1$ attempted to assert the incondition that M1 was unavailable at the same time that $build\_G$ attempted to assert the postcondition that M1 was available, the incondition would be clobbered by the postcondition.

**Table:** Table for **must-assert by/before** algorithm
$\begin{tabular}{\vert r\vert c\vert c\vert c\vert c\vert} \hline & & & $p'$\ mus... ...$\ & $false$\ \\ \hline 19 & F & F & $false$\ & $false$\ \\ \hline \end{tabular}$

**Table:** Table for **may-assert by/before** algorithm
$\begin{tabular}{\vert r\vert c\vert c\vert c\vert c\vert} \hline & & & $p'$\ may... ...ine 18 & ? & F & ${p'}^- \geq p^+$\ & ${p'}^- \geq p^+$\ \\ \hline \end{tabular}$

**Table:** Table for **must/may-assert in** algorithm
$\begin{tabular}{\vert r\vert c\vert c\vert c\vert\vert c\vert c\vert c\vert} \hl... ...se$\ & F & F & ${p'}^+ \leq p^-$\ or ${p'}^- \geq p^+$\ \\ \hline \end{tabular}$

**Table:** Table for **must/may-assert when** algorithm
$\begin{tabular}{\vert r\vert c\vert c\vert c\vert\vert c\vert c\vert c\vert} \hl... ...lse$\ & F & F & ${p'}^+ \leq p^-$\ or ${p'}^- \geq p^+$\ \\ \hline \end{tabular}$

In the case that the ordering constraints allow for alternative synchronizations of the abstract plans, the assertions of summary conditions may come in different orders. Therefore, we formalize must-assert and may-assert to determine when these relationships must or may occur respectively. As mentioned at the beginning of Section 9, this use of ``must'' and ``may'' is based only on disjunctive orderings and not on the

of summary conditions in different decompositions. For the following definitions and algorithms of must- and may-assert, we assume

and

are summary conditions of plans in

Definition 17

$p'\in P$ must-assert [by, before] iff for all histories $h\in H$ and all where is the top-level execution in of some $p\in P$ that requires to be met at , and is the top-level execution of in , there is a where attempts to assert at , and [ $t'\leq t$ , ].

The must-assert algorithm is described in Table 3.

must-assert

iff

entails the relationship given for the row corresponding to the type and timing of the two conditions. Rows of the table indicate the timing of both summary conditions and the constraints that

must dictate for must-assert to be true. 'T' and 'F' in the table indicate whether the timing in the column is true or false for the condition. '?' means that timing doesn't matter for that condition in this case. For example, row 9 says that for the case where

is a

( $\neg last$ ) postcondition of

, and

is an incondition of

with any timing,

must require that the end of

be before or at the start of

in order for

to must-assert

by the time

is asserted or required.

The definitions and algorithms for the other assert relationships are similar. Tables 4-6 describe the logic for the other algorithms. For

relationships, the algorithm returns true iff none of the corresponding ordering constraints in the table are imposed by (can be deduced from)

We illustrate these relationships for the example in Figure 8. In Figure 8a the agents' plans are unordered with respect to each other. Part G is produced either on machine M1 or M2 depending on potential decompositions of the $produce\_G$ plan. $produce\_G$ must-assert

(G) before

(G) in the summary preconditions of $move\_G$ because no matter how the plans are decomposed (for all executions and all histories of the plans under the ordering constraints in the figure), the execution of $produce\_G$ attempts to assert

before the execution of $move\_G$ requires

to be met. The algorithm verifies this by finding that the end of $produce\_G$ is ordered before the start of $move\_G$ (row 1 in Table 3). It is also the case that $equip\_M2\_tool$ may-assert

$\neg available$ (M2) by

(M2) in the summary preconditions of $produce\_G$ because the two plans are unordered with respect to each other, and in some history $equip\_M2\_tool$ can precede $produce\_G$ . The algorithm finds that this is true since $equip\_M2$ is not constrained to start after the start of $produce\_G$ (row 2 in Table 4).

In Figure 8b, $move\_tool$ may-assert

(transport1) in

$\neg free$ (transport1) in $produce\_G$ 's summary inconditions because in some history $move\_tool$ attempts to assert

during the time that $produce\_G$ is using transport1 to move part A to machine M2. In addition, $equip\_M2\_tool$ must-assert

$\neg available$ (M2) when

(M2) in $produce\_G$ 's summary postconditions because $equip\_M2\_tool$ attempts to assert

at the same time that $produce\_G$ requires

to be met. The end of Section 3.3 gives other examples.