Hintikka's World: Scalable Higher-order Knowledge

Tristan Charrier, Sébastien Gamblin, Alexandre Niveau, François SchwarzentruberIJCAI 2019 · DOI

TL;DR

This paper introduces a significant upgrade to "Hintikka's World," a pedagogical tool for understanding higher-order knowledge in AI. By implementing symbolic representations of Kripke models using Binary Decision Diagrams (BDDs), the tool can now handle complex scenarios like real card games, overcoming the state explosion problem that plagued its previous version. This makes it a more powerful and scalable resource for teaching and exploring epistemic logic in AI.

What Problem Does This Paper Address?

Developing AI agents that can reason about "higher-order knowledge" – understanding what other agents know, what they know about what others know, and so on – is a significant challenge. This is crucial for games with imperfect information, where players don't have full visibility of the game state. While epistemic logic and dynamic epistemic logic (DEL) provide formal frameworks for this, existing tools for visualizing and exploring these concepts, like the original "Hintikka's World," were limited. They struggled with scalability, particularly when dealing with the vast number of possible states in realistic scenarios like card games (e.g., Hanabi), where the number of configurations can be astronomically large. This paper addresses the need for a more scalable and practical tool to demonstrate and study these complex reasoning capabilities.

Methods

The core innovation presented is the integration of symbolic Kripke models into Hintikka's World. Instead of explicitly storing every possible world and transition as a graph, the tool now uses Binary Decision Diagrams (BDDs). BDDs are a compact way to represent Boolean functions, which in turn can represent sets of possible worlds and the relationships between them.

Specifically:

  • Symbolic Representation: A world is described by a Boolean formula that defines its properties. Agent knowledge and transitions between worlds are also represented by Boolean formulas.
  • BDD Implementation: These Boolean formulas are then converted into BDDs. This allows for efficient manipulation and counting of possible worlds, even when the total number is enormous.
  • Scalability: This symbolic approach circumvents the "state explosion" problem by not needing to enumerate all states explicitly. The tool can now handle scenarios with a combinatorial explosion of possibilities.
  • Web Assembly: The BDD library (CUDD) is wrapped in C and compiled to Web Assembly, making it usable within the JavaScript-based web application.

Datasets

Not discussed in the paper. The paper focuses on demonstrating the tool's capability with existing game examples and theoretical scenarios.

Key Insights and Ideas

  • Bridging Theory and Practice: The paper successfully bridges the gap between abstract epistemic logic theory and practical, scalable AI applications by making complex concepts visually explorable.
  • The Power of Symbolic Representation: The adoption of BDDs is a critical enabler for scalability, allowing the tool to move beyond toy examples to more realistic, complex scenarios.
  • Pedagogical Value: Hintikka's World, with its comic-strip visualization of Kripke models, remains a powerful pedagogical tool. The symbolic upgrade significantly enhances its ability to illustrate concepts in games like Hanabi, which were previously intractable.
  • Beyond Explicit Models: The shift from explicit graph representations to symbolic ones is not just an optimization; it's a fundamental change that unlocks new possibilities for exploring higher-order knowledge.

Key Results

The primary result is the successful implementation of symbolic Kripke models using BDDs within Hintikka's World. This enables the tool to:

  • Handle Exponential State Spaces: The tool can now represent and explore scenarios with an exponential number of possible worlds, such as the card game Hanabi, which was impossible with the previous explicit model approach.
  • Demonstrate Complex Scenarios: The paper highlights the ability to provide examples featuring real card games, making the abstract concepts of epistemic logic more concrete and relatable.
  • Maintain Graphical Interface: The symbolic models are integrated seamlessly into the existing graphical user interface, preserving the tool's pedagogical strengths.

Limitations and Future Work

Limitations: * While the paper mentions that the tool still presents examples relying on explicit models for teaching DEL fundamentals (like "Sally and Anne"), the focus of the new implementation is on symbolic models for scalability. The exact balance and transition between these modes for pedagogical purposes might be an area for further refinement.

Future Work: * Algebraic Decision Diagrams (ADDs): The authors plan to extend the implementation to ADDs to incorporate examples involving numerical values, relevant for robotics. * Advanced Counting and Sampling: Further research into counting and sampling techniques is planned to tackle even larger and more complex examples. * Robotics Applications: Exploring the use of the tool in robotics, which often involves numerical reasoning, is a key future direction.

Summary updated

BibTeX
@inproceedings{charrier2019hintikka,
  author = {Tristan Charrier and Sébastien Gamblin and Alexandre Niveau and François Schwarzentruber},
  title = {{Hintikka's World: Scalable Higher-order Knowledge}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/934},
}
Figure