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.
Figures & tables
Figure 1: A high-level comparison of (a) LLM-based plan generation, (b) LLM-based action policy, and (c) our LLM-guided search pipeline, which first interacts with the environment for exploration (upper part), then generates a plan based on searching in the state and action space (lower part).
Figure 2: A visualization of the four LLM-based modules in our pipeline.
Obs
Seen
Unseen_obj
Unseen_task
SR
GCR
SR
GCR
SR
GCR
ZS
CoT Wei et al. (2022) +ZSP Huang et al. (2022)
full
75.5
86.3
46.0
66.7
73.4
82.5
ReAct Yao et al. (2023)
partial
55.2
69.5
21.7
49.1
53.7
66.0
Reflexion Shinn et al. (2023)
partial
59.0
68.5
36.0
53.6
64.7
71.8
ProgPrompt Singh et al. (2023)
obj
49.9
61.4
24.2
43.6
50.9
59.8
FLTRNN Zhang et al. (2024a)
full
71.9
83.2
47.8
66.2
75.0
84.1
Table 1: Agent performance on the test splits of the proposed VirtualHome benchmark. The metrics are success rate (SR, whether the task is fully completed) and goal conditions recall (GCR, the ratio of completed goal conditions). We classify the compared methods into API-based zero-shot models (ZS) and finetuned open-source models (FT). We also present the type of environment information required by each method, including full (the complete SG as input), partial (partial observation at each step as input), and obj (a list of all objects in the scene).
TESS-GPT
Reflexion
TESS-Qwen
LID
Trans+Exp+Search=Sum
Trans+Exp+Search=Sum
#call
1+12+51=64
30
1+20+42=63
57
#token in
644+4,534+120,137=125,315
392,201
282+9,350+18,701=28,333
200,678
#token out
25+61+16,722=16,808
4,967
18+146+748=912
773
Table 2: Analysis on the average cost of each module for one task instance.
Table 5
Seen
Unseen
ReAct Yao et al. (2023)
82.8
80.6
Reflexion Shinn et al. (2023)
78.6
72.4
AdaPlanner Sun et al. (2023)
93.6
91.8
Expel Zhao et al. (2024)
74.3
79.8
RAP Kagaya et al. (2024)
87.1
90.3
TESS-GPT (Ours)
96.4
98.5
Table 6: Agent performance (success rate) on the seen and unseen splits of ALFWorld.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Task template
Goal conditions
Instruction for an example task instance
clean A
A is CLEAN
“Can you take care of cleaning waterglass-269 for me?”
turn on A and hold
A is SWITCHON;
“Please turn on lighter-451 and keep holding
agent is holding A
it in your hand.”
put A on B on C
A is on B;
“Put plate-363 on table-575, then arrange food_fish-594
B is on C
and food_vegetable-563 to sit on top of plate-363.”
Appendix
Table 7: Examples of the proposed dataset. We first manually define a set of task templates and their corresponding goal conditions. Then we fill the placeholders with proper object categories to get task instances, and use GPT to generate human-like instructions for the tasks. Note that placeholder “A” may be replaced by more than one objects to enhance task complexity.
# act. types
# cond. types
# target obj. types
# apt.
# task types
ActivityProgram Puig et al. (2018)
40
-
196
7
-
LID Li et al. (2022)
7
4
15
1
-
ProgPrompt Singh et al. (2023)
13
-
35
3
-
llm-mcts Zhao et al. (2023)
6
2
37
2
-
LoTa-Bench Choi et al. (2024)
∼ 6
3
16
7
-
Ours
13
11
307
50
25
Appendix
Table 8: Statistics of different benchmarks on VirtualHome.
Figure 9
ACC/SR
#call
# token in
# token out
Translation
0.94
1
639
24
Goal Checking
0.67
10
124,838
36
Appendix
Table 9: Comparison between LLM-based translation and LLM-based goal state checking.
∣A∣
∣Aobj∣
∣Aprecond∣
∣ALLM∣
175,800
83
4
2
Appendix
Table 10: The average size of the filtered action spaces.
Figure 9: Two qualitative examples of the generated plans. Our TESS-GPT agent generates successful plans for both tasks while the CoT+ZSP and ReAct baselines fail. The steps that lead to failures are marked in red.
Figure 10: The example of an exploration-intensive task, where the agent has to find the target blow_dryer before manipulating it. For TESS-GPT, the actions for exploration are marked in blue. For CoT+ZSP, the full SG is provided so the agent can go directly to the closet where the blow_dryer is located. However, it forgets to open the closet before grabbing the blow_dryer. The ReAct agent keeps trying repeated actions without making meaningful progress and never manages to locate the target object throughout the episode. The results suggest that incorporating an explicit exploration process can be beneficial for task planning.
Translation
Simulation
# max search
SR
GCR
GPT-4.1-mini
GPT-4.1
500
80.0
88.4
GT
GPT-4.1
500
82.0
89.7
GT
GT
500
92.5
97.0
GT
GT
∞
100.0
100.0
Appendix
Table 11: Error analysis by replacing the translation/simulation module with the corresponding groundtruth, and enlarging the budget for search steps.
Method
Avg
Pick
Clean
Heat
Cool
Look
Pick2
GPT-4o Tian et al. (2025)
24
44
22
29
27
7
23
TESS
43
71
42
39
62
22
12
Appendix
Table 12: Results on ALFWorld (visual observation).