Abstract
Troubleshooting is about computing a cost-efficient way to repair a faulty
device. In this paper we investigate the most simple action-based troubleshooting
scenario with a single extension: the overall system test is not
required to be performed after each action, but it may be postponed until
several actions have been performed. As shown by Kadane and Simon,
the simple troubleshooting scenario is easily solvable in polynomial time.
However, we conjecture that the new troubleshooting scenario is NP-hard
and therefore describe an O(n^3) time heuristic. The new heuristic guarantees
optimality for a class of models, and for other classes of models
we benchmark it against the optimal solution and other simpler greedy
heuristics. The benchmark is performed on artificial models as well as a
real-world troubleshooting model, and they suggest that the heuristics are
close to optimal.
device. In this paper we investigate the most simple action-based troubleshooting
scenario with a single extension: the overall system test is not
required to be performed after each action, but it may be postponed until
several actions have been performed. As shown by Kadane and Simon,
the simple troubleshooting scenario is easily solvable in polynomial time.
However, we conjecture that the new troubleshooting scenario is NP-hard
and therefore describe an O(n^3) time heuristic. The new heuristic guarantees
optimality for a class of models, and for other classes of models
we benchmark it against the optimal solution and other simpler greedy
heuristics. The benchmark is performed on artificial models as well as a
real-world troubleshooting model, and they suggest that the heuristics are
close to optimal.
| Originalsprog | Engelsk |
|---|---|
| Udgiver | Department of Computer Science, Aalborg University |
| Status | Udgivet - okt. 2010 |
Emneord
- decision theoretic troubleshooting
- system test
- independent actions