2026-07-22T22:18:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7915 2024-03-06T10:41:34Z ddc:004 open_access

Incorporating Decision Nodes into Conditional Simple Temporal Networks Cairo, Massimo Combi, Carlo Comin, Carlo Hunsberger, Luke Posenato, Roberto Rizzi, Romeo Zavatteri, Matteo Conditional Simple Temporal Networks with Decisions Dynamic Consistency SAT Solver Hyper Temporal Networks PSPACE 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Massimo Cairo and Carlo Combi and Carlo Comin and Luke Hunsberger and Roberto Posenato and Romeo Rizzi and Matteo Zavatteri 2017 Is Part Of LIPIcs, Volume 90, 24th International Symposium on Temporal Representation and Reasoning (TIME 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TIME.2017.9 urn:nbn:de:0030-drops-79155 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2017.9 eng https://creativecommons.org/licenses/by/3.0/legalcode