Incremental Dynamic Controllability in Cubic Worst-Case Time
2014 (English)In: Proceedings of the 21st International Symposium on Temporal Representation and Reasoning (TIME) / [ed] Cesta, A; Combi, C; Laroussinie, F, IEEE Computer Society Digital Library, 2014, 17-26 p.Conference 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.
Place, publisher, year, edition, pages
IEEE Computer Society Digital Library, 2014. 17-26 p.
International Workshop on Temporal Representation and Reasoning. Proceedings, ISSN 1530-1311
Temporal Networks, Dynamic Controllability, Incremental Algorithm
IdentifiersURN: urn:nbn:se:liu:diva-107602DOI: 10.1109/TIME.2014.13ISI: 000349455500002ISBN: 978-1-4799-4227-5OAI: 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 Council, CADICSeLLIIT - The Linköping‐Lund Initiative on IT and Mobile CommunicationsSwedish Foundation for Strategic Research , CUASEU, FP7, Seventh Framework Programme, SHERPAVINNOVA, 2013-01206