An Undecidability Proof for the Plan Existence Problem

Epistemic planning is a significant research direction in artificial intelligence, aiming to simulate complex interactions in multi-agent systems using a dynamic modal logic framework. This approach extends classical planning by incorporating the beliefs and knowledge of multiple agents, better handling coordination, communication, and secrecy issues. In recent years, as multi-agent systems have been increasingly applied across various fields, the importance of epistemic planning has become more prominent. However, the decidability of the plan existence problem remains a core challenge in this field, especially within a modal logic framework.

The core of the plan existence problem is whether, given a goal state, an initial epistemic state (a pointed Kripke model), and a set of epistemic actions, there exists a sequence of actions that can achieve the goal state. The difficulty of this problem lies in the complex interactions in multi-agent systems and state transitions within a modal logic framework. Although previous studies have shown that the problem is decidable under certain conditions, its decidability remains unknown in cases with modal depth at most 1 and no postconditions.

The core innovation of this paper is the first proof of the undecidability of the plan existence problem with modal depth at most 1 and no postconditions. The researchers simplify the problem to a specific modal logic framework and use a reduction from Post's Correspondence Problem to successfully prove undecidability. This method does not rely on specific modal logic assumptions but constructs complex epistemic state and action models. Additionally, the researchers demonstrate how to perform state transitions without postconditions, providing new insights into complex interactions in multi-agent systems.

• �� The researchers first define a formal framework for the plan existence problem, where epistemic states are represented as pointed Kripke models and epistemic actions as pointed Kripke frames.
• �� They then simplify the problem to cases with modal depth at most 1 and no postconditions, using a reduction from Post's Correspondence Problem to prove undecidability.
• �� Specifically, they construct a complex modal logic framework, demonstrating how to construct long paths and define starting and ending states using formulas of modal depth 1 for state transitions.
• �� Finally, the researchers validate the effectiveness of this method in experiments and demonstrate its potential applications in multi-agent systems.

In the experimental design, the researchers validate the effectiveness of their method by constructing long paths and defining starting and ending states using formulas of modal depth 1. The experiments involve multiple agents' epistemic states and action models, demonstrating how to prove the undecidability of the plan existence problem without any assumptions on the modal logic of the agents. The results show that this method effectively handles complex interactions in multi-agent systems and provides new insights into knowledge dynamics.

The experimental results show that the plan existence problem is undecidable for at least two agents without any assumptions on the modal logic. Additionally, for a single agent, if the agent's knowledge follows S5 logic or has negative introspection, the problem is decidable. The researchers also demonstrate how to construct long paths and define starting and ending states using formulas of modal depth 1 for state transitions without postconditions.

The application scenarios of this study mainly focus on complex interactions in multi-agent systems, especially in cases requiring coordination, communication, and secrecy. By proving the undecidability of the plan existence problem, the researchers provide new tools and methods for future research, enabling better understanding and analysis of knowledge dynamics in multi-agent systems.

Despite theoretically proving the undecidability of the plan existence problem, there are still some limitations in practical applications. Firstly, the study focuses primarily on theoretical proof, lacking experimental validation in practical scenarios. Additionally, although undecidability is proven, no effective approximation algorithms are provided for practical problems. Future research could explore handling undecidable plan existence problems in practical applications, potentially requiring new approximation algorithms or heuristics.