License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2017.23
URN: urn:nbn:de:0030-drops-79169
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7916/
Go to the corresponding LIPIcs Volume Portal

Zavatteri, Matteo

Conditional Simple Temporal Networks with Uncertainty and Decisions

pdf-format:
LIPIcs-TIME-2017-23.pdf (0.6 MB)

Abstract

A conditional simple temporal network with uncertainty (CSTNU) is a framework 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 memoryless execution strategies for CSTNUDs proved to be DC. The proposed approach is fully automated.

BibTeX - Entry

@InProceedings{zavatteri:LIPIcs:2017:7916,
  author =	{Matteo Zavatteri},
  title =	{{Conditional Simple Temporal Networks with Uncertainty and Decisions}},
  booktitle =	{24th International Symposium on Temporal Representation and Reasoning (TIME 2017)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-052-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{90},
  editor =	{Sven Schewe and Thomas Schneider and Jef Wijsen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7916},
  URN =		{urn:nbn:de:0030-drops-79169},
  doi =		{10.4230/LIPIcs.TIME.2017.23},
  annote =	{Keywords: cstnud, dynamic controllability, timed game automata, controller synthesis, advanced temporal planning under uncertainty}
}

Keywords: cstnud, dynamic controllability, timed game automata, controller synthesis, advanced temporal planning under uncertainty
Collection: 24th International Symposium on Temporal Representation and Reasoning (TIME 2017)
Issue Date: 2017
Date of publication: 25.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI