Abstract
Decision theoretical troubleshooting is about
minimizing the expected cost of solving a
certain problem like repairing a complicated
man-made device. In this paper we consider
situations where you have to take apart some
of the device to get access to certain clusters
and actions. Specifically, we investigate
troubleshooting with independent actions in
a tree of clusters where actions inside a cluster
cannot be performed before the cluster is
opened. The problem is non-trivial because
there is a cost associated with opening and
closing a cluster. Troubleshooting with independent
actions and no clusters can be solved
in O(n lg n) time (n being the number of
actions) by the well-known "P-over-C" algorithm
due to Kadane and Simon, but an ef-
ficient and optimal algorithm for a tree cluster
model has not yet been found. In this
paper we describe a "bottom-up P-over-C"
O(n lg n) time algorithm and show that it is
optimal when the clusters do not need to be
closed to test whether the actions solved the
problem.
minimizing the expected cost of solving a
certain problem like repairing a complicated
man-made device. In this paper we consider
situations where you have to take apart some
of the device to get access to certain clusters
and actions. Specifically, we investigate
troubleshooting with independent actions in
a tree of clusters where actions inside a cluster
cannot be performed before the cluster is
opened. The problem is non-trivial because
there is a cost associated with opening and
closing a cluster. Troubleshooting with independent
actions and no clusters can be solved
in O(n lg n) time (n being the number of
actions) by the well-known "P-over-C" algorithm
due to Kadane and Simon, but an ef-
ficient and optimal algorithm for a tree cluster
model has not yet been found. In this
paper we describe a "bottom-up P-over-C"
O(n lg n) time algorithm and show that it is
optimal when the clusters do not need to be
closed to test whether the actions solved the
problem.
| Originalsprog | Engelsk |
|---|---|
| Titel | Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010) |
| Forlag | Association for Uncertainty in Artificial Intelligence |
| Publikationsdato | 2010 |
| ISBN (Trykt) | 978-0-9749039-6-5 |
| Status | Udgivet - 2010 |
| Begivenhed | 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010) - Catalina Island, USA Varighed: 8 jul. 2010 → 11 jul. 2010 |
Konference
| Konference | 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010) |
|---|---|
| Land/Område | USA |
| By | Catalina Island |
| Periode | 08/07/2010 → 11/07/2010 |