2011 | OriginalPaper | Buchkapitel
Extensions of Decision-Theoretic Troubleshooting: Cost Clusters and Precedence Constraints
verfasst von : Václav Lín
Erschienen in: Symbolic and Quantitative Approaches to Reasoning with Uncertainty
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In decision-theoretic troubleshooting [5,2], 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.
The troubleshooting problem has received considerable attention over the past two decades. Efficient solution algorithms have been found for some variants of the problem, whereas other variants have been proven
NP
-hard [5,2,4,17,16].
We show that two troubleshooting scenarios —
Troubleshooting with Postponed System Test
[9] and
Troubleshooting with Cost Clusters without Inside Information
[7] — are
NP
-hard. Also, we define a troubleshooting scenario with precedence restrictions on the repair actions. We show that it is
NP
-hard in general, but polynomial under some restrictions placed on the structure of the precedence relation. In the proofs, we use results originally achieved in the field of Scheduling. Such a connection has not been made in the Troubleshooting literature so far.