Risk minimization of disjunctive temporal problem with uncertainty

Author

Hoong Chuin LAU, Singapore Management UniversityFollow
Tuan Anh HOANG, Singapore Management UniversityFollow

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

Citation

LAU, Hoong Chuin and HOANG, Tuan Anh. Risk minimization of disjunctive temporal problem with uncertainty. (2014). Knowledge and Systems Engineering: Proceedings of the Fifth International Conference KSE 2013, Volume 2, Hanoi, Vietnam, 17-19 October, 2013. 2, 223-236.
Available at: https://ink.library.smu.edu.sg/sis_research/1925

Copyright Owner and License

LARC

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.

Additional URL

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