Dynamic controllability of simple temporal networks with uncertainty: Simple rules and fast real-time execution

摘要: Abstract Simple Temporal Networks (STNs) are a well-studied model for representing temporal constraints. They comprise set of time-points (real-valued variables execution times) and binary difference constraints among them. with Uncertainty (STNUs) extend STNs in that some (called contingent) treated as exogenous variables, whose times, bound to fall within given interval from the corresponding activation (as specified by “contingent link”), get revealed only during real-time execution. An STNU is dynamically controllable (DC) if there exists strategy execute its satisfying all constraints, regardless times contingent In this work we present new system constraint propagation rules STNUs, which sound-and-complete DC checking. Our comprises just three which, differently ones proposed previous works, generate unconditioned particular, after applying any our rules, network remains an respects. Moreover, completeness proof short non-algorithmic, based on explicit construction valid strategy. This substantial simplification theory underlies efficient algorithms DC-checking. analysis also shows: (1) existence late strategies (2) equivalence notion several variants semantics (3) fast algorithm runs O ( K N ) total time ≥ 1 links points, considerably improving 3 -time bound.