### Abstract

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.

Original language | English |
---|---|

Title of host publication | Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010) |

Publisher | Association for Uncertainty in Artificial Intelligence |

Publication date | 2010 |

ISBN (Print) | 978-0-9749039-6-5 |

Publication status | Published - 2010 |

Event | 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010) - Catalina Island, United States Duration: 8 Jul 2010 → 11 Jul 2010 |

### Conference

Conference | 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010) |
---|---|

Country | United States |

City | Catalina Island |

Period | 08/07/2010 → 11/07/2010 |

### Fingerprint

### Keywords

- Decision Theoretic Troubleshooting

### Cite this

*Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010)*Association for Uncertainty in Artificial Intelligence.

}

*Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010).*Association for Uncertainty in Artificial Intelligence, Catalina Island, United States, 08/07/2010.

**The Cost of Troubleshooting Cost Clusters with Inside Information.** / Ottosen, Thorsten Jørgen; Jensen, Finn V.

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - The Cost of Troubleshooting Cost Clusters with Inside Information

AU - Ottosen, Thorsten Jørgen

AU - Jensen, Finn V.

N1 - Association for Uncertainty in Artificial Intelligence, AUAI

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Decision Theoretic Troubleshooting

M3 - Article in proceeding

SN - 978-0-9749039-6-5

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

PB - Association for Uncertainty in Artificial Intelligence

ER -