Batch Repair with Heuristic Search

Authors

  • Hilla Shinitzky Ben Gurion University of the Negev
  • Ron Stern Ben Gurion University of the Negev
  • Meir Kalech Ben Gurion University of the Negev

DOI:

https://doi.org/10.1609/socs.v7i1.18411

Keywords:

Heuristic searchl, Automated troubleshooting

Abstract

Recent work has raised the challenge of efficient automated troubleshooting in domains where repairing a set of components in a single repair action is cheaper than repairing each of them separately. This corresponds to cases where there is a non-negligible overhead to initiating a repair action and to testing the system after a repair action. The problem can be formalized as a combinatorial search problem, propose a new objective function to optimize, and investigate several search frameworks to solve it. The resulting search space is not monotone, but we are able to devise an admissible heuristic for it that enables solving it optimally in some cases with A*. Empirical evaluation on standard model-based diagnosis benchmark systems compare the A*-based approach with other search algorithms

Downloads

Published

2021-09-01