Speeding Up the RUL¯ Dynamic-Controllability-Checking Algorithm for Simple Temporal Networks with Uncertainty

A Simple Temporal Network with Uncertainty (STNU) includes real-valued variables called time points, binary difference constraints on those time points, and contingent links that represent actions with uncertain durations. STNUs have been used for robot control, web service composition, and business processes. The most important property of an STNU is called dynamic controllability (DC), and algorithms for checking this property are called DC-checking algorithms. The DC-checking algorithm for STNUs with the best worst-case time complexity is the RUL¯ algorithm due to Cairo, Hunsberger, and Rizzi. Its complexity is O(mn + k²n + kn log n), where n is the number of time points, m is the number of constraints, and k is the number of contingent links. It is expected that this worst-case complexity cannot be improved upon. However, this paper provides a new algorithm, called RUL2021, that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation.