Decidability Results in First-Order Epistemic Planning

Andrés Occhipinti Liberman, Rasmus Kræmmer RendsvigIJCAI 2020 · DOI

TL;DR

This paper tackles the challenge of automated reasoning about agents' knowledge and actions in complex environments. It introduces a new formal language, FODEL, that combines the expressiveness of epistemic logic with the efficiency of first-order logic for representing actions. The authors prove that planning problems in this new framework are decidable for single-agent scenarios and for multi-agent scenarios with simplified action preconditions.

What Problem Does This Paper Address?

Autonomous agents, especially in multi-agent systems, need to reason not only about the physical world but also about what other agents know, believe, and might do. This is the domain of "epistemic planning." Traditional planning languages like PDDL excel at describing physical actions but struggle to represent knowledge. Epistemic logic, on the other hand, is great at modeling knowledge but is often propositional, making it inefficient for domains with many objects.

First-Order Dynamic Epistemic Logic (FODEL) aims to bridge this gap by combining the strengths of both worlds: the expressive power of epistemic logic for reasoning about knowledge and the conciseness of first-order logic for representing actions using schemas (like PDDL's stack(x, y)). However, the decidability of planning problems in FODEL – whether a solution exists – was an open question. This paper investigates this decidability question, seeking to understand when we can guarantee that a plan can be found.

Methods

The core of the paper's contribution lies in adapting concepts from propositional epistemic logic planning to the first-order setting of FODEL. Key techniques include:

  • First-Order Bisimulations: The authors generalize the notion of bisimulation, a crucial tool for proving decidability in propositional epistemic logic. Bisimulations are relations between states (or worlds in a model) that preserve logical properties. The FODEL bisimulations are adapted to handle first-order terms and quantifiers, ensuring that bisimilar states are logically equivalent with respect to a certain modal depth.
  • Product Update: The paper uses a first-order variant of "product update," a mechanism for defining how states change after an action. They show that this update preserves bisimilarity, which is essential for reasoning about state spaces.
  • State Space Reduction: The decidability proofs rely on showing that the potentially infinite state space of planning problems can be finitely represented up to bisimulation. This is achieved by demonstrating that states can be "contracted" into a finite number of canonical forms (bisimulation contractions) without losing essential information relevant to the planning goal.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • FODEL offers a powerful yet potentially tractable framework: By integrating first-order logic with epistemic operators, FODEL provides a more succinct and expressive way to model epistemic planning problems than purely propositional approaches.
  • Bisimulations are key to decidability: The generalization of bisimulations to first-order epistemic logic is the central technical tool that allows the authors to bound the state space and prove decidability.
  • Decidability is not universal but exists for important fragments: While general FODEL planning is undecidable (as it inherits undecidability from propositional epistemic planning), the paper identifies significant decidable fragments. This is crucial for practical applications, as it tells us when we can rely on automated planners.
  • Single-agent planning is decidable: This is a fundamental result, showing that even with first-order epistemic reasoning, finding plans for a single agent is computationally tractable.
  • Multi-agent planning with non-modal preconditions is decidable: This is a significant extension, demonstrating that decidability can be maintained in multi-agent settings as long as the actions' preconditions don't involve complex epistemic reasoning themselves.

Key Results

  • Undecidability for general multi-agent planning (k ≥ 2): This result is inherited from propositional epistemic planning, confirming that unrestricted multi-agent epistemic planning in FODEL is undecidable.
  • Decidability for single-agent FODEL planning (PlanEx(1)): The paper proves that the plan existence problem for single-agent FODEL planning is decidable.
  • Decidability for multi-agent FODEL planning with non-modal preconditions (PlanEx(k) for k ≥ 1): This is a key positive result, showing that if action preconditions are restricted to purely factual (non-epistemic) statements, then multi-agent FODEL planning becomes decidable.

Limitations and Future Work

  • Undecidability of general multi-agent planning: The paper highlights that the full expressiveness of FODEL for multi-agent planning with epistemic preconditions remains undecidable.
  • Complexity: While decidability is established for certain fragments, the complexity of these problems (e.g., PSPACE-complete, EXPTIME-complete) is not deeply explored in this paper.
  • Future Work: The authors suggest exploring other decidable fragments of FODEL planning, investigating the complexity of these decidable fragments, and developing actual planning algorithms for FODEL. This would involve translating the theoretical decidability results into practical computational tools.

Summary updated

BibTeX
@inproceedings{liberman2020decidability,
  author = {Andrés Occhipinti Liberman and Rasmus Kræmmer Rendsvig},
  title = {{Decidability Results in First-Order Epistemic Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/575},
}
Figure