A Faster Algorithm for Checking the Dynamic Controllability of Simple Temporal Networks with Uncertainty

Luke Hunsberger

2014

Abstract

A Simple Temporal Network (STN) is a structure containing time-points and temporal constraints that an agent can use to manage its activities. A Simple Temporal Network with Uncertainty (STNU) augments an STN to include contingent links that can be used to represent actions with uncertain durations. The most important property of an STNU is whether it is dynamically controllable (DC)—that is, whether there exists a strategy for executing its time-points such that all constraints will necessarily be satisfied no matter how the contingent durations happen to turn out (within their known bounds). The fastest algorithm for checking the dynamic controllability of STNUs reported in the literature so far is the O(N4)-time algorithm due to Morris. This paper presents a new DC-checking algorithm that empirical results confirm is faster than Morris’ algorithm, in many cases showing an order of magnitude speed-up. The algorithm employs two novel techniques. First, new constraints generated by propagation are immediately incorporated into the network using a technique called rotating Dijkstra. Second, a heuristic that exploits the nesting structure of certain paths in the STNU graph is used to determine a good order in which to process the contingent links during constraint propagation.

Paper Citation

in Harvard Style

Hunsberger L. (2014). A Faster Algorithm for Checking the Dynamic Controllability of Simple Temporal Networks with Uncertainty . In Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-758-015-4, pages 63-73. DOI: 10.5220/0004758100630073

in Bibtex Style

@conference{icaart14,
author={Luke Hunsberger},
title={A Faster Algorithm for Checking the Dynamic Controllability of Simple Temporal Networks with Uncertainty},
booktitle={Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2014},
pages={63-73},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004758100630073},
isbn={978-989-758-015-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 6th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - A Faster Algorithm for Checking the Dynamic Controllability of Simple Temporal Networks with Uncertainty
SN - 978-989-758-015-4
AU - Hunsberger L.
PY - 2014
SP - 63
EP - 73
DO - 10.5220/0004758100630073