A number of formal models have been proposed to address temporal and resource allocation problems under uncertainty. Such models are typically shipped with an embedded notion of dynamic controllability, enclosing the ability to always make the right decisions, during execution, according to the observed uncontrollable events that always happen. In the business process management community, resource allocation was recently studied to deal with uncontrollable choices, whereas in the security community it was studied to face the uncontrollable availability of resources. The latter is a kind of dynamic controllability known as resiliency where uncontrollable events might also not happen. To the best of our knowledge, approaches handling resiliency on top of dynamic controllability still remain unexplored. To bridge this gap, we propose Generalized Constraint Networks with Uncertainty (GCNUs), a model that we devised to address resource controllability more widely, boosting expressiveness while considering several sources of uncertainty simultaneously. We define dynamic controllability and (J, K)-resiliency of GCNUs. We reason on the structure of these problems, carry out a complexity analysis and provide algorithms to solve them.

Dynamic Controllability and (J,K)-Resiliency in Generalized Constraint Networks with Uncertainty

Matteo Zavatteri;Romeo Rizzi;Tiziano Villa
2020-01-01

Abstract

A number of formal models have been proposed to address temporal and resource allocation problems under uncertainty. Such models are typically shipped with an embedded notion of dynamic controllability, enclosing the ability to always make the right decisions, during execution, according to the observed uncontrollable events that always happen. In the business process management community, resource allocation was recently studied to deal with uncontrollable choices, whereas in the security community it was studied to face the uncontrollable availability of resources. The latter is a kind of dynamic controllability known as resiliency where uncontrollable events might also not happen. To the best of our knowledge, approaches handling resiliency on top of dynamic controllability still remain unexplored. To bridge this gap, we propose Generalized Constraint Networks with Uncertainty (GCNUs), a model that we devised to address resource controllability more widely, boosting expressiveness while considering several sources of uncertainty simultaneously. We define dynamic controllability and (J, K)-resiliency of GCNUs. We reason on the structure of these problems, carry out a complexity analysis and provide algorithms to solve them.
2020
Constraint network GCNU, dynamic Controllability, (J K)-Resiliency, resource allocation under uncertainty, high-availability, online planning, two-player game, PSPACE-completeness
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/1020132
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact