Change search
ReferencesLink to record
Permanent link

Direct link
Efficient Processing of Simple Temporal Networks with Uncertainty: Algorithms for Dynamic Controllability Verification
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-2849-3316
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-5500-8494
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
2016 (English)In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 53, no 6-8, 723-752 p.Article in journal (Refereed) Published
Abstract [en]

Temporal formalisms are essential for reasoning about actions that are carried out over time. The exact durations of such actions are generally hard to predict. In temporal planning, the resulting uncertainty is often worked around by only considering upper bounds on durations, with the assumption that when 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. 

Using Simple Temporal Networks with Uncertainty (STNU), a planner can correctly take both lower and upper duration bounds into  account. It must then verify that the plans it generates are executable regardless of the actual outcomes of the uncertain durations. This is captured by the property of dynamic controllability (DC), which should be verified incrementally during plan generation. 

Recently a new incremental algorithm for verifying dynamic controllability was proposed: EfficiantIDC, which can verify if an STNU that is DC remains DC after the addition or tightening of a constraint (corresponding to a new action being added to a plan). The algorithm was shown to have a worst case complexity of O(n4) for each addition or tightening. This can be amortized over the construction of a whole STNU for an amortized complexity in O(n3). In this paper we improve the EfficientIDC algorithm in a way that prevents it from having to reprocess nodes. This improvement leads to a lower worst case complexity in O(n3).

Place, publisher, year, edition, pages
Springer Publishing Company, 2016. Vol. 53, no 6-8, 723-752 p.
Keyword [en]
Temporal Networks, Simple Temporal Networks with Uncertainty, Dynamic Controllability
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-121949DOI: 10.1007/s00236-015-0248-8ISI: 000383702800007OAI: oai:DiVA.org:liu-121949DiVA: diva2:860637
Funder
Swedish Research Council, CADICSELLIIT - The Linköping‐Lund Initiative on IT and Mobile CommunicationsSwedish Foundation for Strategic Research , CUASEU, FP7, Seventh Framework Programme, SHERPAVINNOVA, NFFP6 2013-01206
Available from: 2015-10-13 Created: 2015-10-13 Last updated: 2016-11-12

Open Access in DiVA

fulltext(660 kB)5 downloads
File information
File name FULLTEXT01.pdfFile size 660 kBChecksum SHA-512
9065599d0ee04fdff9d1454a1ef355ae870e54116ad81efbcada89a4388923b688c60951c667c2012e4f17ec3f5fb32bf6c33d77f8d807f91cd6521879372327
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Nilsson, MikaelKvarnström, JonasDoherty, Patrick
By organisation
Artificial Intelligence and Integrated Computer SystemsFaculty of Science & Engineering
In the same journal
Acta Informatica
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 5 downloads
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

Altmetric score

Total: 112 hits
ReferencesLink to record
Permanent link

Direct link