A Conditional Simple Temporal Network (CSTN) is a data structure for representing and reasoning about time- points and temporal constraints, some of which may apply only in certain scenarios. The scenarios in a CSTN are represented by conjunctions of propositional literals whose truth values are not known in advance, but instead are observed in real time, during execution. The most important property of a CSTN is whether it is dynamically consistent (DC); that is, whether there exists a strategy for executing its time-points such that all relevant constraints are guaranteed to be satisfied no matter which scenario is incrementally revealed during execution. Prior approaches to determining the dynamic consistency of CSTNs (a.k.a., solving the Conditional Simple Temporal Problem) are pri- marily of theoretical interest; they have not been realized in prac- tical algorithms. This paper presents a sound-and-complete DC- checking algorithm for CSTNs that is based on the propagation of constraints labeled by propositions. The paper also presents an empirical evaluation of the new algorithm that demonstrates that it may be practical for a variety of applications. This is the first empirical evaluation of any DC-checking algorithm for CSTNs ever reported in the literature.

A Sound-and-Complete Propagation-based Algorithm for Checking the Dynamic Consistency of Conditional Simple Temporal Networks

POSENATO, Roberto;COMBI, Carlo
2015-01-01

Abstract

A Conditional Simple Temporal Network (CSTN) is a data structure for representing and reasoning about time- points and temporal constraints, some of which may apply only in certain scenarios. The scenarios in a CSTN are represented by conjunctions of propositional literals whose truth values are not known in advance, but instead are observed in real time, during execution. The most important property of a CSTN is whether it is dynamically consistent (DC); that is, whether there exists a strategy for executing its time-points such that all relevant constraints are guaranteed to be satisfied no matter which scenario is incrementally revealed during execution. Prior approaches to determining the dynamic consistency of CSTNs (a.k.a., solving the Conditional Simple Temporal Problem) are pri- marily of theoretical interest; they have not been realized in prac- tical algorithms. This paper presents a sound-and-complete DC- checking algorithm for CSTNs that is based on the propagation of constraints labeled by propositions. The paper also presents an empirical evaluation of the new algorithm that demonstrates that it may be practical for a variety of applications. This is the first empirical evaluation of any DC-checking algorithm for CSTNs ever reported in the literature.
2015
978-1-4673-9317-1
Constraint-based Temporal Reasoning; Temporal Networks; Constraint Satisfaction; Scheduling.
File in questo prodotto:
File Dimensione Formato  
posenatoTIME.2015.26.pdf

solo utenti autorizzati

Descrizione: post-print
Tipologia: Documento in Post-print
Licenza: Accesso ristretto
Dimensione 574.3 kB
Formato Adobe PDF
574.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11562/927189
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 40
  • ???jsp.display-item.citation.isi??? 22
social impact