TY - GEN

T1 - The Cost of Troubleshooting Cost Clusters with Inside Information

A1 - Ottosen,Thorsten Jørgen

A1 - Jensen,Finn V.

AU - Ottosen,Thorsten Jørgen

AU - Jensen,Finn V.

PB - Association for Uncertainty in Artificial Intelligence

PY - 2010

Y1 - 2010

N2 - Decision theoretical troubleshooting is about <br/>minimizing the expected cost of solving a <br/>certain problem like repairing a complicated <br/>man-made device. In this paper we consider <br/>situations where you have to take apart some <br/>of the device to get access to certain clusters <br/>and actions. Specifically, we investigate <br/>troubleshooting with independent actions in <br/>a tree of clusters where actions inside a cluster <br/>cannot be performed before the cluster is <br/>opened. The problem is non-trivial because <br/>there is a cost associated with opening and <br/>closing a cluster. Troubleshooting with independent <br/>actions and no clusters can be solved <br/>in O(n lg n) time (n being the number of <br/>actions) by the well-known "P-over-C" algorithm <br/>due to Kadane and Simon, but an ef- <br/>ficient and optimal algorithm for a tree cluster <br/>model has not yet been found. In this <br/>paper we describe a "bottom-up P-over-C" <br/>O(n lg n) time algorithm and show that it is <br/>optimal when the clusters do not need to be <br/>closed to test whether the actions solved the <br/>problem.

AB - Decision theoretical troubleshooting is about <br/>minimizing the expected cost of solving a <br/>certain problem like repairing a complicated <br/>man-made device. In this paper we consider <br/>situations where you have to take apart some <br/>of the device to get access to certain clusters <br/>and actions. Specifically, we investigate <br/>troubleshooting with independent actions in <br/>a tree of clusters where actions inside a cluster <br/>cannot be performed before the cluster is <br/>opened. The problem is non-trivial because <br/>there is a cost associated with opening and <br/>closing a cluster. Troubleshooting with independent <br/>actions and no clusters can be solved <br/>in O(n lg n) time (n being the number of <br/>actions) by the well-known "P-over-C" algorithm <br/>due to Kadane and Simon, but an ef- <br/>ficient and optimal algorithm for a tree cluster <br/>model has not yet been found. In this <br/>paper we describe a "bottom-up P-over-C" <br/>O(n lg n) time algorithm and show that it is <br/>optimal when the clusters do not need to be <br/>closed to test whether the actions solved the <br/>problem.

KW - Decision Theoretic Troubleshooting

UR - http://event.cwi.nl/uai2010/papers/UAI2010_0174.pdf

SN - 978-0-9749039-6-5

BT - Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010)

T2 - Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010)

ER -