There are thirteen basic relations that can hold between two intervals (see Figure 1; [2,6]). In order to represent indefinite information, the relation between two intervals is allowed to be a disjunction of the basic relations. Sets are used to list the disjunctions. For example, the relation {m,o,s} between events A and B represents the disjunction,
Let I be the set of all basic relations, {b,bi,m,mi,o,oi,s,si,d,di,f,fi,eq}. Allen allows the relation between two events to be any subset of I.
Figure 1: Basic relations between intervals
We use a graphical notation where vertices represent events and directed edges are labeled with sets of basic relations. As a graphical convention, we never show the edges (i, i), and if we show the edge (i, j), we do not show the edge (j, i). Any edge for which we have no explicit knowledge of the relation is labeled with I; by convention such edges are also not shown. We call networks with labels that are arbitrary subsets of I, interval algebra or IA networks.
Example 1. Allen and Koomen [3] show how IA networks can be used in non-linear planning with concurrent actions. As an example of representing temporal information using IA networks, consider the following blocks-world planning problem. There are three blocks, A, B, and C. In the initial state, the three blocks are all on the table. The goal state is simply a tower of the blocks with A on B and B on C. We associate states, actions, and properties with the intervals they hold over, and we can immediately write down the following temporal information.
An IA network is consistent if and only if there exists a mapping M of a real interval M(u) for each event or vertex u in the network such that the relations between events are satisfied (i.e., one of the disjuncts is satisfied). For example, consider the small subnetwork in Figure 2a consisting of the events On(A,B), On(B,C), and Goal. This subnetwork is consistent as demonstrated by the assignment, M(On(A,B)) = [1,5], M(On(B,C)) = [2,5], and M(Goal) = [3,4]. If we were to change the subnetwork and insist that On(A,B) must be before On(B,C), no such mapping would exist and the subnetwork would be inconsistent.
A consistent scenario of an IA network is a non-disjunctive subnetwork (i.e., every edge is labeled with a single basic relation) that is consistent. In our planning example, finding a consistent scenario of the network corresponds to finding an ordering of the actions that will accomplish the goal of stacking the three blocks. One such consistent scenario can be reconstructed from the qualitative mapping shown in Figure 2b.
Figure 2: Representing qualitative relations between intervals
Example 2. Golumbic and Shamir [12] discuss how IA networks can be used in a problem in molecular biology: examining the structure of the DNA of an organism [4]. The intervals in the IA network represent segments of DNA. Experiments can be performed to determine whether a pair of segments is either disjoint or intersects. Thus, the IA networks that result contain edges labeled with disjoint ({b,bi}), intersects ({m,mi,o,oi,s,si,d,di,f,fi,eq}), or I, the set of all basic relations---which indicates no experiment was performed. If the IA network is consistent, this is evidence for the hypothesis that DNA is linear in structure; if it is inconsistent, DNA is nonlinear (it forms loops, for example). Golumbic and Shamir [12] show that determining consistency in this restricted version of IA networks is NP-complete. We will show that problems that arise in this application can often be solved quickly in practice.