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.
Dettaglio pubblicazione
2023, European Conference on Artificial Intelligence, Pages 780-787
Strategy Repair in Reachability Games (04b Atto di convegno in volume)
Gaillard Pierre, Patrizi Fabio, Perelli Giuseppe
ISBN: 9781643684369; 9781643684376
Gruppo di ricerca: Artificial Intelligence and Knowledge Representation
keywords