: A Tighter Bound on the Classical Algorithm
Nilsson, Mikael Kvarnström, Jonas Doherty, Patrick 2014 (English)In: Proceedings of the 6th International Conference on Agents and Artificial Intelligence (ICAART), 2014, 130-141Conference paper (Refereed)
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.
Temporal Networks, Dynamic Controllability
National CategoryComputer Science
Identifiersurn:nbn:se:liu:diva-102963 (URN)10.5220/0004815801300141 (DOI)oai:DiVA.org:liu-102963 (OAI)diva2:685353 (DiVA)
6th International Conference on Agents and Artificial Intelligence (ICAART 2014), 6-8 March 2014, Angers, France
Swedish Research CouncileLLIIT - The Linköping‐Lund Initiative on IT and Mobile CommunicationsSwedish Foundation for Strategic Research EU, FP7, Seventh Framework ProgrammeVinnova