A Linear-Programming Approach to Temporal Reasoning

Abstract

We present a new formalism, Horn Disjunctive Linear Relations (Horn DLRs), for reasoning about temporal constraints. We prove that deciding satisfiability of sets of Horn DLRs is polynomial by exhibiting an algorithm based upon linear programming. Furthermore, we prove that most other approaches to tractable temporal constraint reasoning can be encoded as Horn DLRs, including the ORD-Horn algebra and most methods for purely quantitative reasoning. Introduction Reasoning about temporal constraints is an important task in many areas of AI and elsewehere, such as planning, natural language processing, diagnosis, time serialization in archeology etc. In most applications, knowledge of temporal constraints is expressed in terms of collections of relations between time intervals or time points. Typical reasoning tasks include determining the satisfiability of such collections and deducing new relations from those that are known. The research has largely concentrated on two kinds of formalis...