Game Description Language and Dynamic Epistemic Logic Compared

Game Description Language and Dynamic Epistemic Logic Compared

Thorsten Engesser, Robert Mattmüller, Bernhard Nebel, Michael Thielscher

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1795-1802. https://doi.org/10.24963/ijcai.2018/248

Several different frameworks have been proposed to model and reason about knowledge in dynamic multi-agent settings, among them the logic-programming-based game description language GDL-III, and dynamic epistemic logic (DEL), based on possible-worlds semantics. GDL-III and DEL have complementary strengths and weaknesses in terms of ease of modeling and simplicity of semantics. In this paper, we formally study the expressiveness of GDL-III vs. DEL. We clarify the commonalities and differences between those languages, demonstrate how to bridge the differences where possible, and identify large fragments of GDL-III and DEL that are equivalent in the sense that they can be used to encode games or planning tasks that admit the same legal action sequences. We prove the latter by providing compilations between those fragments of GDL-III and DEL.
Keywords:
Knowledge Representation and Reasoning: Knowledge Representation Languages
Knowledge Representation and Reasoning: Reasoning about Knowlege and Belief
Knowledge Representation and Reasoning: Knowledge Representation and Reasoning for Game Playing