Classical Dynamic Controllability Revisited: A Tighter Bound on the Classical Algorithm
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems
Linköping University, The Institute of Technology
Conference paper (Refereed)
Proceedings of the 6th International Conference on Agents and Artificial Intelligence (ICAART)
6th International Conference on Agents and Artificial Intelligence (ICAART 2014), 6-8 March 2014, Angers, France
Temporal Networks, Dynamic Controllability
CADICS, CUAS, Sherpa, ELLIIT, NFFP6
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.
Accepted for Publication.
Swedish Research Council, CADICS
eLLIIT - The Linköping‐Lund Initiative on IT and Mobile Communications
Swedish Foundation for Strategic Research , CUAS
EU, FP7, Seventh Framework Programme, SHERPA