Search for a command to run...
This thesis introduces a new approach to temporal reasoning which increases both the expressive power and the flexibility of handling temporal information. It also offers a unifying conceptualization of existing approaches and invites the importation of solution techniques from several disciplines. Temporal reasoning is viewed as a constraint satisfaction problem in which variables are forced to comply with a set of constraints. The variables are temporal objects such as intervals (representing time periods during which events occur or propositions hold) and time points (representing beginnings and ends of intervals), and the constraints specify the relative location of these objects along the time line. Unlike existing approaches, our proposal permits the processing of both qualitative and quantitative constraints. First, a model called temporal constraint network is introduced, which facilitates the processing of quantitative information such as duration and timing of events. In this model, variables represent time points, and the constraints refer to absolute timing or time differences between events. Second, a framework called general temporal networks is developed, combining quantitative information about duration and timing with qualitative relations about precedence and occurrences of events. This framework offers the unique flexibility of treating both points and intervals as the primitive objects in the language, thereby generalizing and unifying the temporal-constraint-networks model and common approaches to temporal reasoning such as Allen's interval algebra and Vilain and Kautz's point algebra. We present constraint-based algorithms for performing the following reasoning tasks: finding all feasible times that a given event can occur, finding all possible relationships between two given events, and generating one or more scenarios consistent with the information provided. Several new classes of tractable temporal problems are identified and characterized, involving special formats of qualitative and quantitative expressions. Such problems can be solved in polynomial time using local relaxation algorithms.