EfficientIDC: A Faster Incremental Dynamic Controllability Algorithm

Abstract

The exact duration of an action generally cannot be predicted in advance. Temporal planning therefore tends to use upper bounds on durations, with the explicit or implicit assumption that if an action happens to be executed more quickly, the plan will still succeed. However, this assumption is often false: If we finish cooking too early, the dinner will be cold before everyone is at home and can eat. Simple Temporal Problems with Uncertainty (STPUs) allow us to model such situations. An STPU-based planner must then verify that the networks it generates are executable, captured by the property of dynamic controllability. The FastIDC algorithm can do this incrementally during planning. In this paper we show that the FastIDC method can result in traversing part of a temporal network multiple times, with constraints slowly tightening towards their final values. We then present a new algorithm that uses additional analysis together with a different traversal strategy to avoid this behavior. The new algorithm has a guaranteed time complexity lower than that of FastIDC and is proven sound and complete.