A paper at TIME 2017

Our paper,

Incorporating Decision Nodes into Conditional Simple Temporal Networks

has been accepted at TIME 2017, to be held at Université de Mons, Belgium, Oct. 2017.

Abstract. A Conditional Simple Temporal Network (CSTN) is an extension of Simple Temporal Network (STN) having some special time-points, named observation time-points. In a STN/CSTN, the agent executing the network controls the execution of every time-point. Observation time-points have unique propositional letters associated with them and, when the agent executes one of them, the environment assigns a truth value to the corresponding propositional 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 completely controls the process of assigning 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. A generalisation of the Bellman-Ford algorithm to accommodate the propagation of labeled values has been used to determine whether any given Labeled STN is consistent.

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. It proves that the decision problem of determining whether or not any CSTND is dynamically consistent is PSPACE-complete. And it  presents algorithms that restrict attention to two special classes of CSTNDs: (i) those that contain only decision time-points; and (ii) those in which all decisions are made before starting to execute the network.

Download: paper.