PaperlayerView exact revision on arXiv

Source-linked AI summary

Neurosymbolic Embodied Agents

Mohammad Albinhassan, Yuming Feng, Alessandra Russo, Pranava Madhyastha

arXiv:2608.16794v1cs.ROcs.AIcs.CL

TL;DR

Embodied language and vision-language models can produce plausible but non-executable long-horizon plans because visual grounding and action applicability remain unreliable. This paper combines task-directed visual state acquisition with constrained symbolic planning and search, enabling open 4B–27B models to exceed 90% success on VirtualHome and ALFWorld.

  • Problem

    Embodied models generate plausible plans but lack reliable mechanisms binding visually acquired state to formal action semantics during generation.

  • Method

    A two-phase agent acquires a grounded symbolic initial state, then uses PDDL-constrained decoding and Monte Carlo tree search to generate executable plans.

  • Results

    Open 4B–27B models achieve 94.5–99.5% success in VirtualHome and 90.3–97.8% in ALFWorld, while substantially outperforming larger direct visual policies.

  • Takeaways & Limitations

    Applicability constraints and search maintain executable-by-construction planning under the transition model, with transfer conditioned on correct visual grounding.

  • Takeaways & Limitations

    The method depends on correct visual state acquisition and instance binding; recognition errors can omit required objects and cause task failure.

Abstract

from arXiv · show

Language and vision-language models generate plausible embodied plans but do not guarantee executability, as their outputs can violate environment dynamics or act on incorrectly grounded entities. We present a neurosymbolic agent that factors long-horizon household tasks into task-directed visual exploration and constrained symbolic planning. In the first phase, a vision-language model and exploration harness acquire goal-relevant predicates and instance bindings from egocentric observations and grounded interactions, producing a symbolic initial state. In the second, a PDDL transition model restricts decoding to tokens that extend applicable actions. Monte Carlo tree search then evaluates executable continuations using a domain-independent planning heuristic. The resulting plans are executable by construction under the transition model, with transfer to the environment conditioned on correct visual grounding. On VirtualHome and ALFWorld, open 4B-27B models exceed 90% success in both environments, and our smallest agent substantially outperforms a 27B direct visual policy in each. Constraints and search prove complementary rather than interchangeable: in ALFWorld either alone solves under a third of tasks, whereas their combination solves over 95%. The method also uses several times fewer generated tokens than extended thinking and far fewer model-visible images than direct interaction, and residual failures localize to state acquisition rather than plan generation without any specialized training.

1 Introduction

The paper addresses the gap between plausible vision-language plans and executable embodied behavior with a two-phase neurosymbolic agent that grounds visual state before constrained symbolic planning. Its structure yields executable-by-construction plans and strong performance across two household benchmarks.

  • Motivation: VLMs generate plausible action sequences, but long-horizon execution requires binding visually acquired state to formal action semantics during generation.Direct policies must jointly identify objects, relations, states, applicable actions, and delayed effects, allowing perception and planning errors to compound.
  • Method: The agent separates task-directed visual exploration from goal-directed symbolic planning through a grounded initial-state interface.Exploration acquires only goal-relevant objects, relations, and instance bindings before planning.
  • Method: State-dependent constrained decoding enforces PDDL action applicability, while MCTS selects executable plans using their long-horizon consequences.Applicability remains invariant throughout generation and search, making every returned plan executable under the transition model by construction.
  • Results: 94.5–99.5% success in VirtualHome and 90.3–97.8% in ALFWorld is achieved across Qwen3.5 models from 4B to 27B parameters.The evaluation spans two visually grounded household benchmarks with different action semantics and grounding demands.
  • Results: 32.0 percentage points in VirtualHome and 63.4 points in ALFWorld separate the 4B agent from the 27B direct visual policy.These gains indicate that explicit structure can substitute for considerable model scale.

2 Related Work

This section situates the work at the intersection of symbolic planning, LLM planning, constrained decoding, and embodied perception. It distinguishes the approach by exposing grounded operator applicability during inference, rejecting invalid continuations and restricting search to executable prefixes.

  • Symbolic Planning and LLM Planners: PDDL represents explicit world states whose grounded actions are executable only when preconditions hold, while effects update the state.This enables exact feasibility checks, although the combinatorial grounded action space motivates heuristic planners such as Fast Downward.
  • LLMs with PDDL and Symbolic Planners: LLM+P and NL2Plan translate language into PDDL and invoke planners, but generated domains can be syntactically plausible yet semantically incorrect.Later systems refine PDDL with agents and verifiers, expose symbolic transitions as tools, or induce action models.
  • LLMs with PDDL and Symbolic Planners: The proposed method exposes grounded operator applicability during inference, rejecting invalid continuations and restricting tree search to executable prefixes.This directly links symbolic transition constraints to inference-time plan generation.
  • Constrained Decoding for Structured Generation: Constrained decoding masks next tokens that violate formal specifications, supporting structured generation without fine-tuning, whereas most prior work addresses syntax or text-only generation.The section places these methods alongside embodied perception and planning, where representation construction is separated from goal-directed control.

3 Method: Neurosymbolic Embodied Agents

The method separates task-relevant visual grounding from symbolic planning in a partially observable setting. Exploration produces a grounded initial state, while PDDL constraints and search generate executable long-horizon plans.

  • Problem setting: The task is modeled as a finite-horizon POMDP with latent state, egocentric observations, sparse goal reward, and sequentially applicable actions.The agent does not solve the POMDP in belief space; Phase I reduces uncertainty over task-relevant state and commits to a point estimate.
  • Exploration phase: Phase I couples a VLM with a deterministic exploration harness that selects inspections, grounds skills, and records evidence for task-relevant literals and instance bindings.LOOK acquires additional viewpoints and may invoke grounded interactions; unsupported or conflicting proposals do not establish relational facts.
  • Exploration phase: Phase I terminates when required objects and relations are grounded, DONE is selected, or the interaction budget is exhausted, returning the grounded initial state and final symbol-to-instance binding.The Ready test determines whether the planning problem can be instantiated from the acquired facts.
  • Symbolic planning: Phase II combines the grounded state with a PDDL transition model, enforcing action applicability during token decoding rather than only after plan generation.Invalid tokens receive zero probability, and constraints are recomputed as each action advances the symbolic state.
  • Symbolic planning: PUCB-guided Monte Carlo tree search uses constrained model probabilities to rank valid continuations and evaluates them with symbolic distance and plan-length penalties.The heuristic is domain-independent and does not require a learned critic; search stops at a goal or returns the highest-valued valid candidate within budget.

4 Experimental Setup

The experiments evaluate the agent in complementary household simulators using controlled model-scale comparisons, direct interactive baselines, and Phase II ablations. Evaluation measures task success alongside token, image, plan-length, and failure-attribution costs under a shared egocentric interaction protocol.

  • Benchmarks: VirtualHome contains 200 unique problems across four goal families in furnished Unity apartments, testing novel object instances and multiobject rearrangement.The goal families involve placing objects in a dishwasher, microwave, or refrigerator, and preparing food.
  • Models and baselines: Experiments use Qwen3.5 models at 4B, 9B, and 27B parameters, comparing direct interactive VLM policies with reasoning, search, and constraint ablations.Phase II ablations include unconstrained greedy decoding, unconstrained thinking, constrained greedy decoding, unconstrained MCTS, and constrained MCTS.
  • Evaluation protocol: All methods receive the task goal, the same egocentric RGB interface, and simulator-generated success or concise invalid-action error feedback.Direct policies choose one action per turn, while the exploration harness tracks inspection history and curates high-level exploration skills without exposing privileged scene state.
  • Search: MCTS scores nonterminal prefixes with a weighted average of domain-independent heuristics including Fast Forward, LM-cut, and remaining plan cost.The cited heuristics are associated with Downward and prior planning work.
  • Metrics: The primary metric is simulator-defined task success, supplemented by generated tokens, model-visible RGB images, successful plan length, and failure attribution.Generated-token cost sums output tokens across episode model calls, while image cost counts frames provided to the model rather than internally rendered simulator frames.

5 Results

The neurosymbolic agent achieves high task success across VirtualHome and ALFWorld while using fewer generated tokens and visual observations than unconstrained or direct-interaction baselines. Ablations and failure attribution show that constraints and search jointly improve execution, with residual errors concentrated in visual state acquisition.

  • Task success: 94.5–99.5% VirtualHome and 90.3–97.8% ALFWorld success substantially outperform direct visual interaction and unconstrained chain-of-thought reasoning across model scales.The method factorizes task-directed state acquisition from executable symbolic search.
  • Task success: 94.5% and 90.3% success from the 4B agent exceed the 27B direct VLM by 32.0% and 63.4% points in VirtualHome and ALFWorld.The 4B agent also exceeds unconstrained thinking with the 27B model by 35.5 and 73.4 points.
  • Efficiency: Up to 1.5× fewer generated tokens than unconstrained MCTS and 4.0× fewer than extended thinking are achieved by constrained MCTS.Constraints remove inapplicable branches before token generation focuses on executable alternatives.
  • Efficiency: Up to 5.5× fewer model-visible images than direct interaction are required, typically four to six rather than 13–34.Phase I builds a compact task-relevant representation once, which Phase II reuses during plan comparison.
  • Ablation and failures: 2.3% of VirtualHome tasks and 4.5% of ALFWorld tasks fail during representation acquisition, while only 1.0% of ALFWorld tasks fail after acquiring a usable state.Direct Qwen policies instead fail to reach the goal on 64.2% of evaluated VirtualHome tasks; in ALFWorld, 39.8% fail at grounding and 48.8% terminate without satisfying the goal.
  • Ablation and failures: 95.5% ALFWorld success from combining constraints and MCTS exceeds 32.3% for constraints alone and 29.2% for unconstrained MCTS.In VirtualHome, constrained greedy decoding reaches 98.5% from 61.0%, while unconstrained MCTS reaches 99.0% at higher generation cost.

6 Conclusion · A Extended Experimental Setup

The paper presents a neurosymbolic agent that separates task-directed visual exploration from constrained symbolic planning, maintaining action applicability through generation and search. This factorization enables open 4B–27B models to outperform larger direct visual policies and other baselines while using fewer generated tokens and visual observations.

  • 6 Conclusion: The agent factors long-horizon embodied planning into grounded initial-state construction and constrained symbolic plan generation.A VLM and exploration harness construct the grounded initial state, while state-dependent decoding and MCTS generate a goal-directed plan under explicit PDDL dynamics.
  • 6 Conclusion: State-dependent decoding and MCTS maintain action applicability throughout generation and search.This converts action applicability from a behavior the model repeatedly infers into a constraint maintained during planning.
  • 6 Conclusion: The method uses explicit PDDL dynamics to constrain executable, goal-directed planning.The transition model supports state-dependent decoding, and MCTS searches over the resulting continuations.
  • 6 Conclusion: Open 4B–27B models substantially outperform larger direct visual policies.The comparison is attributed to the factorized exploration-and-planning design.
  • 6 Conclusion: The agent also outperforms unconstrained reasoning and embodied-specialized baselines.The conclusion attributes these gains to maintaining constraints during generation and search.
  • 6 Conclusion: The approach achieves these comparisons while using fewer generated tokens and visual observations.The passage reports reductions in both generated-token usage and visual observations relative to the cited baselines.

A.1 Evaluation Protocol … A.4 MCTS

The evaluation covers 200 VirtualHome tasks and all 134 ALFWorld unseen-split episodes under hidden simulator state and class-level action grounding. The protocol separates visual state acquisition from open-loop symbolic planning, while comparing specified decoding and MCTS configurations.

  • A.1 Evaluation Protocol: 200 VirtualHome tasks and all 134 ALFWorld unseen-split episodes are evaluated from natural-language goals and egocentric RGB observations.Simulator scene graphs, object states, instance identifiers, and admissible actions remain hidden from the model.
  • A.1 Evaluation Protocol: Phase I greedily explores until relevant predicates are grounded or Nexp steps are reached, then Phase II generates an open-loop symbolic plan of at most Nplan actions without visual inputs or executor access.The combined budget Nexp + Nplan is restricted to 20 in VirtualHome and 55 in ALFWorld.
  • A.2 Direct Visual Interaction: Direct policies emit one class-level action per turn from the current first-person observation, with the parser grounding classes to executable instances before simulator advancement.Successful actions return acknowledgments; failed actions return concise grounding or reachability errors and leave the observation unchanged.
  • A.3 Sampling Parameters: Greedy decoding is used for Phase I, direct Qwen, greedy planning, constrained greedy planning, and both MCTS conditions, including temperature-zero reasoning-enabled rows.Qwen supplementary thinking uses recommended sampling settings over seeds 0, 42, and 1738; MiMo and Embodied-R1.5 use recommended sampling configurations.
  • A.3 Sampling Parameters: RoboBrain uses its recommended greedy configuration for the main result, with additional nucleus-sampling sensitivity analysis over three seeds.Table 3 identifies the seeds as 0, 42, and 1738 and uses a dash for no top-k cutoff.
  • A.4 MCTS: Both MCTS variants use token-level prior-weighted UCT with expansion width 16, exploration constant 2.5, base constant 10, and a 250-second task limit.Search stops early on a PDDL-valid goal plan; constrained MCTS masks tokens that cannot extend applicable PDDL actions and caches reusable constrained prefixes, while unconstrained MCTS searches the full model distribution.

A.5 Cluster Specifications · B Statistical Analysis · B.1 Multiple Runs

The paper evaluates local models on A100-80GB and H200 clusters and quantifies stochastic sensitivity through repeated runs with task-cluster bootstrap intervals. Across conditions, the factorized method reduces image-conditioned interactions, while unconstrained baselines remain substantially weaker.

  • A.5 Cluster Specifications: Experiments used NVIDIA A100-80GB and NVIDIA H200 clusters, with each evaluation job using one GPU, 8–16 CPU cores, and 128 GB RAM.Local-model inference used bfloat16 precision with vLLM.
  • A.5 Cluster Specifications: Local inference avoids per-token API charges, and the method is also more accurate than the API-evaluated alternative.Table 4 reports the Gemini 3 Flash high-thinking API costs in USD.
  • B Statistical Analysis · B.1 Multiple Runs: Three repeated runs use seeds 0, 42, and 1738, reporting mean success rate, sample standard deviation, and 95% percentile confidence intervals.Intervals come from 10,000 task-cluster bootstrap replicates that resample task indices consistently across runs.
  • B Statistical Analysis · B.1 Multiple Runs: Deterministic conditions are evaluated once and have zero decoding variance, while stochastic conditions report sample standard deviation across three runs.Table 5 uses a common format, with deterministic conditions marked ±0.0.
  • B.1 Multiple Runs: 57.5% in VirtualHome and 18.5% in ALFWorld are the strongest results for local conditions using neither constraints nor search, achieved by Qwen3.5-27B thinking.Recommended-sampling Qwen thinking remains substantially below the method at every scale and on both benchmarks.
  • B.1 Multiple Runs: 11.0 images per VirtualHome episode and 23.2 images in ALFWorld are used by Gemini, versus 4.8 and 3.8 model-visible images for the 27B method in Phase I.Phase II plans without further image-conditioned model calls and executes the final plan in a single open-loop pass.

B.2 Paired Significance Testing · C Additional Results

Exact paired McNemar tests with Holm correction support the method’s main accuracy claims across model scales, environments, and ablations. Search and transition-model constraints are complementary, with their combination especially important in ALFWorld.

  • B.2 Paired Significance Testing: Exact paired McNemar tests use conservative maximum p-values across stochastic runs, with Holm correction controlling family-wise error at α = 0.05.The tests define separate families for main comparisons and component ablations.
  • B.2 Paired Significance Testing: Our method significantly outperforms matched direct Qwen and recommended-sampling thinking baselines at every model scale in both environments.The comparison is reported after multiple-comparison correction.
  • B.2 Paired Significance Testing: The 4B method significantly exceeds the 27B direct and thinking baselines.Against Gemini 3 Flash with high thinking, the 4B method is not significantly different in VirtualHome but is significantly stronger in ALFWorld.
  • B.2 Paired Significance Testing: Scaling from 4B to 9B is significant in both environments, whereas the difference between 9B and 27B is not significant in either.These conclusions hold after Holm correction.
  • B.2 Paired Significance Testing: In ALFWorld, constrained greedy and unconstrained MCTS are both significantly weaker, while combining search with transition-model constraints provides the decisive gain.The paired tests substantiate the paper’s central task-accuracy claims.

C.1 Failure Attribution by Model and Environment

Disaggregated failure attribution reveals that larger direct Qwen models reduce terminal grounding failures, but substantial long-horizon completion failures remain. Figure 4 also provides model- and environment-specific breakdowns beyond the grouped main-text results.

  • Failure attribution: Figure 4 attributes terminal failures by environment and model, including embodied policies and the Gemini API baseline, without aggregation across environments, Qwen scales, or visual-policy models.Values are percentages of all tasks in each row; successful tasks belong to no failure category.
  • Failure attribution: 16.0% to 0.5% in VirtualHome and 64.9% to 14.9% in ALFWorld: increasing direct Qwen scale reduces terminal grounding failures.The passage reports the reduction across model scales in each environment.
  • Failure attribution: 37.0% and 58.2% of tasks: the 27B policy still terminates without reaching the goal in VirtualHome and ALFWorld, respectively.Scale improves action grounding more than long-horizon completion.

C.2 Phase-II Results across Model Scales

Across Qwen3.5 model scales, the Phase-II breakdown reinforces that constraints are especially effective in VirtualHome, while neither constraints nor unconstrained search alone closes the ALFWorld gap. Combining constraints with search yields 90.3–97.8% ALFWorld success across all three scales, and recommended sampling does not change this ordering.

  • Phase-II results: 90.3–97.8% ALFWorld success is achieved by combining constraints with unconstrained search across all three Qwen3.5 model scales.The combined method outperforms either constraints or unconstrained search alone on ALFWorld.
  • Phase-II results: Constraints alone are highly effective in VirtualHome, particularly at the 9B and 27B model scales.The full scale breakdown reinforces the main ablation, but the supplied passage does not provide the corresponding task-success values.
  • Phase-II results: Neither constraints alone nor unconstrained search alone closes the ALFWorld gap across model scales.Their combination is required to reach the reported 90.3–97.8% ALFWorld success range.
  • Phase-II results: Recommended sampling changes the unconstrained-thinking result but does not alter the ordering among Phase-II conditions.The table reports recommended-sampling thinking values using three seeds; other conditions use deterministic decoding.

D Fine-Grained Failure Analysis … E Prompts

The analysis shows that direct-policy failures persist through interaction limits, weak recovery, and representation-level errors, while embodied policies exhibit distinct failure mechanisms. The prompts separate task-directed exploration from constrained symbolic planning and unconstrained direct interaction.

  • D Fine-Grained Failure Analysis: Direct Qwen’s grounding failures fall from 16.0% to 0.5% in VirtualHome and 64.9% to 14.9% in ALFWorld as scale increases, but interaction limits remain dominant.In ALFWorld, Qwen-27B loses 44.8% of tasks to the interaction limit and 13.4% to premature termination.
  • D Fine-Grained Failure Analysis: VirtualHome embodied policies differ sharply: Embodied-R1.5 reaches the interaction limit or emits DONE on 99.0% of tasks, while RoboBrain’s dominant ALFWorld outcome is repeated ungroundable action generation at 67.9%.MiMo combines substantial grounding and budget-exhaustion limitations, so aggregate embodied results mask qualitatively different failures.
  • D.1 Response to Interaction Failure: Qwen-27B reduces repeated failed requests from 74.5% to 8.3% in VirtualHome and raises recovery from 5.4% to 37.9%, but recovers only 25.7% in ALFWorld.It still enters persistent loops on 42.5% of all ALFWorld tasks.
  • D.1 Response to Interaction Failure: Embodied failures are nonuniform: R1.5 repeats only 4.6% of failed requests but enters loops on 58.0% of VirtualHome tasks, while RoboBrain repeats requests after 84.3% of failed transitions.MiMo encounters failed execution in 96.3% of ALFWorld tasks and recovers none of those affected episodes in the seed-0 run.
  • D.2 Representation-Level Errors: Residual Phase-I errors separate into local perceptual ambiguity for small objects and incomplete search coverage when exploration budgets expire.These failure types are not captured by a single missing-object count.
  • D.3 Representative Policy Traces: Representative traces distinguish local perception, finite active-search coverage, repeated state reversal, and view-control oscillation, showing why scale alone cannot ensure completion.Larger models may choose appropriate actions yet lack persistent scene memory, global progress state, or recovery policies.
  • E.1 Phase I: Task-Directed Exploration: Phase-I prompts provide first-person views, goal-relevant classes, accumulated beliefs, grounded-action history, feedback, and harness-curated inspection skills.The harness executes the selected skill and accepts relational facts only when supported by observations or interactions.
  • E.2 Phase II: Planning / E.3 Direct Visual Interaction: Phase II receives the grounded state and symbolic goal without images, while PDDL decoding masks continuations that cannot form applicable next actions; direct policies instead infer state from visual feedback.Direct Qwen receives first-person observations, reachability, an action DSL, class-name conventions, and a one-action output requirement.
Loading 2608.16794v1…