Investigating the Epistemic Unfolding of Multi-Player Games of Imperfect Information

Abstract: Solving multi-agent planning problems entails finding strategies that ensure that the agents achieve their cooperative objective. In practice, since the agents do not necessarily have perfect knowledge, these planning problems may involve imperfect information. For example, a robot agent may have a damaged or imperfect sensor, or one agent may be in another room and therefore cannot see what the other agents can. A useful model for these problems are cooperative multi-player games of imperfect information. In this paper, we investigate a novel construction known as epistemic unfolding. Epistemic unfolding translates multi-player games of imperfect information to single-player games of perfect information, for which strategy synthesis is much easier. Essentially, the idea of epistemic unfolding is to track the knowledge of the players throughout the duration of the game. Although epistemic unfolding is previously defined, to our knowledge it had neither been implemented nor properly visualized. In order to provide a foundation for future research, we implemented epistemic unfolding as a tool, visualized a set of epistemically unfolded games, and, finally, developed an intuitive understanding of epistemically unfolded games.