Incremental Algorithms for Managing Temporal Constraints

This paper addresses the problem of efficiently updating a network of temporal constraints when constraints are removed from an existing network, or when they are added to it. Such processing tasks are important in many AI-applications requiring a temporal reasoning module. First we analyze the relationship between shortest-paths algorithms for directed graphs and arc-consistency techniques. Then we focus on a subclass of STP called STP- for which we propose new fast incremental algorithms for consistency checking and for maintaining the feasible times of the temporal variables. Our method is based on a metagraph data structure and on shortest-paths algorithms for directed acyclic graphs. An experimental comparison of the proposed algorithms with the (non-incremental) Bellman-Ford’s algorithm shows that drastic CPU-time reductions can be obtained