liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Publications (8 of 8) Show all publications
Nilsson, M., Kvarnström, J. & Doherty, P. (2016). Efficient Processing of Simple Temporal Networks with Uncertainty: Algorithms for Dynamic Controllability Verification. Acta Informatica, 53(6-8), 723-752
Open this publication in new window or tab >>Efficient Processing of Simple Temporal Networks with Uncertainty: Algorithms for Dynamic Controllability Verification
2016 (English)In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 53, no 6-8, p. 723-752Article 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
Keywords
Temporal Networks, Simple Temporal Networks with Uncertainty, Dynamic Controllability
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-121949 (URN)10.1007/s00236-015-0248-8 (DOI)000383702800007 ()
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: 2018-01-11
Nilsson, M. (2015). Efficient Temporal Reasoning with Uncertainty. (Licentiate dissertation). Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>Efficient Temporal Reasoning with Uncertainty
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. p. 116
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1722
Keywords
Temporal Reasoning, Dynamic Controllability, Simple Temporal Network with Uncertainty, Incremental Algorithms, Temporal Networks
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-119409 (URN)10.3384/lic.diva-119409 (DOI)978-91-7685-991-9 (ISBN)
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: 2018-01-11Bibliographically approved
Nilsson, M., Kvarnström, J. & Doherty, P. (2015). Revisiting Classical Dynamic Controllability: A Tighter Complexity Analysis. In: Béatrice Duval; Jaap van den Herik; Stephane Loiseau; Joaquim Filipe (Ed.), Agents and Artificial Intelligence: 6th International Conference, ICAART 2014, Angers, France, March 6–8, 2014, Revised Selected Papers. Paper presented at 6th International Conference, ICAART 2014, Angers, France, March 6-8, 2014 (pp. 243-261). Springer, 8946
Open this publication in new window or tab >>Revisiting Classical Dynamic Controllability: A Tighter Complexity Analysis
2015 (English)In: Agents and Artificial Intelligence: 6th International Conference, ICAART 2014, Angers, France, March 6–8, 2014, Revised Selected Papers / [ed] Béatrice Duval; Jaap van den Herik; Stephane Loiseau; Joaquim Filipe, Springer, 2015, Vol. 8946, p. 243-261Conference paper, Published paper (Refereed)
Abstract [en]

Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems where some durations are uncontrollable (determined by nature), as is often the case for actions in planning.  It is essential to verify that such networks are dynamically controllable (DC) -- executable regardless of the outcomes of uncontrollable durations -- and to convert them to an executable form. We use insights from incremental DC verification algorithms to re-analyze the original, classical, verification algorithm. This algorithm is the entry level algorithm for DC verification, based on a less complex and more intuitive theory than subsequent algorithms. We show that with a small modification the algorithm is transformed from pseudo-polynomial to O(n4) which makes it still useful.  We also discuss a change reducing the amount of work performed by the algorithm.

Place, publisher, year, edition, pages
Springer, 2015
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 8946
Keywords
Temporal Networks, Classical Algorithm
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-121695 (URN)10.1007/978-3-319-25210-0_15 (DOI)000366298500015 ()978-3-319-25209-4 (ISBN)978-3-319-25210-0 (ISBN)
Conference
6th International Conference, ICAART 2014, Angers, France, March 6-8, 2014
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, 2013-01206CUGS (National Graduate School in Computer Science)
Available from: 2015-10-02 Created: 2015-10-01 Last updated: 2018-02-20Bibliographically approved
Nilsson, M., Kvarnström, J. & Doherty, P. (2014). Classical Dynamic Controllability Revisited: A Tighter Bound on the Classical Algorithm. In: Proceedings of the 6th International Conference on Agents and Artificial Intelligence (ICAART): . Paper presented at 6th International Conference on Agents and Artificial Intelligence (ICAART 2014), 6-8 March 2014, Angers, France (pp. 130-141).
Open this publication in new window or tab >>Classical Dynamic Controllability Revisited: A Tighter Bound on the Classical Algorithm
2014 (English)In: Proceedings of the 6th International Conference on Agents and Artificial Intelligence (ICAART), 2014, p. 130-141Conference paper, Published paper (Refereed)
Abstract [en]

Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems wheresome durations are uncontrollable (determined by nature), as is often the case for actions in planning. It is essentialto verify that such networks are dynamically controllable (DC) – executable regardless of the outcomesof uncontrollable durations – and to convert them to an executable form. We use insights from incrementalDC verification algorithms to re-analyze the original verification algorithm. This algorithm, thought to bepseudo-polynomial and subsumed by an O(n5) algorithm and later an O(n4) algorithm, is in fact O(n4) givena small modification. This makes the algorithm attractive once again, given its basis in a less complex andmore intuitive theory. Finally, we discuss a change reducing the amount of work performed by the algorithm.

Keywords
Temporal Networks, Dynamic Controllability
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-102963 (URN)10.5220/0004815801300141 (DOI)978-989-758-015-4 (ISBN)
Conference
6th International Conference on Agents and Artificial Intelligence (ICAART 2014), 6-8 March 2014, Angers, France
Projects
CADICSCUASSherpaELLIITNFFP6
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, 2013-01206
Available from: 2014-01-09 Created: 2014-01-09 Last updated: 2018-01-11
Nilsson, M., Kvarnström, J. & Doherty, P. (2014). EfficientIDC: A Faster Incremental Dynamic Controllability Algorithm. In: Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS): . Paper presented at 24th International Conference on Automated Planning and Scheduling (ICAPS 2014), 21-26 June 2014, Portsmouth, USA (pp. 199-207). AAAI Press
Open this publication in new window or tab >>EfficientIDC: A Faster Incremental Dynamic Controllability Algorithm
2014 (English)In: Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, 2014, p. 199-207Conference paper, Published paper (Refereed)
Abstract [en]

Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems where some durations are uncontrollable (determined by nature), as is often the case for actions in planning. It is essential to verify that such networks are dynamically controllable (DC) – executable regardless of the outcomes of uncontrollable durations – and to convert them to an executable form. We use insights from incremental DC verification algorithms to re-analyze the original verification algorithm. This algorithm, thought to be pseudo-polynomial and subsumed by an O(n5) algorithm and later an O(n4) algorithm, is in fact O(n4) given a small modification. This makes the algorithm attractive once again, given its basis in a less complex and more intuitive theory. Finally, we discuss a change reducing the amount of work performed by the algorithm.

Place, publisher, year, edition, pages
AAAI Press, 2014
Keywords
Temporal Networks, Dynamic Controllability, Incremental Algorithm
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-103012 (URN)978-1-57735-660-8 (ISBN)
Conference
24th International Conference on Automated Planning and Scheduling (ICAPS 2014), 21-26 June 2014, Portsmouth, USA
Projects
CUASCADICSNFFP6SherpaELLIIT
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, 2013-01206
Available from: 2014-01-09 Created: 2014-01-09 Last updated: 2018-01-11
Nilsson, M., Kvarnström, J. & Doherty, P. (2014). Incremental Dynamic Controllability in Cubic Worst-Case Time. In: Cesta, A; Combi, C; Laroussinie, F (Ed.), Proceedings of the 21st International Symposium on Temporal Representation and Reasoning (TIME): . Paper presented at 21st International Symposium on Temporal Representation and Reasoning (TIME 2014), 8-10 September 2014, Verona, Italy (pp. 17-26). IEEE Computer Society Digital Library
Open this publication in new window or tab >>Incremental Dynamic Controllability in Cubic Worst-Case Time
2014 (English)In: Proceedings of the 21st International Symposium on Temporal Representation and Reasoning (TIME) / [ed] Cesta, A; Combi, C; Laroussinie, F, IEEE Computer Society Digital Library, 2014, p. 17-26Conference paper, Published paper (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.

Place, publisher, year, edition, pages
IEEE Computer Society Digital Library, 2014
Series
International Workshop on Temporal Representation and Reasoning. Proceedings, ISSN 1530-1311
Keywords
Temporal Networks, Dynamic Controllability, Incremental Algorithm
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-107602 (URN)10.1109/TIME.2014.13 (DOI)000349455500002 ()978-1-4799-4227-5 (ISBN)
Conference
21st International Symposium on Temporal Representation and Reasoning (TIME 2014), 8-10 September 2014, Verona, Italy
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, 2013-01206
Available from: 2014-06-17 Created: 2014-06-17 Last updated: 2018-01-11
Nilsson, M., Kvarnström, J. & Doherty, P. (2013). Incremental Dynamic Controllability Revisited. In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS): . Paper presented at 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), 10-14 June 2013, Rom, Italy. AAAI Press
Open this publication in new window or tab >>Incremental Dynamic Controllability Revisited
2013 (English)In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS), AAAI Press, 2013Conference paper, Published paper (Refereed)
Abstract [en]

Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems where some durations are determined by nature, as is often the case for actions in planning. As such networks are generated it is essential to verify that they are dynamically controllable – executable regardless of the outcomes of uncontrollable durations – and to convert them to a dispatchable form. The previously published FastIDC algorithm achieves this incrementally and can therefore be used efficiently during plan construction. In this paper we show that FastIDC is not sound when new constraints are added, sometimes labeling networks as dynamically controllable when they are not. We analyze the algorithm, pinpoint the cause, and show how the algorithm can be modified to correctly detect uncontrollable networks.

Place, publisher, year, edition, pages
AAAI Press, 2013
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-88634 (URN)978-1-57735-609-7 (ISBN)
Conference
23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), 10-14 June 2013, Rom, Italy
Projects
CUASCADICSSHERPAELLIIT
Available from: 2013-02-14 Created: 2013-02-14 Last updated: 2018-01-11
Nilsson, M. (2013). On the Complexity of Finding Spanner Paths. In: Sandor P. Fekete (Ed.), Booklet of Abstracts, The European Workshop on Computational Geometry (EuroCG): . Paper presented at The 29th European Workshop on Computational Geometry (EuroCG), March 17-20, Braunschweig, Germany (pp. 77-80).
Open this publication in new window or tab >>On the Complexity of Finding Spanner Paths
2013 (English)In: Booklet of Abstracts, The European Workshop on Computational Geometry (EuroCG) / [ed] Sandor P. Fekete, 2013, p. 77-80Conference paper, Oral presentation with published abstract (Refereed)
Abstract [en]

We study the complexity of finding so called spanner paths between arbitrary nodes in Euclidean graphs. We study both general Euclidean graphs and a special type of graphs called Integer Graphs. The problem is proven NP-complete for general Euclidean graphs with non-constant stretches (e.g. (2n)^(3/2) where n denotes the number of nodes in the graph). An algorithm solving the problem in O(2^(0.822n)) is presented. Integer graphs are simpler and for these special cases a better algorithm is presented. By using a partial order of so called Images the algorithm solves the spanner path problem using O(2^(c(\log n)^2)) time, where c is a constant depending only on the stretch.

Keywords
Spanners, Euclidean Distance Approximation, Computational Geometry, Complexity Classification, Combinatorial Optimization
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-93332 (URN)
Conference
The 29th European Workshop on Computational Geometry (EuroCG), March 17-20, Braunschweig, Germany
Available from: 2013-05-30 Created: 2013-05-30 Last updated: 2018-01-11Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-2849-3316

Search in DiVA

Show all publications