License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2017.9
URN: urn:nbn:de:0030-drops-79155
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7915/
Go to the corresponding LIPIcs Volume Portal


Cairo, Massimo ; Combi, Carlo ; Comin, Carlo ; Hunsberger, Luke ; Posenato, Roberto ; Rizzi, Romeo ; Zavatteri, Matteo

Incorporating Decision Nodes into Conditional Simple Temporal Networks

pdf-format:
LIPIcs-TIME-2017-9.pdf (0.7 MB)


Abstract

A Conditional Simple Temporal Network (CSTN) augments a Simple Temporal Network (STN) to include special time-points, called observation time-points. In a CSTN, the agent executing the network controls the execution of every time-point. However, each observation time-point has a unique propositional letter associated with it and, when the agent executes that time-point, the environment assigns a truth value to the corresponding letter. Thus, the agent observes but, does not control the assignment of truth values. A CSTN is dynamically consistent (DC) if there exists a strategy for executing its time-points such that all relevant constraints will be satisfied no matter which truth values the environment assigns to the propositional letters. Alternatively, in a Labeled Simple Temporal Network (Labeled STN) - also called a Temporal Plan with Choice - the agent executing the network controls the assignment of values to the so-called choice variables. Furthermore, the agent can make those assignments at any time. For this reason, a Labeled STN is equivalent to a Disjunctive Temporal Network. This paper incorporates both of the above extensions by augmenting a CSTN to include not only observation time-points but also decision time-points. A decision time-point is like an observation time-point in that it has an associated propositional letter whose value is determined when the decision time-point is executed. It differs in that the agent - not the environment - selects that value. The resulting network is called a CSTN with Decisions (CSTND). This paper shows that a CSTND generalizes both CSTNs and Labeled STNs, and proves that the problem of determining whether any given CSTND is dynamically consistent is PSPACE-complete. It also presents algorithms that address two sub-classes of CSTNDs: (1) those that contain only decision time-points; and (2) those in which all decisions are made before execution begins.

BibTeX - Entry

@InProceedings{cairo_et_al:LIPIcs:2017:7915,
  author =	{Massimo Cairo and Carlo Combi and Carlo Comin and Luke Hunsberger and Roberto Posenato and Romeo Rizzi and Matteo Zavatteri},
  title =	{{Incorporating Decision Nodes into Conditional Simple Temporal Networks}},
  booktitle =	{24th International Symposium on Temporal Representation and Reasoning (TIME 2017)},
  pages =	{9:1--9:18},
  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/7915},
  URN =		{urn:nbn:de:0030-drops-79155},
  doi =		{10.4230/LIPIcs.TIME.2017.9},
  annote =	{Keywords: Conditional Simple Temporal Networks with Decisions, Dynamic Consistency, SAT Solver, Hyper Temporal Networks, PSPACE}
}

Keywords: Conditional Simple Temporal Networks with Decisions, Dynamic Consistency, SAT Solver, Hyper Temporal Networks, PSPACE
Seminar: 24th International Symposium on Temporal Representation and Reasoning (TIME 2017)
Issue Date: 2017
Date of publication: 14.09.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI