Satisfiability in Nonlinear Time: Algorithms and Complexity

May 1999

Proceedings of the Twelfth International Florida Artificial Intelligence Research Society Conference (FLAIRS 1999)

Volume

Proceedings of the Twelfth International Florida Artificial Intelligence Research Society Conference (FLAIRS 1999)

All Papers

Most work on temporal interval relations and associated automated reasoning methods assumes linear (totally ordered) time. Although checking the consistency of temporal interval constraint networks is known to be NP-hard in general, many tractable subclasses of linear-time temporal relations are known for which a standard O(n^3)constraint propagation algorithm actually determines the global consistency. In the very special case in which the relations are all ``pointizable,'' meaning that the network can be replaced by an equivalent point constraint network (on the start and finish points of the intervals), an O(n^2) algorithm to check consistency exists. This paper explores the situation in non-linear temporal models, showing that the familiar results no longer pertain. In particular, the paper shows that for networks of point relations in partially ordered time, the usual constraint propagation approach does not determine global consistency, although for the branching time model, the question remains open. Nonetheless, the paper presents an O(n^3) algorithm for consistency of a significant subset of the pointizable temporal interval relations in a general partially ordered time model. Beyond checking consistency, for the consistent case the algorithm produces an example scenario satisfying all the given constraints. The latter result benefits planning applications, where actual quantitative values can be assigned to the intervals.