Tree-Planner: Efficient Close-loop Task Planning with Large Language Models
Authors: Mengkang Hu
Yao Mu
Xinmiao Chelsey Yu
Mingyu Ding
Shiguang Wu
Wenqi Shao
Qiguang Chen
Bin Wang
Yu Qiao
Ping Luo
Venue: ICLR 2024 poster (2024)
Keywords: Embodied Agents
Large Language Models
Task Planning
Primary area: applications to robotics, autonomy, planning

Abstract: This paper studies close-loop task planning, which refers to the process of generating a sequence of skills (a plan) to accomplish a specific goal while adapting the plan based on real-time observations.
Recently, prompting Large Language Models (LLMs) to generate actions iteratively has become a prevalent paradigm due to its superior performance and user-friendliness.
However, this paradigm is plagued by two inefficiencies: high token consumption and redundant error correction, both of which hinder its scalability for large-scale testing and applications.
To address these issues, we propose Tree-Planner, which reframes task planning with LLMs into three distinct phases: 
plan sampling,  action tree construction, and grounded deciding.
Tree-Planner starts by using an LLM to sample a set of potential plans before execution, followed by the aggregation of them to form an action tree.
Finally, the LLM performs a top-down decision-making process on the tree, taking into account real-time environmental information.
Experiments show that Tree-Planner achieves state-of-the-art performance while maintaining high efficiency.
By decomposing LLM queries into a single plan-sampling call and multiple grounded-deciding calls,
a considerable part
of the prompt are less likely to be repeatedly consumed. 
As a result, token consumption is reduced by 92.2\% compared to the previously best-performing model.
Additionally, by enabling backtracking on the action tree as needed, the correction process becomes more flexible, leading to a 40.5\% decrease in error corrections.

Published as a conference paper at ICLR 2024
TREE-PLANNER, EFFICIENT CLOSE-LOOP TASK PLANNING WITH LARGE LANGUAGE MODELS
Mengkang Hu Yao Mu
Xinmiao Yu
Mingyu Ding
Shiguang Wu
Wenqi Shao Qiguang Chen
Bin Wang
Yu Qiao
Ping Luo"
ABSTRACT
This paper studies close-loop task planning, which refers to the process of gener- ating a sequence of skills (a plan) accomplish a specific goal while adapting the plan based on real-time observations. Recently, prompting Large Language Mod- els (L.LMs) to generate actions iteratively has become a prevalent paradigm due its superior performance and user- free-fiienlliness. However, this paradigm is plagued by two inefficiencies: high token consumption and redundant error correction, both of which hinder its scalability for large-scale testing and applications. To address these issues, we propose TREE-PLANNER, which reframes task planning with LLMs into three distinct phases: plan sampling, action tree construction, and grounded deciding. TREE-PLANCE PEEE-PLANNER starts by using an LLM to sample a set of potential plans before execution, followed by the aggregation of them form action tree. Finally, the LLM performs top-down decision-makinn process on the tree, taking into account real-time environmental information. Experiments show that TREE-PLANNER achieves statc-of-the performance while maintain- ing high efficiency. By decomposing LLM queries into single plan- plan-sampling call and multiple grounded-decidee calls, a considerable part of the prompt are less likely be repeatedly consumed. As a result, token consumption reduced by 92.2% compared to the previously best-performing model. Additionally, by en- abling backtracking on the action tree as needed, the correction process becomes more flexible, leading to a 40.5% decrease in error corrections.
INTRODUCTION
Task planning is a significant topic in the field of robotics, where system is tasked with crafting a sequence of mid-level actions (skills) that enable robot to complete complex high-level tasks (Kaelbling & Porez,-Pérez, 201 1). This involves consideration of various fac- tors, such as the capabilities of robots, the surrounding environment, and any constraints uncertainties that might exist. An emerging trend within the field task planning is using Large Language Mod- els (LLMs) to generate actions directly (Huang al., 2022a; Song et al., 2023), rather than searching within a pre-defined domain (Ey- senbach et al., 2019; Xu al., 2019).
Instruction You need to lnd planeer who desempses highleyd...
Global Information You an in hursi thet concats of forrnome behmam. [In-Context Emmples) Observation Curranlly you are sanding the Salleoon...
Task Take sap Plan:
LLMs
As shown in Figure 1, the commonly adopted paradigm for LLM- based planning can be summarized as follows: (i) prompt an LLM to generate one action at time; (ii) execute the generated action and then append the obtained observation ate the next action. We categorize such approaches as ITERATIVE. PLANNER, which enables the model generate subsequent actions in an auto-regressive manner. when errors occur during action execution, existing research en-
Iterative Planner (Multiple Calls)
Figure 1: An overview of
the LLM; and (iii) gener- the traditional paradigm.
Based on ETERAATIV-PLAANEEE deavors either re-generate actions at the current timestep (Raman al., 2022; Guo al., 2023) re-generate the entire plan from the initial timestep (Shinn et al., 2023), referred to as LOCAL REPLAN and GLOBAL REPLAN, respectively.
"Coresponding authors: Mingyu Ding and Ping Luo ([dingmyu, pluo. (h) @ @gom) The University of Hong Kong. Harbin Institute of Technology. O Noah's Ark Laboratory. Shanghai AT Laboratory.

---

Published as a conference paper at ICLR 2024
Plan Sampling (Single Call)
II. Action Tree Construction
Instruction nod asi plasss who docesteescs ligh level... dlobal
Joke
Inttial Obsenation
buthroons...
[In Con-Cot Exomples]
Task: Take
Plan:
[Walk]
[Watk] Seuslo
LLMs
[Walk] Siae-
[Walk]] Staadh
[Lk] Secacli
(Walk) shodnssn?
[Walk]] Steahasee
[Widk] Scoache
[Walk]] chaal
[Wilk] Souach
[Rle) Konseit
[Lie] sied
[Sit] Vonach>
[Cloef
cheds
[Choe] Seariun?
/Sloy!
(Sloxy
/Sleep
(Siapl
(Sieap]
/Sleay)
ITI. Grounded Deciding (Multiple Calls)
Instruction coc cachrmmmen will yousit woth ofarraational conraamentio iooemnnt, wall brghllce beart to and provissis mriviste exb-owke crecuted sobee (t)) Clueenty, you crsttuiligg bedroon.... [Histary]
sub-tsk optionsl pros deto compleetlcc iosootdeooooee based obscrvition...
dharaoer....
Teaki sap
Decósion Request (h) Anocg the fdlavigaccios wlick actios youald [Wald] -hemnom--l (Walk) vzeudko
[nntrrctioo]
[Insrrcctoo) Error Info:
[Observttin](s) (tz)
LLMs
History' You cvocated faz
gresiously choosed actin [[aikk] <caack" carsddan emor "cooacs"" not the ar anviecment.
[Walk] -badnasee
Decision Requerti.)
SMOP
Anong the milowing sctioss which adtinccooilyooae A. (Find] ched-
Obsernaioo
Frovr Ieformatioon
Decision Request (b):
cometteecheree othost A [Walk) -baalowss
[Find]
Figure 2: An overview of our TREE- PLANNER pipeline: (l) prompt an LLM to sample potential plans for "Take nap" before execution; (II) construct an action tree to aggregate sampled plans; (III) prompt the LLM again in closed loops to reason on the action tree. Bottom-left: "[WALK] <bed- room>" is successfully executed. Move
the next level. Bottom-right: "[WALK] <couch>" fails because the absense "couch". Mark the failed node as invalid, then track back and re-decide. The complete prompt and action can be found in Appendix F and Appendix G, respectively.
All methods above have the following two drawbacks: (i) Token Inefficiency: The expenses for a sin- gle LLM call increase proportionally with the number of tokens utilized, including both the prompt tokens and the generated tokens. However, in the scenario of task planning, the prompt tokens often consists of instructions, global information about the environment, in-context learning examples, and environmental observation (Vemprala et al., 2023) while the generated tokens predominantly represent a concise action. The discrepancy in the number of tokens between prompt tokens and generated tokens results in the issue of token inefficiency (Cheng et al., 2023). Moreover, due to the multi-step nature complex task (usually involving 5-20 steps), the prompt tokens incur repeated charges. leading even higher costs. (ii) Correction Inefficiency: LOCAL REPLAN can be viewed as a trial-and-error approach implemented at the execution failed time step, which makes it difficult for the model to detect errors that occurred several time steps earlier. While GLOBAL REPLAN can mitigate this problem by regenerating the entire plan, it may still come at the cost of increased time and token consumption. The token and correction inefficiencies inherent in ITERATIVV-PLANNEE limit its applicability for large-scale inference or frequent use in everyday life.
To address the issues above while maintaining high performance, we propose TREE-PLANNES as illustrated in Figure 2. In general, TREE-PPANNEE divides the queries to an LLM into two parts: single plan-sampling call and multiple grounded-decidigg calls to reduce the repetitive computa- tional cost for several components in prompt tokens. These two stages are bridged using a tree-like structure, which leads to more effective logical correction. More specifically, TREE- PLANNER first prompts the LLM to sample potential task plans with its inherent commonsense (Stage I). Sub- sequently, an action tree is constructed to aggregate the sampled plans (Stage II). Lastly, TREE- PLANNER instructs the LLM again in closed loops to reason on the action tree with the environ- mental observations (Stage III). In terms of token efficiency, TREE-PLANNER only charges once for global information about the environment and in-context examples in plan sampling. However, for SEERAAIVE-PLANNEE this information must be charged at each time step. In terms of correction efficiency, the correction process based the action tree can be seen as an intermediate between
2

---

Published as a conference paper at ICLR 2024
LOCAL REPLAN and GLOBAL REPLAN.
not only reduces the likelihood of re- dundant decision-making at a specific time step through backtracking but also significantly reduces the time and tokens required to generate the entire plan from scratch.
We demonstrate the effectiveness of TREE- PLANNER framework in VirtualHome (Puig et al., 2018), simulated environment for complex household tasks. The experiments are conducted under two different settings: with correction and without correction. In with correction setting, the model is required modify the plan when errors occur, while in without correction setting, the opposite is true. The main result shows that TREE-PLANNEE achieves state-of-the-ar results in both experi- mental settings, surpassing the best baseline models by 1.29% and 3.65% in terms of success rate, respectively. At the same time, TREE-PLANNER PLANNER exhibits high efficiency. In terms of token effi- ciency, PLAANER reduces the token cost of ITERATIVE PI.N by 53.29%. Furthermore, when compared to LOCAL REPLAN and GL.OBAT. REPLAN under the with correction setting, TREE- PLANNER achieves even greater improvement with reductions of 74.36% and 92.24%, respectively. In terms of correction efficiency, and 40.52%, respectively. In further analysis, we formally verify the token efficiency of TREE- PLANNER and derive the critical value of the number of sampled plans required for the model to possess token efficiency. We also perform an ablation study on both plan sampling and grounded de- ciding, demonstrating the effectiveness of the individual components of -LANNL., Finally, we provide a manual error analysis of potential areas for improvement in the model.
SEEE-PL reduces the number of corrections by 37, 37.99%
PRELIMINARY
Task and Motion Planning (TAMP) (Kaelbling & Lozano- Pérez, 2011)in is the process of generating a sequence of actions and robot motions to achieve a desired goal in a given environment. As shown in Figure 2, a high-level task description such as "Take nap" is decomposed into several mid- level actions. We assume the existence of a low-level controller that can execute these mid-level actions, which typically requires training using reinforcement learning (RL. methods or fine-tuning with expert data. Task planning can be categorized into closed-loop task planning and open-loop task planning, Open-loop task planning aims to decompose a high-level task description into mid-level plan without any feedback from the environment. Closed-loop task planning, on the other hand, involves continuously adjusting planning strategies through perception and feedback mechanisms to adapt to environmental changes and uncertaintics during execution. This paper focuses on closed- loop task planning, which is more suitable for task execution in dynamic and complex environments.
We formulate the closed-loop task planning problem as a partially observable Markov decision processes (POMDPs) denoted by (S, O,A, 'T), which is similar to Li et al. (2022a).
Problem Setup
S, O,A are sets of states, observations and actions respectively and T(5++1 1++1/5 |ec az) is a transition model. In POMDP setting, the observation on represents a subset of the underlying state 8t. Let g be the task, the optimal policy π <aeegg he, 0²) must take into account not only the current observation ot, but also the entire history of actions h4 {ai...... a--1).
3 MODEL
3.1 PLAN SAMPLING
Abstract specifications often restrict task planning. Take the "Take nap" task as an example, the robot needs to understand that napping can be done on a bed, and the bed is typically located in a bedroom. Many works hold the belief that LLMs trained on large-scale data encode commonsense knowledge about the real-world (Davison et al., 2019; Li et al., 2022b; Bian et al., 2023). Recently, several studies have investigated the integration of LLMS into task planning, which aims to address language ambiguities and provide robots with background knowledge (Huang et al., 2022a; Li et al., 2022a; Ahn et al., 2022). In contrast to these approaches, which typically use LLMs directly as policies,
prompts an LLM to generate prospective task plans before executing them in specific environment. We consider this as a way to extract commonsense knowledge from LLM through sampling, which serves as prior knowledge for task planning. Let Pps be the prompt for plan sampling, g be the task name, the process of plan sampling can be formalized as: LLM(pps:9) 9) (C1, C2; .2 ). where N is hyper-parameter which determines the number of sampled
3

---

Published as a conference paper at ICLR 2024
plans. Each plan candidate c; is sequence of actions, i.e., C, {aalt 1, ...... m(i)) m(i) is the number of actions in plan and ag is the action of plan at time step t. The prompt consists of four parts: instruction, global information, initial observation, and in-context examples. The instruction provides the L.M with a clear and concise explanation of the process of task planning. The global information provides the LLM with background knowledge about the environment and available action space. The initial observation provides the LLM with an initial snapshot at the starting point of the task. The in-context examples are additional task plans that serve to indicate the format of the output plan and have also been proven to be helpful in enhancing performance (Brown et al., 2020). In Section 5.2, we provide a quantitive analysis of the upper-bound on plan sampling.
3.2 ACTION TREE CONSTRUCTION
Sam Prefir
(Walk]
[Waik] Aestmoees
[Walk] Sonach
[Walk]
[Walk]
[Walli] cooell
<hebrose
(Walk] chat-
(Walk) chets
[Rle] rosseis
[Sa] Sonsck
[Watk] thort
[Lab Souedks
[Sii] Sccasel
[Lkd
[Bi] sike!
(looed Sabert
[Tle] Sonols
[Lie]
[Si Sibelt
[Choel
[Choe]]
[T Senarkk
[Skep]
|leepi
[Sterpl
[Slpp]
[Skeep]
Sompled Plans
Tree
The process of constructing the action tree. Left: each path represents sampled plan. Right: plans with the same prefix are aggregated together. Note that although certain paths have the same action ([Sleep)), they are not aggregated together due inconsistent prefixes.
Figure 3:
To select an optimal plan from potential plans, an obvious approach would to execute and test each plan in the environment. However, this approach has two drawbacks: (i) It is time-consuming to execute multiple plans in the environment; (ii) Different plans may have overlapping parts, so repeating the execution of these overlapping parts in the environment is redundant. For example, in plan I and plan 2 shown in Figure 2, the first step in both plans is: "[Walk] <hedroom>", designed a structured representation that aggregates the sampled
Based on the previous analysis, potential plans called Action Tree. As is shown in Figure 3. when two plans share a common prefix but differ in their actions specific time step, their shared prefix is aggregated into a single branch, while their differing actions form divergent paths. This process repeats iteratively until all sampled plans are organized into a complete tree structure. The motivation behind is convert the filtering of the plan level into search at the action level, thereby reducing the execution time in the environment. an action tree with root node r can be formalized as T(c) (V, E), where V and E represent the sets of nodes and edges respectively. Each node v is associated with an action a, and a time step byp i.e., v = (av, (v)). Each edge e represents pair of adjacent actions plan c; i.e., E = {e(v1, 12) U1. U2 E V, 2 (a,,, t), 12 (0.(++1), t 1)]. The root node is not associated with any specific action, and its child nodes are the set of nodes obtained by aggregating the first action of each plan. The construction process of the action tree is presented in Algorithm 1.
3.3 GROUNDED DECIDING
During grounded deciding, an LLM functions as the policy T he, 0z). However, instead of sampling from the entire corpus of LLMs the ITERATIVE-PLANNER, we limit the choices few child nodes of the current node at time / on the action tree. This process simulates the decision- making process of humans, who first propose several action options and then combine their current real-world observations to make decisions. Specifically, we provide an LLM with instruction, ob- servation, and history (the previously executed actions) as prompts, and then the LLM chooses one from the child nodes of the current node. Furthermore, we also designed corresponding error correction method. When chosen action fails to execute the environment, TREE-PLANNE marks the nodes on the subtree rooted at the failed node invalid nodes; (ii) traces back on the action tree to find the previous valid fork node with available valid child nodes. all the child nodes of particular node are invalid, then the fork node should also be marked invalid. (iii) executes the inverse process of previously executed actions (c.g., the inverse of [SwitchOn]] is [SwitchOfff) to recover the state of the agent; (iv) re-decides at the fork node. Error correction with grounded
(i)
4

---

Published as a conference paper at ICLR 2024
Algorithm 1: Action Tree Construction
Input c
Output: r
Function ConstructactionT:oo. (c, r): forall Gi co
6 for t mi) do en <- GetChildNode((,, ea);
if en is None then
< CreateChidNNde((a.)) AddChildNode(1, en):
end end 12 end
11
deciding is more effective than the commonly adopted methods presented in Section 1. This is be- cause the action tree serves as an important prior completing the current task. Therefore, when an сггог occurs at a node on the tree, it is possible to selectively backtrack on the action tree, thus alleviating repetitive decisions correction on the action tree also relieves the need to return to the initial time step as in GLOBAL REPLAN, thereby reducing time and token consumption. The process described above is displayed in Figure 4. Quantitive analysis of the effectiveness of error correction is presented in Section 5.3,
particular time step as in LOCAL REPLAN. Performing error
(a) Error Correction
(b) Successful Execution
Legend
Execation
Evecuted Palk
Trnccbock Park
Rost Node
X
Lease Nade
Deprecated Park
Node
Figure 4: An overview of the process of grounded deciding. Left: When an error occurs, TREE- PLANNER tracks back and marks the nodes along the way invalid. Afterward, makes a new decision at the previous fork node. Right: After the action is successfully executed, makes decision the current node, and then the agent moves the next level.
4
EXPERIMENTAL RESULTS
4.1 EXPERIMENTAL SETUP
Environment. We conduct the experiments in the VirtualHome (VH) Environment (Puig et al., 2018), simulation platform for household tasks. Each scene in every VH environment contains hundreds of objects. These objects may possess individual properties, and there may also be rela- tionships between different objects. There are 28 different action types VH, which are listed in Appendix A. 1. The task-relevant goal conditions refer to set of specific states of objects predi- cates between objects. For example, a goal condition for Turn on TV would be On(TV), while goal condition for Sit would be Onf character, chair).
Dataset. We constructed a dataset consisting of 4 VH scenes and 35 unique VH tasks. Each task includes task name, goal conditions, and gold plan. We started by annotating goal conditions for each task from ActivinyProgranss knowledge base by Puig et al. (2018) via executing the programs. And then, applied simple heuristics to filter the low-quality annotations in the dataset: (i) the length of the plan is less than 3; (ii) the execution of the program fails. To highlight the necessity of grounding L.LMs in the real environment which has variation in the objects and preconditions,
5

---

Published as a conference paper at ICLR 2024
replicated the annotation above process across 4 distinct scenes provided in VirtualHome, ultimately yielding 71 annotated tasks. We denote the distinct scenes as EN 2, 3,344, 4). Then, we hired two CS CS-majored graduate students to conduct manual quality control to ensure that the task descriptions were in line with their corresponding goal conditions and programs. We eliminate cases that do not meet the alignment criteria were originally annotated with errors, resulting in a high-quality dataset comprising 35 tasks. To double-check the quality of the dataset, we also study the agreement between annotators. The results indicated "almost perfect agreement" with Fleiss Kappa (Landis & Koch, 1977) scores of 0.88.
Evaluation Metrics. We use four metries to evaluate the performance of different methods: exe- cutability (ExEc.), success rate (SR). goal conditions recall (GCR), and the financial expenditure for evaluation (SCOST). EXEC. refers to whether the plan can be executed in the given environ- ment, regardless of its relevance to the task. GCR is calculated by taking the difference between the ground truth goal conditions and the goal conditions that were achieved with the generated plan and then dividing this difference by the total number of goal conditions. SR measures whether all goal conditions are fulfilled, i.e., SR = only when GCR = 1. SCOST is used to evaluate the to- ken efficiency of different methods, which is calculated based the pricing provided by OpenAL.' For evaluation with error correction, we use NO.EC to represent the number of error corrections of each method. No.EC does not directly measure performance but rather evaluates how effectively different models can correct errors.
Baselines. For experiments without error correction, we compare our method to two strong pub- lished LLM-based task planning methods with OpenAl APIs, including: (i) ZERO-SHOT PLAN- NER (Huang al., 2022a); (ii) PROGPROMPT (Singh et al., 2022). Furthermore, we also implement the (TERATIVE-PLANNED method discussed in Section I as a baseline model. For experiments with error correction, we enhance the ITERATIVE- PLANNER -ERAATIVE-PLANNER method with the two re- re-planning methods: LOCAL REPLAN and GLOBAL REPLAN, and consider them as the baseline models. More imple- mentation details and an introduction to each baseline model can be found in Appendix B.2.
Implementation Details. We use the OpenAl GPT-3.5 (text-davinci-003) API 2 model as a LLM backbone in our experiments for all evaluated methods. The cost of this model 0.02S per 1000 tokens. The prompt for TREE-PLANNES and ITERATIVE-PLANNER was designed with the prin- ciples proposed in Vemprala et al. (2023), and examples can be found in Appendix F. We take representative tasks from the dataset in-context learning exemplars and the rest the validation set. The examples are fixed to be: "Watch TV", "Turn on light", "Go to sleep", " and "Brush teeth". To sample diverse plans, we applied a temperature of 0.8 and a top-p value of 0.95. We heuristically set the number of samplings N E (25.50) 50}. During grounded deciding, we set the temperature to 20. Additionally, we utilize majority vote to obtain the final option in order to alleviate format errors in the output of LLMs. The maximum number of error corrections is set to 10 for all evaluated approaches.
0.7, top-p to 1. 1.0, and sampling parameter
4.2 MAIN RESULTS
Based on the results presented in Table 1, several advantages of TREE-PLANNER can be derived: (i) TREE-PLANNER outperforms listed baseline systems, surpassing the previous state-of-the-art by absolute 1 11.2% and 7.04% on Executability, 6.71% and 7.29% on GCR and 1. 1.29% and 3.65% on SR under both experimental settings respectively. This experimental observation demonstrates that reframing the LLM- planning pipeline does not compromise its performance. (ii) TREE- PLANNER has significant advantage in token efficiency. In without correction setting, TREE- PLANNER reduces the cost of SERRAAIVE-PLANNEE by 53.29%. In with correction setting, the token cost is further reduced by 74.36% and 92.24%, respectively, compared to LOCAL REPLAN and GLOBAL REPLAN. (iii) TREE-PLAS PLANNER also demonstrates high correction efficiency, resulting in reduction of the number of action-retry times for LOCAL REPLAN and GLOBAL REPLAN by 37.99% and 40.52%, respectively. A reduced amount of conrections also contributes to a decrease in token consumption.
Note that, while not having a token efficiency advantage compared to ZERO-SHOT PLANNER and PROGPROMPT, TREE-PPLANNER significantly outperforms these methods in terms of performance
hhttps://opena comm

---

Published as a conference paper at ICLR 2024
Table I: Performance of different methods on Virtual Home. w/o correction means that during the plan execution, there is no allowance for retrying failed actions. While with correction implies the opposite. The reported evaluation metries are the average of 3 independent runs across the scenes.
EXEC. t
SR f
GCR f
SCOST +
No.EC 1
w/o correction
ZERO-SHOT PLANNER
16.49+3.08
0.07
0.52=0075
1.36
N/A
PROGPROMPT
35.04
12.54+2.20
19.99-42.83
1.25
N/A
ITERATIVE-LLANNER PLANNER
44.54-1.099
27.04=4.65
33.25::532
5.1210.14
N/A
PREE-PLANNER
55.74
28.33+1.118
39.96:1.116
2.3910.44
N/A
PEAE-PLANNERN-O.
49.01=5..67
28.14+2.445
35.84+4.20
3.48
N/A
with correction
LOCAL REPLAN
79.66.2..33
37.46=1.71
01.9
12.88
3.29:00.6
GLOBAL REPLAN
1..0
37.93=11222
52.4610.86
02.59
0.43
89.1310.17
35.30
56.65+1.09
3.30
1.85+0.05
TREE-PLANNER
88.26+2.44
41.58+3.20
59.55
0.54
2.04
by 27.26% and 15.79% on SR respectively. is also worth noting that increasing the hyper- parameter N does not result in consistently improved performance. This experimental phenomenon will be further discussed in Section 5.2.
5 ANALYSIS
5.1 TOKEN EFFICIENCY
In Section 4.2, the quantitative analysis has demonstrated that TREE-PLANNES consumes fewer tokens compared to mulation to demonstrate this point. The number of tokens required for an LLM API call typically includes two parts: prompl tokens and generaled tokens. Let and yp represent the prompt tokens and generated tokens. Let ps, gd, ip stand for plan sampling, grounded deciding, and ITERATIVE: PLANNER, respectively. Normally, we have Pip R Pps + Pgd. That is because, as shown in Figure and Figure 1, the prompt for plan sampling typically includes global information and in-context examples, while the prompt for grounded deciding includes observation and history. These types of information usually need the number of tokens for each action type |a| is the same and the total number of steps M is the same for each generated plan. The hyper-paramett number of sampling is N for plan sampling and grounded decoding and is 1 for STERATIVE-PLAN
In this section, we will further provide a specific for-
included in every step of ITERATIVE- PLANNER. Assuming that
Based on the given information, we have Pps = MM]aa, Pgd = N and Pip = |a|. The consumed tokens Hours and Pip can calculated as follows: Mours Pps + 9ps + M1 (Pyd Pga) and Map = M (Pip + PPp)). Based the above formula, we can determine the boundary conditions for that satisfy the inequality Pours < Mip as aa
I+1/|a| Tal |al+1- And we have Pps >> |a), since the prompt of plan sampling may contain thousands of tokens and action only contains few tokens. We use the average number of tokens for all action types to estimate |al and the average length of all gold plans to estimate M. As result, we obtain the critical value of N in our experiment as follows: N < 197.72. Detailed derivation can be found in Appendix D. In conclusion, our model exhibits remarkably high token efficiency, especially scenarios where not particularly high.
follows: N 1-1/M
5.2 PLAN SAMPLING
Since grounded deciding fundamentally involves selecting from the sampled plans, the upper limit of our TTREE-PLAANE
determined by plan sampling. We propose two additional metries study the upper limit of plan sampling: (i) the maximum GCR for all generated plans, i.c., GC..maz (c)
N max(GG((c:);; (ii) the average GCR for all generated plans, i.e., GC (c) = ΣN EN, (GCR()))
i=1
GCR represents the upper limit of the performance of PREE-PLANNER, In other words, the model can only succeed if there a "correct" plan among the sampled plans. GC Rang reflects the proportion of "correct" plans to sampled plans. When GC Ravg is low, it undoubtedly poses greater

---

Published as a conference paper at ICLR 2024
EXEC.
SR
GCR
74077
w/o correction
55.74
28.33
38.96
GCR GCR
with oracle t
7.16
9.84
8.5
60
TREE-PLANNER PLANNERN=50
49.01
28.14
35.84
i with oracle 1
3.41
6.54
4.78
with correction
43005
TREE-PLA SHEE-PLANNER--1
89.13
35.3
56.65
with oracle
8.45
26.8
19.76
PREE-PLANNER
88.26
41.58
59.55
with oracle
6.9
10.57
7.47
Figure 5: Maximum and average GCR for all sampled plans. The x-axis of the anno- tated coordinate points represents the cho- sen N for the main experiments.
Table 2:
Ablation study grounded deciding. i represents the performance improvement after adding gold plan to action tree construction.
challenges for grounded deciding. Some conclusions can be drawn from Figure 5: (i) The maximum value GCRmmas being 81.2% indicates that plan sampling is effective. (ii) As N increases, there noticeable increase in GCRmaaz but it eventually reaches threshold. Therefore, large value of N will lead to increased token consumption without necessarily improving the performance limit. When applying PREE-PLANNER it is essential choose an appropriate value of N that balances token assumption and model performance. (iii) GCReeg does not consistently increase with an increased N. This implies that as N becomes larger, the proportion of "correer" plans sampled plans may not necessarily increase.
5.3 GROUNDED DECIDING
To investigate the effectiveness of grounded deciding, we conducted ablation experiments. We in- corporated gold plan for each task into construction of the action tree. As is shown in Table 2, after incorporating the gold plan, there was significant improvement in performance. Ad- ditionally, there was also a decrease in the number of eтror corrections. For TREE- PLANNER =225 the number decreased from 1.85 to 1.21, and for PRLEE-LANNER 1.39. The quantitive experimental results presented above demonstrate the effectiveness of grounded deciding. Another noteworthy experimental phenomenon is that the improvement in performance for TREE-PLANNER, 25 was greater than that for TREE-PLANNER N=50- This further validates the conclusion we drew Section 5.2: when the number of plans increases, but the proportion of correct plans decreases, the performance may be negatively impacted.
decreased from 2.04 to
5.4 ERROR ANALYSIS
We categorize error types into two distinct classifications: (i) Missing Correct Plan; (ii) Grounded Deciding Error. As is listed in Table the majority of errors are attributed the missing correct plans (54.5%). Therefore, despite the ability of plan sampling to achieve relatively high GC GC'Rmas Rmax as discussed Section 5.2, it still serves as a bottleneck for our model some extent. Furthermore, considerable portion of the errors occurred due to mistakes made by LLM during grounded deciding (45.5%). We also provide a qualitative analysis of each error type in Appendix E.
Table Distribution of error types the TRBE-PLANNER,A w/o correction model.
Error Type
Explanation
Proportion (%)
Missing Correct Plans
Plan sampling did not yield correct plans Misunderstandings actions objects
54.5%
Environment Misunderstanding
18.2%
Incomplete Plan
The absence essential steps
18.2%
Illogical Error
The generated plan is logically incorrect Execution failed but semantically correct Execution ervor during grounded deciding
13.6%
Semantically Correct
9.1%
Grounded Deciding Error
45.5%
Incorrect Deciding
Incorrect decisions specific nodes Execution failed but semantically correct
31.8%
Semantically Correct
13.7%
8

---

Published as a conference paper at ICLR 2024
6
RELATED WORKS
Task Planning with Large Language Models. We categorize the mainstream methods in the task planning domain into two groups: search- based methods (Jiang et al., 2018; Garrett et al., 2018) and generate-based methods (Song et al., 2023; Wu et al., 2023a; Ding et al.. 2023; Mu et al., 2023). L.MMs trained on large-scale corpus contain a vast amount of commonsense knowledge for task planning (Pallagani et al., 2023; Sun et al., 2023b;a). Thanks to this advancement, generate-based methods have gradually become hot topic of research in recent years. When considering the utilization of LLM, some works directly generate the entire plan without executing in the environ- ment (Singh al., 2022; Liang al., 2023; Wu et al., 2023b; Zeng et al., 2023; Lin al., 2023b; Yang et al., 2023). While these models possess token efficiency, they are unable to modify the plan when encountering emrors dynamically. Another line of works has adopted the paradigm presented in Section to generate actions iteratively (Vemprala et al., 2023; Yao et al., 2022; Huang et al., 2022a;b; Shinn et al., 2023), which is more flexible for error correction, human interaction and the grounding of environment. Works like Carta et al. (2023); Huang et al. (2023); Ahn et al. (2022) in- volve the use of implicit representations of LLM. In contrast these works, our study concentrates on Black-box LLMs, which are utilized in a manner more frequently by researchers and industry, as they provide only input and output without any additional information.
Tree-based Modeling for the Output of Large Language Models. Yao et al. (2023); Long (2023) both propose an alternative for chain-of-thought, called trre-offthouuhtt.. for problem-solving. These studies do not involve the interaction between inner steps in the tree and the environment but rather focus on reasoning tasks. Considering the robotic area, Cao & Lee (2023) leverages LLMs for automatic sataviorrttre-basee task generation. Zhao et al. (2023); Hao et al. (2023) propose using an LLM as a world model to assist planning algorithms such as Monte Carlo Tree Search (MCTS). However, TREE- PLANNER samples diverse paths once and aggregates the paths into action tree rather than requiring multiple calls to LLM like the aforementioned studies. This approach offers advantages in terms of both run-time efficiency and token efficiency.
Generate then Select. From another perspective, grounded deciding selects a prediction from the follows the paradigm of generate then select,
sampled potential plans. Hence, TREE-PLANNE which is commonly adopted to optimize the output of LLMs. Some models (Glass et al., 2022; Suzgun al., 2022; Wang et al., 2023b; Gu et al., 2023) use external controllers re-rank the generations. In Wang et al. (2023a), the best answer is selected from multiple generations of an LLM through a majority vote. Logeswaran al. (2022) proposes to incorporate the state information from the environment to re-rank the generated plans. Unlike these works, instead of selecting at the level of entire generation, we use action trees to perform more fine-grained selection (action-level).
Efficient Inference with Large Language Models. Most previous works suggest modifying the architecture of transformer or decoding strategy to achieve efficient inference (Wang et al., 2020; Katharopoulos et al., 2020; Leviathan et al., 2023; Chen et al., 2023). Cheng et al. (2023) pro- pose a batch prompting method to reduce the frequency of invoking LLMs. Lin et al. (2023a) achieve efficient inference with LLMs by incorporating small LM fine- munet oracle trajectories. TREE- PLEEN-L differs from previous studies by simply reframing the process of LLM planning to alleviate repeated token consumption without the need for additional training.
CONCLUSION
In this paper, we have introduced TREE-PLANNER, a novel framework for task planning with LLMs. The motivation behind TREE-PLANNER is address the inefficiencies of the commonly adopted paradigm while still achieving high performance. Through extensive experiments in the Virtull- Home environment, we have demonstrated that TREE-PLANNER outperforms other strong baselines and achieves state-of-the-a performance. We have also shown that our framework is highly effi- cient in terms of token consumption and error correction. To gain a deeper understanding of our framework, we have conducted several studies analyzing its performance gains and identifying po- tential bottlenecks. Furthermore, we have performed a qualitative error analysis to identify areas where the model may fail. Overall, we believe that TREE-PLANCE PLANNER represents a new paradigm for LLM-based task planning that strikes a balance between efficiency and performance. We hope that work will inspire further research and the development of more efficient task-planning methods.

---

Published as a conference paper at ICLR 2024
8 ETHICS STATEMENTS
We build the dataset based on the ActivityPrograms knowledge base by Puig et al. (2018), which under the MIT license. Our approach has no ethical or social issues on its own, except those inherited from large language models.
ACKNOWLEDGMENTS
This paper is partially supported by the National Key R&D Program of China No. No.20222D0011000 and the General Research Fund of Hong Kong 1720062.
REFERENCES
Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Daniel Ho, Jasmine Hsu, Julian Ibarz, Brian Ichter, Alex Irpan. Eric Jang. Rosario Jauregui Ruano, Kyle Jeffrey, Sally Jesmonth, Nikhil J Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Kuang-Huei Lee, Sergey Levine, Yao Lu, Linda Luu, Carolina Parada, Peter Pastor, Jornell Quiambao, Kanishka Rao, Jarek Rettinghouse, Diego Reyes, Pierre Sermanet, Nicolas Sievers, Clayton Tan, Alexander Toshev, Vincent Vanhoucke, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Mengyuan Yan, and Andy Zeng. Do i can, not i say: Grounding language in robotic affordances, 2022. 3,9
Ning Bian, Xianpei Han, Le Sun, Hongyu Lin, Yaojie Lu, and Ben He. Chatgpt is knowledgeable but inexperienced solver: An investigation of commonsense problem in large language models, 2023. 3
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler. Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020. 4
Yue Cao and C. S. George Lee. Robot behavior-tree-basek task generation with large language models, 2023. 9
Thomas Carta, Clément Romac, Thomas Wolf, Sylvain Lamprier, Olivier Sigaud, and Pierre Yves Oudeyer. Grounding large language models in interactive environments with online reinforcement learning, 2023. 9
Charlie Chen, Sehastian Borgeaud, Geoffrey Irving, Lean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling, 2023.
Zhoujun Cheng. Jungo Kasai, and Tao Yu. Batch prompting: Efficient inference with large language model apis, 2023. 2, 9
Joe Davison, Joshua Feldman, and Alexander Rush. Commonsense knowledge mining from pre- trained models. In Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 1173-1178, Hong Kong, China, November 2019, Association for Com- putational Linguistics. doi: 10.18653/v1DD1--11000 URL hetpss//aclantholle org
b19-1109.
Yan Ding, Xiaohan Zhang, Chris Paxton, and Shiqi Zhang. Task and motion planning with large language models for object rearrangement, 2023.
Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridg- ing planning and reinforcement learning. arXiv: Artificial Intelligence, Artificial Intelli- gence, Jun 2019.
10

---

Published as a conference paper at ICLR 2024
CaelanReed Garrett, Tomás Lozano-Péree and LesliePack Kaelbling. PddIstream: Integrating sym- bolic planners and blackbox samplers via optimistic adaptive planning. arXiv: Artificial Intelli- gence,arXiv: Artificial Intelligence, Feb 2018. 9
Michael Glass, Gaetano Rossiello, Md Faisal Mahbub Chowdhury, Ankita Rajaram Naik, Pengshan Cai, and Alfio Gliozzo. Re2g: Retrieve, rerank, generate, 2022. 9
Yu Gu, Xiang Deng, and Yu Su. Don't generate, discriminate: A proposal for grounding language models to real-world environments, 2023.
Yanjiang Guo, Yen-Jen Wang, Lihan Zha, Zheyuan Jiang, and Jianyu Chen. Doremi: Grounding language model by detecting and recovering from plan-execution misalignment, 2023.
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305. 2023. 9
Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. Language models as zero- shot planners: Extracting actionable knowledge for embodied agents. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 1148-914. PMLR, 2022a. URL https: /ttp://prrco http///ccceeeenggg///ee/ mlr. wwwps/eeevvveee. 62 22//6///uuuua http/hhang2aaaaaaa html. 1, 6,
Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, Pierre Sermanet, Noah Brown, Tomas Jackson, Linda Luu, Sergey Levine, Karol Hausman, and Brian Ichter. Inner monologue: Embodied reasoning through planning with language models, 2022b. 9
Wenlong Huang, Fei Xia, Dhruv Shah, Danny Driess, Andy Zeng, Yao Lu, Pete Florence, Igor Mordatch, Sergey Levine, Karol Hausman, and Brian Ichter. Grounded decoding: Guiding text generation with grounded models for robot control, 2023. 9
Yuqian Jiang, Shiqi Zhang, Piyush Khandelwal, and Peter Stone. Task planning in robotics: empirical comparison of pddl-based and asp-based systems. Coreell University arXiv, University arXiv, Apr 2018.
Leslie Pack Kaelbling and Tomás Lozano-Pérez. Hierarchical task and motion planning the now. In 2011 / IEEE International Conference on Robotics and Automation, pp. 1470-1477, 2011. doi: 1099/./// 1.590091.. 1,3
Angelos Katharopoulos, Apoory Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns:: Fast autoregressive transformers with linear attention, 2020. 9
Richard Landis and Gary G. Koch. The measurement of observer agreement for categorical data. Biometrics, 33(1):159-111)) 174, 1977. ISSN 0006341X, 15410420, HtL:ttt::/wwer jstor. org/ stable/
Yaniv Leviathan, Matan Kalman, and Yossi Matias, Fast inference from transformers via speculative decoding. 2023. 9
Shuang Li, Xavier Puig, Chris Paxton, Yilun Du, Clinton Wang. Linxi Fan, Tao Chen, De-An Huang, Ekin Akyürek, Anima Anandkumar, Jacob Andreas, Igor Mordatch, Antonio Torralba, and Yuke Zhu. Pre-trained language models for interactive recision-making, In Alice H. Oh, Alekh Agar- wal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022a. URL https: /ttp://///e..ee...ee/m net/ forum? Pd a. 3,
Xiang Lorraine Li, Adhiguna Kuncoro, Jordan Hoffmmann, Cyprien de Masson d' Autume, Phil Blun- som, and Aida Nematzadeh. A systematic investigation of commonsense knowledge in large language models. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 11838-1 1838-11855, Abu Dhabi, United Arab Emirates, December 2022b. Association for Computational Linguistics. doi: 10.18653/v wog.oloyoyooooooooooooooooo .er22..mmllpmm emnlp-mat ht.pppaman..................1
main.812. URL

---

Published as a conference paper at ICLR 2024
Jacky Liang, Wenlong Huang, Fei Xia, Peng Xu, Karol Hausman, Brian Ichter, Pete Florence, and Andy Zeng. Code as policies: Language model programs for embodied control, 2023.
Bill Yuchen Lin, Yicheng Fu, Karina Yang, Prithviraj Ammanabrolu, Faeze Brahman, Shiyu Huang, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. Swiftsage: A generative agent with fast and slow thinking for complex interactive tasks, 2023a. 9
Bill Yuchen Lin, Chengsong Huang, Qian Liu, Wenda Gu, Sam Sommerer, and Xiang Ren. On grounded planning for embodied tasks with language models. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 37, pp. 13192-13200, 2023b. 9
Lajanugen Logeswaran, Yao Fu, Moontae Lee, and Honglak Lee. Few-shot subgoal planning with language models. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 1493-5506, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10.18653/v1/ 20222.aacl-- Saaallmmain4422 URL ht : / anthe org 2022. naacl -main a......0 402.
Jieyi Long. Large language model guided tree-of-thoughe 2023, 9
Yao Mu, Qinglong Zhang, Mengkang Hu, Wenhai Wang, Mingyu Ding, Jun Jin, Bin Wang, Jifeng Dai, Yu Qiao, and Ping Luo. Embodiedgpt: Vision-language pre-training via embodied chain of thought, 2023. 9
Vishal Pallagani. Bharath Muppasani, Keerthiram Murugesan, Francesca Rossi, Biplav Srivastava, Lior Horesh, Francesco Fabiano, and Andrea Loreggia. Understanding the capabilities of large language models for automated planning. arXiv preprint vrxiv:2305.16151, 2023.
Xavier Puig, Kevin Ra, Marko Boben, Jiaman Li, Tingwu Wang, Sanja Fidler, and Antonio Tor- ralba. Virtualhome: Simulating household activities via programs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018. 3, 5, 10, 14
Shreyas Sundara Raman, Vanya Cohen, Eric Rosen, Ifrah Idrees, David Paulius, and Stefanie Tellex. Planning with large language models via corrective re-prompting. CoRR, abs/2211 1.99955, 2022. doi: 10.48550/arxiv.22111.. 11.09555. URL https: //doi. http://t..oog//////// 48550/8550//0 /a..5//axxiv..v 2211 09935.
Noah Shinn, Beck Labash, and Ashwin Gopinath. Reflexion; autonomous agent with dynamic memory and self-reftection. arXiv preprint arXiv:2303.11366 2023. 1,
Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. Progprompt: Generating situated robot task plans using large language models, 2022. 6, 9, 15
Chan Hee Song, Jiaman Wu, Clayton Washington, Brian M. Sadler, Wei-Lun Chao, and Yu Su. Llm- planner: Few-shot grounded planning for embodied agents with large language models, 2023. 1,
Haotian Sun, Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang. Adaplanner: Adaptive planning from feedback with language models. arXiv preprint arXiv:2305. /6653, 2023a. 9
Simeng Sun, Yang Liu, Shuohang Wang, Chenguang Zhu, and Mohit Tyyer. Pearl: Prompt- ing large language models to plan and execute actions over long documents. arXiv preprint ar0iv:2305. 14564, 2023b.
Mirac Suzgun, Luke Melas Kyrrizz,,, and Dan Jurafsky. Prompt-and-rerank method for zero-shot and sew-shot arbitrary textual style transfer with small language models. In arXiv, 2022. 9
Sai Vemprala, Rogerio Bonatti, Arthur Bucker, and Ashish Kapoor. Chatgpt for robotics: Design principles and model abilities. Microsoft Autonomous Systems and Robotics Research, 2023. 2, 6,
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity, 2020.
12

---

Published as a conference paper at ICLR 2024
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain thought reasoning in language models. In The Eleventh International Conference Learning Representations, 2023a. URL petps://cpenreee ew. net. forum?id-li 1 IMMr
Zihao Wang, Shaofei Cai, Anji Liu, Xiaojian Ma, and Yitao Liang. Describe, explain, plan and select: Interactive planning with large language models enables open-world multi-task agents, 2023b.
Yue Wu, So Yeon Min, Yonatan Bisk, Ruslan Salakhutdinov, Amos Azaria, Yuanzhi Li, Tom Mitchell, and Shrimai Prabhumoye. Plan, eliminate, and track language models are good teach- for embodied agents, 2023a. 9
Zhenyu Wu, Ziwei Wang, Xiuwei Xu, Jiwen Lu, and Haibin Yan. Embodied task planning with
large language models, 2023b. 9
Danfei Xu, Roberto Martín-Martín, De-An Huang, Yuke Zhu, Silvio Savarese, and Li Fei-Fei. Re- gression planning networks. arXiv: Artificial Intelligence,a arxivv Artificial Intelligence, Sep 2019.
Sherry Yang. Ofir Nachum, Yilun Du, Jason Wei, Picter Abbeel, and Dale Schuurmans. Foundation models for decision making: Problems, methods, and opportunities, 2023. 9
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint 10X0v:2210.03629, 2022. 9
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models, 2023.
Andy Zeng, Maria Autarian, brian ichter, Krzysztof Marcin Choromanski, Adrian Wong, Stefan Welker, Federico Tombari, Aveek Purohit, Michael S Ryoo, Vikas Sindhwani, Johnny Lee, Vin- cent Vanhoucke, and Pete Florence. Socratic models: Composing zero-shot multimodal reason- ing with language. In The Eleventh International Conference on Learning Representations, 2023. URL https: openrevii ew. net/ f forum? d=G2g2Mh3avo..
Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models as commonsense knowledge for large-scale task planning, 2023,
13

---

Published as a conference paper at ICLR 2024
Appendix
A ENVIRONMENT
A.1 ACTION SPACE
The action types in the Virtual Home Environment are listed as follows:
1. Sleep
8. Wipe
15. Touch
22. Drop
2. StandUp
9. Pull
16. Open
23. Lie
3. Wp
10. Push
17. Close
24. SwitchOn
4. Walk
11. Pour
18. Run
25. SwitchOff
5. Find
12. TurnTo
19. Sit
26. Drink
6. Grab
13. PointAt
20. Read
27. Putln
7. Wash
14. Watch
21. PutOn
28. PutBack
10
5.5
12.5
20.0
Length
Figure 6: Distribution of plan length.
A.2 PARTIAL OBSERVATION
We implemented partial observation based on Li et al. (2022a). The official definition of partial observation that when the agent situated in room, its observation consists of all the objects in the room that are not located inside enclosed objects. For instance, if an apple is placed inside closed refrigerator, will not appear the observation the agent.
A.3 OBSERVATION REPRESENTATION
In the VirtualHome Environment (Puig et al., 2018), observations primarily consist of two compo- nents: object states and inter-object relationships. The object states describes the state in which an object exists. For example, the state of television can either be "on" or "off", i.e., "On(TV)" or "Of""TV"" The inter-object relationships are represented using predicates to express the relation- ships between objects. For example, when character is in close proximity to television, there may be a predicate such as: "Chose(character; TVJ". We convert the observations from VH into English sentences using rule-based approach. For example, the predicate chhaseechrracter TV)" transformed into "character is close to TV", and the predicate ""Of[TV)) is transformed into "TV off".
14

---

Published as a conference paper at ICLR 2024
A.4 BASIC STATISTICS
In the gold plan annotated in the dataset, the plan with the longest length consists of 23 actions, while the average length is 8.13. The frequency distribution histogram regarding the length of the plan is shown in Figure 6. Furthermore, we have also computed the frequency histograms for actions and objects, which are depicted in Figure 7 and Figure
Figure 7: Histogram of action frequencies. Cer- tain actions exhibit significantly higher fre- quency than others, such as Find and Walk.
Figure 8: Histogram of object frequencies. Only objects with a frequency in the top 20 in- cluded for better visualization.
B MORE IMPLEMENTATION DETAILS
B. HYPER-PARAMETT SEARCH
For both Grounded Deciding and ITERATIVE- PLANNER,,, we conducted grid search over the sam- pling parameters of OpenAl APIs. The search range for temperature was from 0.1 1.0 in increments of 0.1, while the search range for top-p was set to 0.85, 0.9, 0.95, and 1.0.
In the case of Grounded Deciding, the optimal hyperparameter combination was found to be temperature of 0.7 and topp of 1.0. As for ITERATIVE--LANNER, the optimal hyperparameter combination was a temperature of 0 and topp of 1.0.
B.2 BASELINE MODELS
ZERO-SHOT PLANNER (Huang al., 2022a) propose to translate each unstructured action gen- erated by LLM into an admissible action via another pre-trained masked language model. The translated action is then appended to the prompt used for generating the remaining steps. We uti- lize the official implementation provided by Huang et al. (2022a), which employs dynamically retrieved plan as an exemplar in the prompt. Moreover, concerning the hyper-parameters, we con- figure the maximum number of steps as 20 and set the early stopping threshold to 0.5 to achieve optimal performance.
FROGPROMEE (Singh al., 2022) proposes programming eagguage-inspired prompt with an assert statement. These assert statements provide a mechanism for incorporating environment feed- back into the plan generation process, ensuring that preconditions for each action met;
B.3 POST-PROCESSING
To ensure the generated plan is actionable in the environment, we further implement a post- processing module after plan sampling: (i) Format Checking: Actions that do not conform to the required format and thus cannot be parsed, is discarded. Given the strong format following ability of GPT-3.5, the number of discarded items is minimal; (ii) Object & Action Translation: Even with the correct format, the plan generated by the LLM might include actions objects not present in the environment. This issue often arises from semantically accurate but not exactly matching results. For instance, if the environment's object name is "food egg" but the generated action includes
15

---

Published as a conference paper at ICLR 2024
"egg", this discrepancy requires resolution. Firstly, parse the LLM's action string to identify the action and object names. Then we use BERT similarity to match these with the environment's available actions and objects ?. For example, for the LLM's generated string '/Switch On] <telly >' the action parser identifies "Switch On" as the action and "telly" as the object. These are then matched with available actions and objects result in the actionable action "[SwitchOn] <TV >"
C MORE EXPERIMENTAL RESULTS
C.I RESULTS BY PLAN LENGTII
EXEC, t
SR f
GCR
No.EC
0 << << A
a < 5
100.00 + 0.00
64.72::..20
77.12+4.113
0.30
S 10
83.59:L4.03
35.10:5.995
52.25+3.33
2.47::0335
10 L
S 15
88.09+8.488
55.98=7.00 22.22+00.00
26.98:+4.89
3.20+1.112 36.11+0.00
15
66.67=0.00
4.09
Table 4: The performance of TREE--LLANNER across different plan sequence lengths.
categorized by different plan se- quence lengths. In general, as the plan sequence length increases, the performance of the model tends to decrease. Specifically, for tasks with plan lengths smaller than 5, the SR can reach 64.72% and even 100% for EXEC.. However, for tasks with plan lengths larger than 15, the SR decreases to 22.22% (-42.5%), and EXEC. decreases to 66.67% (-33.33%). Furthermore, increases, the number corrections in the model also increases. This is due to the higher likeli- hood of errors accumulating in longer sequential task planning, thus necessitating greater need for error correction. The above experimental results provide a more comprehensive analysis of the performance of our approach, emphasizing potential directions for future enhancements. Further- more, we have provided the results of LOCAL REPLAN as shown in Table 5. It can be observed that maintains comparable performance across different plan lengths, exhibits a significant advantage in terms of the number of corrections.
Table 4 above presents the performance of TRREE-PLANNER,
the plan length
while
EXEC. f
SR t
GCR
No.EC 1
0 <<<0
la
S 5
94.17 + 2.04
56.94 + 0.79
69.46 1.70
1.05 + 0.32
5 la
< 10
77.02 + 7.63
38.10 3.57
49.66 5.45
3.92 : 0.56
10 <
A
S 15
69.84 + 2.97
24.78 +:5 5.83
44.52 2.116
1144:.11
15
72.22 + 28.33
22.22 + 0.00
35.65 + 8.36
4.83 + 0.87
Table 5: The performance of LOCAL REPLAN across different plan sequence lengths.
C.2 RESULTS BY SCENE
As is shown in Table 6, TREE-PLANNER exhibits consistent performance across various scenes, thereby further illustrating its robustness.
EXEC.
SR
GCR f
No.EC 4
ENV-1
92.42+2.14
45.45+3.71
64.7243.25
1.74+0.44
ENV-2
91.30.1.110
36.75.4.10
52.4317.11
2.33+00.7
ENV-3
85.18
37.04
50.8043.19
1.83:1039
ENV-4
88.8943.14
48.8943.14
66.74+1.72
2.35
Table 6: The performance of TREE-PLANNER =50 across different scenes.
hhttps://ww.sste
16

---

Published as a conference paper at ICLR 2024
C.3 DIVERSITY OF SAMPLED PLANS
As shown in Figure 9, the number of different plans varies approximately linearly with the change in the sampling Therefore, when conducting plan sampling, the issue homogenization due to the sampled plans will not arise.
Number Different Plans
25.3
16.6
35.0
0
20
40
60
50
100
Sampling
Figure 9: The diversity of plans generated. The x-axis represents the number of programs sampled, while the y-axis represents the average number of different plans generated.
C.4 UPPER LIMIT OF PLAN SAMPLING
We also compute the corresponding Success Rate (SR) result of Figure by: (i) the maximum SR for all generated plans, i.e., S.maa (c) max(SR(c))): (ii) the average SR for all generated plans, i..., SRung (c) x >> (SR(c)). As is shown in Figure 10, the trend of SR concerning N closely aligns with the trajectory of GCR.
2=1
SRmax
59.2
SRava
35
34.93
15
30
40
70
N
Figure 10: Maximum and average Success Rate (SR) for all sampled plans.
C.5 EXPERIMENTAL RESULTS WITH BEST-FIRST SEARCH
Language-Guut Guided Best-First Search The edges of the action are assigned weights based on the log probabilities of the actions they lead to. These weights are aggregated when multiple paths converge into the same action, thereby reflecting the cumulative likelihood of reaching that action within the context of the tree's structure. The evaluation function of Language-Guided Best-First (lng(he(aa))
Search defined as: (a,)
Σ, (ogg(MaKa,)) Here, a; represents one of the child nodes of
given node and iterates over all child nodes. The softmax function normalizes the log probabilities, making them suitable for probabilistic comparison and selection.
Environment-Guiid Best-First Search Actions are weighted based on the observability of their associated objects. If all objects involved in action observable in the environment, the action
17

---

Published as a conference paper at ICLR 2024
is assigned higher weight (1), otherwise, lower weight (0). To facilitate comparative analysis and to account for varying numbers of actions and objects, softmax function is applied to the weights of actions emanating from each node. The evaluation function of Eavironment-Guiie Guided Best-First Search is defined as fu(a;) C (hemanltt(a,))
Ej (hurobliyleg)
Hybrid Best-First Search The Hybrid Method combines the probabilistic language and environ- ment observability factors. The evaluation function is: [H,bria(a,) a.fi(aa) + a') fe.)) this function, a is hyper-parametts between and that balances the influence of the language-bart probabilities and the environmental observability
Experimental Setup We conducted experiments in the case of N=50 without error correction. As for the hyper-parameter a, we heuristically it to 0.5.
Experimental Results As demonstrated by Table 7, although heuristic methods exhibit greater advantage terms of token efficiency, their SR falls short compared to grounded deciding (using ILM as an implicit evaluation function). Moreover, combining both evaluation functions yields even greater performance improvements, thus demonstrating that there is still room for enhancement through the optimization of the evaluation function in heuristic methods.
Table 7: Experimental Results with Best-First Search
EXeC.
SR t
GCR t
SCoST
PLANNER LANGUAGEGUIDED
49.01
28. 28.14
35.8444.20
3.48+0004
34.71
15.06+11.02
22.47+1.72
2.16:t0.02
ENVIRONMENTGUDDED
37.26:10.17
6.24-10.65
12.10
2.16::0.02
HYBRID,=0.5
38.714:0.22
17.74400.69
25.34
2.16+00.2
C.6 PROPORTION OF NEW OBJECTS
The relationship between the number of steps and the proportion of new objects in evaluated tasks is shown in Figure 11.
0.85
Proportion of New Objects
0.80
0.75
x
X
x
0.70
XX
x
x
x
x
0.65
X
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
22.5
Number of Steps
Figure 11: Each point represents a distinct task. The proportion of new objects calculated with gold plans in the dataset.
18

---

Published as a conference paper at ICLR 2024
D DETAILS ON TOKEN EFFICIENCY
The detailed derivation of the boundary conditions for N is as follows:
to prove Pours < Pabs
Pps M [a] + M (Pyd + N) M (pps
Pyd + (al)
MN + M N < (M 1) Pps + M |a|
M (Ia] + 1). N < (M-
1)
Pps + M |a|
1 - 1/M Pps
aa|
N
+
+ 1/|a|
|a|
a
E QUALITATIVE ANALYSIS ON ERRORS
E.I INCORRECT DECIDING
Task: Hang up jacket
Action Tree: See Figure 12
Hang up Lagers1
[Wik]] sobities jockep Layonó
[Wak] <batrocur- Layeni)
[Fid] selotes jacker (1) Laper3
(hant--tange--t)) (1) Layer:
[Fidd iickttss jacket (1) Lager]
(dakt- jacket Layer
[Gnb] soletee jaceets (1) Layer?
[Pind] <hangers (1) Layen??
[Gibh] solothe jocests (I) Tayor?
[Frd] soliras joicn (1)
[Fiul) Layor)
(WSik] <langar Layer'
[Gmh] jacker Layar!
Lagar
[Fid]] stanger- Layord
[Ginb] solothes jocket (1) Layer4
[Fidd] starger- Layor4
[Wak]-thnggr- (1)
Layer4
(PND L
(END)
[Pulfook] solitto jacket (I) -honger
(Find] -langet (1) Laye:3
Lager
Lagar
Layenh
Figure 12: Visualization of the action tree for Hang up jacket. The red path is the plan chosen by LLM, while the green path is the correct plan.
Explanation: As depicted in Figure 12, the model made an incorrect decision during the second step. This is due to the failure of PREE-PLANNER to comprehend the sequential order of searching for a jacket and searching for hanger.
E.2 ENVIRONMENT MISUNDERSTANDING
Task: Clean toilet
19

---

Published as a conference paper at ICLR 2024
Example Plan:
1. [Walk] <bathroom>
7. [Wash] <toilet>(1)
2. [Walk] <toilet><1)
8. [Find] <mop.bucket>(1)
3. [Pull] <toilet>(1)
9. [Walk] <detergent>>1)
4. [Wash] <toilet>(1)
10. [Grab] <detergent><1)
5. [Wipe] <toilet><I)
11. [Pour] <detergent>(1
6. [Push] <toilet><1)
(mop_bucket>>1)
Explanation:
The toilet is not movable, so the execution of step 3 would be failed.
E.3 INCOMPLETE PLAN
Task: Put alarm clock bedroom
Example Plan:
1. [Walk] <bedroom>>(1)
2. [Walk] <alarm_clock>>0
3. [Find] <alarm_clock>(()
4. [Grab] <alarm_clock><()
5. [Find] <dresser><(1)
6. [Open] <dresser><(1
7. [SwitchOn] <Ilarm.clock>>()
Explanation: After executing this plan, the alarm clock will be in the hand the character. How- step is missing: [PutBack] the <alarm clock>(() the <dresser><1) to place the alarm clock in bedroom.
E.4 ILLOGICAL. ERROR
Task: Shave
Example Plan:
1. [Walk] <bathroom>>(1)
7. [Walk] <razor>(1)
2. [Find] <shaving.cream>>
8. [Find] <razor>(1)
3. [Grab] wshaving.cream>>/
9. [Grab] <razor>(1)
4. [Walk] <after.shave>>.1 (1)
10. [PutOn] <shaving.creamm>[1
5. [Find] <after shave>>)
11. [Wash] <headset><()
6. [Grab] <after.shave><()
12. [PutOn] <after_shave>((
Explanation: The character does not have a free hand when executing step 9. This is because, in steps and 6, the character has already picked up two items.
E.5 SEMANTICALLY CORRECT
Task: Use computer
Example Plan:
1. [Walk] <home office:>(1)
2. [Walk] <computer><()
20

---

Published as a conference paper at ICLR 2024
3. [Find] <chair>(1)
4. [Sit] <chair>(1)
5. [SwitchOn] <computer>
6. [Type] <keyboard><1)
Explanation: The error information from the environment is as follows: "<keyboard >" cannot be found when executing "[Type] <keyboard >(1". However, at this moment, the character is seated in front of the computer, indicating that the keyboard should be located near the character.
E.6 MORE RESULTS ON ERROR TYPES
As illustrated in Table 8, we conducted further analysis of the error types in the PREE-PPLANNER, model with correction. The distribution strikingly similar that of the model without correction. Moreover, owing to the presence of error correction, the model demon- strates enhanced capability in avoiding semantically correct errors during the grounded deciding stage.
F PROMPTS
F.1 ITERATIVE-PLANNER
(Instruction) You need to act as task planner who decomposes a high-level household task into several sub-tasks. The temporal relationship between subtask sequences must adhere common- sense logic. Each sub-task can be one of the following form: 1. faction_name, 2. [action _nmme] <object name 1>> (object id 1). 3. [action name] <object name [>boeet id <object name (object id 2). The number of arguments depends on the action type. The (object id) is used to tell the simulator that the actions should be done on the same object instance. For example a program as: [Walk] <glass>(1) [Grab] <glass>>(1 Indicates that the agent should first walk to glass and then grab that same glass. If you think your task has been successful, you can output [END], which action type 1.
(Global Information) For action type 1, the available actions are: [Sleep], [StandUp], [WakeUp] For action type 2, the available actions are: [Walk], [Find], [Grab], [Wash], [Wipe], [Pull]. [Push], [Pour], [TurnTo], [PointAt]. [Watch], [Touch], [Open], [Close]. [Run], [Sit]. [Read], [PutOn], [Drop]. [Lie], [SwitchOn], [SwitchOff], [Drink] For action type 3, the available actions are: [PutIn], [PutBack] | All action_nann _name of the sub-tasks must be chosen from the above actions, and follow the corresponding format. You are in house that consists of four rooms. These rooms are bathroom, dining bedroom, home_office Available objects in the house are clothes_hat, ceilinglamp, cpuscreen, orchid, couch, trashcan, dresser, dishwasher, centerpiece, phone, toaster, mneasuring.cupp stereo, mat, computer, envelope, oven_mitts, bench, box, photoframe, shower, ceiling, wall, window, freezer, faucet, detergent, light, desk, napkin, food rice, kitchen counter, folder, stovefan, walllamp, food food, coffee pot, food steak, jelly, vacuum cleaner, powersocket, filing cabinet, al- cohol, bathroom, door, bathroom _oonttrr,, clothes-gloves, microwave, oven, sink, milk, ice, bed- room, laptop, doorjamb, food_cake, bills, tea_bag. television, laser_pointer, toilet, board game, sponge, carrot, table, tray, cupboard, mousepad, picture, tvstand, tablelamp, hanger, pot,
Table 8: Distribution of error types of the TREE-PLANNER, N-25 with correction model.
Error Type
Explanation
Proportion (%)
Missing Correct Plans
Plan sampling did not yield correct plans Misunderstandings actions objects
52.6%
Environment Misunderstanding
21.1%
Incomplete Plan
The absence of essential steps
15.8%
Illogical Error
The generated plan is logically incorrect
5.3%
Semantically Correct
Execution failed but semantically correct
10.5%
Grounded Deciding Error
Errors during grounded deciding Incorrect decisions specific nodes Execution failed but semantically correct
47.4%
Incorrect Deciding
47.4%
Semantically Correct
0.0%
21

---

Published as a conference paper at ICLR 2024
dry -asta, floor, knifeblock, curtain, chair, food_bread, drawing, creditcard, check, coffe_makers character, pasta, bag, food_bacon, bookshelf, toothbrush_ cutting. home_offin din- ing room, nail polish, pillow, tape, nightstand, bathroom cabinet, bench, conditioner, cat, bed, key- board, mouse All object names must be chosen from the above object list
Currently, you standing in the bedroom, and holding nothing in your right hand and nothing in your left hand. pillow clean. napkin is clean. pillow is dirty. bed clean. mat is dirty. pillow close drawing. tablelamp is close bed. mat is facing drawing, pillow is inside bedroom. mat is close to table. bed is close to drawing. table is close to mat. pillow is on floor. floor close to bed. tablelamp close pillow. mat is close to curtain. bed facing computer. mat close to floor. pillow is facing drawing. curtain is close to mat. bed is close to tablelamp. wall is close to mat. napkin inside bedroom. window close to mat. pillow close to tablelamp. bed close to floor. pillow is close to wall. mat is close to fllingccabine' drawing is close to bed. pillow close to floor. bed is close to wall. filing_cabing inside bedroom. pillow is close to pillow. pillow is close to nightstand. mat is close to wall. wall is close to pillow. nightstand close to pillow. nightstand is close bed. drawing is close to pillow. floor is close to pillow. bed is inside bedroom. floor is close to mat. wall is close to bed. mat is close inside bedroom.
(Observation)
is close mat. bed is close to nightstand. mat
to window.
(In-Context Examples)
Task: Watch TV
[Find] <remote (remote_control>(1
[Fid]
<television>>()
[SwitchOn] <television>>()
[Find] (conc)<<cuch>>1))
[Sit] <couch><1)
[Touch] <remote control>(1)
[TurnTo]] (television>>()
[LookAt]
<television>(1)
Task: Turn on light
[Walk]
[Walk]
<light>(11
[Find]
<light>(1)
[SwitchOn] <light><11) [Find] <light><() [SwitchOn] <light>
Task: Go to sleep [Walk] <bedroom><() [Walk] <b)d>>(1) [Lie] <bed>>(1) [Sleep]
Task: Brush teeth
[Walk] <bathroom>>1)
[Walk] <toothbrush (h (1)
[ind]
foothbrushhholddrr..
[ind]
<toothbrush><1))
[Grab
(1)othbrush>>))
[Wlkk] <tooth_paste>>(0
Find]
<tooth (1)te>(1)
(rab)]
<tooth paste>((1)
Pourr
<tooth_paste><()
<toothbrush><))
Find] <teeth>(11)
[Scrub]
<tecth><()
22

---

Published as a conference paper at ICLR 2024
Task: Take nap
[Wakk] <bedroom>>()
F.2 PLAN SAMPLING
(Instruction) You need to act a task planner, who decompose a high-level household task into several sub-tasks. The temporal relationship between subtask sequences must adhere to common- sense logic. Each sub-task can be one of the following form: [action name]; [action name] <ooject name (object id 1). 3. [amtio <object name (objecc id 1) <'ojject name (object id 2). The number arguments depends on the action type. The (object id) is used to tell the simulator that the actions should be done the same object instance. For example program as: [Walk] <glass>(1) [Grab] <glass><1) Indicates that the agent should first walk to a glass, and then grab that same glass.
(Global Information) For action type 1, the available actions are: [Sleep], [StandUp]. [WakeUp] For action type 2, the available actions are: [Walk], [Find], [Grab], [Wash], [Wipe], [Pull], [Push], [Pour], [TurnTTo]. [PointAt], [Watch], [TTuuhh, [Open], [Close]. [Run], [Sit]. [Read], [PutOn], [Drop], [Liee] [SwitchOn], [SwitchOfff, [Drink] For action type 3, the available actions are: [PutIn], [PutBack] All action_ -amo of the sub-tasks must be chosen from the above actions, and follow the corresponding format. You are in house that consists of four rooms. These rooms are bathroom, dining room, bedroom, home home-office. Available objects in the house are clothes.hat ceilinglamp, epuscreen, orchid, couch, trashcan, dresser, dishwasher, centerpiece, phone, toaster, measuring cup, stereo, mat, computer, envelope, wve__mitts, piano bench, box, photoframe, shower, ceiling, wall, window, freezer, faucet, detergent, light, desk, napkin, food_rice, kitchen Kitchen_counter, folder, stovefan, walllamp, food_food, coffee-pot, food_steak, jelly, vacuum powersocket, filing.cabinet, al- cohol, bathroom, door, bathroom room, laptop, doorjamb, food cake, bills, tea bag. television, laser pointer, toilet, board game, sponge, food carrot, table, tray, cupboard, mousepad, picture, tvstand, tablelamp, hanger, pot, dry -asta, floor, knifeblock, curtain, chair, food bread, drawing, creditcard, check, _affe, character, pasta, bag, food_bacon, bookshelf, toothbrush_holee rng-room, nail. polish, pillow, tape, nightstand, bathroom. naabne, bench, conditioner, cat, bed, key- board, mouse All object names must be chosen from the above object list
clothes-gloves, microwave, oven, sink, milk, ice, bed-
cotting.board, home_ ooffie,, din-
(Initial Observation) Currently, you are standing in the homeeoffice, and holding nothing in your right hand and nothing in your left hand.
(In-Context Examples)
Task: Watch TV
[ind] <remote_controlll
[Find] <television>>()
[SwitchOn] <television>>()
((nd)<<couch>(1))
[Sit] <couch><(I)
[Touch]
[TurnTo] (television>>1)
[LookAt] <television>>))
Task: Turn on light
[Walk] <diningrroom>>))
[Walk] <lighh><(1)
[Find]
<light><(1)
[SwitchOn] <light><11) [Find] <light><(2
[SwitchOn] <light>(2))
Task: Go to sleep
[Walk] <bedroom>>()
[Walk] <b)d><(1)
[Lie] (1)
23

---

Published as a conference paper at ICLR 2024
[Sleep]
Task: Brush teeth
[Walk] <bathroom>>()
[Walk] ceathbruushhooder>>-
(1)
[Find] <toothbrush_holder>>> (1)
[ind] <1oothbrush>>11)
[Grab] <toothbrush>>1)
[Wlk] <tooth.paste>>))
[Fidd] (tooth_paste>(1]
Grab]
<tooth paste>(()
[Pour] <tooth_paste>>))
(1oothbrush>>())
[ind]
<teeth><(1)
[Scrub]
<teeth>(1)
Task: Take nap
F.3 GROUNDED DECIDING
(Instruction) You need to act home robot. At each moment, I will provide you with observations of your current environment, as well as the high-level task I want you to do, and previous mid-level sub-tasks that have been executed. Then, you need to select the best sub-task from the options I provide to complete the designated home task based on the observation and your past experience. When one choosed sub-task causes error in the environment, you will be provided with the error information and the corresponding sub-task, and you need to re-choose a corrective sub-task at the current time step. For example, The sub-tasks that have been executed in the environment are:
[GRAB] <plate>(1)
[WALK] <dining room>>()
The choosed sub-task is: [PUTBACK] <plate>(1) <table><(1)
The prompt (error information) would be: The sub-task: "[PUTBACK] <plate>(1) <table>(1)" caused an eтror: Script is not executable, since <character><1) is not close to <table>(1) when executing "[PUTBACK] <plate>(1) <table>(I) [1]" Among the following actions, which action would you take.
A. [Find] <table>(1)
B. [Find] <plate>(1)
A corrective choice of sub-task would be (You just need to provide the mark before the option you want to choose): A
(Observation) Currently, you are standing in the bedroom, and holding nothing in your right hand and nothing in your left hand. pillow clean. napkin is clean. pillow is dirty. bed is clean. mat is dirty. pillow is close to drawing. tablelamp is close to bed. mat is facing drawing. pillow is inside bedroom. mat is close table. bed is close drawing. table is close mat. pillow is floor. floor is close to bed. tablelamp is close to pillow. mat is close to curtain. bed is facing computer. mat is close floor. pillow is facing drawing. curtain is close mat. bed close tablelamp. wall is close to mat. napkin is inside bedroom. window is close to mat. pillow is close to tablelamp. bed is close to floor. pillow is close to wall. mat close to filing cabinet. drawing is close bed, pillow is close to floor. bed is close to wall. filing.cabinet is close to mat. bed is close to nightstand. mat is inside bedroom. pillow is close to pillow. pillow is close to nightstand. mat is close to wall. wall close to pillow. nightstand is close pillow. nightstand is close bed. drawing is close pillow. floor is close to pillow. bed is inside bedroom. floor is close to mat. wall close to bed. mat is close to window. pillow,,apkin, www.:w..a..eee..lllllll..o.o
is inside bedroom.
Your task is: Take nap.
(History)
Your previously executed sub-tasks are: [Walk] <bedroom><11
Among the following sub-tasks, which one would you take.
A. [FIND] <1)
24

---

Published as a conference paper at ICLR 2024
B. [WALK]
<couch><1)
C.
[WALK] (1)
D.
[FIND] <couch>(1)
E. [FIND] <pillow>(1)
The best choice of sub-task is:
G VISUALIZED ACTION TREE
We visualized the action trees for the tasks listed in Table 9 for interested readers.
Task
Action Tree
Take nap
See Figure 13
Put on your shoes
See Figure
Pick up spare change dresser
See Figure 15
Clean toilet
See Figure 16
Put alarm clock in bedroom
See Figure 17
Table 9: Action trees for various tasks.
Leyad
Ligeet
iFat rezadi-1 (1)
[ba] rossde (I)
[WuB] rosate (Il
(Wat dhal-())
Liped
lesez
Legez
Layect
Leyer2
Klapy
(Lokky) Soeeet (1)
Hilpp
Maaioed (1)
[Tarda] (ell)) (7)
Lypck
Lapase
Ligari
PAUI
JNNX
cheil Lipes
(1 (+ftaa)))))
[NE]] Lipeto
Hkdi- Ligues
Skupl Layez!
BNNO
Eayer
Figure 13: Visualization of the action tree for Take nap.
25

---

Published as a conference paper at ICLR 2024
(0 lowrt
Toyer
Tayrt
Dkl of Lanc
Lpers
Dhu saeae Lows
live
Deco di
Dia Hubeen io
Fatt Futhi Inleen II
Fill Falliae (el
bank
Dhice (doverd)
Pher DI
Lipec
Lape!
Aipa
Lates
Figure 14: Visualization of the action tree for Put on your shoes.
26

---

Published as a conference paper at ICLR 2024
Pick up spare change dresser Layen-l
[Walk] <bedroomp (1) Layertl
[Walk] Layer!
[Fixd] <dressee> (1)
Layen:2
[Pal] sdroser (1) Layar3
[Gib]] <coiiz (1)
[Open] <dresser> (1)
[Find] scoine (1)
Layen3
Layer3
Layer3
[Find] Scoip? ()) Layers
[Grab] Scoiro (2)
[END] Layars
[Find] Scoin (1) Layersl
[Grab] Spoinn (l)
Layer4
Layerst
[Gmb) (1)
[END] Layer5
[Grab) <cole> (1)
Layer5
Layer5
Layers
[END] Layerd
[Close] suroserr (1) Layers
[END] Layers
[END] Layer!
Figure 15: Visualization of the action tree for Pick up spare change dresser.
Figure 16: Visualization of the action tree for Clean toilet.
27

---

Published as a conference paper at ICLR 2024
Figure 17: Visualization of the action tree for Put alarm clock in bedroom.
28


Reviews:
[{"review_id": "sWImQStYhZ", "reviewer": "Reviewer_mZgD", "summary": "The paper presents an algorithm specialized in LLMs for interacting with an environment for solving tasks that require planning. In this context, the state, the observations and the actions are represented as text. \n\nIn previous work, called iterative-planning in the submission, When an action is executed, another call to a LLM appends the observation and attempts to obtain a new action. In the planning literature, that is close to what is called integrated planning&execution, as the agent must choose actions for achieving the goal, but observations might lead the agent to change the course of action completely.\n\nIn contrast, the paper follows a more restricted mode that can be more efficient under some circumstances: offline planning, then execution of the plan. This is the more studied case in the symbolic planning literature, where offline planning has received much more attention than execution.\n\nThe proposed algorithm \u001f—Tree-Planner— is relevant for domains expressed in text, where a LLM could approximate a world model, and could produce a plan using knowledge widely available in text. \n\nWhile the task can be formulated as a POMDP, the initial phase –called plan sampling– does not deal with further possible observations but just the general scene. Indeed, the samples are converted that represent common prefixes of the plans. So, the policy from plan sampling can be seen as a stochastic policy. That makes sense in some cases, but it generally cannot solve POMDPs where policies might need to map state distributions into actions, and update state distributions with new observations.\n\nAlways assuming the use of a LLM, the main hypothesis mentioned in the abstract are:\n1. Tree-planner might be more effective than alternatives like iterative planning by avoiding redundant error correction.\n2. Tree-planner might have a lower token cost.\n\nThe second hypothesis is true, almost by construction, as the algorithm only needs less information about actions and objects. The first hypothesis is only studied for VirtualHome, a domain of some interest. The main claim is that backtracking allows more effective recovery than appending the error and letting the LLM recover.\n\nThe paper shows how high-quality data was refined to allow the evaluation of metrics like success rate. \n\nThe experimental setup reports a comparison with baselines including iterative-planning, all using the proprietary LLM GPT-3.5.\n\nThe results show improvements in the 35 tasks of the dataset. For N=50 samples, the best possible GCR (goal condition recall) reaches 81.2% of the tasks.", "questions": "- What are some other environments where this method could be tested?\n\t- Why was only VH selected?\n- Given a fixed task, is the same prompt used for the four scenes?\n- Does the observation of plan-sampling include the full description of the room or just the type of room?\n\t- I understand that in VirtualHome, the top-down view allows the agent to see everything except what’s hidden in containers like drawers.\n\t- The prompts in section F include a long “(observation)” for iterative planning and the grounded-deciding phase, but not for plan sampling.\n- Did you consider adding the observation history?\n\t- The list of actions with the observation context where they were made might need to be more informative.\n\t- Unless the observations are monotonic, meaning that after each action, the agent observes more and more. For instance, if once the agent opens a drawer, it would still see what’s there.\n\t- Are the observations monotonic?\n- GCR metric: what’s the distribution of the number of goal conditions? Are the number of goal conditions the same for each of the 35 tasks?\n- Sect 5.2\n\t- Did you randomize the results for table 2? A new seed might generate another set of plans.\n\t- What would be the results for SR? Table 1 shows how GCR grows with SR, but doesn’t predict SR. Actually, the gap between GCR and SR is higher for Tree-Planner than for other approaches.\n\t- Related: Table 3 reports 45.5 of errors due to missing correct plan.\n- What is the inverse of all the actions? \n\t- The supplementary material lists them, please list the corresponding inverse, say how that information was obtained, and discuss how realistic it is for that information to be available or learned.\n- Branches in action trees.\n\t- Some node action trees have no branches. See leftmost path Fig 12. Is the LLM prompt for choosing one action or are they executed? Is this accounted in the cost of the predictions?\n- Please report the average number of branches for reaching the leaves for each of the 35 tasks. This is equivalent to aggregating sequences without branching into a single action. For instance, Fig 12 has 8 leaves with [1, 1, 2, 2, 3, 3, 2, 3] branches, average 2.125 branches per leave. So, the agent should make an average of 2.125 decisions when following that branch.\n- Please discuss the number of error corrections in Table 1 compared to the number of branches. Otherwise, it’s hard to know whether 3.29 vs 1.86 is a significant difference.\n- Sect 4.1: Dataset: what are the 35 unique tasks?\n\t- VirtualHome has multiple programs for some tasks, not a single gold plan.\n\t- Did you create new scenes or used scenes in VH?\n\t- Are the gold truth plans associated to a task or to (task, scene)?\n\t- Please list the 35 tasks descriptions.\n\t- What is the distribution of the number of steps for the gold truth? Even better, provide this information for each task\n- Methodological: was N=50 selected using the 35 tasks?\n\t- Is it possible that examining the tasks leads to bias in the selection of N?\n- Sect 4.1: implementation.\n\t- Was majority vote only used for grounded-deciding? Please add a reference for the method.\n- Table 3: errors for Tree-planner N 25\n\t- Is this success rate, SR?\n\t- The false negative is misleading. In the appendix, the error explanation says that the environment reports that there is no keyboard. Are keyboards part of the possible objects? The observations in the prompt mention a computer but no keyboard.\n\t- The example of the keyboard should be an environment misunderstanding.\n\t- Please fix the tables, and refine the definition of false negative. Perhaps you might to add false negative to the missing correct plan, calling it “semantically correct.”\n- What are the error modalities with correction?\n- Sect C.1 describes performance across plan length. \n\t- Can you provide the statistics for other approaches?\n\t- What about kind of task?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "- Good idea: While for model-based planning, offline planning might be weaker than integrated planning and execution, that might be different for LLM-based planning. Obtaining a policy without the distraction of the incoming observations might allow a more systematic execution.\n- The paper is reasonably well-written.\n- The benchmark is interesting.\n- The LLM-based baselines are reasonable enough. Some readers might want to see Chain-of-Though or Self-reflection, but I think zero-shot and iterative replanning are enough.\n- The results using the ground truth plans (oracle planner) show that more samples lead to a smaller improvement, showing the initial phase tends to find more of the correct plan.\n- Using success rate is robust with respect to alternative ways to achieve the goal.", "weaknesses": "- Not clear if the policy is grounded in the environment or in the LLM implicit distribution.\n\t- Section 3.1 mentions the initial observation as part of the prompt, but the prompts in section F include a long “(observation)” for iterative planning and the grounded-deciding phase, but **not** for plan sampling.\n\t- If a detailed initial observation is given, then it’s possible that many of the actions are grounded on them, reducing the significance of seeing the algorithm as dealing with a POMDP.\n\t- If a detailed initial observation is **not** given, then the LLM might be retrieving possible courses of action given the initial description but not grounded in the environment.\n\t- Both scenarios diminish the apparent significance of the work.\n- No discussion of the systematicity of LLM-based planning.\n\t- LLM-based planning is a popular topic, but the increasing body of work might call for a more careful examination. Each paper in this direction is an opportunity to examine the problem and the methodology.\n\t- In general, planning seems easier in the “happy path,” where text with high likelihood matches what might work in an environment, but things can get more complicated quickly.\n\t- Consider the task of “calling Mary using the cell phone”. A good plan is not about assuming that the cell phone is on a table but exploring the space until the cell phone is found. A diverse set of plans might include the more usual places, perhaps even mentioning multiple places in a single path. But it’s possible that the cell phone is in the fridge or in the supermarket bag. \n\t- While the prompt in the grounded deciding phase includes the full observation, the super-market bag would be there, prompting to choose among a few actions to pass the responsibility of examining the supermarket bag and the freezer to the plan sampling phase.\n\t- It’s possible that finding a cell phone might require samples beyond a fixed N, and no alternative is offered.\n\t- So, the **key underlying problem** is that a flexible plan dealing with observations **cannot** be found using a fixed number of samples. Some tasks might require fewer samples, and some might require more. That’s precisely why planning algorithms use search.\n- Experimental significance: a single environment with only 35 tasks.\n\t- The dataset subsection explains that 35 tasks were used, but the tasks were not listed. The VH has many other tasks. The 35 tasks may be biased in a way that affects the significance of the observations.\n- Experimental significance: Only VH\n\t- There are other environments for testing these ideas. For instance, the reference below. The related work section must cover what other alternatives are used in related work and why it’s a good idea to select only this environment.\n\t- (Jericho) Hausknecht, Matthew, Prithviraj Ammanabrolu, Marc-Alexandre Côté, and Xingdi Yuan. “Interactive Fiction Games: A Colossal Adventure.” arXiv:1909.05398 [Cs], February 25, 2020. http://arxiv.org/abs/1909.05398.\n- In general, given the absence of task descriptions and their plans, it’s hard to know whether the results are significant.\n\t- Even if we have the 35 tasks and their plans, the results might be an artifact of this particular environment. Perhaps the current version of GPT 3.5 is better at those household tasks than at navigating in a store to buy groceries.\n\nSecondary issues:\n\n- Goal Condition Recall might be a misleading metric\n\t- different subgoals might be easier than others\n\t- we don’t know the structure of the subgoals \n- Confusions in the theoretical emphasis on POMDPs.\n\t- The hallmark of POMDPs, being a Markov decision process, is the Markov assumption: decisions can be made just by looking at the state without the history. However, the policy in section 2 includes the history of actions but perhaps not the observation history.\n\t- The emphasis on POMDPs is over-stated as the VH has high visibility while other environments feature more partial observability  (for instance, Jericho)\n- Global replan is non-comparable with other algorithms.\n\t- Whether it’s possible to teleport to the initial state or not fundamentally changes the problem.\n- The notion of inverse actions is a form of symbolic knowledge, leaving the scope of the paper.\n\t- A more purist approach would task the LLM to undo the last k actions, perhaps offering the list of actions.\n\nMinor\n\n- The best GCR in section 5.2 is interesting, but GCR is not a good predictor of SR (success rate).\n\t- Actually, in Table 2, the gap between GCR and SR is higher for Tree-Planner than for other approaches.\n\t- Related: Table 3 reports 45.5% of errors due to missing correct plan.\n- It must be clarified if the LLM is called when there is only one possible action.\n\t- Some action trees in the appendix have a few actions with no branches. This affects the overall cost but not other statistics.\n- Alg 1 doesn’t add much. Any algorithm for building a “trie” data structure would work.\n\n\nRecommendations:\n\n- The paper should distinguish the world model from planning. Discussing the percentage of correct plans is useful but not actionable in a new domain as the set of possible plans in a domain is heavily unbounded.\n- The directions suggested in error analysis (re-sample, chain-of-thought, self-reflection) might increase the context size, reducing one of the advantages.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W0wuAMP6hZ", "reviewer": "Reviewer_K1gw", "summary": "The paper proposes TreePlanner, an LLM-based algorithm for task planning. TreePlanner uses the LLM more efficiently without reducing performance. The main contributions are algorithmic and empirical. The key idea is to decompose the planner into two distinct stages of LLM use. In the first stage (plan sampling), an expensive set of calls to the LLM is used to sample a number of full plans. These plans are aggregated into a tree structure which is then searched over in the second stage of the planner. The main source of efficiency (wrt LLM costs) is that the second stage (grounded deciding) can use a simpler prompt to perform action selection (instead of action generation). Experiments on tasks from the VirtualHome domain indicate the method is far more efficient without any loss of performance, compared to strong baselines.", "questions": "- I was unable to identify what error information is included in the history of the prompt used for grounded deciding. Per Figure 2 and Appendix F.3, it seems like some information about previously failed actions seems to be included in the history part of the prompt. If yes, are failed actions restricted to those on the current trajectory from the root to the current node or are they a global history over the entire tree? Which variant is better and why?\n\n- How sensitive is overall performance (e.g., success rate) to the prompt used in Plan Sampling? Since the absence of valid / optimal plans in the constructed tree leads to severely degraded performance and LLM performance is known to be very dependent on its prompt, it'd be useful to understand how much performance might be gained from a better Step 1 prompt? \n  - A related (but harder) question, how does the choice of LLM affect performance (e.g., off-the-shelf black box vs fine-tuned, etc.)?\n\n- Would it be possible to include additional tasks beyond those in VirtualHome? For example, is Toolbench relevant here?\n\n- Given the paper's emphasis is on efficient use of the LLM, what performance improvement does the LLM offer in grounded deciding over other action selection mechanisms? For example, is it feasible to replace the use of the LLM in grounded deciding with \"classical\" action selection techniques (e.g., UCB, best-first heuristic search)? How might this perform? More generally, please discuss where exactly the LLM is required / beneficial over classical search-based planners.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ The paper tackles an important and popular problem of leveraging LLMs for task planning. Progress here would likely be impactful and of interest to the community.\n\n+ The main ideas in TreePlanner are intuitively clear. The two step approach for efficient use of the LLM seems novel, to my knowledge.\n\n+ The results show that compared to the baselines, TreePlanner makes very efficient use of the LLM without losing performance.", "weaknesses": "- While the method clearly shows good performance on the considered domains, the experiments could be improved to address important questions about the approach, namely prompt engineering and the most efficient use of an LLM in task planning. \n  - For example, how good is the current prompt used in the plan sampling step? Given that errors made here are currently catastrophic and the prompt needs to be task-specific, a careful analysis of the quality of this prompt would be interesting. \n  - Another open question is whether it's more efficient to restrict the use of the LLM to plan sampling alone. See the questions for more details. (I'd be open to adjusting my score based on the responses to these questions.)\n\n- The set of tasks considered are from a single domain (VirtualHome). This makes it difficult to evaluate the broader utility of the proposed ideas.\n\n- Some of the the implementation details of the prompts, especially the one used in grounded deciding, are not fully described. See the questions for more details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NEmlCZT85L", "reviewer": "Reviewer_cPrG", "summary": "This paper revisits LLM-based close-loop task planning on a classical application benchmark (VirtualHome). \nPrevious LLM use has been faced with two major limitations, which are high token consumption and redundant error correction. The proposed approach, TREE-PLANNER, aims at addressing the above limitations by reframing LLM-based task planning with LLMs into three distinct phases: plan sampling, action tree construction, and grounded deciding. \nThis decomposition of queries into a single plan-sampling call ensures token efficiency, while factoring action trees facilitates backtracking and error correction.  The system is compared to two baseline systems: Zero-Shot planner and ProgPrompt, and surpasses the state-of-the-art on multiple criteria, each time by at least a few percentage points.", "questions": "1) What guarantees scalability to domains comprizing a larger number of actions and greater tree perplexity?\n2) Could you discuss how different LLM could be used (GPT-4, or LLaMA) with a similar approach and whether the prompting strategy would be affected?\n3) Is partial observability really a salient property of this specific set of 28 actions?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper adresses a competitive topic in the field of LLM for agents and its rationale is presented in a very compelling fashion. It is technically sound, with an excellent balance of technical description and use of supplementary material for examples. The approach itself can be seen as an improvement over previous approaches, but the grounds for such improvements are well justified, and address specific limitations rather than incremental tuning of pre-existing models, conferring originality to the work.\nVery good presentation of related work by structuring it through relevant topics (to the exception of LLM for traditional Planning). \nWell-presented technical insights, in particular the formalization of token consuption, or the analysis of error types.\nDetailed results, using a panel of criteria both technical and practical (i.e. cost), which are quite convincing.", "weaknesses": "Although the paper includes a fairly comprehensive list of related works, it does not address some of the LLM-based planning work. For instance, while 'Tree of Thoughts' is referenced, there is no mention of 'Faithful CoT' [Lyu et al., 2023] and its suggestion for LLM to produce PDDL representations to be passed to a regular Planner (which would still support online planning or replanning via restarting). \nIt would be good to include such a discussion, or to justify not including it (e.g. on grounds of partial observability), provided such grounds effectively preclude adoption. \n\nLyu, Q., Havaldar, S., Stein, A., Zhang, L., Rao, D., Wong, E., Apidianaki, M. and Callison-Burch, C., 2023. Faithful chain-of-thought reasoning. arXiv preprint arXiv:2301.13379.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YPG1DoTkwK", "reviewer": "Reviewer_m5sK", "summary": "Language model planning frameworks operate iteratively by generating one action per time-step, appending it back to the prompt (along with observation for closed-loop planning), and repeating the process until the task is executed. Such approaches are token-inefficient because of their repetitive use of prompt tokens (which includes the task, action-observation history, and in-context exemplars) for each action-step generation. Moreover, in closed-loop planning, such methods may often lead to infeasible action steps, thus, requiring corrective steps/replanning (local or global). In this paper, the authors propose a way to make closed-loop planning (i) more token-efficient (i.e. requiring fewer tokens) than an iterative planner and (ii) more replanning efficient (requiring fewer corrective steps). \n\nSpecifically, the authors propose to sample multiple plans from the LLM in a non-iterative and offline fashion (Plan Sampling). These plans are then merged into a tree-like structure to avoid repetitive actions (Action Tree Construction). Finally, these executable actions are selected by prompting the LLM with the task, current observation, and the history of executed actions (Grounded Deciding). The non-iterative plan sampling approach is more token-efficient. The tree-like structure helps to backtrack and select different steps in case of action failure without having to plan from scratch, avoiding large token costs.", "questions": "1. When sampling plans (action sequences) non-iteratively, an error in one action step (something that diverges from the list of executable actions) can lead to subsequent actions being erroneous, leading to a so-called \"compounding effect\" as highlighted in [C]. This would lead to most of the sampled plans being infeasible. How do the authors address this problem?\n\n2. \"In terms of correction efficiency, TREE-PLANNER reduces the number of corrections by 37.99% and 40.52%, respectively:\" How do you define and measure an error \"correction\": For instance, it could be (i) a new action insertion; (ii) an action deletion; (iii) replacing one action with another generated action. Is it evaluated irrespective of the success rate (i.e. is it only measured for plans that have succeded in correctly executing the task or for any plan)?\n\nMinor comments: \n\na considerable part of the prompt \"is\" less …\n\nFigure 4: Leave node -> leaf node\n\nMissing citation: SayCanPay (see [B] in Weaknesses)\n\n\n[C] Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents, Huang et al., 2022", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Overall, the paper is well-motivated. \n* Through a number of empirical and ablation studies on VirtualHome environment, the authors show how their approach is significantly more token-efficient compared to the general iterative closed-loop planning approaches. The authors also show improved performance wrt ProgPrompt, however, ProgPrompt is more token-efficient (Table 1)\n* The framework would be of significance to the planning and decision-making audience (especially in academia) who want to use the larger models for similar works.", "weaknesses": "* Originality: Placing this paper in the context of existing works (like Tree-of-Thoughts & SayCan), much of the contributions seem to be merely engineering tweaks that do not contribute (significantly) on a more fundamental level. Considering how generating and planning over tree-like structures have been explored in the past in open-loop/offline planning [A][B], where planning trees are generated iteratively, while simultaneously grounding the actions, the only novelty here is to decouple the tree construction from the grounding (Grounded deciding) for token-efficiency. Backtracking is also something that has already been introduced in Tree-of-Thoughts, although not in a proper task-planing framework. \n\n* Clarity: From what I understand, the sampled plans were generated in one go (non-iteratively) to avoid higher costs. However, iterative planning is useful in avoiding compounding errors and it is unclear as to how the authors handle such errors in their non-iterative setup (see Questions). Certain details like the definition of \"corrections\" are somewhat ambiguous.\n\n[A] Reasoning with Language Model is Planning with World Model, Hao et al., 2023 \n\n[B] SayCanPay: Heuristic Planning with Large Language Models Using Learnable Domain Knowledge, Hazra et al., 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)