Recent work on Conditional Simple Temporal Networks (CSTNs) has focused on checking the dynamic consistency (DC) property for the case where an execution strategy can react instantaneously to observations. Three alternative semantics for such strategies—IR-dynamic, 0-dynamic, and π-dynamic—have been presented. However, the most practical DC-checking algorithm has only been analyzed with respect to the IR semantics. Meanwhile, 0-dynamic strategies were shown to permit a kind of circular dependence among simultaneous observations, making them impossible to implement, whereas π-dynamic strategies prohibit this kind of circularity. Whether IR-dynamic strategies allow this kind of circularity and, if so, what the consequences would be for the above-mentioned DC-checking algorithm remained open questions. This paper makes the following contributions: (1) it shows that IR-dynamic strategies do allow circular dependence and, thus, that the IR semantics does not properly capture instantaneous reactivity; (2) it shows that one of the constraint-propagation rules from the IR-DC-checking algorithm is unsound with respect to the IR semantics; (3) it presents a simpler DC-checking algorithm, called the π-DC-checking algorithm, that uses half of the rules from the earlier algorithm, and that it proves is sound and complete with respect to the π-DC semantics; (4) it empirically evaluates the new algorithm. Thus, the paper places practical DC checking for CSTNs in the case of instantaneous reaction on a solid theoretical foundation.

Dynamic-Consistency Checking for Conditional Simple Temporal Networks: Strengthening the Theoretical Foundations and Presenting a Faster Algorithm

Posenato, Roberto
2018-01-01

Abstract

Recent work on Conditional Simple Temporal Networks (CSTNs) has focused on checking the dynamic consistency (DC) property for the case where an execution strategy can react instantaneously to observations. Three alternative semantics for such strategies—IR-dynamic, 0-dynamic, and π-dynamic—have been presented. However, the most practical DC-checking algorithm has only been analyzed with respect to the IR semantics. Meanwhile, 0-dynamic strategies were shown to permit a kind of circular dependence among simultaneous observations, making them impossible to implement, whereas π-dynamic strategies prohibit this kind of circularity. Whether IR-dynamic strategies allow this kind of circularity and, if so, what the consequences would be for the above-mentioned DC-checking algorithm remained open questions. This paper makes the following contributions: (1) it shows that IR-dynamic strategies do allow circular dependence and, thus, that the IR semantics does not properly capture instantaneous reactivity; (2) it shows that one of the constraint-propagation rules from the IR-DC-checking algorithm is unsound with respect to the IR semantics; (3) it presents a simpler DC-checking algorithm, called the π-DC-checking algorithm, that uses half of the rules from the earlier algorithm, and that it proves is sound and complete with respect to the π-DC semantics; (4) it empirically evaluates the new algorithm. Thus, the paper places practical DC checking for CSTNs in the case of instantaneous reaction on a solid theoretical foundation.
2018
Temporal Constraints, Constraint Networks, Conditional Temporal Network
File in questo prodotto:
File Dimensione Formato  
technicalReport103_2018.pdf

accesso aperto

Descrizione: main article
Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 485.15 kB
Formato Adobe PDF
485.15 kB Adobe PDF Visualizza/Apri

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