Appendix A: Algorithms for Computing Interval Relations

The algorithms for determining whether the defined relations hold between summary conditions for plans in 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 ; a row and column for both (start endpoint of execution of ) and (finish endpoint) are added for each plan . Each cell of the table gives a time point constraint of the row to the column that can be , , , , , , , 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 and where they are constrained such that 's execution contains that of . Table 2 shows a table where just the start of is constrained to be earlier than the start of . Both are transitive closures of these constraint relations. Table 1 can be computed from Table 2 by constraining (by putting in the cell of row and column ) and then computing the transitive closure, an algorithm for 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.

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

We determine that a plan in 's subplans is temporally ordered
*always-*[,]
if and only if [, ] is
constrained [before, after] or equal to all other points in the point
algebra table for 's subplans. This is done by looking at each
entry in the row for [, ] and checking to see that the
constraint is [, ], , or [, ]. If this is not
the case, then is *not-always-*[,].
is *always-not-*[,] if and only if in the
row for [, ] there is an entry with the [, ]
constraint; otherwise, it is *sometimes-*[,].

An interval is *covered* by a set of intervals
if and only no interval can be found that
intersects and intersects nothing in . 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 is covered by looking at all pairs of intervals to see if
they overlap. is not covered if (1) either no intervals in meet either or
, (2) there are any intervals that have an endpoint that is
contained only by and do not meet the opposite endpoint of another
interval in or an endpoint of , or (3) there are no intervals
overlapping . Otherwise, is covered. Examples are given in Figure 34.