💻 computer science

Interleaved POMDP Planning for Multi-Object Search in Unknown Multi-Room Household Environments

The paper introduces Inter-POMDP, a novel interleaved planning algorithm that combines an LLM-informed high-level POUCT planner with an obstacle-aware low-level motion planner to efficiently and safely solve multi-object search tasks in unknown, cluttered household environments, demonstrating significant reductions in collisions, navigation steps, and detection counts compared to baseline methods.

Original authors: Ruochu Yang, Ziyi Xia, Huibo Zhang, Yatong Han, Yiming Zhao, Yingke Li, Fumin Zhang, Yorai Wardi, Mengxue Hou

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ruochu Yang, Ziyi Xia, Huibo Zhang, Yatong Han, Yiming Zhao, Yingke Li, Fumin Zhang, Yorai Wardi, Mengxue Hou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a robot detective sent into a giant, messy house you've never seen before. Your mission? Find three specific items: a cup, an apple, and a fork. But here's the catch: the house is full of hidden traps (unknown obstacles), the furniture is arranged in confusing ways, and you can't see everything at once. You have to guess where things might be while trying not to bump into chairs or walls.

This is exactly the challenge tackled in a new study by a team of researchers. They created a smart planning system called Inter-POMDP to help robots solve this "multi-object search" puzzle.

The Problem: Why Old Methods Stumble

Think of the old ways robots tried to find things as having two separate brains that never talked to each other.

Brain A (The Big Picture): This brain knew general rules, like "cups are usually near coffee makers." It would pick a room to search based on these guesses.
Brain B (The Navigator): This brain was responsible for actually walking the robot to that room.

The problem? Brain A would say, "Go to the kitchen!" without knowing that the path to the kitchen was blocked by a pile of books. Brain B would then try to walk there, get stuck, crash, or take a huge detour, and then just tell Brain A, "I failed." Brain A wouldn't learn from this; it would just pick the same bad path again. The paper argues that this "separate and sequential" approach is inefficient and leads to too many crashes and wasted steps.

The Solution: The "Interleaved" Dance

The researchers propose a new way where the two brains talk to each other constantly in a loop. They call this Interleaved POMDP Planning.

Here is how it works, using a creative analogy:

Imagine the robot is a detective with a Sherlock Holmes sidekick (the High-Level Planner) and a Scout sidekick (the Low-Level Planner).

The Sherlock Sidekick (High-Level): This sidekick uses a "magic book" (an AI language model) to guess where objects might be. It knows that "a cup is likely on a table" or "a fork is near a plate." It draws a map of probabilities—like a heatmap showing where the cup is most likely to be.
The Scout Sidekick (Low-Level): This sidekick is the one actually walking. It carries a "cloud of possibilities" (particle beliefs) about where hidden obstacles might be. It doesn't just see walls; it imagines invisible tripwires and bumps in the dark.
The Interleaved Loop:
- Sherlock says, "Let's check the kitchen!"
- The Scout tries to walk there but realizes, "Whoa, the path is super narrow and risky. It will take 80 steps and I might crash."
- Crucially, the Scout doesn't just say "No." It sends that "80 steps and high risk" info back to Sherlock.
- Sherlock updates its map: "Okay, the kitchen is a bad idea right now. Let's try the living room instead, even if the cup is less likely there, because the path is safe and short."

This back-and-forth happens over and over. The robot learns from its own mistakes in real-time, balancing where to look with how hard it is to get there.

What the Experiments Showed

The researchers tested this system in two ways: inside a computer simulation of a house with 8 to 12 rooms, and on a real robot in a real room. They compared their new system against two other methods (CSG-TL and COSPOMDP).

The results were quite clear in these tests:

Fewer Crashes: The new system crashed into obstacles up to 63% less often than the other methods. In the simulation, it managed to find the second and third objects with zero collisions, while the others still crashed occasionally.
Shorter Walks: The robot took up to 35% fewer steps to find the items. For example, in one specific test scenario (called "train 13"), finding the third object took the new robot only 14 ± 1 steps. The other robots took 80 ± 2 and 166 ± 5 steps respectively. That's a massive difference!
Smarter Looking: The robot didn't need to "look" (use its camera) as much. It reduced the number of times it had to stop and scan the room by up to 32%. By the third object, it only needed 1 ± 0.1 detection attempts, whereas others needed 2 to 4.

What They Don't Claim

It's important to note what this paper doesn't say. The researchers are careful to point out that their method is specifically for searching in unknown multi-room environments with unknown obstacles. They do not claim this solves every robot problem. For instance, they mention that their current setup focuses on 2D maps and doesn't yet handle the complex 3D manipulation of picking up objects from a cluttered table (though they suggest this as a future goal). They also note that while their system uses a "magic book" (LLM) for guessing, it still relies on the robot's own sensors to confirm where things actually are.

The Bottom Line

The paper suggests that by letting the "big picture" planner and the "walking" planner talk to each other constantly, robots can become much better at finding things in messy, unknown houses. They don't just guess; they learn from the difficulty of the path they are about to take. In their simulations and real-world tests, this "interleaved" teamwork made the robot faster, safer, and more efficient than the old ways of doing things.

Technical Summary: Interleaved POMDP Planning for Multi-Object Search in Unknown Multi-Room Household Environments

Problem Statement

The paper addresses the challenge of multi-object search for mobile robots operating in unknown, cluttered, multi-room household environments. Unlike deterministic settings, these environments present extensive uncertainty: target object locations are unknown, obstacles (e.g., chairs, tables) are unobserved, and the state space is vast due to the combinatorial nature of multiple objects and obstacles.

The core difficulty lies in Partially Observable Markov Decision Process (POMDP) planning. While POMDPs offer a principled framework for sequential decision-making under uncertainty, they are computationally intractable in large domains. The belief space dimensionality grows exponentially with the number of objects, and the lack of prior knowledge regarding obstacle locations makes long-horizon planning particularly difficult. Existing methods often fail to balance planning quality with efficiency, either ignoring geometric navigation constraints or relying on simple replanning strategies that lack robustness against physical-world uncertainties.

Methodology: Inter-POMDP

The authors propose Inter-POMDP, a novel interleaved POMDP planning algorithm that decomposes the problem into two interacting levels to manage complexity while maintaining robustness.

1. Hierarchical Decomposition

The framework separates the planning task into:

High-Level Planner (Semantic Reasoning): Operates on a semantic map ( $M_s$ ) to determine where to search. It selects abstract actions (Navigate, Search, Sense, Declare) based on object distributions.
Low-Level Planner (Geometric Reasoning): Operates on a topological map ( $M_p$ ) and occupancy grid ( $M_o$ ) to determine how to navigate safely. It handles primitive actions (move, turn) and models trajectory-level uncertainty caused by unknown obstacles.

2. Key Components

Belief Representations:
- High-Level: Uses histogram beliefs over discretized furniture locations. These are refined using LLM-informed semantic priors (object-object and object-furniture relations) to guide search toward promising areas (e.g., a cup is likely on a table).
- Low-Level: Uses particle beliefs to represent hypotheses about obstacle configurations. This allows the planner to reason about collision risks along candidate trajectories.
LLM Integration: Instead of training complex relation models, the system leverages Large Language Models (LLMs) to infer semantic relations (e.g., "coffee cup on kitchen table") and accumulate domain-specific knowledge online via a memory map.
Interleaved Communication (The Core Innovation):
- Unlike sequential hierarchical approaches where the high-level planner is unaware of execution costs, Inter-POMDP establishes a bidirectional feedback loop.
- The low-level planner computes navigation costs based on observed and hypothesized obstacles.
- These costs are propagated upward as domain knowledge to initialize the POUCT (Partially Observable Upper Confidence Tree) search at the high level.
- Specifically, the Q-values ( $Q(s,a)$ ) in the high-level tree search are initialized with low-level navigation costs rather than zero. This biases the search toward subtasks that are not only semantically promising but also geometrically feasible, preventing the selection of paths that are blocked or costly.

3. Algorithm Flow

The algorithm iteratively updates maps and beliefs:

The high-level planner selects a semantic subtask using POUCT, guided by LLM priors and low-level cost feedback.
The low-level planner executes motion primitives, updating particle beliefs and the topological map based on LiDAR/camera observations.
Navigation costs derived from the low-level execution are fed back to the high-level planner to prune redundant search branches and refine future action selection.

Key Contributions

Novel Interleaved Framework: The paper introduces the first interleaved POMDP planning algorithm for multi-object search in unknown multi-room environments. It designs a principled interaction between a semantic high-level planner and a geometric low-level planner.
Domain Knowledge Integration: The method effectively couples LLM-informed semantic reasoning with grounded navigation feedback. By treating uncertainty as physical (via particle beliefs) rather than purely semantic, it integrates navigation costs directly into the high-level decision-making process.
Robustness and Efficiency: The framework balances planning quality and efficiency by using particle beliefs for obstacle avoidance and LLM priors for search direction, avoiding the computational intractability of joint state-space planning.

Experimental Results

The authors evaluated Inter-POMDP against two baselines, CSG-TL and COSPOMDP, in both simulation (ProcTHOR environments with 8–12 rooms) and real-world deployments (a dual-arm mobile robot).

Collision Reduction: Inter-POMDP reduced collision counts by up to 63% compared to baselines. In many trials, it achieved zero collisions for the second and third objects, whereas baselines exhibited higher and less systematic collision rates.
Navigation Efficiency: The algorithm reduced navigation steps by up to 35%. In specific scenarios (e.g., finding the third object in complex scenes), it reduced steps by over 90% compared to CSG-TL.
Sensing Economy: Detection counts were reduced by up to 32%, indicating the robot directed its sensors more precisely to target locations rather than engaging in exploratory sensing.
Generalizability: The method maintained stable performance across diverse scenes without scene-specific tuning, whereas baselines showed high variance in performance depending on the environment layout.

Significance and Claims

The paper claims that Inter-POMDP provides a principled solution to the trade-off between planning quality and efficiency in large, unknown environments. By systematically incorporating grounded navigation information into the belief update process, the framework makes planning under uncertainty more robust.

The authors emphasize that their approach moves beyond simple replanning or LLM-based action re-selection by creating a continuous, iterative co-refinement of the global plan. The significance lies in demonstrating that low-level geometric constraints (obstacle uncertainty) can and should inform high-level semantic decisions (search order), leading to safer and more efficient autonomous search in realistic household settings. The work suggests that treating uncertainty as physical, rather than purely semantic, is critical for deploying fully autonomous household robots.