Incremental Dynamic Controllability in Cubic Worst-Case Time
Nilsson, Mikael Kvarnström, Jonas Doherty, Patrick 2014 (English)In: Proceedings of the 21st International Symposium on Temporal Representation and Reasoning (TIME), 2014, 17-26Conference paper (Refereed)
It is generally hard to predict the exact duration of an action. The uncertainty in the duration is often modeled in temporal planning by the use of upper bounds on durations, with the 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 ready to eat. Simple Temporal Problems with Uncertainty (STPUs) allow us to model such situations. An STPU-based planner must verify that the plans it generates are executable, captured by the property of dynamic controllability. The EfficientIDC (EIDC) algorithm can do this incrementally during planning, with an amortized complexity per step of $O(n^3)$ but a worst-case complexity per step of $O(n^4)$. In this paper we show that the worst-case run-time of EIDC does occur, leading to repeated reprocessing of nodes in the STPU while verifying the dynamic controllability property. We present a new version of the algorithm, called EIDC2, which through optimal ordering of nodes avoids any need for reprocessing. This gives EIDC2 a strictly lower worst-case run-time, making it the fastest known algorithm for incrementally verifying dynamic controllability of STPUs.
Temporal Networks, Dynamic Controllability, Incremental Algorithm
National CategoryComputer Science
IdentifiersURN: urn:nbn:se:liu:diva-107602DOI: 10.1109/TIME.2014.13ISBN: 978-1-4799-4228-2OAI: oai:DiVA.org:liu-107602DiVA: diva2:725791
21st International Symposium on Temporal Representation and Reasoning (TIME 2014), 8-10 September 2014, Verona, Italy
FunderSwedish Research CouncileLLIIT - The Linköping‐Lund Initiative on IT and Mobile CommunicationsSwedish Foundation for Strategic Research EU, FP7, Seventh Framework ProgrammeVINNOVA