Abstract
Simple Temporal Networks with Uncertainty
(STNUs) provide a useful formalism with which
to reason about events and the temporal constraints
that apply to them. STNUs are in particular
notable because they facilitate reasoning over
stochastic, or uncontrollable, actions and their
corresponding durations. To evaluate the feasibility of a set of constraints associated with an
STNU, one checks the network’s dynamic controllability, which determines whether an adaptive
schedule can be constructed on-the-fly. Our work
improves the runtime of checking the dynamic
controllability of STNUs with integer bounds to
O
min(mn, m?n log N) + km + k2n + kn log n.
Our approach pre-processes the STNU using an
existing O(n3) dynamic controllability checking
algorithm and provides tighter bounds on its
runtime. This makes our work easily adaptable to
other algorithms that rely on checking variants of
dynamic controllability