An Algorithm for Checking the Dynamic Controllability of a Conditional Simple Temporal Network with Uncertainty

Carlo Combi, Luke Hunsberger, Roberto Posenato

2013

Abstract

A Simple Temporal Network with Uncertainty (STNU) is a framework for representing and reasoning about temporal problems involving actions whose durations are bounded but uncontrollable. A dynamically controllable STNU is one for which there exists a strategy for executing its time-points that guarantees that all of the temporal constraints in the network will be satisfied no matter how the uncontrollable durations turn out. A Conditional Simple Temporal Network with Uncertainty (CSTNU) augments an STNU to include observation nodes, where the execution of each observation node provides, in real time, the truth value of an associated proposition. Recent work has generalized the notion of dynamic controllability to cover CSTNUs. This paper presents an algorithm—called a DC-checking algorithm—for determining whether arbitrary CSTNUs are dynamically controllable. The algorithm, which is proven to be sound, is the first such algorithm to be presented in the literature. The algorithm extends edge-generation/constraint-propagation rules from an existing STNU algorithm to accommodate propositional labels, while adding new rules required to deal with the observation nodes. The paper also discusses implementation issues associated with the management of propositional labels.

Paper Citation

in Harvard Style

Combi C., Hunsberger L. and Posenato R. (2013). An Algorithm for Checking the Dynamic Controllability of a Conditional Simple Temporal Network with Uncertainty . In Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-8565-39-6, pages 144-156. DOI: 10.5220/0004256101440156

in Bibtex Style

@conference{icaart13,
author={Carlo Combi and Luke Hunsberger and Roberto Posenato},
title={An Algorithm for Checking the Dynamic Controllability of a Conditional Simple Temporal Network with Uncertainty},
booktitle={Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2013},
pages={144-156},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004256101440156},
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 - An Algorithm for Checking the Dynamic Controllability of a Conditional Simple Temporal Network with Uncertainty
SN - 978-989-8565-39-6
AU - Combi C.
AU - Hunsberger L.
AU - Posenato R.
PY - 2013
SP - 144
EP - 156
DO - 10.5220/0004256101440156