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 obtained
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11582/1230
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact