Constraint Networks (CNs) are a framework to model the constraint satisfaction problem (CSP), which is the problem of finding an assignment of values to a set of variables satisfying a set of given constraints. Therefore, CSP is a satisfiability problem. When the CSP turns conditional, consistency analysis extends to finding also an assignment to these conditions such that the relevant part of the initial CN is consistent. However, CNs fail to model CSPs expressing an uncontrollable conditional part (i.e., a conditional part that cannot be decided but merely observed as it occurs). To bridge this gap, in this paper we propose constraint networks under conditional uncertainty (CNCUs), and we define weak, strong and dynamic controllability of a CNCU. We provide algorithms to check each of these types of controllability and discuss how to synthesize (dynamic) execution strategies that drive the execution of a CNCU saying which value to assign to which variable depending on how the uncontrollable part behaves. We benchmark the approach by using ZETA, a tool that we developed for CNCUs. What we propose is fully automated from analysis to simulation.
Constraint Networks Under Conditional Uncertainty
Zavatteri, Matteo;Viganò, Luca
2018-01-01
Abstract
Constraint Networks (CNs) are a framework to model the constraint satisfaction problem (CSP), which is the problem of finding an assignment of values to a set of variables satisfying a set of given constraints. Therefore, CSP is a satisfiability problem. When the CSP turns conditional, consistency analysis extends to finding also an assignment to these conditions such that the relevant part of the initial CN is consistent. However, CNs fail to model CSPs expressing an uncontrollable conditional part (i.e., a conditional part that cannot be decided but merely observed as it occurs). To bridge this gap, in this paper we propose constraint networks under conditional uncertainty (CNCUs), and we define weak, strong and dynamic controllability of a CNCU. We provide algorithms to check each of these types of controllability and discuss how to synthesize (dynamic) execution strategies that drive the execution of a CNCU saying which value to assign to which variable depending on how the uncontrollable part behaves. We benchmark the approach by using ZETA, a tool that we developed for CNCUs. What we propose is fully automated from analysis to simulation.File | Dimensione | Formato | |
---|---|---|---|
ICAART_2018_19.pdf
solo utenti autorizzati
Tipologia:
Versione dell'editore
Licenza:
Accesso ristretto
Dimensione
356.42 kB
Formato
Adobe PDF
|
356.42 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.