The Satisfiability of Temporal Constraint Networks

Raúl E. Valdés-Pérez

A popular representation of events and their relative alignment in time is James Allen’s intervals and algebra. Networks of disjunctive interval constraints have served both to assimilate knowledge from ambiguous sentences, and to hold partial solutions in a planner. The satisfiability of these networks is of practical concern, and little has been achieved beyond proving that determining satisfiability is NP-hard. This paper scrutinizes the interval representation and its mechanisms. We make explicit the unstated assumptions of the mechanisms, introduce several useful theorems regarding interval networks, distinguish three types of inconsistency exhibited by these networks, and point out under what conditions these inconsistencies are detected. Finally the theorems, observations, and distinctions regarding inconsistency are exploited to design a practical algorithm to determine the satisfiability of an interval network. The extension of our results to two-dimensional spatial reasoning is under investigation.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.