Extending constraint logic programming for temporal reasoning

In recent years, several constraint‐based temporal reasoning frameworks have been proposed. They consider temporal points or intervals as domain elements linked by temporal constraints. Temporal reasoning in these systems is based on constraint propagation. In this paper, we argue that a language based on constraint propagation can be a suitable tool for expressing and reasoning about temporal problems. We concentrate on Constraint Logic Programming (CLP) which is a powerful programming paradigm combining the advantages of Logic Programming and the efficiency of constraint solving. However, CLP presents some limitations in dealing with temporal reasoning. First, it uses an “arc consistency” propagation algorithm which is embedded in the inference engine, cannot be changed by the user, and is too weak in many temporal frameworks. Second, CLP is not able to deal with qualitative temporal constraints. We present a general meta CLP architecture which maintains the advantages of CLP, but overcomes these two main limitations. Each architectural level is a finite domain constraint solver(CLP(FD)) that reasons about constraints of the underlying level. Based on this conceptual architecture, we extend the CLP(FD)language and we specialize the extension proposed on Vilain and Kautz’sPoint Algebra, on Allen’s Interval Algebra and on the STP framework by Dechter, Meiri and Pearl. In particular, we show that we can cope effectively with disjunctive constraints even in an interval‐based framework.