wpu.nu

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

Från wpu.nu

Den här sidan har inte korrekturlästs


I. Introduction

The problem of representing temporal knowledge and temporal reasoning arises in a wide range of disciplines, including computer science, philosophy, psychology, and linguistics. In computer science, it is a core problem of information systems, program verification, artificial intelligence, and other areas involving process modeling. For a recent survey of work in temporal representation, see the special sections in the April 1982 issues of the SIGART and SIGMOD Newsletters.

Information systems, for example, must deal with the problem of outdated dala. One approach to this is simply to delete outdated data; however, this eliminates the possibility of accessing any information except that which involves facts that are presently true. In order to consider queries such as, "Which employees worked for us last year and made over $15,000," we need to represent temporal information. In some applications, such as keeping medical records, the time course of events becomes a critical part of the data.

In artificial intelligence, models of problem solving require sophisticated world models that can capture change. In planning the activities of a robol, for instance, one must model the effects of the robot's actions on the world to ensure that a plan will be effective. In natural language processing, researchers are concerned with extracting and capturing temporal and tense information in sentences. This knowledge is necessary to be able to answer queries about the sentences later. Further progress in these areas requires more powerfUL representations of temporal knowledge than have been previously available.

This paper addresses the problem from the perspective of artificial intelligence. Il describes a temporal representation which takes the notion of a temporal interval as primitive. It then describes a method of representing the relationships between temporal intervals in a hierarchical manner using constraint propagation lechniques. By using reference intervals, the amount of computation involved when adding a fact can be controlled in a predictable manner. This representation is designed explicitly to deal with the problem that much of our temporal-knowledge is relative, and hence can't be described by a date (or even a "fuzzy" date).

We shall start with a survey of current techniques for modeling time, and point out various problems that need to be addressed. After a discussion of the relative merits of interval-based systems versus point-based systems in Section III, a simple interval-based deduction technique based on constraint propagation is introduced in Section IV. This scheme is then augmented in Section V with reference intervals, and examples in three different domains are presented. In the final sections of the paper, extensions to the basic system are proposed in some detail. These would extend the representation to include reasoning about the duration of intervals, reasoning about dates when they are available, and reasoning about the future given knowledge of what is true at the present.

The system as described in Section V has been implemented and is being used in a variety of research projects which are briefly described in Section VI. Or the extensions, the duration reasoner is fully implemented and incorporated into the system, whereas the date reasoner has been designed but not implemented.