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
Incremental Algorithms for Managing Temporal Constraints
Perini, Anna;Ricci, Francesco
1996-01-01
Abstract
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 obtainedI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.