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.

Strategy Repair in Reachability Games / Gaillard, Pierre; Patrizi, Fabio; Perelli, Giuseppe. - 372:(2023), pp. 780-787. (Intervento presentato al convegno European Conference on Artificial Intelligence tenutosi a Kraków; Poland) [10.3233/FAIA230344].

Strategy Repair in Reachability Games

Fabio Patrizi;Giuseppe Perelli
2023

Abstract

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.
2023
European Conference on Artificial Intelligence
reasoning about strategies; synthesis; planning; formal games
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Strategy Repair in Reachability Games / Gaillard, Pierre; Patrizi, Fabio; Perelli, Giuseppe. - 372:(2023), pp. 780-787. (Intervento presentato al convegno European Conference on Artificial Intelligence tenutosi a Kraków; Poland) [10.3233/FAIA230344].
File allegati a questo prodotto
File Dimensione Formato  
Gaillard_Strategy_2023.pdf

accesso aperto

Note: DOI 10.3233/FAIA230344
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 393.76 kB
Formato Adobe PDF
393.76 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1691213
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact