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:
Classical Dynamic Controllability Revisited: A Tighter Bound on the Classical Algorithm
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 6th International Conference on Agents and Artificial Intelligence (ICAART)
Conference:
6th International Conference on Agents and Artificial Intelligence (ICAART 2014), 6-8 March 2014, Angers, France
Pages:
130-141
Year of publ.:
2014
URI:
urn:nbn:se:liu:diva-102963
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-102963
Subject category:
Computer Science
Keywords(en) :
Temporal Networks, Dynamic Controllability
Project:
CADICS, CUAS, Sherpa, ELLIIT, NFFP6
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.

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-01-09
Created:
2014-01-09
Last updated:
2014-03-20
Statistics:
34 hits