Risk minimization of disjunctive temporal problem with uncertainty
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2014
|
| Subjects: | |
| Online Access: | https://ink.library.smu.edu.sg/sis_research/1925 https://ink.library.smu.edu.sg/context/sis_research/article/2924/viewcontent/dtpu_long.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | 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. |
|---|