Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

2014

Abstract

The Disjunctive Temporal Problem with Uncertainty (DTPU) is a fundamental problem that expresses temporal reasoning with both disjunctive constraints and contingency. A recent work (Peintner et al, 2007) develops a complete algorithm for determining Strong Controlla- bility of a DTPU. Such a notion that guarantees 100% confidence of execution may be too conservative in practice. In this paper, following the idea of (Tsamardinos 2002), we are interested to find a schedule that minimizes the risk (i.e. probability of failure) of executing a DTPU. We present a problem decomposition scheme that enables us to compute the probability of failure efficiently, followed by a hill-climbing local search to search among feasible solutions. We show experimentally that our approach effectively produces solutions which are near-optimal.

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Publication

Knowledge and Systems Engineering: Proceedings of the Fifth International Conference KSE 2013, Volume 2, Hanoi, Vietnam, 17-19 October, 2013

Volume

2

First Page

223

Last Page

236

ISSN

2194-5357

ISBN

9783319028217

Identifier

10.1007/978-3-319-02821-7_21

Publisher

Springer Verlag

City or Country

Cham

Copyright Owner and License

LARC

Additional URL

http://doi.org/10.1007/978-3-319-02821-7_21

Download

Share

COinS