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-01-01
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.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.