# Tru-POMDP: Task Planning Under Uncertainty via Tree of Hypotheses and Open-Ended POMDPs

arXiv: https://arxiv.org/abs/2506.02860 · HTML: https://mlsanity.com/paper/2506.02860/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 37 references that are in the map.
- First posted on arXiv 3 Jun 2025.

## Builds on (most cited first, 27 of 27)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Code as Policies: Language Model Programs for Embodied Control](https://mlsanity.com/paper/2209.07753/) (2022)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [ProgPrompt: Generating Situated Robot Task Plans using Large Language Models](https://mlsanity.com/paper/2209.11302/) (2022)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [RoboCasa: Large-Scale Simulation of Everyday Tasks for Generalist Robots](https://mlsanity.com/paper/2406.02523/) (2024)
- [Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners](https://mlsanity.com/paper/2307.01928/) (2023)
- [Large Language Models as Commonsense Knowledge for Large-Scale Task Planning](https://mlsanity.com/paper/2305.14078/) (2023)
- [Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning](https://mlsanity.com/paper/2305.14909/) (2023)
- [AdaPlanner: Adaptive Planning from Feedback with Language Models](https://mlsanity.com/paper/2305.16653/) (2023)
- [Agent-FLAN: Designing Data and Methods of Effective Agent Tuning for Large Language Models](https://mlsanity.com/paper/2403.12881/) (2024)
- [Watch Every Step! LLM Agent Learning via Iterative Step-Level Process Refinement](https://mlsanity.com/paper/2406.11176/) (2024)
- [ISR-LLM: Iterative Self-Refined Large Language Model for Long-Horizon Sequential Task Planning](https://mlsanity.com/paper/2308.13724/) (2023)
- [Agent Planning with World Knowledge Model](https://mlsanity.com/paper/2405.14205/) (2024)
- [Dynamic Planning with a LLM](https://mlsanity.com/paper/2308.06391/) (2023)
- [Learning From Failure: Integrating Negative Examples when Fine-tuning Large Language Models as Agents](https://mlsanity.com/paper/2402.11651/) (2024)
- [SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledge](https://mlsanity.com/paper/2308.12682/) (2023)
- [InterPreT: Interactive Predicate Learning from Language Feedback for Generalizable Task Planning](https://mlsanity.com/paper/2405.19758/) (2024)
- [Interactive Planning Using Large Language Models for Partially Observable Robotics Tasks](https://mlsanity.com/paper/2312.06876/) (2023)
- [Grounding LLMs For Robot Task Planning Using Closed-loop State Feedback](https://mlsanity.com/paper/2402.08546/) (2024)
- [SelfGoal: Your Language Agents Already Know How to Achieve High-level Goals](https://mlsanity.com/paper/2406.04784/) (2024)
- [AutoGPT+P: Affordance-based Task Planning with Large Language Models](https://mlsanity.com/paper/2402.10778/) (2024)
- [RoboHorizon: An LLM-Assisted Multi-View World Model for Long-Horizon Robotic Manipulation](https://mlsanity.com/paper/2501.06605/) (2025)
- [From Words to Actions: Unveiling the Theoretical Underpinnings of LLM-Driven Autonomous Systems](https://mlsanity.com/paper/2405.19883/) (2024)
- [LLM-Guided Probabilistic Program Induction for POMDP Model Estimation](https://mlsanity.com/paper/2505.02216/) (2025)

## Built on by (most cited first, 4 of 4)

- [Learning POMDP World Models from Observations with Language-Model Priors](https://mlsanity.com/paper/2605.13740/) (2026)
- [Actively Resolving Contextual Uncertainty for Underspecified Tasks in Natural Language](https://mlsanity.com/paper/2609.30428/) (2026)
- [PO-PDDL: Learning Symbolic POMDPs from Visual Demonstrations for Robot Planning Under Uncertainty](https://mlsanity.com/paper/2606.15654/) (2026)
- [Beyond Memory: Harnessing Long-Horizon Agents with Explicit Belief States](https://mlsanity.com/paper/2610.01415/) (2026)

## Abstract (arXiv)

Task planning under uncertainty is essential for home-service robots operating in the real world. Tasks involve ambiguous human instructions, hidden or unknown object locations, and open-vocabulary object types, leading to significant open-ended uncertainty and a boundlessly large planning space. To address these challenges, we propose Tru-POMDP, a planner that combines structured belief generation using Large Language Models (LLMs) with principled POMDP planning. Tru-POMDP introduces a hierarchical Tree of Hypotheses (TOH), which systematically queries an LLM to construct high-quality particle beliefs over possible world states and human goals. We further formulate an open-ended POMDP model that enables rigorous Bayesian belief tracking and efficient belief-space planning over these LLM-generated hypotheses. Experiments on complex object rearrangement tasks across diverse kitchen environments show that Tru-POMDP significantly outperforms state-of-the-art LLM-based and LLM-tree-search hybrid planners, achieving higher success rates with significantly better plans, stronger robustness to ambiguity and occlusion, and greater planning efficiency.