MemPlan: Memory-Conditioned PDDL Planning for Partially Observable Text Environments

AI summary

Overview

Research area: Neuro-symbolic AI for sequential decision-making — specifically, combining classical automated planning (PDDL) with large language models for agents that act in partially observable text-based environments.

Technical level: Intermediate. The paper assumes familiarity with PDDL concepts (domains, problems, preconditions, effects, action costs) and with LLM agent baselines such as ReAct, but the core idea is explained clearly enough for a reader who knows only one of the two halves.

Scope (1 sentence): The paper proposes MemPlan, a framework that keeps a fixed PDDL domain and rebuilds the PDDL problem at every step from parsed observations, candidate hypotheses, and positive/negative memory, so that a classical planner — not an LLM — does the long-horizon planning in text environments.

What This Paper Is About

LLM agents can read text observations and issue text commands, but using an LLM as the primary long-horizon planner is expensive and unreliable: it hallucinates actions, forgets earlier observations, and loses plan coherence. Classical planners are the opposite — fast, exact, and cheap, but they require a complete symbolic world state, which partially observable text games never provide. MemPlan's goal is to bridge these two worlds without letting the LLM rewrite PDDL files online: instead, the LLM is demoted to a narrow, offline-trained "language-to-symbol" translator, while all search and decision-making is handed to a classical planner that is fed a freshly reconstructed problem at each step.

Key Contributions

1. Memory-conditioned PDDL problem construction. A closed-world planner is made usable in partially observable text environments without any online PDDL rewriting: the domain stays fixed, and only the instance-level problem file is rebuilt each step from parsed facts, candidate hypotheses, and memory.

2. A positive/negative memory mechanism compiled into planning structure. Positive memory is a typed directed multigraph whose retrieval relevance is turned into PDDL action costs that rank unresolved hypotheses; negative memory records execution-refuted assumptions and compiles them into exclusions (searched, not_at) so the planner cannot re-test what the environment has already contradicted.

3. An offline-trained, schema-conditioned language–symbol interface. One frozen model performs only two constrained jobs — observation-to-fact parsing (validated against the domain's predicate/type schema and object glossary) and symbolic-action-to-command grounding — removing the LLM from the online planning role entirely.

4. A placeholder mechanism for unresolved entities. Missing objects, locations, or conditions are represented as typed placeholders (e.g., unknown_grill_1) placed in a virtual location loc_limbo, so the planner can reason about entities it has not yet discovered.

Main Findings

• ALFWorld completion and efficiency: MemPlan reaches 100% success across the six ALFWorld task types on 134 episodes (clean, cool, examine, heat, put, puttwo all at 1.00), with 6.91 environment steps and 0.906M online tokens. For comparison, ReAct with GPT-5.1 scores 98.5% at 10.92 steps and 2.74M tokens; PDDLEGO+-Native 94.8% at 14.32 steps and 2.31M tokens; PDDLEGO+-Shared 92.5% at 15.47 steps and 1.82M tokens; LLM-DP 96.0% at 13.16 steps and 0.633M tokens.

• Token cost is dramatically lower than LLM planning, but not the lowest overall: MemPlan uses far fewer online tokens than ReAct with GPT-4o (5.07M vs 0.906M in Table 1) and than GPT-4o with domain descriptions (13.09M). However, LLM-DP retains the lowest online token cost (0.633M in Table 2; 4.7k tokens per episode vs MemPlan's 6.9k in Table 5). The paper states this trade-off explicitly: MemPlan spends slightly more tokens than LLM-DP but achieves shorter episodes and higher completion.

• Very low invalid-action rate: MemPlan's invalid-action rate on ALFWorld is 0.00, versus 0.03 for ReAct (GPT-4o) and 0.01 for LLM-DP. Its online LLM calls are limited to parsing and grounding (16.87 calls per episode versus 6.91 planner calls), and planner calls consume no LLM tokens.

• TextWorld memory-agent comparison: On the 7 TextWorld task instances, the paper reports that MemPlan obtains the strongest normalized-score performance among the compared memory-augmented LLM agents (Full History, Summary, RAG, Reflexion, Simulacra, AriGraph, and the Human All reference). Exact per-instance scores appear in Figure 2 and the appendix rather than in the running text, and the authors explicitly frame this as evidence on the reported setting rather than a broad claim.

• Robotouille, synchronous vs. asynchronous: MemPlan reaches 71.2% synchronous and 41.3% asynchronous success. ReAct with GPT-5.1 gets 63.6% / 24.7%, LLM-DP 57.9% / 18.5%, ReAct with GPT-4o 47.0% / 11.0%, ReAct with GPT-4o-mini 11.0% / 0.0%, Gemini-1.5-Flash 0.0% / 0.0%, and Claude-3-Haiku 2.0% / 0.0%. The margin over baselines is larger in the asynchronous setting, which the authors attribute to feedback-driven replanning helping when action effects are delayed.

• Three distinct ablation failure modes (TextWorld, 21 runs each):

  • Structural failure: removing placeholders collapses normalized score to 0.27 and produces 1.0 terminal planner dead ends per run — unobserved entities simply cannot be represented.
  • Recovery failure: removing negative memory drops score to 0.64 and raises repeated hypothesis checks from 0.0 to 12.0 per run and steps from 31.0 to 60.0.
  • Execution-reliability failure: removing the parser (0.55), the grounder (0.45), or the whole learned interface (0.36) degrades performance mainly through invalid actions (4.0, 9.0, and 12.0 per run respectively).
  • Cost shaping is about efficiency, not feasibility: uniform-cost hypotheses retain a 1.00 normalized score but require 38.0 steps instead of 31.0, with 1.0 repeated check per run.

• Cross-task interface reuse: The single fine-tuned interface (from TextWorld cook and hunt tasks, using 17,000 observation-to-fact examples and 9,600 symbolic-action-to-command examples) is reused across TextWorld task types without task-specific fine-tuning, including the held-out Cleaning family.

• Offline domain generation is feasible: In the TextWorld protocol, GPT-5.1 drafted domains with no access to test maps, object placements, oracle trajectories, interaction logs, or evaluation feedback; 5/7 domains (71.4%) were valid on the first attempt and the remaining two were repaired after one offline feedback round, then fixed for evaluation.

• Case study: On a TextWorld Cooking Hard task, MemPlan used a placeholder for a missing grilling device, executed a look observation command when grounding failed, avoided treating the unrealized symbolic action as executed, replanned, and resolved the device to bbq_0 — finishing in 31 steps with normalized score 1.00 and a final score of 14/14.

Methodology in Plain English

The researchers split the labor between two very different kinds of machinery.

The planner does the thinking. For each environment (ALFWorld, TextWorld, Robotouille) they fix one PDDL domain — object types, predicates, action schemas with preconditions and effects — that never changes during evaluation. Fast Downward, a classical planner, searches over that domain. What changes at each step is the problem file: which objects exist, what is initially true, and what the goal is.

The LLM does only translation. A Qwen2.5-7B model is fine-tuned offline to do two narrow jobs and then frozen. Parsing turns a sentence like "the orange bell pepper is in the fridge" into a typed triple, but only if the relation exists in the domain schema and the entities appear in the current object glossary — otherwise the fact is rejected. Grounding turns a symbolic action the planner chose into one of the actual commands the environment is currently offering, by scoring each admissible command and picking the best match.

Missing information becomes a hypothesis rather than a guess. If the goal needs something the agent has not seen, MemPlan inserts a typed placeholder into the problem and a virtual location called loc_limbo, plus special "check this hypothesis" actions. The planner can then plan around the unknown and go test it.

Memory shapes the search, twice over. Positive memory is a graph of everything observed or confirmed. For each candidate hypothesis, the system builds a short text description of that candidate plus its one-hop graph neighborhood, embeds it with frozen multilingual Contriever (mContriever), compares it to an embedding of the goal plus the placeholder, and min–max normalizes the cosine similarities into a score in [0, 1]. That score becomes a PDDL action cost: with base cost κ_base = 1, threshold τ = 0.50, and penalty scale λ = 10, a hypothesis check costs 1 + ⌈10 · max(0, 0.50 − score)⌉. Plausible checks are cheap; implausible ones are expensive, so the planner tries promising candidates first. Negative memory works the other way: when a targeted check comes back "not found," that candidate is written into an exclusion predicate so later problem files simply cannot propose it again.

The loop is: parse, build problem, plan, execute one action, update memory, replan. Only the first action of each plan is ever executed, so the agent constantly re-anchors on real feedback.

Why This Matters

For research: The paper makes a concrete architectural claim that pushes back on the trend of giving memory to LLM agents as retrieved text context. Here memory is compiled into planner-visible costs and constraints — a structural intervention rather than a prompting one. It also shows a workable middle path between two unsatisfying extremes: LLM-DP-style commitment to a single completed world state, and PDDLEGO-style online rewriting of PDDL files (which the authors note can produce malformed PDDL, hallucinated facts, or forgotten observations). The result that a 7B model suffices as a frozen interface, while a classical planner does the reasoning, is a useful data point on where the compute should go in neuro-symbolic agents.

Real-world applications (implied by the design, not evaluated in the paper):

• Household and service robotics: the ALFWorld/ALFRED setting is a text stand-in for manipulation tasks where the robot must search for objects it has not yet located in rooms it has not yet entered.
• Enterprise workflow and RPA agents: long-running processes over constrained action APIs, where a wrong action has a cost and an invalid action is rejected by the system.
• Game AI and interactive narrative: NPCs or player-side agents in text worlds that must satisfy multi-step objectives under fog of war.
• Tool-using LLM assistants in constrained environments: any setting where the available commands are a finite, enumerated set and cheap replanning matters more than fluent generation.

Industry relevance: The cost argument is the practical one. The paper cites prior work (Dagan et al., 2023) showing that replacing an LLM planner with a classical planner saves approximately 93.1% of LLM tokens. MemPlan's own numbers — 0.906M tokens versus 5.07M for ReAct with GPT-4o on the same 134 ALFWorld episodes — point at the same conclusion: if planning moves off the LLM, the per-episode inference bill drops by a large factor, and the remaining LLM calls are short, schema-checked, and cacheable.

Future Directions

1. Automating domain construction online. The biggest stated limitation is the hard dependency on a correct task-level PDDL domain. The authors show GPT-5.1 can draft TextWorld domains offline with 5/7 valid on the first attempt, but MemPlan itself does not build or repair domains during interaction. Bringing validated domain induction inside the loop — without reintroducing online hallucination risk — is the obvious next step.

2. Replacing hard exclusions with confidence-weighted negative memory. Currently a refuted candidate is removed from all future problem files. This is brittle: ambiguous or misparsed feedback can permanently exclude a correct candidate. Confidence-weighted negative memory that merely demotes a candidate rather than deleting it is proposed directly by the authors.

3. Extending beyond simulated, benchmark-specific action spaces. The evaluation is confined to text environments with enumerated admissible commands. Whether the parse/ground/plan/replan loop survives open-ended environments without a constrained command set, or physical robotics and safety-critical deployment, is untested.

4. Reducing the remaining token gap. LLM-DP still achieves a lower online token cost (0.633M vs 0.906M on ALFWorld). Since MemPlan's tokens all go to parsing and grounding (16.87 LLM calls per 6.91 planner calls), shrinking or further specializing those interface calls is a direct efficiency target — and the appendix's nine-setting sensitivity analysis over κ_base, τ, and λ suggests cost calibration is another dial worth exploring.

Target Audience

Researchers and engineers working on LLM agents, neuro-symbolic reasoning, or automated planning who want a principled way to keep a classical planner in the loop without giving up natural-language interaction. It is most valuable to readers who already know what a PDDL problem file is and what ReAct-style agents cost to run, and who are deciding where to put the LLM in their architecture. Practitioners building long-horizon agents over constrained action APIs will find the efficiency and invalid-action numbers the most actionable part; students entering the neuro-symbolic planning area will find the ablation table a compact map of which components fail in which way.

Authors’ abstract

LLM agents are flexible in language interaction, but using them as long-horizon planners is costly and prone to hallucinated or invalid actions. This paper targets a different role for LLMs: constrained bridges between language and symbolic planning. We propose MemPlan, a memory-conditioned PDDL planning framework for partially observable interactive text environments. MemPlan keeps the PDDL domain fixed and reconstructs the PDDL problem at each step from parsed observations, candidate hypotheses, and interaction memory. Positive graph memory assigns relevance-based action costs to candidate hypotheses for missing objects, locations, or conditions, guiding the planner toward more plausible checks. Negative memory records execution-refuted assumptions and compiles them into exclusion constraints, preventing repeated attempts at candidates already contradicted by feedback. A unified schema-conditioned language--symbol interface, trained offline with supervised fine-tuning, connects text environments to the planning loop through observation-to-fact parsing and symbolic-action-to-command grounding. Experiments on TextWorld, ALFWorld, and Robotouille show that MemPlan improves task completion and step efficiency over language-only and PDDL-aware baselines, while substantially reducing online token cost compared with LLM-planning baselines such as ReAct. The same fine-tuned interface is also reused across TextWorld task types without task-specific fine-tuning. Our code and data are available at: https://github.com/tewiSong/MemPlan.