PaperlayerView exact revision on arXiv

Source-linked AI summary

Large Language Models as Commonsense Knowledge for Large-Scale Task Planning

Zirui Zhao, Wee Sun Lee, David Hsu

arXiv:2305.14078v2cs.RO

TL;DR

Large-scale task planning must handle huge action spaces, long horizons, and partial observability. The paper combines an LLM commonsense world model with MCTS and an LLM heuristic, finding strong performance on complex tasks and proposing MDL as a guide for choosing model-based planning or direct policy use.

  • Problem

    Large-scale, partially observable planning is challenging because many objects and locations create vast action spaces and long planning horizons, while direct LLM policies degrade on novel, complex tasks.

  • Method

    LLM-MCTS uses an LLM to build a commonsense world model for MCTS and uses LLM policy outputs as heuristics to guide search.

  • Results

    LLM-MCTS outperforms L-Model and L-Policy for complex task planning; in multiplication, the model-based method achieves 100% accuracy for arbitrarily large numbers when its single-digit table is accurate.

  • Takeaways & Limitations

    MDL provides a useful guiding principle: using an LLM as a world model is likely better when the world description is substantially shorter than the policy description.

  • Takeaways & Limitations

    The theoretical analysis assumes iid training data and major assumptions about predictor classes, and error propagation may require separate analysis.

Abstract

from arXiv · show

Large-scale task planning is a major challenge. Recent work exploits large language models (LLMs) directly as a policy and shows surprisingly interesting results. This paper shows that LLMs provide a commonsense model of the world in addition to a policy that acts on it. The world model and the policy can be combined in a search algorithm, such as Monte Carlo Tree Search (MCTS), to scale up task planning. In our new LLM-MCTS algorithm, the LLM-induced world model provides a commonsense prior belief for MCTS to achieve effective reasoning; the LLM-induced policy acts as a heuristic to guide the search, vastly improving search efficiency. Experiments show that LLM-MCTS outperforms both MCTS alone and policies induced by LLMs (GPT2 and GPT3.5) by a wide margin, for complex, novel tasks. Further experiments and analyses on multiple tasks -- multiplication, multi-hop travel planning, object rearrangement -- suggest minimum description length (MDL) as a general guiding principle: if the description length of the world model is substantially smaller than that of the policy, using LLM as a world model for model-based planning is likely better than using LLM solely as a policy.

1 Introduction

Large-scale task planning faces huge search spaces and poor generalization on novel, complex tasks. The paper combines an LLM-derived commonsense world model with MCTS and an LLM heuristic, and uses MDL to guide when modeling or policy is preferable.

  • Motivation: Household planning is difficult because hundreds of movable items and locations create a huge search space.The robot must reason about likely object locations, spatial relations, traversal, and multi-step actions.
  • Existing approaches: L-Policy queries an LLM directly for next actions, but its generalization degrades on uncommon, complex tasks.LLMs use commonsense knowledge to avoid exhaustive search, yet direct action commitment remains limited.
  • LLM-MCTS: LLM-MCTS builds a commonsense world model, performs online MCTS, and uses LLM choices as heuristics rather than committing to them.The method combines model-based planning with policy-guided branch selection.
  • Evidence across tasks: GPT4 achieves 100% accuracy on single-digit multiplication and 99% on two-digit multiplication, but only 4% on four-digit multiplication.A model-based long-multiplication procedure can achieve 100% accuracy for arbitrarily large numbers when its single-digit table is accurate.
  • Guiding principle: MDL favors L-Model when its world-model description is shorter than the policy description, as in multiplication for sufficiently large n.The policy representation requires O(n102^n) bits, whereas the model-based representation has constant size.
  • Findings: LLM-MCTS combines L-Model and L-Policy and outperforms either alone for complex task planning, especially object arrangement.The LLM-induced world model can be sufficiently accurate, while search restricted near the policy improves performance.

2 LLM-MCTS: Monte Carlo planning with commonsense knowledge

LLM-MCTS combines an LLM-induced commonsense world model with an LLM-guided heuristic inside MCTS for large-scale planning under partial observation. It represents beliefs over object locations, translates goals and language outputs into executable planning components, and searches possible trajectories online.

  • 2.1 Task planning: LLM-MCTS uses an LLM-generated commonsense world model as a belief over states and uses MCTS for reasoned planning under partial observation.The task is modeled as a POMDP with states, actions, observations, transitions, rewards, and discounting.
  • 2.2 LLM as a world model: The initial belief represents movable objects, containers, surfaces, rooms, and their abstract spatial relationships in an object-centric graph.The belief is updated using actions and observations, while MCTS samples states from it during simulation.
  • 2.2 LLM as a world model: LLMs translate natural-language goals into formal tuples describing target objects, relations, and locations for MCTS.Compositional instructions become multiple tuples, such as placing an apple on a table and a plate inside a dishwasher.
  • 2.3 LLM as a heuristic policy: LLMs guide PUCT action selection by proposing next actions from the goal, observation, demonstrations, and action history, without directly committing those actions to execution.The sampled language outputs are converted into admissible actions and approximated as an empirical policy distribution mixed with a uniform distribution.
  • 2.4 LLM-MCTS: Each MCTS simulation samples a root state from the commonsense belief, selects actions using value estimates, visit counts, and the LLM policy, then updates the search tree.The search procedure repeatedly simulates trajectories and returns the action with the highest estimated value.

3 Experiments

Experiments evaluate LLM-MCTS on VirtualHome object-rearrangement tasks spanning in-distribution, compositional, novel, and shifted-apartment settings. GPT3.5-MCTS generally outperforms policy and search baselines, while ablations show that heuristic guidance and accurate state priors matter; failures mainly arise from policy, model, and translation errors.

  • 3.1 Experimental setup: VirtualHome provides a large, partially observable household environment with hundreds of interactive objects and containers for evaluating embodied task planning.The evaluation includes randomly generated object-rearrangement tasks with success measured by satisfying all target positions within 30 steps.
  • 3.1 Experimental setup: The evaluation spans simple, compositional, novel, and distribution-shifted apartment tasks, with compositional variants increasing the planning horizon.Training data contain randomly initialized scenes and expert trajectories, while test tasks include unseen combinations and differing object-position distributions.
  • 3.2 Results: GPT3.5-MCTS outperforms all compared baselines, especially in unseen situations, while UCT performs poorly because its search lacks commonsense guidance in a huge tree.On simple in-distribution tasks, all principal policies perform reasonably, but GPT3.5-MCTS still achieves the strongest performance.
  • 3.2 Results: On compositional tasks, GPT3.5-MCTS works far better than finetuned GPT2 and GPT3.5 policies as longer horizons expose compounding and replanning errors.MCTS supplements the policy with Q values and visit counts, encouraging exploration of alternative search directions.
  • 3.2 Results: Ablations show that removing heuristic policy guidance harms complex-task search, while a uniform state prior misleads value estimates and degrades planning.With full observability, GPT3.5-MCTS only slightly outperforms its partially observed counterpart, suggesting the LLM world model is practically sufficient.
  • 3.2 Results: Policy, model, and translation errors are primary failure causes, with policy errors accounting for most failures.Examples include inadmissible actions, repetitive behaviors, incorrect object positions, and translations that ignore VirtualHome interaction constraints.

4 LLM as a model or a policy?

The paper uses MDL to compare LLM-induced models and policies, finding that model-based planning is favored when world descriptions are shorter and search is available.

  • MDL selects between an LLM-induced model and policy by favoring the shorter description when both fit training data well.The formal bound relates expected loss to description length and training loss, but applying it here assumes both training losses are small.
  • The air-travel comparison represents flights as a sparse graph for shortest-path search, whereas the policy must encode route choices across city pairs.The analysis contrasts approximately n log n bits for models with n^2 log n for policies.
  • For air travel, the LLM model plus search consistently outperforms the LLM policy, with larger gaps for mid-size than large cities.Performance decreases with path length for both methods because longer paths require more flight predictions.
  • For object rearrangement, L-Model descriptions are shorter than L-Policy descriptions, especially as composed tasks increase policy complexity.MCTS decomposes composed tasks automatically, while L-Policy must learn the decomposition.
  • The policy may instead be preferable when its description is shorter than the model, as illustrated by tourist-itinerary recommendation.The paper presents this as a domain-dependent expectation rather than a universal rule.
  • When no efficient search algorithm is available, LLM-MCTS uses the LLM-induced policy as a heuristic to improve search efficiency.This combines the world model with policy-guided exploration rather than executing the policy’s selected actions directly.

5 Related work

Prior work addressed large-scale planning with classical search, learned policies, heuristics, and LLMs, while this paper combines LLM world modeling and heuristic guidance within MCTS.

  • Classical discrete-state planning methods become intractable for large-scale, long-horizon problems, motivating learning-based policies and search heuristics.Earlier learned policies and heuristics were reported as insufficiently generalizable to other domains.
  • Monte Carlo methods scale tree search through random sampling, while deep learning can bias action selection and reduce sampling.These combinations have been applied to large-scale planning scenarios.
  • LLMs have been used as few-shot policies, reasoning policies, heuristics, and transition functions, but transformer LLMs may be limited on multi-step reasoning.The paper positions its approach among these uses by employing LLMs for both world modeling and heuristic guidance.

6 Conclusion

The conclusion presents LLM-MCTS as a way to combine commonsense world modeling with policy-guided MCTS for complex daily-task planning, while noting runtime and bias concerns.

  • LLM-MCTS uses LLMs as both a commonsense world model and heuristic policy within MCTS for daily-task decision-making.MCTS explores action combinations using biased state and action sampling informed by the LLM.
  • For certain real-world domains, the paper suggests using an LLM as a model when the world description is substantially shorter than the policy description.This conclusion is supported by the paper’s analysis and empirical evidence.
  • LLM-MCTS runtime is hindered by requiring multiple LLM calls, despite substantially improved results.The paper identifies smaller models and knowledge distillation as possible future directions.
  • LLM biases may produce unfair or risky decisions in some domains, motivating further fairness and bias study.

A Virtualhome experimental environments

The VirtualHome environment represents household object rearrangement as a partially observable 3D setting with many interactive objects, containers, and surfaces.

  • VirtualHome is a 3D household simulator with partial observation, a large action space, and a long planning horizon.It supports object rearrangement tasks involving hundreds of interactive objects and containers.
  • The environment lets movable objects be placed in containers or on surfaces, while containers and surfaces are located in rooms.
  • The listed containers include appliances and cabinets, while surfaces include furniture and household work areas.The object inventory contains common household items such as food, books, tools, and electronics.

A.2 Tasks

The evaluation uses natural-language object-rearrangement tasks across task-composition and apartment-distribution settings, including seen and unseen environments.

  • Task setup: Agents search for household objects and move them to desired positions from natural-language instructions and partial observations.The task requires actions over objects, containers, and rooms in the environment.
  • Task types: The benchmark includes Simple, Novel Simple, Comp., and Novel Comp. tasks, varying whether object-location combinations are familiar and whether multiple objects must be moved.Compositional tasks involve longer plans than single-object tasks.
  • Apartment settings: Seen Apartments reuse training apartment environments with object positions randomly initialized from a commonsense distribution.The apartment map is shared with training environments, but object placements are randomized.
  • Apartment settings: Unseen Apartments use different household environments and sample object positions from a different commonsense distribution.Both the apartment structure and object-position distribution differ from training.

A.3 Goal specification

VirtualHome specifies rearrangement goals with predicates and supports navigation, object manipulation, and container interaction through grounded actions and partial observations.

  • Goal specification: Goals are represented as predicates such as Inside(apple, fridge):2 and Inside(plate, dishwasher):1, specifying object counts and destinations.Simple tasks move one object, whereas compositional tasks move multiple objects.
  • Action space: VirtualHome supports walking, grabbing, placing objects inside containers or on surfaces, and opening or closing containers.Actions are grounded to movable objects, containers, and rooms.
  • Action space: Walk(<item>) requires the item to be visible and moves the agent close to an object or inside a room.The action is translated into natural-language commands for LLM input.
  • Action space: Open(<item>) and Close(<item>) require the agent to be close to the target and change its opened state.These actions apply to movable objects or containers.
  • Action space: Put(<item1>, <item2>) places a held object inside a nearby open container, while PutBack(<item1>, <item2>) places it on a nearby surface.Both actions leave the agent holding no object and are converted to natural-language descriptions.
  • Observation representation: Partial observations list visible objects, relationships, and open or closed states, with relationships translated into natural-language descriptions for LLMs.The fine-tuned GPT2 policy additionally uses 3D object coordinates.

B Data gathering

Expert trajectories are collected in VirtualHome using regression planning with handcrafted heuristics and full environmental observation.

  • Expert trajectories: Experts search for solutions from goal predicates and full observations using handcrafted task-specific heuristics.Compositional tasks are decomposed into subtasks and completed progressively.

C Implementation details of belief in LLM-MCTS

LLM-MCTS represents states and beliefs through object relationships, querying the LLM to estimate uncertain object positions and updating beliefs from observations.

  • Belief implementation: The implementation details concern the state belief used in GPT3.5-MCTS, with source code planned for release.The section focuses on how beliefs are represented and updated.
  • State representation: States list uniquely identified objects, their states, and relationships such as Inside, On, Close, and Facing.VirtualHome provides 59 relationship types, which are retained in the state representation.
  • Belief representation: Beliefs parameterize object relationships with probability vectors, retaining only Inside and On because the LLM is queried for object positions.The vectors are affiliated with object representations.
  • Belief construction: The LLM predicts each object, container, and surface position, and sampling approximates the resulting position distribution.Movable-object positions are defined through Inside or On relationships, while containers and surfaces are positioned relative to rooms.
  • Belief update: New observations update beliefs after the transition function predicts the next state, setting observed relationships to one and masking incompatible alternatives.This update incorporates newly revealed object-position information during interaction.

D Visualized examples

The examples illustrate successful object-rearrangement trajectories and failure modes caused by policy, model, and translation errors.

  • Policy, model, and translation errors are identified as the primary causes of failed trajectories.
  • An inadmissible action such as walking to an unobserved cutlery fork can be translated to a semantically incorrect valid action and cause failure.
  • Incorrect object-location predictions can produce higher estimated Q-values during random rollouts, misleading exploration toward wrong states.
  • Successful trajectories complete multi-object rearrangement instructions through ordered walking, grabbing, opening, and placement actions.Examples include placing a plate in a kitchen cabinet and chicken in a microwave, or an apple on a kitchen table and toothbrush in a bathroom cabinet.
  • A failed trajectory can terminate when the plan attempts to open a kitchen cabinet before continuing subsequent object-placement actions.

E Runtime performance

The runtime section reports experimental conditions for one-step decisions and documents the prompts used for the policy, world model, and instruction interpretation.

  • Runtime performance is measured for one-step decisions on simple one-item object-rearrangement tasks from the training-data distribution.The setup uses 100 simulations for GPT3.5-MCTS and a 120-second runtime bound for UCT.
  • The heuristic-policy prompt asks the LLM to generate household-task plans from allowed actions and visible objects.
  • The commonsense world-model prompt asks the LLM to predict movable-object, container, and surface positions across apartment rooms.
  • A separate prompt converts natural-language goals into formal goal representations containing relations, objects, locations, and quantities.
Loading 2305.14078v2…