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.9
URN: urn:nbn:de:0030-drops-79155
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7915/
Cairo, Massimo ;
Combi, Carlo ;
Comin, Carlo ;
Hunsberger, Luke ;
Posenato, Roberto ;
Rizzi, Romeo ;
Zavatteri, Matteo
Incorporating Decision Nodes into Conditional Simple Temporal Networks
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 |
|
Collection: |
|
24th International Symposium on Temporal Representation and Reasoning (TIME 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
25.09.2017 |
