LiU Electronic Press
Full-text not available in DiVA
Author:
Nilsson, Mikael (Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems) (Linköping University, The Institute of Technology)
Kvarnström, Jonas (Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems) (Linköping University, The Institute of Technology)
Doherty, Patrick (Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems) (Linköping University, The Institute of Technology)
Title:
Incremental Dynamic Controllability in Cubic Worst-Case Time
Department:
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems
Linköping University, The Institute of Technology
Publication type:
Conference paper (Refereed)
Language:
English
In:
Proceedings of the 21th International Symposium on Temporal Representation and Reasoning (TIME)
Conference:
21th International Symposium on Temporal Representation and Reasoning (TIME 2014), 8-10 September 2014, Verona, Italy
Year of publ.:
2014
URI:
urn:nbn:se:liu:diva-107602
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-107602
Subject category:
Computer Science
Keywords(en) :
Temporal Networks, Dynamic Controllability, Incremental Algorithm
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.

Note:

Accepted for Publication.

Research funder:
Swedish Research Council, CADICS
Research funder:
eLLIIT - The Linköping‐Lund Initiative on IT and Mobile Communications
Research funder:
Swedish Foundation for Strategic Research , CUAS
Research funder:
EU, FP7, Seventh Framework Programme, SHERPA
Research funder:
Vinnova, 2013-01206
Available from:
2014-06-17
Created:
2014-06-17
Last updated:
2014-08-08
Statistics:
7 hits