Published in

Principles and Practice of Constraint Programming – CP 2007, p. 856-863

DOI: 10.1007/978-3-540-74970-7_64

Links

Tools

Export citation

Search in Google Scholar

Strong Controllability of Disjunctive Temporal Problems with Uncertainty

Proceedings article published in 2007 by Bart Peintner, Kristen Brent Venable, Neil Yorke-Smith ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Question mark in circle
Preprint: policy unknown
Upload
Question mark in circle
Postprint: policy unknown
Upload
Question mark in circle
Published version: policy unknown
Upload

Abstract

The Disjunctive Temporal Problem with Uncertainty (DTPU) is an extension of the Disjunctive Temporal Problem (DTP) that accounts for events not under the control of the executing agent. We investigate the semantics of DTPU constraints, refining the existing notion that they are simply disjunctions of STPU constraints. We then develop the first sound and complete algorithm to determine whether Strong Controllability holds for a DTPU. We analyze the complexity of our algorithm with respect to the number of constraints in different classes, showing that, for several common subclasses of DTPUs, determining Strong Controllability has the same complexity as solving DTPs.