The Consistent Labeling Problem in Temporal Reasoning

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 6

Planning

Temporal reasoning can be performed by maintaining a temporal relation network, a complete network in which the nodes are time intervals and each arc is the temporal relation between the two intervals which it connects. In this paper, we point out that the task of detecting inconsistency of the network and mapping the intervals onto a date line is a Consistent Labeling problem (CLP). The problem is formalized and analyzed. The significance of identifying and analyzing the CLP in temporal reasoning is that CLPs have certain features which allow us to apply certain techniques to our problem. We also point out that the CLP exists when we reason with disjunctive temporal relations. Therefore, the intractability of the constraint propagation mechanism in temporal reasoning is inherent in the problem, not caused by the representation that we choose for time, as [Vilain $ Kautz 86] claims.