Tree-Planner: Efficient Close-loop Task Planning with Large Language Models

1 INTRODUCTION

• Robotic task planning generates mid-level skills to accomplish complex high-level tasks, and LLMs have emerged as an alternative to searching predefined domains.The passage describes LLMs generating actions directly.Source: §1 · p. 1
• Iterative LLM planning repeatedly incurs prompt costs over multi-step tasks, while local replanning can miss earlier errors and global replanning costs more time and tokens.Prompts include instructions, environment information, examples, and observations, whereas generated outputs are often concise actions.Source: §1 · p. 2
• TREE-PLANNER samples potential plans before execution, aggregates them into an action tree, then uses environmental observations to decide in closed loops.The approach charges once for global environment information and in-context examples during plan sampling.Source: §1 · p. 2
• Backtracking on the action tree reduces redundant decisions at a timestep and the time and tokens needed to regenerate a complete plan.The correction process is described as intermediate between LOCAL REPLAN and GLOBAL REPLAN.Source: §1 · p. 3
• TREE-PLANNER surpassed the best baselines by 1.29% and 3.65% in success rate across with- and without-correction settings, respectively, and reduced GLOBAL REPLAN token cost by 92.24%.The evaluation used VirtualHome household tasks.Source: §1 · p. 3

2 PRELIMINARY

• Task and Motion Planning generates actions and robot motions to achieve a desired goal in an environment.The paper assumes a low-level controller can execute the mid-level actions.Source: §2 · p. 3
• Unlike open-loop planning, closed-loop planning continuously adjusts strategies using perception and feedback to adapt to environmental changes and uncertainties.The paper focuses on closed-loop planning for dynamic and complex environments.Source: §2 · p. 3
• The POMDP policy for a task conditions on the current observation and the full history of previously executed actions.The formulation defines states, observations, actions, and a transition model.Source: §2 · p. 3

3.1 PLAN SAMPLING

• Plan sampling prompts an LLM to generate candidate action sequences from task descriptions, treating sampled plans as prior commonsense knowledge for planning.The prompt includes instructions, environment information, an initial observation, and in-context examples.Source: §3.1 · pp. 3–4

3.2 ACTION TREE CONSTRUCTION

• The action tree aggregates plans with shared prefixes into common branches, turning plan-level filtering into action-level search.Plans with the same action are not merged when their prefixes differ.Source: §3.2 · p. 4, Figure 3 · p. 4

3.3 GROUNDED DECIDING

• Grounded deciding limits the LLM's choices to valid child nodes and conditions its selection on instructions, observations, and executed-action history.On execution failure, the method invalidates the failed subtree, backtracks to a fork with valid choices, reverses prior actions to recover the agent state, and re-decides.Source: §3.3 · pp. 4–5, Figure 4 · p. 5

4.1 EXPERIMENTAL SETUP

• Evaluation used a curated 35-task dataset spanning four VirtualHome scenes, with annotator agreement of Fleiss Kappa 0.88.The four scenes contain household objects and task-relevant object-state or relation goals.Source: §4.1 · pp. 5–6
• The evaluation measured executability, goal-conditions recall, success rate, cost, and error-correction count, comparing published LLM planners and re-planning baselines.ZERO-SHOT PLANNER and PROGPROMPT were compared without correction; LOCAL REPLAN and GLOBAL REPLAN were correction baselines.Source: §4.1 · p. 6

4.2 MAIN RESULTS

• Without correction, Tree-Planner reduces cost versus ITERATIVE-PLANNER by 53.29%; with correction, cost falls 74.36% versus LOCAL REPLAN and 92.24% versus GLOBAL REPLAN, with 37.99% and 40.52% fewer retries, respectively.The retry reductions are relative to LOCAL REPLAN and GLOBAL REPLAN, respectively.Source: §4.2 · p. 6
• Tree-Planner also outperforms ZERO-SHOT PLANNER and PROGPROMPT by 27.26% and 15.79% on SR, respectively.Increasing sampling hyperparameter N does not consistently improve performance.Source: §4.2 · pp. 6–7
• Tree-Planner surpasses the previous state of the art by 11.2% and 7.04% on Executability, 6.71% and 7.29% on GCR, and 1.29% and 3.65% on SR across the two settings.The reported VirtualHome results average three runs across four scenes.Source: §4.2 · p. 6, Table 1 · p. 7

5.1 TOKEN EFFICIENCY

• The token analysis estimates that TREE-PLANNER uses fewer tokens than ITERATIVE-PLANNER when N is below 197.72 under the stated assumptions.The derivation assumes the same number of steps and average action-token length across plans.Source: §5.1 · p. 7

5.2 PLAN SAMPLING

• GCRmax reaches 81.2% at its maximum and plateaus as N rises, while GCRavg does not consistently increase.GCRmax bounds TREE-PLANNER because success requires a correct sampled plan; increasing N can add token cost without raising the performance ceiling.Source: §5.2 · pp. 7–8, Figure 5 · p. 8

5.3 GROUNDED DECIDING

• Adding a gold plan significantly improves performance and reduces corrections from 1.85 to 1.21 at N=25 and 2.04 to 1.39 at N=50.The authors report a larger performance improvement at N=25 than at N=50.Source: Table 2 · p. 8, §5.3 · p. 8

5.4 ERROR ANALYSIS

• Missing correct plans account for 54.5% of errors, while grounded-deciding errors account for 45.5%.The authors identify plan sampling as a bottleneck despite its relatively high GCRmax.Source: Table 3 · p. 8, §5.4 · p. 8

Task Planning with Large Language Models

• Generate-based planning includes both whole-plan generation, which cannot dynamically modify plans after errors, and iterative action generation, which supports more flexible correction and grounding.The section also distinguishes the paper's focus on black-box LLMs from work using implicit representations.Source: §6 · p. 9

Tree-based Modeling for the Output of Large Language Models

• Unlike tree-of-thought and related approaches, TREE-PLANNER aggregates sampled paths into an action tree without repeated LLM calls.The paper characterizes this as an advantage for run-time and token efficiency.Source: §6 · p. 9

Generate then Select

• TREE-PLANNER selects at the action level using action trees, rather than reranking entire generated plans.The related work contrasts this with approaches that use external controllers, majority voting, or environmental state to select full plans.Source: §6 · p. 9

Efficient Inference with Large Language Models

• Unlike approaches that modify model architecture, decoding, or training, TREE-PLANNER reframes LLM planning to reduce repeated token consumption without additional training.Source: §6 · p. 9

• TREE-PLANNER is introduced as a framework for task planning with LLMs that addresses inefficiencies while aiming to maintain high performance.Source: §7 · p. 9
• Experiments in VirtualHome show that TREE-PLANNER outperforms strong baselines and achieves state-of-the-art performance.Source: §7 · p. 9
• The conclusion reports token-consumption and error-correction efficiency, alongside analyses of performance gains and potential bottlenecks.Source: §7 · p. 9

8 ETHICS STATEMENTS

• The authors report no ethical or social issues inherent to their approach beyond those inherited from large language models.Source: §8 · p. 10

A.1 ACTION SPACE

• The appendix identifies the action types available in the VirtualHome environment.Source: §A.1 · p. 14

28. PutBack

• A figure presents the distribution of plan length for PutBack.Source: Figure 6 · p. 14

A.2 PARTIAL OBSERVATION

• Under partial observation, an agent sees objects in its room that are not inside enclosed objects.An apple inside a closed refrigerator is not visible to the agent.Source: §A.2 · p. 14

A.3 OBSERVATION REPRESENTATION

• VirtualHome observations encode object states and inter-object relationships, which the authors convert into English sentences with rules.Source: §A.3 · p. 14

A.4 BASIC STATISTICS

• Gold plans average 8.13 actions, with the longest reaching 23.Figure 6 presents the plan-length frequency distribution.Source: §A.4 · p. 15
• The paper computes frequency histograms for actions and objects, depicting them in Figures 7 and 8; among actions, Find and Walk occur significantly more often than certain others.Source: §A.4 · p. 15, Figure 7 · p. 15
• Find and Walk occur at notably higher frequencies than some other actions.Figure 7 shows the action-frequency histogram.Source: Figure 7 · p. 15

B.1 HYPER-PARAMETER SEARCH

• Grounded Deciding uses temperature 0.7 and top-p 1.0; ITERATIVE-PLANNER uses temperature 0 and top-p 1.0.The sampling parameters were selected by grid search.Source: §B.1 · p. 15

B.2 BASELINE MODELS

• The ZERO-SHOT PLANNER baseline translates generated actions into admissible actions, while PROGPROMPT uses assert statements to incorporate environment feedback.The ZERO-SHOT PLANNER implementation uses a dynamically retrieved plan as a prompt exemplar.Source: §B.2 · p. 15

B.3 POST-PROCESSING

• Post-processing discards unparsable actions and uses BERT similarity to match generated action and object names to those available in the environment.For example, “telly” can be matched to the available object “TV.”Source: §B.3 · pp. 15–16

C.1 RESULTS BY PLAN LENGTH

• For plans longer than 15 actions, TREE-PLANNER SR is 22.22% (-42.5%) and EXEC. is 66.67% (-33.33%); corrections also increase with plan length.The table reports TREE-PLANNER with N=50 across plan sequence lengths.Source: Table 4 · p. 16, §C.1 · p. 16

C.2 RESULTS BY SCENE

• TREE-PLANNER maintains comparable performance across different scenes.Table 6 reports TREE-PLANNER with N=50 across scenes.Source: Table 6 · p. 16, §C.2 · p. 16

C.3 DIVERSITY OF SAMPLED PLANS

• Plan diversity varies approximately linearly with the number of sampled programs, with no reported homogenization of sampled plans.Figure 9 plots the number of sampled programs against the average number of different plans generated.Source: Figure 9 · p. 17, §C.3 · p. 17

C.4 UPPER LIMIT OF PLAN SAMPLING

• As N changes, the maximum and average SR of sampled plans follow a trend closely aligned with GCR.Figure 10 presents maximum and average SR for all sampled plans.Source: Figure 10 · p. 17, §C.4 · p. 17

C.5 EXPERIMENTAL RESULTS WITH BEST-FIRST SEARCH

• Language-guided weights aggregate action log-probabilities, environment-guided weights favor observable objects, and the hybrid balances both factors using α.The environment-guided method assigns higher weight to actions whose objects are all observable.Source: §C.5 · pp. 17–18
• Heuristic best-first search is more token-efficient but has lower SR than grounded deciding; combining its evaluation functions improves performance.Table 7 reports experimental results with best-first search.Source: Table 7 · p. 18, §C.5 · p. 18

C.6 PROPORTION OF NEW OBJECTS

• Figure 11 relates evaluated-task steps to the proportion of new objects; each point is a task, and the proportion is calculated using dataset gold plans.The passage describes the relationship but reports no specific outcome.Source: Figure 11 · p. 18, §C.6 · p. 18

D DETAILS ON TOKEN EFFICIENCY

• The token-efficiency derivation gives the boundary M · (|a| + 1) · N < (M − 1) · ρps + M · |a|.This is the stated condition in the derivation for N.Source: D DETAILS ON TOKEN EFFICIENCY · p. 19

E.1 INCORRECT DECIDING

• In the jacket task, the model chooses incorrectly at step two after failing to understand the required search order for a jacket and hanger.Figure 12 marks the chosen path in red and the correct path in green.Source: Figure 12 · p. 19, §E.1 · p. 19

E.2 ENVIRONMENT MISUNDERSTANDING

• The toilet task fails because the toilet is not movable, making the plan’s Pull action unsuccessful.The listed sequence includes “[Pull] <toilet>.”Source: §E.2 · p. 20

E.3 INCOMPLETE PLAN

• The alarm-clock plan leaves the clock in the character’s hand; it omits putting the clock back on the dresser to satisfy the task.The missing action is [PutBack] on the dresser.Source: §E.3 · p. 20

E.4 ILLOGICAL ERROR

• The illogical plan picks up shaving cream and after shave before a later action, leaving the character without a free hand at step nine.The explanation attributes the occupied hands to the two earlier pickups.Source: §E.4 · p. 20

E.5 SEMANTICALLY CORRECT

• In the computer task, the environment reports that the keyboard cannot be found even though the character is seated in front of the computer.The passage says this position indicates that the keyboard should be nearby.Source: §E.5 · p. 21

E.6 MORE RESULTS ON ERROR TYPES

• The error-type distribution is strikingly similar with and without correction, while correction improves avoidance of semantically correct errors during grounded deciding.Table 8 reports error types for TREE-PLANNER with N=25 and correction.Source: §E.6 · p. 21, Table 8 · p. 21

F.1 ITERATIVE-PLANNER

• The Iterative-Planner prompt includes action-format instructions, environment and action lists, an observation, and in-context task examples.The appendix illustrates these prompt components with household tasks.Source: §F.1 · pp. 21–22

F.2 PLAN SAMPLING

• The plan-sampling prompt provides action-format and environment information, an initial observation, and in-context examples.The prompt examples include tasks such as watching TV and turning on a light.Source: §F.2 · p. 23

F.3 GROUNDED DECIDING

• Grounded deciding receives an instruction, current observation, and action history, then selects among candidate subtasks; its example prompt also describes corrective choices after errors.The example presents five candidate subtasks for “Take nap.”Source: §F.1 · p. 22, §F.3 · pp. 24–25

G VISUALIZED ACTION TREE

• The appendix visualizes action trees for Take nap, putting on shoes, picking up spare change, cleaning the toilet, and placing an alarm clock in the bedroom.Table 9 is described as containing action trees for various tasks.Source: G VISUALIZED ACTION TREE · p. 25, Table 9 · p. 25, Figure 13 · p. 25