We introduce Strategy Repair, the problem of finding a minimal
amount of modifications to turn a strategy for a reachability game from
losing into winning. The problem is relevant for a number of settings in
Planning and Synthesis, where solutions essentially correspond to
winning strategies in a suitably defined reachability game. We show, via
reduction from Vertex Cover, that Strategy Repair is NP-complete and
devise two algorithms, one optimal and exponential and one polynomial
but sub-optimal, which we compare experimentally. The reported
experimentation includes some heuristics for strategy modification,
which proved crucial in dramatically improving performance.
12/07/2023