Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
The Cost of Troubleshooting Cost Clusters with Inside Information
Thorsten Ottosen, Finn Jensen
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.
Keywords:
Pages: 409-416
PS Link:
PDF Link: /papers/10/p409-ottosen.pdf
BibTex:
@INPROCEEDINGS{Ottosen10,
AUTHOR = "Thorsten Ottosen and Finn Jensen",
TITLE = "The Cost of Troubleshooting Cost Clusters with Inside Information",
BOOKTITLE = "Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-10)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2010",
PAGES = "409--416"
}


hosted by DSL   •   site info   •   help