Appendix A: Algorithms for Computing Interval Relations

The algorithms for determining whether the defined relations hold between summary conditions for plans in $P$ use a point algebra constraint table [Vilain, Kautz, 1986]. This point algebra table is constructed for the interval endpoints corresponding to the executions of the plans in $P$; a row and column for both $p^{-} \equiv t_s(e)$ (start endpoint of execution $e$ of $p$) and $p^{+} \equiv t_f(e)$ (finish endpoint) are added for each plan $p\in P$. Each cell of the table gives a time point constraint of the row to the column that can be $<$, $\leq$, $=$, $\geq$, $>$, $\neq$, $<=>$, or empty. $<=>$ means that the points are unconstrained. If a cell is empty, then there are no allowed temporal relations, indicating inconsistency. Table 1 shows a point algebra table for plans $p$ and $p'$ where they are constrained such that $p$'s execution contains that of $p'$. Table 2 shows a table where just the start of $p$ is constrained to be earlier than the start of $p'$. Both are transitive closures of these constraint relations. Table 1 can be computed from Table 2 by constraining $p^{+}<{p'}^{+}$ (by putting $<$ in the cell of row $p^{+}$ and column ${p'}^{+}$) and then computing the transitive closure, an $O(n^2)$ algorithm for $n$ points [Vilain, Kautz, 1986]. After the transitive closure is computed, the constraints of any point on any other point can be looked up in constant time.

Table 1: Point algebra table for $p$ contains $p'$

Table 2: Point algebra table for $p^{-}$ before or at ${p'}^{-}$

Similarly, the constraints in $order$ for $P$ can be added to the table, and the transitive closure can be computed to get all constraints entailed from those in $order$. This only needs to be done once for any $P$ and $order$ to determine $achieve$ and $clobber$ relationships defined in the next section.

We determine that a plan $q$ in $p$'s subplans is temporally ordered always-[$first$,$last$] if and only if [$q^{-}$, $q^{+}$] is constrained [before, after] or equal to all other points in the point algebra table for $p$'s subplans. This is done by looking at each entry in the row for [$q^{-}$, $q^{+}$] and checking to see that the constraint is [$<$, $>$], $=$, or [$\leq$, $\geq$]. If this is not the case, then $q$ is not-always-[$first$,$last$]. $q$ is always-not-[$first$,$last$] if and only if in the row for [$q^{-}$, $q^{+}$] there is an entry with the [$>$, $<$] constraint; otherwise, it is sometimes-[$first$,$last$].

An interval $i_0$ is covered by a set of intervals $I=\{i_1,i_2,\ldots,i_k\}$ if and only no interval can be found that intersects $i_0$ and intersects nothing in $I$. Our particular covering problem describes the intervals in terms of a partial order over endpoints, so we represent these intervals in a point algebra table. An algorithm for the covering problem is to check to see if $i_0$ is covered by looking at all pairs of intervals to see if they overlap. $i_0$ is not covered if (1) either no intervals in $I$ meet either $i_0^{-}$ or $i_0^{+}$, (2) there are any intervals that have an endpoint that is contained only by $i_0$ and do not meet the opposite endpoint of another interval in $I$ or an endpoint of $i_0$, or (3) there are no intervals overlapping $i_0$. Otherwise, $i_0$ is covered. Examples are given in Figure 34.

Figure 34: a) Interval A is covered by B, C, and D. b) E is not covered by F, G, and H. c) I is not covered.