wpu.nu

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

Från wpu.nu

Den här sidan har inte korrekturlästs


remains constant. A new NOW interval, below the new reference interval in the hierarchy, must be introduced. For example, the beginning of a new day would make much of the old hierarchy part of the past (i.e., "yesterday").

While many intervals will be generated by this succession of intervals for NOW, many of them can be garbage collected when the reference intervals are updated. In particular, any interval that is not used to index any events or facts may be removed from the data base. In a system modeling a natural language dialogue, a large number of these intervals would be used only to index the time of an utterance. These generally can be deleted without harm.

VI. Discussion

The temporal representation described is notable in that il is both expressive and computationally feasible. In particular, it does not insist that all events occur in a known fixed order, as in the state space approach, and it allows disjunctive knowledge, such as that event A occurred either before or afler event B, not expressible in date-based systems or simple systems based on before/after chaining. It is not as expressive as a full temporal logic (such as that of McDermolt (1982]), but these systems do not currently have viable implementations.

This balance between expressive power and computational efficiency is achieved by the restricted form of disjunctions allowed in the system. One can only assert disjunctive information about the relationship of two intervals. In other words, we can assert that A is before or meets B, but not that (A meets B) or (C before D). This limited form of disjunction is ideal for the constraint propagation algorithm.

The system has been implemented and is being used in a variety of applications. Both FRANZ LISP (Foderaro, 1980] and INTERLISP versions are running on a VAX 11/780 under UNIX. The system presently also includes the duration reasoner described below. It is currently being used in research in representing actions, events, and interactions that arise in natural language dialogues (Allen, Frisch, and Lilman, 1982). We are also using the representation as a world model for research in automatic problem-solving systems (Allen and Koomen, 1983). Such systems have long been constrained by their inadequate temporal models.

Vilain (1982] has implemented a version of this system which, at the cost of greater space requirements, can perform consistency maintenance. In other words, in his system, when an inconsistency is found, the set of facts that caused the inconsistency can be identified. This system also explicitly allows time points in the representation and has a larger transitivity table, including all interval/point and point/point in teractions. This violates the semantics of the interval representation, and so has not been adopted in our present system.

Let us consider why we would like time points, however. They seem to be referred to in English. We can, for instance, talk about the beginning and ending of events. There is no reason to assume, however, that these "endpoints" are truly zerowidth points rather than intervals small enough so that they appear to be instantaneous. What this suggests is that there might be a minimum duration such that all intervals of duration less than a would be viewed as points. This would

C,