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.8
URN: urn:nbn:de:0030-drops-79136
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7913/
Go to the corresponding LIPIcs Volume Portal

Cairo, Massimo ; Rizzi, Romeo

Dynamic Controllability Made Simple

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

Abstract

Simple Temporal Networks with Uncertainty (STNUs) are a well-studied model for representing temporal constraints, where some intervals (contingent links) have an unknown but bounded duration, discovered only during execution. An STNU is dynamically controllable (DC) if there exists a strategy to execute its time-points satisfying all the constraints, regardless of the actual duration of contingent links revealed during execution.

In this work we present a new system of constraint propagation rules for STNUs, which is sound-and-complete for DC checking. Our system comprises just three rules which, differently from the ones proposed in all previous works, only generate unconditioned constraints. In particular, after applying our sound rules, the network remains an STNU in all respects. Moreover, our completeness proof is short and non-algorithmic, based on the explicit construction of a valid execution strategy. This is a substantial simplification of the theory which underlies all the polynomial-time algorithms for DC-checking.

Our analysis also shows: (1) the existence of late execution strategies for STNUs, (2) the equivalence of several variants of the notion of DC, (3) the existence of a fast algorithm for real-time execution of STNUs, which runs in O(KN) total time in a network with K contingent links and N time points, considerably improving the previous O(N^3)-time bound.

BibTeX - Entry

@InProceedings{cairo_et_al:LIPIcs:2017:7913,
  author =	{Massimo Cairo and Romeo Rizzi},
  title =	{{Dynamic Controllability Made Simple}},
  booktitle =	{24th International Symposium on Temporal Representation and Reasoning (TIME 2017)},
  pages =	{8:1--8:16},
  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/7913},
  URN =		{urn:nbn:de:0030-drops-79136},
  doi =		{10.4230/LIPIcs.TIME.2017.8},
  annote =	{Keywords: Simple Temporal Network with Uncertainty, Dynamic controllability}
}

Keywords: Simple Temporal Network with Uncertainty, Dynamic controllability
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