wpu.nu

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

Från wpu.nu

Den här sidan har inte korrekturlästs


II. Background

Before we consider some previous approaches to temporal representation, let us summarize some important characteristics that are relevant to our work:

The representation should allow significant imprecision. Much temporal knowledge is strictly relative (e.g., A is before B) and has little relation to absolute dates. The representation should allow uncertainty of information. Often, the exact relationship between two times is not known, but some constraints on how they could be related are known. The representation should allow one 10 vary the grain of reasoning. For example, when modeling knowledge of history, one may only need to consider time in terms of days, or even years. When modeling knowledge of computer design, one may need 10 consider times on the order of nanoseconds or less. The model should support persistence. It should facilitate deſault reasoning of the type, "If I parked my car in lot A this morning, it should still be there now," even though proof is not possible (the car may have been towed or stolen).

This does not exhaust all the issues, and others will come up as they become relevant. It provides us with a starting criteria, however, for examining previous approaches. Previous work can be divided roughly into four categories: slale space approaches, date line systems, before/after chaining, and formal models.

State space approaches (e.g., [Fikes and Nilsson, 1971; Sacerdoti, 1977]) provide a crude sense of time that is usefUL in simple problem-solving tasks. A slate is a description of the world (i.e., a data base of facts) at an instantaneous point in time, Actions are modeled in such systems as functions mapping between stales. For example, if an action occurs that causes fact P to become true, and causes fact Q 10 be no longer true, its effect is simulated by simply adding fact P to the current slale and deleting fact Q. If the previous states are retained, we have a representalion of time as a series of data bases describing the world in successive stales

. In general, however, it is too expensive to maintain all the previous states, so most systems only maintain the present state. While this technique is usefUL in some applications, il does not address many of the issues which concern us. Note that such systems do provide a notion of persistence, however. Once a fact is asserted, it remains true until it is explicitly deleted.

In date-based systems (e.g., (Kahn and Gorry, 1977; Bruce, 1972; Hendrix, 1973; Bubenko, 1980]), each fact is indexed by a date. A date is a representation of a time such that the temporal ordering between two dates can be computed by fairly simple operations. For example, we could use the integers as dates, and then temporal ordering could be computed using a simple numeric comparison. Of course, more complicated schemes based on calendar dates and times are typically more usefUL. Because of the nice computational properties, this is the approach of choice if one can assiga dates for every event. Unfortunately, in the applications we are