A Logic-Based Explanation Generation Framework for Classical and Hybrid Planning Problems

Stylianos Loukas Vasileiou, William Yeoh, Tran Cao Son, Ashwin Kumar, Michael Cashmore, Daniele Magazzeni

Introduction

As AI agents become increasingly integrated into collaborative environments, the ability to explain their decisions to human partners is paramount. This is the core of Human-Aware Planning. Often, an agent and a human have differing "mental models" of a task—discrepancies in understanding preconditions, effects, or the initial state of the environment. When an agent proposes a plan that seems invalid or sub-optimal to the human, it must reconcile these models. This process is known as the Model Reconciliation Problem (MRP).

Traditional approaches to MRP have been tightly coupled to specific planning algorithms and primarily focused on "classical" planning—discrete, deterministic environments. However, real-world scenarios are rarely so simple. They often involve continuous variables (like fuel levels or time) and exogenous events, categorized as Hybrid Systems. This paper introduces a novel, logic-based framework that leverages Knowledge Representation (KR) and SAT/SMT solvers to provide robust, planner-agnostic explanations for both classical and hybrid planning problems.

The Logic-Based Framework

The authors shift the paradigm of model reconciliation from a search through the planning space to a problem of logical entailment. By representing the planning problem as a Knowledge Base ($KB$), the task of finding an explanation becomes finding a subset of formulas from the agent’s model ($KB_a$) that, when shared with the human, allows the human's model ($KB_h$) to logically prove the plan's validity or optimality.

Encoding the Problem

  1. Classical Planning: These problems are encoded into Boolean Satisfiability (SAT) instances. The logic captures the transitions between discrete states.
  2. Hybrid Planning (PDDL+): To handle continuous changes and time-dependent processes, the framework uses Satisfiability Modulo Theories (SMT). Specifically, it utilizes linear real arithmetic to model how variables like battery life or distance change over time.

Algorithms for Explanation Generation

The framework employs two primary algorithms to navigate the search space of possible explanations:

  • ALG1 (Best-First Search): This algorithm explores subsets of the agent's knowledge to find the "most preferred" explanation. Preference is typically defined by a cost function, such as minimizing the number of facts the human needs to learn.
  • ALG3 (Pre-processing and Pruning): To address scalability issues in complex models, ALG3 introduces a pre-processing step. It uses a "partial model" of the agent's plan to identify and correct direct contradictions in the human's knowledge base immediately. This significantly prunes the search space, allowing the system to handle much larger discrepancies between models.

Bridging the Communication Gap

A logical proof (e.g., a set of SMT clauses) is not inherently user-friendly. To make these explanations accessible, the authors implemented a template-based system. Logical formulas are mapped to natural language. For instance, a formula representing a missing precondition is translated into a clear statement: "Action [A] requires [Condition B] to be true." This ensures that the mathematical rigor of the logic-based approach is translated into actionable information for the human user.

Evaluation and Results

The framework was tested against standard International Planning Competition (IPC) benchmarks and complex PDDL+ hybrid domains.

Performance and Scalability

In classical domains, the ALG3 algorithm demonstrated a significant performance leap. When compared to the previous state-of-the-art method (CSZK), ALG3 was up to two orders of magnitude faster, particularly in scenarios where the human's model was highly inaccurate or the required explanation was long. In hybrid domains, the SMT-based approach maintained runtimes of less than one second for most problems, proving its viability for real-time applications.

Human-Centric Validation

The ultimate test of an explanation is its impact on a human user. The authors conducted a study with 72 participants using a custom "Plan Editor" in a logistics domain.

  • Success Rate: 91% of users who received the logic-based explanations were able to correct their plans.
  • Control Group: Only 24% of users in a control group (who were told their plan was wrong but not why) were successful. This stark difference highlights the effectiveness of providing structured, model-reconciling information.

Conclusion and Future Work

By moving to a logic-based, planner-agnostic framework, the authors have created a versatile tool for explainable AI. The system's ability to handle hybrid planning problems marks a significant step toward deploying explainable agents in real-world engineering and robotics contexts.

Future research will focus on moving beyond "one-shot" explanations toward iterative dialogues, where humans can ask follow-up questions. Additionally, the authors aim to address the challenge of proving "optimality" in hybrid systems—a task that remains mathematically complex but is crucial for high-stakes decision-making.

Summary updated

Abstract

In human-aware planning systems, a planning agent might need to explain its plan to a human user when that plan appears to be non-feasible or sub-optimal. A popular approach, called model reconciliation, has been proposed as a way to bring the model of the human user closer to the agent’s model. To do so, the agent provides an explanation that can be used to update the model of human such that the agent’s plan is feasible or optimal to the human user. Existing approaches to solve this problem have been based on automated planning methods and have been limited to classical planning problems only. In this paper, we approach the model reconciliation problem from a different perspective, that of knowledge representation and reasoning, and demonstrate that our approach can be applied not only to classical planning problems but also hybrid systems planning problems with durative actions and events/processes. In particular, we propose a logic-based framework for explanation generation, where given a knowledge base KBa (of an agent) and a knowledge base KBh (of a human user), each encoding their knowledge of a planning problem, and that KBa entails a query q (e.g., that a proposed plan of the agent is valid), the goal is to identify an explanation ε ⊆ KBa such that when it is used to update KBh, then the updated KBh also entails q. More specifically, we make the following contributions in this paper: (1) We formally define the notion of logic-based explanations in the context of model reconciliation problems; (2) We introduce a number of cost functions that can be used to reflect preferences between explanations; (3) We present algorithms to compute explanations for both classical planning and hybrid systems planning problems; and (4) We empirically evaluate their performance on such problems. Our empirical results demonstrate that, on classical planning problems, our approach is faster than the state of the art when the explanations are long or when the size of the knowledge base is small (e.g., the plans to be explained are short). They also demonstrate that our approach is efficient for hybrid systems planning problems. Finally, we evaluate the real-world efficacy of explanations generated by our algorithms through a controlled human user study, where we develop a proof-of-concept visualization system and use it as a medium for explanation communication.
BibTeX
@article{vasileiou2022logic,
  author = {Stylianos Loukas Vasileiou and William Yeoh and Tran Cao Son and Ashwin Kumar and Michael Cashmore and Daniele Magazzeni},
  title = {{A Logic-Based Explanation Generation Framework for Classical and Hybrid Planning Problems}},
  journal = {J. Artif. Intell. Res.},
  year = {2022},
  doi = {10.1613/jair.1.13431},
}
Figure