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.2018.15
URN: urn:nbn:de:0030-drops-97808
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9780/
Go to the corresponding LIPIcs Volume Portal

Hunsberger, Luke ; Posenato, Roberto

Reducing epsilon-DC Checking for Conditional Simple Temporal Networks to DC Checking

pdf-format:
LIPIcs-TIME-2018-15.pdf (0.5 MB)

Abstract

Recent work on Conditional Simple Temporal Networks (CSTNs) has introduced the problem of checking the dynamic consistency (DC) property for the case where the reaction time of an execution strategy to observations is bounded below by some fixed epsilon > 0, the so-called epsilon-DC-checking problem. This paper proves that the epsilon-DC-checking problem for CSTNs can be reduced to the standard DC-checking problem for CSTNs - without incurring any computational cost. Given any CSTN S with k observation time-points, the paper defines a new CSTN S_0 that is the same as S, except that for each observation time-point P? in S: (i) P? is demoted to a non-observation time-point in S_0; and (ii) a new observation time-point P_0?, constrained to occur exactly epsilon units after P?, is inserted into S_0. The paper proves that S is epsilon-DC if and only if S_0 is (standard) DC, and that the application of the epsilon-DC-checking constraint-propagation rules to S is equivalent to the application of the corresponding (standard) DC-checking constraint-propagation rules to S_0. Two versions of these results are presented that differ only in whether a dynamic strategy for S_0 can react instantaneously to observations, or only after some arbitrarily small, positive delay. Finally, the paper demonstrates empirically that building S_0 and DC-checking it incurs no computational cost as the sizes of the instances increase.

BibTeX - Entry

@InProceedings{hunsberger_et_al:LIPIcs:2018:9780,
  author =	{Luke Hunsberger and Roberto Posenato},
  title =	{{Reducing epsilon-DC Checking for Conditional Simple Temporal Networks to DC Checking}},
  booktitle =	{25th International Symposium on Temporal Representation  and Reasoning (TIME 2018)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-089-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{120},
  editor =	{Natasha Alechina and Kjetil N{\o}rv{\aa}g and Wojciech Penczek},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9780},
  URN =		{urn:nbn:de:0030-drops-97808},
  doi =		{10.4230/LIPIcs.TIME.2018.15},
  annote =	{Keywords: Conditional Simple Temporal Networks, Dynamic Consistency, Temporal Constraints}
}

Keywords: Conditional Simple Temporal Networks, Dynamic Consistency, Temporal Constraints
Collection: 25th International Symposium on Temporal Representation and Reasoning (TIME 2018)
Issue Date: 2018
Date of publication: 08.10.2018

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