Paper ID: 2412.06706 • Published Dec 9, 2024
Asynchronous Agents with Perfect Recall: Model Reductions, Knowledge-Based Construction, and Model Checking for Coalitional Strategies
Dilian Gurov, Filip Jamroga, Wojciech Jamroga, Mateusz Kamiński, Damian Kurpiewski, Wojciech Penczek, Teofil Sidoruk
TL;DR
Get AI-generated summaries with premium
Get AI-generated summaries with premium
Model checking of strategic abilities for agents with memory is a notoriously
hard problem, and very few attempts have been made to tackle it. In this paper,
we present two important steps towards this goal. First, we take the
partial-order reduction scheme that was recently proved to preserve individual
and coalitional abilities of memoryless agents, and show that it also works for
agents with memory. Secondly, we take the Knowledge-Based Subset Construction,
that was recently studied for synchronous concurrent games, and adapt it to
preserve abilities of memoryful agents in asynchronous MAS.
On the way, we also propose a new execution semantics for strategies in
asynchronous MAS, that combines elements of Concurrent Game Structures and
Interleaved Interpreted Systems in a natural and intuitive way.