King's College London

Research portal

Conditional Simple Temporal Networks with Uncertainty and Decisions

Research output: Contribution to journalArticle

Matteo Zavatteri, Luca Viganò

Original languageEnglish
Pages (from-to)77-101
Number of pages48
JournalTheoretical Computer Science
Volume797
Early online date6 Nov 2018
DOIs
Publication statusPublished - 10 Dec 2019

King's Authors

Abstract

A Conditional Simple Temporal Network with Uncertainty (CSTNU) is a formalism able to model temporal plans subject to both conditional constraints and uncertain durations. The combination of these two characteristics represents the uncontrollable part of the network. That is, before the network starts executing, we do not know completely which time points and constraints will be taken into consideration nor how long the uncertain durations will last. Dynamic controllability (DC) implies the existence of a strategy scheduling the time points of the network in real time depending on how the uncontrollable part behaves. Despite all this, CSTNUs fail to model temporal plans in which a few conditional constraints are under control and may therefore influence (or be influenced by) the uncontrollable part. To bridge this gap, this paper proposes Conditional Simple Temporal Networks with Uncertainty and Decisions (CSTNUDs) which introduce decision time points into the specification in order to operate on this conditional part under control. We model the dynamic controllability checking (DC-checking) of a CSTNUD as a two-player game in which each player makes his moves in his turn at a specific time instant. We give an encoding into timed game automata for a sound and complete DC-checking. We also synthesize memo- ryless execution strategies for CSTNUDs proved to be DC and carry out an experimental evaluation with Esse, a tool that we have designed for CST- NUDs to make the approach fully automated.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454