wpu.nu

Sida:Ann-1983 JBC25001-00 James Allen - Maintaining knowledge about temporal intervals.pdf/12

Från wpu.nu

Den här sidan har inte korrekturlästs


does not detect all inconsistencies in its input. In fact, it only guaranlees consistency between three node subnetworks. There are networks thal can be added which appear consistent by viewing any three nodes, but for which there is no consistent overall labeling. The network shown in Figure 5 is consistent if we consider any three nodes; however, there is no overall labeling of the network.2 To see this, if we assign the relationship between A and C, which could be for fi according to this nelwork, to either f alone, or fi alone, we would arrive at an inconsistency. In other words, there is no consistent labeling with A --(1)→ C, or with A --(ſi)→ C, even though the algorithm accepts A --(f fi) -- C.

<Figure 5)

To ensure total consistency, one would have to consider constraints between three arcs, between four arcs, etc. While this can be done using techniques outlined in Freuder (1982), the computational complexity of the algorithm is exponential. In practice, we have not encountered problems from this deficiency in our applications of the model. We can verify the consistency of any subnetwork, if desired, by a simple backtracking search through the alternative arc labelings until we arrive at a labeling for the whole subnetwork in which every arc has only one label.

V. Controlling Propagation: Reference Intervals

In order to reduce the space requirements of the representation without greally affecting the inferential power of the mechanism, we introduce reference intervals. Formally, a reference interval is simply another interval in the system, but it is endowed with a special property that affects the computation. Reference intervals are used to group together clusters of intervals for which the temporal constraints between each pair of intervals in the cluster is fully computed. Such a cluster is related to the rest of the intervals in the system only indirectly via the reference interval.

V.1. Using Reference Intervals

Every interval may designate one or more reference intervals (i.e., node clusters to which it belongs). These will be listed in parentheses after the interval name. Thus the node names

Il(RI) 12(R1,R2)

describe an interval named Il that has a reference interval R1, and an interval named 12 that has two reference intervals RI and R2. Since 12 has two reference intervals, it will be fully connected to two clusters. An illustration of the connectedness of such a network is formed in Figure 6.

2This network is due to Henry Kautz, personal communication.