Konferenční příspěvek

Symbolic and Quantitative Approaches to Reasoning with Uncertainty

Lecture Notes in Artificial Intelligence

Springer

Heidelberg

2011

978-3-642-22151-4

0302-9743

Ing. Václav Lín (ÚTIA - Oddělení matematické teorie rozhodování)

Computational Complexity, Decision-Theoretic Troubleshooting

In decision-theoretic troubleshooting, we try to find a cost efficient repair strategy for a malfunctioning device described by a formal model. The need to schedule repair actions under uncertainty has required the researchers to use an appropriate knowledge representation formalism, often a probabilistic one. We show that two troubleshooting scenarios — Troubleshooting with Postponed System Test and Troubleshooting with Cost Clusters without Inside Information —are NP-hard. Also, we define a troubleshooting scenario with precedence restrictions on the repair actions.