Teaching Robots to Tidy Up: Planning Under Uncertainty in Multi-Room Environments
How hierarchical planning with object-oriented beliefs enables robots to rearrange objects when they can't see everything at once.
Series context & running example. Within the Planning Under Uncertainty series, HOO-POMDP is the abstraction strategy — shrink a large POMDP through factorization and hierarchy until a principled planner can handle it; the companion post (Part 4: GammaZero) takes the complementary learning strategy. The series' running example is warehouse-delivery under partial observability; HOO-POMDP was developed for the MultiRoomR benchmark (described later), the same idea at robotics scale — object-oriented states, partial observability across rooms instead of zones — and the reasoning transfers directly back to the warehouse from Part 1.
The Challenge: A Messy House, A Limited View
Imagine asking a robot to tidy up your home. Books need to go to bookshelves, mugs to the kitchen, toys to the bedroom. Simple enough for a human. Catastrophically hard for a robot.
Why? The robot can only see what's directly in front of it. When it starts in the living room, it doesn't know where objects in the bedroom are. It doesn't even know which objects are in the bedroom. It needs to search, remember, plan, and act—all while dealing with the fact that its object detector fails 40% of the time.
This is the multi-object rearrangement problem under partial observability. And it gets worse.
- Blocked paths: A book on the floor blocks the doorway to the bedroom
- Blocked goals: A bowl sits exactly where the mug needs to go
- Swap scenarios: Object A is where B should be, and B is where A should be
- Detector failures: The robot looks right at an object and doesn't see it
Existing approaches fall into two camps, and both struggle:
| Approach | Handles Uncertainty | Handles Blocked Paths | Scales to Many Objects | Optimal Planning |
|---|---|---|---|---|
| End-to-End RL | Implicit | No | No | No |
| Greedy/Heuristic | No | No | Yes | No |
| HOO-POMDP (Ours) | Yes | Yes | Yes | Yes |
Comparison of approaches to multi-object rearrangement. Only HOO-POMDP handles all challenges in a principled, unified framework.
The Core Insight: Two Levels of Abstraction
The key insight behind HOO-POMDP is a separation of concerns:
Don't make the strategic planner worry about how to physically pick up objects. Don't make the low-level controller decide which room to explore next.
This hierarchical decomposition is the "H" in HOO-POMDP:
Perception
RGB + Depth
→ Object detections
Belief Update
Update probabilities
per object
Abstraction
Continuous → Discrete
Sample locations
POMDP Planner
Select sub-goal
(Move, PickPlace)
Low-Level Policy
A* + RL
Primitive actions
The HOO-POMDP pipeline: from raw perception to primitive actions, through hierarchical abstraction.
Level 1: The Strategic Planner (POMDP)
At the top level, a POMDP planner reasons about what to do next under uncertainty:
- Should I search for the missing lamp, or move the mug I've already found?
- Should I verify that uncertain plate detection, or trust it and proceed?
- The book is blocking the doorway—should I move it first, even though it's not my current target?
The planner works with abstract actions: Move(A→B), Rotate(θ), PickPlace(Object, Goal). It doesn't care how these happen—just that they do.
Level 2: The Low-Level Policies
Each abstract action maps to a specialized policy:
- Move/Rotate: A* pathfinding on the known occupancy map
- PickPlace: Three-stage pipeline—RL to pick, A* to navigate, RL to place
These policies handle the continuous control problem: motor commands, collision avoidance, precise manipulation.
Object-Oriented Beliefs: The Scalability Trick
The "OO" in HOO-POMDP stands for Object-Oriented. This is crucial for scalability.
A naive POMDP would maintain a probability distribution over all possible world states. With 10 objects, each potentially at 100 locations, that's 10010 states. Intractable.
The object-oriented formulation factors the belief by object:
Object Independence Assumption
The probability of observing object A doesn't depend on where object B is (conditioned on A's state). This lets us maintain separate belief distributions for each object: b = b₁ × b₂ × ... × bₙ
Now we have n × 100 states instead of 100n. Linear instead of exponential.
O1 (Mug) Belief
High confidence
O5 (Lamp) Belief
Needs exploration
O2 (Book) Belief
Blocking path!
Object-factored beliefs: each object maintains an independent probability distribution over locations. This enables scalable planning with 10-20 objects.
The Abstraction Layer: Bridging Continuous and Discrete
The POMDP planner needs discrete states and actions. But the real world is continuous—objects can be anywhere, not just at grid cells.
The abstraction layer converts the continuous belief state into a discrete representation suitable for planning:
-
loc_i: Most likely location from belief -
pick_i: Location from which robot can pick (sampled from belief) -
place_locs: Candidate locations to place (goal + nearby receptacles) -
is_held: Is the robot currently holding this object? -
at_goal: Is the object at its goal location?
The abstraction layer converts continuous belief probabilities into discrete pick/place options for the POMDP planner.
This is where blocked paths and goals get handled naturally. If an object is blocking a path:
- The abstraction layer detects that the robot can't reach certain locations
- Those locations are marked as unreachable in the abstract state
- The planner is forced to find an alternative—which means moving the blocking object first
Results: What Works and What Breaks
We evaluated HOO-POMDP against multiple baselines across three datasets of increasing difficulty.
Main Results: HOO-POMDP vs. Baselines
Scene success: all objects must reach goals. HOO-POMDP consistently outperforms baselines. VRR (pure RL) fails completely at scale. MSS cannot handle blocked paths (NC = Not Computable).
Object success: partial progress counts. HOO-POMDP maintains 36-71% object success even as complexity increases, while baselines deteriorate rapidly.
Ablation: What Matters Most?
Ablations reveal what matters: (1) Hierarchy is essential—flat POMDP fails. (2) Lookahead is critical—greedy planning finds no solutions. (3) Performance gap to oracle is small, showing robustness to detector failures.
The MultiRoomR Benchmark
Existing benchmarks don't test the hard cases. RoomR has single rooms with most objects visible. We introduce MultiRoomR:
| Feature | RoomR | ProcThor | MultiRoomR (Ours) |
|---|---|---|---|
| Rooms | 1 | 2 | 2-4 |
| Objects | 5 | 5 | 10-20 |
| Initial Visibility | ~60% | ~40% | 10-30% |
| Blocked Paths | No | No | 50% of scenes |
| Configurations | 25 × 40 | 125 × 80 | 400 |
MultiRoomR benchmark: designed to test severe partial observability, large object counts, and complex spatial dependencies.
Scaling Performance
HOO-POMDP (green) stays close to the Oracle performance (blue dashed) across all complexity levels. Baseline methods (orange) degrade rapidly.
Example Scenario: Blocked Paths
Objects 1-6 each have colored paths to their goals (dashed squares). Object 3 (red path) is sitting on Object 1's goal location. The planner must reason: "Move Object 3 first, then Object 2 can clear the corridor, then Object 1 can reach its goal."
A real scenario from our benchmark. HOO-POMDP correctly identifies the dependency chain and computes the optimal execution order.
Lessons for Other Research
Beyond the specific results, HOO-POMDP demonstrates principles that generalize:
1. Hierarchy Enables Tractable Abstraction
POMDP planning is exponentially hard in the action space. But most planning problems have natural hierarchies: strategic decisions (what to do) vs. execution details (how to do it). By separating these, each level becomes tractable.
Applicable when: Your problem has actions at multiple time scales, or strategic choices that are independent of execution details.
2. Factor Your Beliefs by Entity
The object-oriented belief representation—treating each object's location as independent—is a strong assumption but enables dramatic scalability. Similar factorizations work whenever your entities don't directly interact continuously.
Applicable when: You have multiple similar entities (objects, agents, tasks) whose states are conditionally independent given observations.
3. Abstraction Bridges Continuous and Discrete
Real-world problems are continuous. Formal planning methods need discrete states. The abstraction layer in HOO-POMDP shows one way to bridge this: sample from continuous distributions to create discrete action candidates.
Applicable when: You want to apply discrete planning methods (MCTS, POMDP solvers) to continuous domains.
4. Robustness to Perception Errors Through Belief Updates
HOO-POMDP doesn't need a perfect detector. The belief update mechanism naturally handles false negatives (didn't see the object) and false positives (saw it in wrong place). This robustness comes "for free" from the POMDP formulation.
Applicable when: Your perception system is noisy or unreliable, and you need planning that degrades gracefully.
Limitations and Open Questions
- Object independence assumption: Fails in cluttered environments where objects occlude each other or interact physically. Relaxing this is non-trivial.
- Unknown object classes: HOO-POMDP needs to know which object classes to search for. Handling truly novel objects requires additional machinery.
- Low-level policy failures: Most failures come from the RL pick/place policies, not the high-level planner. Better low-level policies would improve overall performance.
- Computation time: MCTS search adds latency. Real-time applications might need faster approximate methods.
Where HOO-POMDP runs out — and why the next chapter exists
Computation time deserves its own treatment because it's where HOO-POMDP's success becomes its own ceiling. At 20 objects, the planner spends nearly half an hour per task. The abstraction layer is doing its job — the planner only reasons about a handful of object slots at any time, not the full state — but the inner loop is still POMCP. Every decision still runs MCTS. Every leaf is still evaluated by a random rollout that simulates forward until termination. The rollouts are noisy enough that the planner needs many simulations per decision to get a stable value estimate, and the time per decision grows with both the simulation budget and the depth of the rollouts.
This bottleneck is structural. Better abstractions would help at the margin, but they can't change the fact that POMCP's leaf evaluation is the dominant cost. To break through, the rollout itself has to change — from "simulate a random trajectory and average the return" to "predict the value directly with a learned function." That swap is exactly what AlphaZero did for board games: replace random rollouts with a neural value head, replace uniform priors with a learned policy head. Applied to POMDPs, with a representation that handles variable-size belief spaces, it becomes GammaZero.
Read HOO-POMDP as the achievable ceiling of principled abstraction with classical search inside. Read the next post as what happens when that inside is replaced.
The ceiling, on the foggy warehouse
Foggy warehouse scaling from 4 to 20 objects. The abstraction layer keeps things tractable in state-space terms; the rollouts make decisions expensive.
The blue curve is real; the green is what comes next. The HOO-POMDP per-task time scales as plan depth times particles times random rollouts at every leaf. The state-space abstraction reduces one factor; the rollouts dominate the others. GammaZero replaces those rollouts with a single learned forward pass — the network predicts what the rollout average would have been, so the per-decision cost stops growing with rollout count.
Summary
HOO-POMDP shows that multi-object rearrangement under partial observability is tractable with the right decomposition:
- Hierarchical planning separates strategic decisions from execution
- Object-oriented beliefs enable scalable uncertainty tracking
- Abstraction bridges continuous perception and discrete planning
- POMDP formulation provides principled handling of detector failures
The result: a system that handles 20 objects across 4 rooms with blocked paths—scenarios where baselines completely fail.
Paper: "Hierarchical Object-Oriented POMDP Planning for Object Rearrangement"
Authors: Rajesh Mangannavar, Alan Fern, Prasad Tadepalli (Oregon State University)
arXiv: 2412.01348