A Conditional Simple Temporal Network with Uncertainty and Decisions (CSTNUD) is a for- malism to model, validate, and execute temporal plans subject to controllable and uncon- trollable events as well as controllable and uncontrollable choices simultaneously. Dynamic Controllability implies the existence of a strategy scheduling the events and fixing the controllable choices in real time in a way that only depends on the already executed uncontrollable events and already fixed uncontrollable choices. This paper unifies CSTNUDs with other temporal network formalisms by providing Conditional Temporal Networks with Uncertainty and Decisions (CTNUDs) and proposes a semantics for dynamic controllability modeled as a two-player game between Controller and Nature where each player can react instantaneously to the other player moves. Such a game is designed to guarantee termination with exactly one winner (i.e., the game is determined). We prove that adopting the instantaneous reaction semantics allows for modeling any possible reaction time, absorbing de facto previous proposed semantics of dynamic controllability. We provide an encoding into Timed Game Automata to synthesize an execution strategy for any dynamically controllable CTNUD. We implement our approach to synthesize C++ programs for the execution of dynamically controllable CTNUDs. We test our software on a set of randomly-generated instances.

Dynamic controllability of temporal networks with instantaneous reaction

Zavatteri, Matteo
;
Rizzi, Romeo;Villa, Tiziano
2022-01-01

Abstract

A Conditional Simple Temporal Network with Uncertainty and Decisions (CSTNUD) is a for- malism to model, validate, and execute temporal plans subject to controllable and uncon- trollable events as well as controllable and uncontrollable choices simultaneously. Dynamic Controllability implies the existence of a strategy scheduling the events and fixing the controllable choices in real time in a way that only depends on the already executed uncontrollable events and already fixed uncontrollable choices. This paper unifies CSTNUDs with other temporal network formalisms by providing Conditional Temporal Networks with Uncertainty and Decisions (CTNUDs) and proposes a semantics for dynamic controllability modeled as a two-player game between Controller and Nature where each player can react instantaneously to the other player moves. Such a game is designed to guarantee termination with exactly one winner (i.e., the game is determined). We prove that adopting the instantaneous reaction semantics allows for modeling any possible reaction time, absorbing de facto previous proposed semantics of dynamic controllability. We provide an encoding into Timed Game Automata to synthesize an execution strategy for any dynamically controllable CTNUD. We implement our approach to synthesize C++ programs for the execution of dynamically controllable CTNUDs. We test our software on a set of randomly-generated instances.
2022
Conditional simple temporal network with uncertainty and decisions, Timed game automata, Planning and scheduling under uncertainty, Instantaneous reaction, C++ controller software synthesis
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/1075206
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact