BakSTP

What is an STN (simple temporal network)?

Simple Temporal Problems (Networks)

The notion of time is central to temporal planning. EUROPA uses variables to explicitly represent timepoints for plan activities and states. Constraints among timepoints provide a natural way to express domain axioms. For example, in order to state that activity A must occur before activity B we can say that the end timepoint of A is <= the start timepoint of B. Dechter et al. (Dechter 1991) proposed that constraints among timepoints can be grouped together to form a Simple Temporal Network (STN). Such a network can be transformed into a Distance Graph (DG) where the outward arc from a node represents the maximum distance from the source node to the target node. The diagram below illustrates a simple STN with just 2 variables and a single constraint. It also shows the resulting DG.

![stn] (images/stn.png)

Dechter et al. (Dechter 1991) also showed that shortest path algorithms could be used to propagate values in the network and discover a negative cycle. A negative cycle is a path from a node to itself that has a path length less than 0. If such a cycle exists, the network is inconsistent. It was further shown that a single-source shortest path algorithm was sufficient to detect a negative cycle and provide sufficient propagation to yield a backtrack-free search. Thus we have an efficient and complete algorithm for propagating an STN. These results build on the already established notion of a CSP and are naturally incorporated into the general representation and propagation scheme used in EUROPA.