Efficient execution of dynamically controllable simple temporal networks with uncertainty

摘要: A simple temporal network with uncertainty (STNU) is a data structure for representing and reasoning about constraints where the durations of certain intervals--the contingent links--are only discovered during execution. The most important property an STNU whether it dynamically controllable (DC)--that is, there exists strategy executing its time-points that will guarantee all be satisfied no matter how links turn out. literature on STNUs includes variety DC-checking algorithms execution algorithms. fastest algorithm reported so far $$O(N^3)$$O(N3)-time due to Morris (Integration AI OR techniques in constraint programming--11th international conference, CPAIOR 2014, volume 8451 Lecture Notes Computer Science. Springer, Berlin, pp 464---479, 2014). Hunsberger (Proceedings 20th symposium representation (TIME-2013). IEEE Society, Washington, 2013). This paper begins by providing first comprehensive, rigorous, yet streamlined treatment theoretical foundations STNUs, including semantics, dynamic controllability, set results have been collected into what has recently called fundamental theorem STNUs. carefully argues from basic definitions proofs major theorems which algorithmic work depends. Although many parts this presentation appeared various forms, papers, scattered nature allowed too holes theory persist, relied often proof sketches leave details unexamined. combines sources, while also introducing novel approaches proofs. concludes presenting modified version recent managing literature. organizes computations more efficiently corrects oversight original algorithm.