Hypothesis-driven Model Expansion under Uncertainty for Open-World Robot Planning
Source: arXiv:2607.06501 · Published 2026-07-07 · By Anxing Xiao, Hanbo Zhang, Tianrun Hu, David Hsu
TL;DR
This paper addresses the challenge of autonomous robot planning in open-world household environments, where robots lack complete knowledge about objects, their attributes, and action effects. Traditional closed-world planning relying on fixed symbolic models or static knowledge bases often fails in such settings due to unmodeled, unexpected situations. To overcome this, the authors propose HUME (Hypothesis-driven Uncertainty-aware Model Expansion), a novel framework that enables service robots to generate, verify, and iteratively refine hypotheses about missing environment knowledge. By treating these hypotheses as uncertain latent variables and integrating them into the planning process, HUME enables robots to actively select actions that both accomplish task goals and verify unknowns to reduce uncertainty.
HUME leverages foundation models, particularly large language and vision-language models, to generate initial hypotheses about object existence, attributes, and unknown action effects conditioned on the task and current partial model. It formulates planning as a Bayesian adaptive problem, augmenting symbolic world models with these uncertain hypotheses. The approach interleaves task execution with hypothesis verification actions, using perception and question answering for verification feedback. Iterative replanning incorporates verification results to refine the model. Extensive experiments in simulation (Block Processing World and AI2-THOR household tasks) and real-world tests with a Fetch robot demonstrate that explicit hypothesis representation and reasoning under uncertainty substantially improve planning success rates and task performance compared to baselines that lack model expansion or uncertainty modeling.
Overall, this work advances open-world robot planning by tightly combining foundation-model-driven knowledge expansion with classical and language-model-based planning under uncertainty, providing a practical framework for continual autonomous knowledge acquisition in human environments.
Key findings
- Explicit model expansion with hypotheses increases success rates by up to 69% in Block Processing World vs 28% without expansion (Fig. 6).
- Incorporating uncertainty-aware reasoning over hypotheses further improves success rates to 87% in Block Processing World and 82% in mobile manipulation tasks, outperforming deterministic expansion (Figs. 6, 8).
- Both classical PDDL planners and LLM-based planners benefit significantly from explicit and uncertainty-aware model expansion, narrowing performance gaps between them under increased task openness (Fig. 7).
- Uncertainty-aware expansion encourages the planner to schedule verification actions early, reducing execution risk from incorrect assumptions and improving success-weighted path length (SPL).
- The hypothesis generation module uses GPT-4.1 (April 2025) prompted on current symbolic state, missing predicates, and historical verification outcomes to produce object-centric hypotheses (object existence, attributes, action effects).
- Verification actions invoke perception modules (OWLv2 object detector) and vision-language models for hypothesis confirmation or rejection with direct sensory input, tightly integrating observation and reasoning.
- In real-world experiments on a Fetch mobile manipulator in a typical home setup, HUME enables the robot to discover unknown objects and effects and plan accordingly, validating the framework beyond simulation.
- Optimistic determinization of verification actions in classical planning allows tractable planning under uncertain hypotheses, with replanning triggered upon hypothesis refutation.
Threat model
The paper does not explicitly consider adversarial threats but addresses uncertainty arising from incomplete and underspecified world models. The 'adversary' can be conceptualized as the open-world unknowns and knowledge gaps that may cause planning failures. The robot cannot fully observe or know the true state or effects upfront and must actively resolve uncertainties. No malicious agents or direct adversarial manipulations are modeled.
Methodology — deep read
The paper formulates open-world robot planning as planning under incomplete symbolic models. The initial world model (M) consists of a predicate space, action space, and deterministic transitions, typically lacking critical information about some objects, attributes, or action effects compared to the unknown ground-truth world (M_gt).
Hypotheses represent factorized, object-centric missing knowledge (object existence, attributes, or action effects) with unknown truth values. An LLM-based hypothesis generator maps natural language instructions and the robot’s current symbolic state into a set of plausible hypotheses relevant to task goals. Historical observations and past hypothesis verification outcomes form the context, preventing redundant or cyclic hypothesis regeneration.
Each hypothesis includes metadata such as conditions for verification, represented as preconditions that must hold for verification to be feasible, and an API call that modifies the symbolic PDDL problem definition to augment the model. Verification conditions specify interacting or sensing states required, e.g., the robot must hold an object or be at a particular location.
Planning operates over an augmented state space pairing physical symbolic states with belief states over hypotheses' truth values. Verification actions are introduced into the action set, with each hypothesis having a dedicated sensing or interaction action. To enable classical planning tractability, verification actions—intrinsically non-deterministic—are determinized into optimistic branches that assume verification succeeds, prompting replanning if verification fails during execution.
A cost penalty is added to actions relying on unverified hypotheses, incentivizing the planner to perform verification actions early to minimize risk. Planning is performed using the Fast Downward classical planner or an LLM-based planner, enabling comparisons.
During execution, actions are passed to low-level robotic skills. Verification actions invoke perceptual modules—an object detector (OWLv2) for confirming existence hypotheses or vision-language models for attribute and effect verification from visual inputs.
Verification feedback updates the belief over hypotheses and the symbolic model representation. Hypotheses refuted by sensory data are marked false and excluded; new hypotheses are generated conditioned on the expanded history and updated model.
The iterative loop cycles between hypothesis generation, planning, execution, and verification, incrementally expanding and refining the robot's model of the world towards successful task completion under uncertainty.
Empirical evaluation covers two simulations: Block Processing World where the robot discovers effects of multiple processor blocks, and AI2-THOR-based mobile manipulation in household environments with unknown object locations and attributes. The real robot experiments involve a Fetch manipulator in a multi-room home environment using a 3D scene graph representation and modular perception pipeline.
This methodology enables a concrete example: given a task ('heat a chicken burger'), the system generates hypotheses like 'burger is inside fridge' or 'pressing microwave + button adds 10 seconds heat', plans an action sequence that includes verification actions (e.g., verifying burger location by opening fridge), executes and observes outcomes, and updates the knowledge and hypotheses accordingly, repeating until a feasible plan succeeds.
Technical innovations
- Formulating open-world robot planning as a Bayes-adaptive MDP over symbolic states augmented by uncertain object-centric hypotheses generated by foundation models.
- Integrating active hypothesis verification actions directly into the planning problem, enabling joint optimization of task achievement and knowledge acquisition under uncertainty.
- Applying an optimistic all-outcomes determinization scheme for verification actions to enable classical deterministic planning under model uncertainty with replanning triggered on refutations.
- Using foundation models (LLMs and VLMs) not just for passive knowledge generation but in a closed-loop system with hypothesis generation, verification via perception/question answering, and iterative model updating.
- Designing a two-level framework combining formal symbolic planners with hypothesis-driven model expansion and large language model-based planners under consistent uncertain knowledge representations.
Datasets
- AI2-THOR ProcTHOR houses benchmark — 5 houses, 8 tasks, 3 trials per house — public AI2-THOR simulation environment
- Block Processing World — synthetic simulated domain extending classic Blocks World — details in Appendix
- Real-world household environment scanned for Fetch robot deployment — not publicly released
Baselines vs proposed
- Formal Planner w/o Model Expansion: Success Rate = 28% (Block Processing World) vs Formal Planner w/ Uncertain Expansion: 87%
- LLM Planner w/o Model Expansion: Success Rate = 0% vs LLM Planner w/ Uncertain Expansion: 69% (Block Processing World)
- Formal Planner w/ Model Expansion (deterministic): Success Rate = 42% vs with Uncertain Expansion: 87% (Block Processing World)
- LLM Planner w/ Model Expansion (deterministic): Success Rate = 36% vs with Uncertain Expansion: 69% (Block Processing World)
- Similar trends for Success-weighted Path Length (SPL) with uncertainty-aware expansion outperforming other methods (Fig. 6, Fig. 8)
- In mobile manipulation simulations, formal planner w/ uncertain expansion achieves 82% success vs 49% without uncertainty handling (Fig. 8)
Figures from the paper
Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.06501.
Fig 1: Illustration of a service robot operating in an open-world scenario.
Fig 2: High-level idea. It combines foundation-model priors as hypotheses
Fig 3: Overview of the HUME. The robot iteratively generates hypotheses to expand its model, plans with a model augmented by uncertain hypotheses,
Fig 4 (page 1).
Fig 5 (page 1).
Fig 6 (page 1).
Fig 7 (page 1).
Fig 8 (page 1).
Limitations
- Relies on accurate initial symbolic models capturing predicate vocabulary and base action definitions; poor initial models may limit hypothesis usefulness.
- Assumes reliable skill execution and sensing capabilities when verifying hypotheses, excluding low-level failures and partial observability issues.
- Verification actions determinization employs optimistic assumptions and replanning, which may not fully capture real-world uncertainty or handle catastrophic verification failures gracefully.
- The hypothesis generator depends on LLM capabilities and prompt design, which may limit hypothesis quality or completeness in highly novel environments.
- Experiments largely focus on household/domestic tasks; generalization to other robot domains remains untested.
- Real-world study is limited to a single robotic platform and environment; scalability and robustness in larger-scale or more dynamic settings are not evaluated.
Open questions / follow-ons
- How to scale hypothesis generation and verification for long-horizon tasks with combinatorial explosion of hypotheses?
- Can end-to-end learning or reinforcement learning approaches be integrated with symbolic hypothesis-driven planning to improve efficiency?
- How to better incorporate execution uncertainty and partial observability into the verification and replanning process?
- How robust is the system to failures or inaccuracies in foundation model outputs and perception modules in varied real-world conditions?
Why it matters for bot defense
For bot-defense and CAPTCHA practitioners, this work presents a systematic approach to autonomous knowledge acquisition and verification under uncertainty, tightly integrating large foundation models with structured reasoning. Similar techniques could inspire bot detection or challenge generation systems that maintain uncertain hypotheses about bot behavior or environment interaction and actively verify them through adaptive tests rather than static rules. The explicit modeling of uncertain claims and their active verification via interaction parallels challenges in differentiating scripted bots from humans. Moreover, the iterative generate-verify-update framework aligns with active learning and adaptive challenge design strategies relevant for CAPTCHA robustness against evolving adversaries. However, the robotic physical environment focus may require abstraction to be applied in web or network security settings.
Cite
@article{arxiv2607_06501,
title={ Hypothesis-driven Model Expansion under Uncertainty for Open-World Robot Planning },
author={ Anxing Xiao and Hanbo Zhang and Tianrun Hu and David Hsu },
journal={arXiv preprint arXiv:2607.06501},
year={ 2026 },
url={https://arxiv.org/abs/2607.06501}
}