Research map / Large language models / Agents, code and math
Tru-POMDP: Task Planning Under Uncertainty via Tree of Hypotheses and Open-Ended POMDPs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Tru-POMDP, which builds LLM-generated hierarchical particle beliefs (Tree of Hypotheses), filters them with Bayesian particle updates, and plans with DESPOT using an LLM-written C++ rollout policy for open-ended kitchen rearrangement.
Problem
Task planning for home-service robots under open-ended uncertainty: ambiguous instructions, hidden objects, and open-vocabulary object types make the belief and action spaces effectively unbounded.
Approach
Use hierarchical LLM queries (target objects, placement goals, hidden locations) to build a weighted particle belief, update it with Bayesian particle filtering and re-query the LLM only when particle weight drops, then run DESPOT belief-tree search with a dynamically built action space and an LLM-synthesized C++ rollout policy.
Key results
- Tru-POMDP significantly outperforms LLM-based and LLM-tree-search baselines in success rate and reward on 300 kitchen rearrangement tasks; LLM-MCTS exceeds the 10-minute time limit in all tasks.
- ReAct and Reflexion achieve below 20% success on tasks with three or more unknown target objects, while prompt-augmented variants reach around 40%.
- Removing Bayesian filtering (w/o HBU) increases planning time up to three times due to frequent LLM belief regeneration.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Tru-POMDP instead of the compared LLM-based and LLM-augmented tree-search planners | Object rearrangement tasks across five RoboCasa kitchen environments · RoboCasa kitchen environments | success rate | Helped |
| Use Tru-POMDP instead of the compared LLM-based and LLM-augmented tree-search planners | Object rearrangement tasks across five RoboCasa kitchen environments · RoboCasa kitchen environments | cumulative reward | Helped |
| Use Tru-POMDP instead of LLM-MCTS | Object rearrangement tasks · RoboCasa kitchen environments | LLM token usage | Helped |
| Add structured task-domain descriptions to ReAct | ReAct on object rearrangement tasks · Object rearrangement tasks | success rate: below 20% -> around 40% | Helped |
| Add structured task-domain descriptions to Reflexion | Reflexion on object rearrangement tasks · Object rearrangement tasks | success rate: below 20% -> around 40% | Helped |
| Use Tru-POMDP instead of LLM-MCTS | Object rearrangement tasks · RoboCasa kitchen environments | planning time: 10-minute | Helped |
| Add explicit belief modeling instead of relying on a single most-likely hypothesis (ablation) | Tru-POMDP · Object rearrangement tasks under uncertainty | performance | Helped |
| Add Bayesian filtering and reuse the belief instead of regenerating a new particle belief at every step (ablation) | Tru-POMDP · High-difficulty object rearrangement tasks | performance | Helped |
| Add Bayesian filtering instead of regenerating beliefs at every step (ablation) | Tru-POMDP · Object rearrangement tasks | planning time: up to three times higher | Helped |
| Use the hierarchical Tree of Hypotheses instead of a flat, one-shot set of particle hypotheses (ablation) | Tru-POMDP · Object rearrangement tasks | performance | Helped |
| Use an LLM-generated rollout policy instead of a random legal-action policy (ablation) | Tru-POMDP belief tree search · Object rearrangement tasks | performance | Helped |
| Use explicit belief tree search instead of asking the LLM to choose the next action directly (ablation) | Tru-POMDP · Object rearrangement tasks | success rate | Helped |
Surprising findings
- A flat single-query particle belief (w/o TOH) performs worse than the single-hypothesis variant, attributed to LLM hallucination.
Limitations
- Tree of Hypotheses incurs computational overhead from multiple LLM calls.
- Assumes noise-free perception and deterministic actions, and conditional independence between object placements.
- Evaluated only on object rearrangement tasks in five kitchen layouts.
Experimental setup
Datasets: RoboCasa kitchen scenes
Benchmarks: RoboCasa kitchen rearrangement tasks (300 procedurally generated tasks)
Metrics: success rate cumulative reward step count planning time LLM token usage
Baselines: ReAct Reflexion ReAct* Reflexion* LLM-MCTS
Builds on: DESPOT ReAct Reflexion LLM-MCTS
Closest papers by meaning
- PO-PDDL: Learning Symbolic POMDPs from Visual Demonstrations for Robot Planning Under Uncertainty (NeurIPS 2026 · similarity 0.89)
- Introspective Planning: Aligning Robots' Uncertainty with Inherent Task Ambiguity (NeurIPS 2024 · similarity 0.88)
- Towards Reliable LLM-based Robots Planning via Combined Uncertainty Estimation (NeurIPS 2025 · similarity 0.88)
- PlanU: Large Language Model Reasoning through Planning under Uncertainty (NeurIPS 2025 · similarity 0.86)
- RoboCerebra: A Large-scale Benchmark for Long-horizon Robotic Manipulation Evaluation (NeurIPS 2025 · similarity 0.86)
- Simplifying Complex Observation Models in Continuous POMDP Planning with Probabilistic Guarantees and Practice (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.