A Simple Framework for Cognitive Planning

Jorge Luis Fernandez Davila, Dominique Longin, Emiliano Lorini, Frédéric MarisAAAI 2021 · DOI

Presented at AAAI-2021, this research introduces a formal logical framework for "cognitive planning," extending the capabilities of traditional epistemic planning. While epistemic planning focuses on modifying what an agent knows, cognitive planning aims to influence what an agent intends to do. By utilizing belief bases and a specific NP-complete fragment of epistemic logic, the authors provide a computationally grounded method for artificial agents to persuade humans through structured dialogue.

Problem Statement: Beyond Logical Omniscience

In AI planning, "classical planning" typically involves changing the physical state of the world, while "epistemic planning" focuses on changing the mental states of agents. However, existing epistemic models often suffer from two major drawbacks:

  1. Computational Complexity: Most models are PSPACE-complete or undecidable, making them impractical for real-time interaction.
  2. Logical Omniscience: Standard epistemic logic assumes agents automatically know all logical consequences of their beliefs. Real humans have finite reasoning capabilities and limited "belief bases."

This paper addresses these challenges by creating a tractable framework that models how a "persuader" agent can provide information to a "persuadee" to lead them toward a specific intention, while respecting the human's cognitive limits.

Methodology

The framework is built upon three primary pillars designed to ensure both theoretical rigor and practical efficiency:

  1. Belief Bases: Instead of using computationally explosive Kripke semantics, the authors represent an agent’s mental state as a set of formulas they explicitly hold. This distinguishes between explicit belief (what is currently in the agent's mind) and implicit belief (what could be logically deduced).
  2. The $\mathcal{L}_{Frag}$ Fragment: To maintain tractability, the authors identify a subset of logic where the machine agent has unbounded reasoning, but the human agent's beliefs are restricted. They prove that checking satisfiability within this fragment is NP-complete.
  3. Reduction to SAT: The authors provide a polynomial-size reduction process, translating cognitive logic into propositional logic. This allows the use of high-performance, off-the-shelf SAT solvers to find optimal planning solutions.
  4. Informative Actions: The model introduces "speech acts." When the AI informs the human of a fact, it triggers a private expansion of the human's belief base, potentially leading to new intentions.

Evaluation: The Sport Assistant Scenario

As a theoretical contribution, the framework is evaluated using a synthetic Human-Machine Interaction (HMI) scenario called the "Sport Assistant." In this setup, an AI agent helps a human user choose a sport to practice based on various attributes.

Table of sports and their attributes used in the Sport Assistant synthetic scenario.

The dataset for this scenario consists of a truth table (Figure 1) defining options like swimming, tennis, and squash against variables such as cost, intensity, and sociality. The AI's goal is to find a sequence of speech acts that convinces the user that a specific sport is their "ideal" choice based on their underlying desires.

Key Results and Insights

  • Persuasion as Intentional Change: The core insight is that intentions cannot be directly dictated; they must follow logically as "justified" conclusions from updated beliefs about the world.
  • Computational Tractability: The paper successfully proves that the satisfiability problem for $\mathcal{L}_{Frag}$ is NP-complete. Furthermore, the problem of "plan existence" is shown to be in $\Sigma^P_2$, which is manageable for modern solvers.
  • Proof of Concept: In the Sport Assistant example, the authors demonstrate that a sequence of just six speech acts (e.g., informing the user about danger levels, then location, then intensity) can successfully move a user from an undecided state to a justified intention to practice squash.

Limitations and Future Work

While the framework provides a solid foundation, several areas remain for future exploration:

  • Belief Revision: The current model only handles "belief expansion" (adding information). Future iterations need to handle revision, where users must discard old, incorrect beliefs when presented with new evidence.
  • Bidirectional Dialogue: The framework currently focuses on one-way information flow. Incorporating user feedback and questions would create a more natural dialogue system.
  • Learning Priors: The authors suggest using Inductive Logic Programming (ILP) to allow the AI to learn a user's initial desires through observation rather than relying on hard-coded starting states.

Summary updated

BibTeX
@inproceedings{davila2021simple,
  author = {Jorge Luis Fernandez Davila and Dominique Longin and Emiliano Lorini and Frédéric Maris},
  title = {{A Simple Framework for Cognitive Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16786},
}
Figure