When To Test? Troubleshooting with Postponed System Test

Thorsten Jørgen Ottosen, Finn V. Jensen

Publikation: Working paperForskning

250 Downloads (Pure)

Resumé

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.
OriginalsprogEngelsk
UdgiverDepartment of Computer Science, Aalborg University
StatusUdgivet - okt. 2010

Emneord

  • decision theoretic troubleshooting
  • system test
  • independent actions

Citer dette

Ottosen, T. J., & Jensen, F. V. (2010). When To Test? Troubleshooting with Postponed System Test. Department of Computer Science, Aalborg University.
Ottosen, Thorsten Jørgen ; Jensen, Finn V. / When To Test? Troubleshooting with Postponed System Test. Department of Computer Science, Aalborg University, 2010.
@techreport{f8ecc58723fd4361a0d460934b9f477f,
title = "When To Test?: Troubleshooting with Postponed System Test",
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.",
keywords = "decision theoretic troubleshooting , system test, independent actions",
author = "Ottosen, {Thorsten J{\o}rgen} and Jensen, {Finn V.}",
year = "2010",
month = "10",
language = "English",
publisher = "Department of Computer Science, Aalborg University",
type = "WorkingPaper",
institution = "Department of Computer Science, Aalborg University",

}

Ottosen, TJ & Jensen, FV 2010 'When To Test? Troubleshooting with Postponed System Test' Department of Computer Science, Aalborg University.

When To Test? Troubleshooting with Postponed System Test. / Ottosen, Thorsten Jørgen; Jensen, Finn V.

Department of Computer Science, Aalborg University, 2010.

Publikation: Working paperForskning

TY - UNPB

T1 - When To Test?

T2 - Troubleshooting with Postponed System Test

AU - Ottosen, Thorsten Jørgen

AU - Jensen, Finn V.

PY - 2010/10

Y1 - 2010/10

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

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

KW - decision theoretic troubleshooting

KW - system test

KW - independent actions

M3 - Working paper

BT - When To Test?

PB - Department of Computer Science, Aalborg University

ER -

Ottosen TJ, Jensen FV. When To Test? Troubleshooting with Postponed System Test. Department of Computer Science, Aalborg University. 2010 okt.