Next: Appendix B: Algorithms for Up: Abstract Reasoning for Planning Previous: 9 Conclusion

# 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.

Next: Appendix B: Algorithms for Up: Abstract Reasoning for Planning Previous: 9 Conclusion