A Simple Temporal Network with Uncertainty (STNU) is a framework for representing and reasoning about temporal problems involving actions whose durations are bounded but uncontrollable. A dynamically controllable STNU is one for which there exists a strat- egy for executing its time-points that guarantees that all of the temporal constraints in the network will be satisfied no matter how the uncon- trollable durations turn out. A Conditional Simple Temporal Network with Uncertainty (CSTNU) augments an STNU to include observation nodes, the execution of which incrementally and dynamically determines the set of constraints that must be satisfied. Previously, we generalized the notion of dynamic controllability to cover CSTNUs and presented a sound algorithm for determining whether arbitrary CSTNUs are dynam- ically controllable. That algorithm extends edge-generation/constraint- propagation rules from an existing DC-checking algorithm for STNUs with new rules required to deal with the observation nodes. This paper revisits that algorithm, modifying some of its rules to cover more cases, while preserving the soundness of the algorithm.

An Algorithm for Checking the Dynamic Controllability of a Conditional Simple Temporal Network with Uncertainty - Revisited

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

Abstract

A Simple Temporal Network with Uncertainty (STNU) is a framework for representing and reasoning about temporal problems involving actions whose durations are bounded but uncontrollable. A dynamically controllable STNU is one for which there exists a strat- egy for executing its time-points that guarantees that all of the temporal constraints in the network will be satisfied no matter how the uncon- trollable durations turn out. A Conditional Simple Temporal Network with Uncertainty (CSTNU) augments an STNU to include observation nodes, the execution of which incrementally and dynamically determines the set of constraints that must be satisfied. Previously, we generalized the notion of dynamic controllability to cover CSTNUs and presented a sound algorithm for determining whether arbitrary CSTNUs are dynam- ically controllable. That algorithm extends edge-generation/constraint- propagation rules from an existing DC-checking algorithm for STNUs with new rules required to deal with the observation nodes. This paper revisits that algorithm, modifying some of its rules to cover more cases, while preserving the soundness of the algorithm.
2014
9783662444399
temporal network; temporal controllability; temporal uncertainty; temporal workflow
File in questo prodotto:
File Dimensione Formato  
algorithm4CSTNU_CCIS_published.pdf

solo utenti autorizzati

Descrizione: postprint
Tipologia: Documento in Post-print
Licenza: Accesso ristretto
Dimensione 814.1 kB
Formato Adobe PDF
814.1 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/866383
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 16
social impact