Publications

2026

1. SWAT-26

   Strategy Repair in Reachability Games via Graph Quotientation

   Tiziana Calamoneri, Pierre Gaillard, Giacomo Paesani, and 1 more author

   In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026), 2026

   Abs Bib PDF

   Reachability Games over graphs (RGs) are a powerful modelling tool for synthesis and planning. The solutions to RGs are strategies that are used in program design. Sometimes, due to model deviation at execution time, specification updates, or simply a bug, the strategy provided as a solution to an RG no longer works. Strategy Repair aims to solve this problem by adjusting strategies with a minimum number of modifications. Such a minimisation requirement is motivated by the costs that one may incur when implementing the new strategy. To minimise implementation costs, one wants to reuse as much of the provided strategy as possible. In the literature, Strategy Repair has been investigated from both theoretical and practical perspectives. First, it has been shown to be NP-complete. Second, two algorithmic approaches have been proposed to tackle the problem in practice, one provides an optimal solution, the other an approximated solution. Both approaches underutilise the graph-theoretical properties of games, which could significantly improve their performance and accuracy (in the case of approximation algorithms). This paper provides a graph-theoretic characterisation of Strategy Repair that provably improves every algorithmic approach to solving the problem. It does so by introducing a new notion of quotient graph that allows us to identify and merge those vertices that are equivalent from the perspective of every solution to the problem. This way, solving Strategy Repair can be done in a reduced instance, which we call the quotient game. The approach not only reduces the problem’s input size, but also improves the effectiveness of MUSTFIX, an optimisation condition previously introduced for the problem. Besides the theoretical characterisation, we test our approach empirically by running experiments to demonstrate improvements over the quotient graph approach.

   @inproceedings{C-CGPP26,
     author = {Calamoneri, Tiziana and Gaillard, Pierre and Paesani, Giacomo and Perelli, Giuseppe},
     title = {{Strategy Repair in Reachability Games via Graph Quotientation}},
     booktitle = {20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
     year = {2026},
     pages = {12:1--12:16},
     series = {Leibniz International Proceedings in Informatics (LIPIcs)},
     isbn = {978-3-95977-421-5},
     issn = {1868-8969},
     volume = {370},
     editor = {Fraigniaud, Pierre},
     publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
     address = {Dagstuhl, Germany},
   }

2023

1. ECAI-23

   Strategy Repair in Reachability Games.

   Pierre Gaillard, Fabio Patrizi, and Giuseppe Perelli

   In 26th European Conference on Artificial Intelligence, ECAI, 2023

   Abs Bib PDF

   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.

   @inproceedings{C-GPP23,
     author = {Gaillard, Pierre and Patrizi, Fabio and Perelli, Giuseppe},
     title = {Strategy Repair in Reachability Games.},
     booktitle = {26th European Conference on Artificial Intelligence, {ECAI}},
     volume = {372},
     pages = {780--787},
     publisher = {{IOS} Press},
     year = {2023},
   }