Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Series
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
Identifiers
URN: urn:nbn:se:liu:diva-119409DOI: 10.3384/lic.diva-119409ISBN: 978-91-7685-991-9 (print)OAI: oai:DiVA.org:liu-119409DiVA: diva2:847532
Presentation
2015-09-10, Alan Turing, Hus E, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Funder
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)173 downloads
File information
File name FULLTEXT01.pdfFile size 1381 kBChecksum SHA-512
c240b4d4352e845496a0a5fd277cb8f697d3b3bcf74831d459aff094f0b12f92ec830258f27d13b1f15a0d9006eb46782f32b06c97ee6056522f48d53e842855
Type fulltextMimetype application/pdf
omslag(33 kB)8 downloads
File information
File name COVER01.pdfFile size 33 kBChecksum SHA-512
46b7189d9fccca4503d9603bf0e2290f6222e28a7df4d083eb0a1b0b0f9114094630bc41744220dfd0341d16be2777a20d1bfc11cec0eb0e948f6ef9a1ce41bf
Type coverMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Nilsson, Mikael

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: 173 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 2306 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf