stnu

STNU, short for Simple Temporal Network with Uncertainty, is a formal model used to reason about temporal plans in environments with uncertain durations. It extends the classical Simple Temporal Network (STN) by incorporating contingent links that capture durations not under an agent’s control, while preserving a set of deterministic temporal constraints.

An STNU consists of a set of timepoints, a set of deterministic (requirement) constraints of the form t_j − t_i ≤ w between timepoints, and a set of contingent links that specify bounds on the duration between two timepoints. A contingent link from timepoint i to timepoint j with duration in [l, u] means that if i occurs, then j will occur after some duration d, where l ≤ d ≤ u, and the exact value of d is determined by the environment.

The semantics of an STNU asks whether there exists an execution strategy for choosing the times of controllable timepoints that ensures that all constraints are satisfied for every admissible realization of the contingent durations. An execution strategy is dynamic if the time assigned to controllable timepoints can depend on the actual outcomes of previously realized contingent durations.

STNUs are used in planning, robotics, and automated scheduling where actions have uncertain durations or where external conditions influence timing. They relate to STNs by extending them with uncertainty; they are also discussed in relation to more general temporal networks that include conditional or contingent information.

In practice, algorithms for STNUs aim to determine dynamic controllability and to synthesize execution strategies, enabling plans to be carried out reliably in the face of uncertainty.