Reachability Games in Dynamic Epistemic Logic

Reachability Games in Dynamic Epistemic Logic

Bastien Maubert, Sophie Pinchinat, François Schwarzentruber

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 499-505. https://doi.org/10.24963/ijcai.2019/71

We define reachability games based on Dynamic Epistemic Logic (DEL), where the players? actions are finely described as DEL action models. We first consider the setting where a controller with perfect information interacts with an environment and aims at reaching some desired state of knowledge regarding the observers of the system. We study the problem of existence of a strategy for the controller, which generalises the classic epistemic planning problem, and we solve it for several types of actions such as public announcements and public actions. We then consider a yet richer setting where observers themselves are players, whose strategies must be based on their observations. We establish several decidability and undecidability results for the problem of existence of a distributed strategy, depending on the type of actions the players can use, and relate them to results from the literature on multiplayer games with imperfect information.
Keywords:
Agent-based and Multi-agent Systems: Multi-agent Planning
Planning and Scheduling: Theoretical Foundations of Planning
Knowledge Representation and Reasoning: Non-classical Logics for Knowledge Representation
Planning and Scheduling: Distributed;Multi-agent Planning
Agent-based and Multi-agent Systems: Formal Verification, Validation and Synthesis