TESS: LLM-guided Translation, Exploration, Simulation, and Search for Embodied Task Planning

AI summary

Overview

Research area: Embodied AI / robot task planning, combining large language models (LLMs) with classical heuristic search.

Technical level: Advanced — the paper assumes familiarity with LLM prompting and finetuning, scene-graph world representations, and classical planning algorithms (BFS, A*).

Scope: The paper presents TESS, a pipeline that uses LLMs in four supporting roles — translating instructions into checkable goal predicates, guiding exploration under partial observation, simulating action effects with generated Python functions, and pruning the candidate action space — so that an A*-style search over environment states can produce executable plans in text-based household simulators.

What This Paper Is About

Embodied task planning asks an agent to break a natural-language instruction into a sequence of atomic actions in an interactive environment. LLM-based planners can produce such sequences but often generate plans that are wrong or cannot actually be executed, while classical search algorithms would guarantee correct plans if only the environment were fully observable, the action effects known, and the goal state well defined. The paper's goal is to make classical search usable in realistic, partially observable, object-rich environments by filling those three gaps with LLM commonsense knowledge.

Key Contributions

1. TESS, an LLM-guided search pipeline for embodied task planning, in which search is performed directly in the environment's state and action space rather than over an LLM's output tokens, with LLM-based modules handling translation, exploration, simulation, and action filtering.
2. A new VirtualHome benchmark built on the evolving-graph simulator, spanning 25 task categories, 50 apartments, and 300+ target object categories, with human-like GPT-written instructions and automated goal-condition evaluation; apartments are split 30/10/10 for train/validation/test, and experiments use a 1k-task test set and a 3k-task training set.
3. A rule-based world model generated by an LLM: one Python precondition function and one effect function per action type, operating on the scene graph, instead of prompting an LLM for every state transition.
4. Empirical validation on two simulators — the proposed VirtualHome benchmark and ALFWorld — showing gains for both an API-based (GPT) and a finetuned (Qwen3-8B) instantiation of TESS.

Main Findings

• VirtualHome success rates: TESS-GPT reaches 85.1 SR / 90.9 GCR on Seen, 71.4 / 83.1 on Unseen_obj, and 74.7 / 86.4 on Unseen_task. TESS-Qwen reaches 87.2 / 92.4, 72.0 / 81.9, and 70.3 / 79.4 on the same splits. Both use only partial observations, yet outperform baselines given the complete scene graph (CoT+ZSP at 75.5 / 86.3 Seen, FLTRNN at 71.9 / 83.2 Seen) and re-planning baselines such as Reflexion and TP.
• Unseen objects are the hardest split for prior work: TESS's largest margin appears on Unseen_obj, where CoT+ZSP drops to 46.0 SR and ReAct to 21.7; the authors attribute the difficulty to those tasks containing more target objects on average.
• Finetuned baselines generalize worse to new task types: LID scores 53.4 SR and Equilibrium 59.4 SR on Unseen_task, versus 74.7 for TESS-GPT, which the authors read as evidence for the generality of search-based planning.
• Translation module is reliable: predicate-prediction accuracy is 96.0% for TESS-GPT and 89.1% for TESS-Qwen; substituting ground-truth predicates changes overall SR only marginally (80.0 to 82.0 for TESS-GPT, 80.2 to 84.8 for TESS-Qwen).
• Exploration is far cheaper than random: average exploration steps are 19.9 (TESS-GPT) and 30.2 (TESS-Qwen) versus 66.6 for a random policy; the 2.3-step figure under full observability is described as a loose lower bound.
• Search design ablation: BFS gives 64.4 SR / 79.2 GCR with 180 average search steps; A* gives 78.5 / 88.3 with 112 steps; A* plus LLM action filtering gives 80.0 / 88.4 with 55 steps. The per-episode search budget is 500 steps and the heuristic weight k is set to 3.
• Token cost: per task, TESS-GPT uses 64 LLM calls and 125,315 input / 16,808 output tokens (1+12+51 calls across translation, exploration, search), below Reflexion's 392,201 input tokens over 30 calls and LID's 200,678 input tokens over 57 calls. TESS-Qwen uses 63 calls and 28,333 input / 912 output tokens. Simulation costs about 2k/4k input/output tokens for the whole experiment.
• ALFWorld transfer: TESS-GPT achieves 96.4 success on the seen split and 98.5 on the unseen split, compared with AdaPlanner at 93.6 / 91.8, RAP at 87.1 / 90.3, ReAct at 82.8 / 80.6, Reflexion at 78.6 / 72.4, and Expel at 74.3 / 79.8.

Methodology in Plain English

The team treats planning as a graph search: each node is a possible world state, and two states are connected if one atomic action turns the first into the second. Plain breadth-first search would find a correct plan, but only if the agent can see everything, knows what every action does, and can tell when the task is done. TESS supplies each missing piece with an LLM.

First, a translation module converts the instruction into a set of grounded predicates — simple checks like "the mug is inside the cabinet" — which serve as an automatic stopping condition and as progress counters, avoiding an LLM call at every search step.

Second, an exploration module lets the agent wander only until every object mentioned in those predicates has been seen, then freezes the accumulated scene graph as the starting state. When choosing where to look next, the LLM picks among unexplored containers and rooms using its knowledge of typical household layouts.

Third, a simulation module replaces per-step LLM queries with a compact rule-based world model: because there are only about 40 action types in VirtualHome, the LLM writes one Python function per type describing preconditions and effects (e.g., opening a fridge resembles opening a cabinet), and these functions update the scene graph directly.

Fourth, search is performed with A* using the number of unsatisfied predicates as the distance-to-goal estimate. The action space is trimmed in three stages: only actions involving task-relevant objects are considered, physically infeasible ones are removed via the precondition functions, and the LLM then discards actions that are semantically nonsensical in context. Two instantiations are studied — calling GPT-4.1 series models, or finetuning three separate Qwen3-8B models with LoRA for translation, exploration, and filtering, while keeping the GPT-based simulator because suitable training data for that stage was lacking.

Why This Matters

The work argues that search-based planning, once bootstrapped by LLM priors, can be both more reliable and more interpretable than having an LLM emit a plan directly, and that it can be cheaper in total tokens because each LLM call handles a small, well-scoped subproblem. It also offers a reusable benchmark with automated evaluation for VirtualHome, addressing what the authors describe as a lack of task diversity or of automatic metrics in prior datasets.

Real-world applications:

• Household service robots that must fetch, place, clean, or switch on objects across rooms, where the guarantee that a plan is executable matters more than stylistic fluency.
• Warehouse and logistics picking, where the same fetch-and-place structure appears with many object categories and partially observable storage.
• Assistive technology for elderly or disabled users, translating a spoken instruction into a verified sequence of actions rather than a plausible-sounding guess.
• Simulation-based training and validation of embodied agents, using the generated benchmark's template-based pipeline to create task instances at scale.

Industry relevance: the modular design lets companies swap the LLM (proprietary API or a finetuned 8B open model) independently at each stage, and the token accounting shows the approach can undercut prior LLM-policy methods on cost — important for deploying agents that must run many episodes.

Future Directions

• Add perception and low-level control: the current pipeline abstracts away visual perception and robotic control; the authors point to the Unity-based VirtualHome simulator as the path toward vision-based planning.
• Handle richer instruction types and dynamics: the limitations section notes that temporal constraints, procedural requirements, open-ended instructions, dynamically changing environments, and non-deterministic actions are all unaddressed, and that the method relies on a known action space.
• Detect unsolvable problems: the pipeline cannot explicitly distinguish a task that has no solution from one that is merely hard to search.
• Scale the data: the authors plan to release roughly 100k task instances, extending both training of the finetuned modules and evaluation breadth.

Target Audience

Researchers and graduate students working on embodied AI, LLM-based planning, or the integration of language models with classical planners; robotics engineers evaluating whether search-plus-LLM pipelines are practical for household or warehouse task planning; and benchmark builders interested in the automated VirtualHome data-generation pipeline. Readers should be comfortable with search algorithms and LLM prompting to get the most from the technical sections.

Authors’ abstract

In this work we focus on the problem of embodied task planning, which requires an agent to accomplish a complex task by separating it into atomic actions. Recent studies have developed LLM-based methods to address this problem. However, the executability and correctness of the generated plans remain suboptimal in complex environments and tasks. On the other hand, classical search algorithms have the potential to solve the planning problems perfectly, yet they require fully observable environments, known state transitions and goal state, which are often unattainable in general task domains. Therefore, we propose to implement an LLM-guided search algorithm that makes the search process possible and efficient by incorporating LLMs' commonsense knowledge. Our method leverages LLMs to (1) translate natural language instructions into formatted goal conditions, (2) facilitate efficient exploration in partially observable environments, (3) implement a rule-based world simulator, and (4) prune the space of candidate actions to improve search efficiency. Experimental results on VirtualHome and ALFWorld demonstrate its superior performance.