New Techniques for Checking Dynamic Controllability of Simple Temporal Networks with Uncertainty

摘要: A Simple Temporal Network with Uncertainty STNU is a structure for representing time-points, temporal constraints, and intervals uncertain--but bounded--durations. The most important property of an whether it dynamically controllable DC--that is, there exists strategy executing its time-points such that all constraints will necessarily be satisfied no matter how the uncertain durations turn out. Algorithms checking from scratch STNUs are called full DC-checking algorithms. insertion one new constraint into preserves dynamic controllability incremental This paper introduces novel techniques speeding up both DC checking. first technique, rotating Dijkstra, enables generated by propagation to immediately incorporated network. second uses heuristics exploit nesting certain paths in graphs determine good orders which propagate constraints. third only applies checking, maintains information acquired previous invocations reduce redundant computation. contribution algorithm, Inky, results using these techniques. Like fastest known competitors, Inky cubic-time algorithm. However, comparative empirical evaluation top algorithms, have very recently appeared literature, must left future work.