Theoretical and Experimental Studies of Temporal Constraint Satisfaction Problem

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Student Abstracts

Reasoning with time is embedded in many application domains than we are often aware of. For example, understanding a parallel program involves how each unit of the program is temporally related to the other unit through dependency. There is a growing awareness about the importance of understanding time in any dynamic or evolving situation. Within last twenty years different dimensions of reasoning have been identified, such as, qualitative reasoning versus quantitative reasoning, point-based representation versus interval-based representation, propositional expression versus first order expression. My work concentrates on interval-based qualitative propositional reasoning. The representation scheme and a polynomial approximate algorithm were proposed by James Allen. The problem of detecting global consistency has been subsequently proved to be NP-complete. Practical reasoning systems have been developed based on Allen’s S-consistency algorithm. This algorithm checks for consistency over constraints between each subset of 3 temporal entities of the full set of temporal assertions in the system (rather than checking for complete consistency between all constraints, which is called global-consistency). There has been very little systematic study on either the S-consistency problem, or the global-consistency problem.