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
- Classical Planning: These problems are encoded into Boolean Satisfiability (SAT) instances. The logic captures the transitions between discrete states.
- 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,ALG3introduces 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