Home » Publication » 27756

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

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.
ISBN: 9781643684369; 9781643684376
keywords
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma