A Conditional Simple Temporal Network with Uncertainty (CSTNU) is a data structure for rep- resenting and reasoning about time. CSTNUs incorporate observation time-points from Condi- tional Simple Temporal Networks (CSTNs) and contingent links from Simple Temporal Networks with Uncertainty (STNUs). A CSTNU is dynamically controllable (DC) if there exists a strategy for executing its time-points that guarantees the satisfaction of all relevant constraints no matter how the uncertainty associated with its observation time-points and contingent links is resolved in real time. This paper presents the first sound-and-complete DC-checking algorithms for CSTNUs that are based on the propagation of labeled constraints and demonstrates their practicality.

Sound-and-Complete Algorithms for Checking the Dynamic Controllability of Conditional Simple Temporal Networks with Uncertainty

Luke Hunsberger;Roberto Posenato
2018-01-01

Abstract

A Conditional Simple Temporal Network with Uncertainty (CSTNU) is a data structure for rep- resenting and reasoning about time. CSTNUs incorporate observation time-points from Condi- tional Simple Temporal Networks (CSTNs) and contingent links from Simple Temporal Networks with Uncertainty (STNUs). A CSTNU is dynamically controllable (DC) if there exists a strategy for executing its time-points that guarantees the satisfaction of all relevant constraints no matter how the uncertainty associated with its observation time-points and contingent links is resolved in real time. This paper presents the first sound-and-complete DC-checking algorithms for CSTNUs that are based on the propagation of labeled constraints and demonstrates their practicality.
2018
Temporal Networks, Conditional Simple Temporal Problem with Uncer- tainty, Dynamic Controllability, Checking Algorithm
File in questo prodotto:
File Dimensione Formato  
LIPIcs-TIME-2018-14.pdf

accesso aperto

Descrizione: main article
Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 611.83 kB
Formato Adobe PDF
611.83 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/986313
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? ND
social impact