Dynamic Path Consistency for Interval-based Temporal Reasoning

M. Mouhoub (Canada)


Temporal Reasoning, Constraint Satisfaction, Path Consistency, Planning and Scheduling.


Path consistency is an important component of the resolution method needed to check for the consistency of an Allen's Interval-based temporal network. While this lo cal consistency algorithm reduces, in general, the size of the search space before applying the backtrack search, it implies the consistency of the problem for some specific temporal networks. Our goal in this paper is to maintain the path consistency of a temporal network in a dynamic environment i.e anytime a temporal relation is added or re moved. For this purpose we propose a dynamic path con sistency algorithm based on van Beek's path consistency technique. Experimental tests on randomly generated dy namic interval-based temporal networks demonstrate the efficiency of our algorithm to deal with large size tempo ral problems in a dynamic environement.

Important Links:

Go Back