Knowledge-Based Expansions for Strategy Synthesis in Discrete Games on Graphs
Axel Janson, Marc Du Rietz · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2020
When analyzing situations involving intelligent agents with objectives, it can be helpful to use discrete games as models. Within such game models the synthesis of winning strategies is of interest, and many algorithmic methods have been developed for this purpose. This project focused on a less tractable game type, involving a coalition of players without the ability to communicate. For this type of game we propose two methods for exploring knowledge-based strategies. One is an extension of the previously developed Multiplayer Knowledge- Based Subset Construction with the additional assumption of action observability within the coalition. The other is a novel method called Epistemic Expansion, which assumes that the coalition coordinates before playing the game. We demonstrate how these methods can be used to help find winning strategies in example games with relevant properties.