Change search
ReferencesLink to record
Permanent link

Direct link
Efficient Temporal Reasoning with Uncertainty
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-2849-3316
2015 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

Automated Planning is an active area within Artificial Intelligence. With the help of computers we can quickly find good plans in complicated problem domains, such as planning for search and rescue after a natural disaster. When planning in realistic domains the exact duration of an action generally cannot be predicted in advance. Temporal planning therefore tends to use upper bounds on durations, with the explicit or implicit 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 at home and can eat. Simple Temporal Networks with Uncertainty (STNUs) allow us to model such situations. An STNU-based planner must verify that the temporal problems it generates are executable, which is captured by the property of dynamic controllability (DC). If a plan is not dynamically controllable, adding actions cannot restore controllability. Therefore a planner should verify after each action addition whether the plan remains DC, and if not, backtrack. Verifying dynamic controllability of a full STNU is computationally intensive. Therefore, incremental DC verification algorithms are needed.

We start by discussing two existing algorithms relevant to the thesis. These are the very first DC verification algorithm called MMV (by Morris, Muscettola and Vidal) and the incremental DC verification algorithm called FastIDC, which is based on MMV.

We then show that FastIDC is not sound, sometimes labeling networks as dynamically controllable when they are not.  We analyze the algorithm to pinpoint the cause and show how the algorithm can be modified to correctly and efficiently detect uncontrollable networks.

In the next part we use insights from this work to re-analyze the MMV algorithm. This algorithm is pseudo-polynomial and was later subsumed by first an n5 algorithm and then an n4 algorithm. We show that the basic techniques used by MMV can in fact be used to create an n4 algorithm for verifying dynamic controllability, with a new termination criterion based on a deeper analysis of MMV. This means that there is now a comparatively easy way of implementing a highly efficient dynamic controllability verification algorithm. From a theoretical viewpoint, understanding MMV is important since it acts as a building block for all subsequent algorithms that verify dynamic controllability. In our analysis we also discuss a change in MMV which reduces the amount of regression needed in the network substantially.

In the final part of the thesis we show that the FastIDC method can result in traversing part of a temporal network multiple times, with constraints slowly tightening towards their final values.  As a result of our analysis we then present a new algorithm with an improved traversal strategy that avoids this behavior.  The new algorithm, EfficientIDC, has a time complexity which is lower than that of FastIDC. We prove that it is sound and complete.


Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2015. , 116 p.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1722
Keyword [en]
Temporal Reasoning, Dynamic Controllability, Simple Temporal Network with Uncertainty, Incremental Algorithms, Temporal Networks
National Category
Computer Science
URN: urn:nbn:se:liu:diva-119409DOI: 10.3384/lic.diva-119409ISBN: 978-91-7685-991-9 (print)OAI: diva2:847532
2015-09-10, Alan Turing, Hus E, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
CUGS (National Graduate School in Computer Science)Swedish 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
Available from: 2015-08-31 Created: 2015-06-16 Last updated: 2015-08-31Bibliographically approved

Open Access in DiVA

fulltext(1381 kB)109 downloads
File information
File name FULLTEXT01.pdfFile size 1381 kBChecksum SHA-512
Type fulltextMimetype application/pdf
omslag(33 kB)6 downloads
File information
File name COVER01.pdfFile size 33 kBChecksum SHA-512
Type coverMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Nilsson, Mikael
By organisation
Artificial Intelligence and Intergrated Computer systemsFaculty of Science & Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 109 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: 436 hits
ReferencesLink to record
Permanent link

Direct link