A Flexible Simple Temporal Network with Uncertainty (FTNU) represents temporal constraints between time-points. Time-points are variables that must be set (executed) satisfying all the constraints. Some time-points are contingent. It means that they are set by the environment and only observed by the system executing the network. The ranges repre- senting temporal constraints associated with contingent time-points (guarded ranges) can be shrunk during execution only to some extent to have more flexibility in the execution of the network. Subsets of time-points/constraints may be executed/considered in different contexts according to some observed conditions. The main issue here consists of determining whether all the time-points, under the control of the system, are executable in a way that all the specified constraints are satisfied for any possible occurrence of contingent time-points and any possible context. Such property is called controllability. Even though an algorithm was proposed for checking the controllability of such networks, we show that such an algorithm has a limit. Indeed, it does not determine the right bounds for guarded links, and, therefore, it doesn’t permit the system to exploit the potential flexibility of the network. We then propose a new constraint-propagation algorithm for checking controllability, prove that such a new algorithm determines the right guarded ranges, and it is sound-and-complete. Thus, it can be used also for executing the network, by leveraging its flexibility.

Adding flexibility to uncertainty: Flexible Simple Temporal Networks with Uncertainty (FTNU)

Posenato, Roberto
;
Combi, Carlo
2022

Abstract

A Flexible Simple Temporal Network with Uncertainty (FTNU) represents temporal constraints between time-points. Time-points are variables that must be set (executed) satisfying all the constraints. Some time-points are contingent. It means that they are set by the environment and only observed by the system executing the network. The ranges repre- senting temporal constraints associated with contingent time-points (guarded ranges) can be shrunk during execution only to some extent to have more flexibility in the execution of the network. Subsets of time-points/constraints may be executed/considered in different contexts according to some observed conditions. The main issue here consists of determining whether all the time-points, under the control of the system, are executable in a way that all the specified constraints are satisfied for any possible occurrence of contingent time-points and any possible context. Such property is called controllability. Even though an algorithm was proposed for checking the controllability of such networks, we show that such an algorithm has a limit. Indeed, it does not determine the right bounds for guarded links, and, therefore, it doesn’t permit the system to exploit the potential flexibility of the network. We then propose a new constraint-propagation algorithm for checking controllability, prove that such a new algorithm determines the right guarded ranges, and it is sound-and-complete. Thus, it can be used also for executing the network, by leveraging its flexibility.
Conditional simple temporal constraint network with uncertainty, Dynamic controllability, Guarded constraints, Contingency, Conditional propositions, Temporal constraint networks, Flexible temporal networks
File in questo prodotto:
File Dimensione Formato  
2022Posenato_Combi__Adding_flexibility_to_uncertainty.pdf

accesso aperto

Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 2.7 MB
Formato Adobe PDF
2.7 MB 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/1052937
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact