Exploring Plan Space through Conversation: An Agentic Framework for LLM-Mediated Explanations in Planning

1. Problem Statement

Automated planning systems often struggle to replace human planners in real-world sequential decision-making because they cannot fully capture human preferences, constraints, and evolving objectives. The planning process is inherently iterative: humans must guide the AI to refine goals and resolve conflicts.

• The Gap: While interactive planning is a known paradigm, interactive explanations are under-investigated. Static explanations (e.g., templates) fail to support the fluid, multi-turn dialogue required to resolve conceptual misunderstandings or complex goal conflicts.
• The Challenge: Large Language Models (LLMs) excel at natural language interaction but are unreliable at performing complex planning tasks independently. Conversely, traditional planners are rigid and lack conversational capabilities. The challenge is to create a hybrid system where LLMs facilitate the interaction (translation, questioning, explanation) while specialized algorithms handle the computation (planning, conflict detection).

2. Methodology

The authors propose a Multi-Agent LLM Framework that mediates between a human user and a formal planning system. The architecture is agnostic to the specific explanation framework used, focusing on the interaction layer.

A. System Architecture (Figure 1 & 2)

The system consists of specialized LLM agents acting as translators and classifiers, interacting with a backend "black box" containing the Planner and the Explanation Framework (EFCC).

1. Question Suggester ($S_Q$): Analyzes the current planning state (iteration step) to suggest relevant questions to the user, reducing cognitive load and guiding exploration.
2. Question Translator ($T_Q$): Classifies user input into specific question types (e.g., "Why is this unsolvable?" or "Can I add this goal?") and extracts arguments. It routes the query to the appropriate agent.
3. Goal Translator ($T_G$): Converts natural language goal descriptions (e.g., "never bring kids to the store") into formal temporal logic constraints (LTLf) required by the planner.
4. Explanation Translator ($T_E$): Takes formal explanations (sets of Minimal Unsolvable Subsets - MUS, or Minimal Correction Sets - MCS) generated by the backend and converts them into natural language responses, capable of summarization and context-aware follow-ups.
5. Dispatcher: Routes queries based on the question type (Direct answer, Follow-up, or Query to the Explanation Framework).

B. Theoretical Framework

• Iterative Planning Steps: The process is defined as a sequence of steps $\delta = \langle G_{ref}, G_{enf}, \pi \rangle$, where $G_{ref}$ are reference goals, $G_{enf}$ are enforced goals, and $\pi$ is a sample plan.
• Goal-Conflict Explanations: The system relies on MUS (Minimal Unsolvable Subsets) to explain why a set of goals cannot be satisfied, and MCS (Minimal Correction Sets) to explain how to make a task solvable (i.e., which goals to drop).
• Question Types: The framework supports a rich set of question types (Table 1), extending beyond simple "Why-not" queries to include:
  • US-why/US-how: Handling unsolvable tasks.
  • S-why-not/S-how: Explaining why specific goals are missing from a solvable plan.
  • S-can/S-what-if: Checking feasibility of adding new goals.

C. Implementation Details

• LLM Model: All agents use GPT-4.1-mini.
• Context Management: Agents maintain separate context histories for each iteration step to prevent hallucination and ensure clarity, while still allowing for follow-up questions within a step.
• Formal Logic: The system uses Linear Temporal Logic on finite traces (LTLf) to represent temporal goals, bridging the gap between natural language and the planner's requirements.

3. Key Contributions

1. Formal Framework: A generalized framework for iterative planning with natural language questions and explanations, defining the roles of translators and the structure of interaction steps.
2. Rich Explanation Interface: An extension of the "Explanation Framework with Conflicts and Corrections" (EFCC) that supports diverse question types (US-why, S-how, S-can, etc.), moving beyond simple template responses.
3. Agentic Implementation: A working multi-agent system where LLMs handle translation (NL $\leftrightarrow$ Formal Logic) and explanation generation, while delegating heavy computation to specialized solvers (Fast Downward).
4. User Study: A comprehensive evaluation comparing the LLM-based interface against a template-based baseline.

4. Results (User Study)

The authors conducted a user study with 131 participants (65 on a template-based interface, 66 on the LLM-based interface) using a "Parents' Afternoon" planning scenario (maximizing utility under time/resource constraints).

• Objective Performance:

  • Utility: The LLM group ($G_{LLM}$) achieved a slightly higher average utility (20.8 vs. 20.5) and reached the maximum utility more frequently (15.2% vs. 13.8%), though the difference was not statistically significant ($p > 0.05$) due to variance.
  • Efficiency: $G_{LLM}$ users asked significantly fewer questions (11.4 vs. 22.8) but these questions were more complex, triggering equivalent backend queries. This suggests higher information density per interaction.
  • Convergence: $G_{LLM}$ users showed a trend toward converging on acceptable plans in fewer iteration steps, particularly in the early stages.

• Subjective Performance:

  • Perceived Difficulty: Users in the LLM group reported significantly lower task difficulty ($p=0.02$).
  • Helpfulness: The LLM interface was rated significantly higher for helping users improve plans ($p=0.01$) and selecting unsolvable goals ($p=0.07$).
  • Engagement: The average conversation length was 4.3 turns, with 50% of interactions involving follow-up questions, indicating that users found the conversational aspect valuable for refining their understanding.

• Agent Evaluation:

  • The Question Translator ($T_Q$) achieved 91% accuracy in classifying question types and arguments.
  • The Question Suggester ($S_Q$) was highly adopted, with 61.7% of user questions coming from suggested options.

5. Significance and Future Work

• Bridging the Gap: The paper demonstrates that LLMs are highly effective as "intermediaries" in planning systems. They do not need to solve the planning problem themselves; rather, they translate human intent into formal constraints and translate formal conflicts back into human-understandable narratives.
• Trust and Usability: The study provides empirical evidence that conversational, LLM-mediated explanations significantly improve user trust and perceived ease of use compared to static templates, even if the raw objective metrics (utility) are similar.
• Future Directions:
  • Evaluating the framework with domain experts (who may ask more complex questions) rather than lay users.
  • Extending the approach to other explanation frameworks (e.g., Constraint Programming).
  • Improving the Goal Translator ($T_G$) to handle more complex, real-world goal creation without pre-defined templates.

In conclusion, this work establishes a robust architecture for Human-AI collaborative planning, proving that multi-agent LLM systems can effectively manage the "conversation" around planning, making complex optimization problems accessible and understandable to non-expert users.