liu.seSearch for publications in DiVA
ReferencesLink to record
Permanent link

Direct link
Incremental Dynamic Controllability in Cubic Worst-Case Time
2014 (English)In: Proceedings of the 21st International Symposium on Temporal Representation and Reasoning (TIME), 2014Konferensbidrag (Refereed)
Abstract [en]

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.

Keyword [en]
Temporal Networks, Dynamic Controllability, Incremental Algorithm
National Category
Computer Science
Identifiers
urn:nbn:se:liu:diva-107602 (URN)oai:DiVA.org:liu-107602 (OAI)
Conference
21st International Symposium on Temporal Representation and Reasoning (TIME 2014), 8-10 September 2014, Verona, Italy
Funder
Swedish Research CouncileLLIIT - The Linköping‐Lund Initiative on IT and Mobile CommunicationsSwedish Foundation for Strategic Research EU, FP7, Seventh Framework ProgrammeVinnova
Available from2014-06-17 Created:2014-06-17 Last updated:2014-10-23

Open Access in DiVA

No fulltext

Search in DiVA

By author/editor
Nilsson, MikaelKvarnström, JonasDoherty, Patrick
By organisation
Artificial Intelligence and Intergrated Computer systemsThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Citations

Web of Science®:
Totalt: 17 hits
ReferencesLink to record
Permanent link

Direct link