TL;DR
This paper demonstrates that even simplified versions of epistemic planning problems, involving just two agents, a fixed set of actions, and a small number of propositions, can be undecidable. This is achieved by cleverly simulating cellular automata, revealing fundamental limits in reasoning about knowledge and action sequences.
What Problem Does This Paper Address?
Epistemic planning deals with agents reasoning about their own knowledge and the knowledge of others to achieve goals. While classical planning focuses on achieving physical goals, epistemic planning extends this to goals involving knowledge states (e.g., "agent A knows that agent B doesn't know P"). This field is known to be generally undecidable, meaning there's no algorithm that can always determine if a plan exists for any given problem. However, previous proofs of undecidability haven't provided bounds on the complexity of the problems, leaving open the question of whether simpler, more constrained versions might be decidable. This paper tackles this by investigating whether specific, small instances of epistemic planning problems remain undecidable, even with limited actions, propositions, and agents.
Methods
The core of the paper's contribution lies in its novel use of cellular automata (CAs) to prove undecidability for restricted epistemic planning problems. The authors establish a connection between the reachability problem in CAs and the epistemic planning problem.
Here's a breakdown of their approach:
- Simulating CAs in Dynamic Epistemic Logic (DEL): They show how to model the step-by-step evolution of a cellular automaton within the framework of DEL. This involves defining states in DEL that represent configurations of cells in a CA and actions in DEL that mimic the CA's transition rules.
- Reduction Technique: The undecidability of CA reachability problems (specifically, determining if a certain pattern emerges in a CA's evolution) is a known result. The authors leverage this by reducing these CA problems to epistemic planning problems. If a CA problem is undecidable, then the corresponding epistemic planning problem must also be undecidable.
- Small Instances: They focus on specific, small CAs, like Wolfram's Rule 110, and universal CAs with limited symbols. This allows them to construct epistemic planning problems with:
- A fixed, small repertoire of actions (sometimes just one).
- A small, fixed number of propositions (e.g., 2 or 6).
- A fixed number of agents (two).
- The initial state being either finite or "automatic" (a more complex, potentially infinite structure with a finite description).
- Common Knowledge Elimination: A secondary contribution is showing how to eliminate the "common knowledge" operator from goal formulas, which simplifies the goals without affecting undecidability. This is done by introducing "shift" actions that allow agents to examine different parts of their knowledge state.
Datasets
Not discussed in the paper. The paper focuses on theoretical undecidability proofs rather than empirical evaluation on datasets.
Key Insights and Ideas
- Undecidability Lurks in Simplicity: The most striking insight is that even highly constrained epistemic planning problems can be undecidable. This suggests that the complexity of reasoning about knowledge is inherent and not just a consequence of large problem sizes.
- Cellular Automata as a Powerful Tool for Undecidability Proofs: The paper demonstrates the effectiveness of using cellular automata as a reduction target for proving undecidability in epistemic planning. This opens up avenues for transferring undecidability results from other areas of computation theory to epistemic logic.
- The "Automatic" Nature of States Matters: The paper highlights that even when states are potentially infinite but have a finite, "automatic" description, epistemic planning can remain undecidable. This contrasts with some areas where moving from finite to automatic structures preserves decidability.
- Common Knowledge is Not Essential for Undecidability: The work shows that undecidability can be achieved even without the complex common knowledge operator, by using simpler goals and carefully constructed actions.
Key Results
The paper establishes two main undecidability results:
- Undecidability with Fixed Actions and Propositions: The epistemic planning problem is undecidable even when the repertoire of actions is fixed to a single action, the number of propositions is fixed to at most 6, and there are only two agents. The undecidability arises from the complexity of the initial knowledge state.
- Undecidability with Automatic States and Public Actions: The epistemic planning problem is undecidable for automatic structures (potentially infinite states with finite descriptions) using only one public action and two propositions. This is a particularly strong result, as public actions often lead to decidability in other contexts.
Limitations and Future Work
- Focus on Undecidability: The paper primarily establishes undecidability. While it shows that certain problems are not decidable, it doesn't provide algorithms for solving the decidable cases or characterize the boundary between decidable and undecidable problems precisely.
- Specific CA Models: The reductions are based on specific universal cellular automata (like Smith's) and Wolfram's Rule 110. While these are well-chosen examples, exploring other CA models might reveal further nuances.
- Future Work: The authors suggest that their work connects epistemic planning to cellular automata, implying that many other undecidability results from CA theory could potentially be transferred to epistemic planning. They also propose using decidability techniques (like those for CAs) to find decidable cases and sharpen the understanding of the decidability/undecidability frontier in epistemic planning.
Summary updated