Magic Loops in Simple Temporal Networks with Uncertainty - Exploiting Structure to Speed Up Dynamic Controllability Checking

Luke Hunsberger

2013

Abstract

A Simple Temporal Network with Uncertainty (STNU) is a structure for representing and reasoning about temporal constraints and uncontrollable-but-bounded temporal intervals called contingent links. An STNU is dynamically controllable (DC) if there exists a strategy for executing its time-points that guarantees that all of the constraints will be satisfied no matter how the durations of the contingent links turn out. The fastest algorithm in the literature for checking the dynamic controllability of arbitrary STNUs is based on an analysis of the graphical structure of STNUs. This paper (1) presents a new method for analyzing the graphical structure of STNUs, (2) determines an upper bound on the complexity of certain structures---the indivisible semi-reducible negative loops; (3) presents an algorithm for generating loops---the magic loops---whose complexity attains this upper bound; and (4) shows how the upper bound can be exploited to speed up the process of DC-checking for certain networks. Theoretically, the paper deepens our understanding of the structure of STNU graphs. Practically, it demonstrates new ways of exploiting graphical structure to speed up DC checking.

Paper Citation

in Harvard Style

Hunsberger L. (2013). Magic Loops in Simple Temporal Networks with Uncertainty - Exploiting Structure to Speed Up Dynamic Controllability Checking . In Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-8565-39-6, pages 157-170. DOI: 10.5220/0004260501570170

in Bibtex Style

@conference{icaart13,
author={Luke Hunsberger},
title={Magic Loops in Simple Temporal Networks with Uncertainty - Exploiting Structure to Speed Up Dynamic Controllability Checking},
booktitle={Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2013},
pages={157-170},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004260501570170},
isbn={978-989-8565-39-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - Magic Loops in Simple Temporal Networks with Uncertainty - Exploiting Structure to Speed Up Dynamic Controllability Checking
SN - 978-989-8565-39-6
AU - Hunsberger L.
PY - 2013
SP - 157
EP - 170
DO - 10.5220/0004260501570170