💻 computer science

POMDP-based Object Search with Growing State Space and Hybrid Action Domain

This paper proposes GNPF-kCT, a novel online POMDP solver that integrates neural process filtering, k-center clustering, and belief tree reuse to efficiently guide mobile robots in locating objects within complex 3D indoor environments, outperforming both traditional POMDP baselines and state-of-the-art LLM-based methods in simulation and real-world tests.

Original authors: Yongbo Chen, Hesheng Wang, Shoudong Huang, Hanna Kurniawati

Published 2026-04-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yongbo Chen, Hesheng Wang, Shoudong Huang, Hanna Kurniawati

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 walking into a messy, cluttered living room. Your mission? Find a specific blue snack box hidden somewhere on a table. But here's the catch: you can't see the whole table at once. There are coffee cups, laptops, and books blocking your view. Some items might be hiding the snack box completely. You don't know exactly where everything is, and you can't just "look" everywhere at once because your camera has a limited field of view.

This paper presents a new "brain" for robots to solve this exact problem. The authors call their system GNPF-kCT. Let's break down how it works using some everyday analogies.

1. The Problem: The "Blind Detective"

Most robots are like detectives who only look at what's directly in front of them. If a cup blocks the snack box, they might give up or spin in circles randomly.

The Challenge: The robot needs to figure out: "Is that cup hiding the box? Should I move the cup? Should I move my head to look from a different angle?"
The Old Way: Previous methods were either too rigid (only looking at a few pre-set spots) or too slow (trying to calculate every possible movement in a continuous world).

2. The Solution: A Smart, Adaptive Brain

The authors treat this as a game of "20 Questions" where the robot is constantly guessing, checking, and updating its map of the world. They use a mathematical framework called POMDP (Partially Observable Markov Decision Process). Think of this as the robot's internal "belief system."

Here are the three "superpowers" their new brain has:

A. The "Gut Feeling" Filter (Neural Processes)

Imagine you are in a huge warehouse looking for a needle. You could try to pick up every single object, but that would take forever.

The Innovation: The robot uses a "Neural Process" (a type of AI) to act like a seasoned detective with a gut feeling. Before it even tries to move, this AI looks at the scene and says, "Hey, moving the robot's head to the left is probably useless right now. But moving it up and looking down? That looks promising."
The Result: It filters out the "bad ideas" (useless actions) instantly, saving the robot from wasting time on dead ends.

B. The "Grouping" Strategy (K-Center Clustering)

Once the robot has a list of "promising" moves, there are still thousands of tiny variations (move 1 inch left, move 1.1 inches left, etc.).

The Innovation: Instead of testing every single inch, the robot groups these moves into "neighborhoods" (hyperspheres). It picks a representative move from each neighborhood to test.
The Analogy: Imagine you are looking for a lost key in a park. Instead of checking every single blade of grass, you check the "center" of the flower beds, the "center" of the benches, and the "center" of the paths. If you find something interesting in a flower bed, then you zoom in and check the specific flowers there. This makes the search incredibly fast.

C. The "Memory Reuse" Trick (Belief Tree Reuse)

This is the most clever part. Usually, when a robot sees something new (like a new chair it didn't know was there), it has to throw away its entire mental map and start over.

The Innovation: GNPF-kCT is like a human who remembers their previous steps. If the robot moves a cup and sees a new book, it doesn't delete its entire memory of the room. It just "grows" its existing map to include the new book.
The Result: It doesn't have to re-calculate everything from scratch. It keeps its progress, making it much faster at solving complex puzzles where new obstacles appear as you go.

3. The "Guessed Target" Strategy

Sometimes the robot doesn't know exactly what the target looks like or where it is.

The Trick: The robot creates a "ghost" version of the target object in its mind. It assumes, "Okay, the target is probably here, and it's probably this size." It then plans its moves to find this "ghost." As it gets real data, it updates the ghost. If the ghost turns out to be wrong, the robot quickly adjusts. It's like playing "Hot and Cold" with a friend who is hiding an object; you start with a guess and refine it as you get closer.

4. Real-World Results

The authors tested this on real robots (Fetch and Stretch) in both computer simulations and actual office environments.

The Outcome: Their robot found objects faster and more reliably than other top-tier methods, including those powered by Large Language Models (LLMs).
Why LLMs Struggled: The paper notes that while AI chatbots are great at writing stories, they aren't great at the physics of moving a robot arm to push a cup out of the way without knocking over a vase. The robot's "math brain" (POMDP) is better at the physical nitty-gritty of moving through a cluttered room.

Summary

In simple terms, this paper teaches a robot how to be a smart, patient explorer.

It uses AI to guess which moves are worth trying.
It groups similar moves to test them efficiently.
It remembers its progress even when the room changes, so it doesn't have to start over.
It physically interacts with the world (moving cups, changing angles) to find what's hidden.

It's the difference between a robot that spins in circles confused by a messy room, and a robot that calmly moves a book, checks behind it, and says, "Aha! There it is."

1. Problem Definition

The paper addresses the challenge of mobile robot object search in complex, cluttered indoor environments (e.g., homes with shelves, tables, and beds). The specific difficulties include:

Partial Observability: Objects are often occluded by furniture or other items.
Growing State Space: As the robot explores, it discovers new objects, causing the state space to expand dynamically.
Hybrid Action Domain: The robot must perform both continuous actions (adjusting base position, lift height, and camera pan/tilt for optimal viewing) and discrete actions (declaring an object as a target/obstacle or removing an obstacle).
Uncertainty: Localization errors, limited fields of view (FOV), and imperfect perception make the environment partially observable.

The goal is to find an optimal policy to locate and retrieve a target object (given only a photo) by strategically moving, observing, and interacting with the environment (removing obstacles).

2. Methodology: GNPF-kCT

The authors propose a novel online solver named GNPF-kCT (Growing Neural Process filtered k-center clustering Tree). It frames the problem as a Partially Observable Markov Decision Process (POMDP) with a hybrid action space and a growing state space.

A. POMDP Formulation

State Space ( $S$ ): Includes robot configuration (base pose, lift, head angles) and object states (pose, size, move-ability, and grid-based belief). Crucially, the state space grows as new objects are detected ( $S_k = S_{k-1} \times \Delta S_{k-1}$ ).
Action Space ( $A$ ): A hybrid domain $A = A_c \times A_d$ $A = A_{c} \times A_{d}$ .
- $A_c$ : Continuous actions for robot configuration (position, orientation, lift).
- $A_d$ : Discrete actions for declaring objects or removing them.
Observation Space ( $O$ ): Discrete updates to a "grid world" representing the log-odds of object presence on specific surfaces.
Guessed Target Object: To handle scenarios where the target is not yet detected, the system introduces a "guessed" target object with a grid-world model. This allows the robot to explore potential locations even without visual confirmation, updating beliefs via log-odds similar to occupancy grid mapping.

B. The GNPF-kCT Solver

The solver integrates three key mechanisms to handle high dimensionality and complexity:

Neural Process (NP) Filtering:
- Motivation: In continuous action spaces, many sampled actions are physically inefficient or impossible.
- Mechanism: A pre-trained Neural Process network predicts the "score" (probability of success) of primitive actions based on the current state, point cloud data, and grid world.
- Theorem 1: Uses a probabilistic bound ( $\mu(a) > \beta^*\sigma(a)$ ) to filter out actions with low probability of updating the target's belief, effectively reducing the search space to a feasible region $X$ .
k-Center Clustering Tree (Hypersphere Discretization):
- Mechanism: The remaining high-dimensional continuous actions are clustered using k-center clustering. Each cluster is represented as a hypersphere with a center and radius.
- Refinement: During Monte Carlo Tree Search (MCTS), if a hypersphere is visited frequently, it is recursively split into smaller clusters (refined) to increase resolution, ensuring the search converges toward the optimal action.
Belief Tree Reuse:
- Challenge: Traditional solvers must rebuild the entire belief tree when the state space grows (new objects detected), which is computationally expensive.
- Solution: GNPF-kCT maintains history tuples (state history, action-observation history, rewards, and depth vectors). When new objects are detected, the solver reuses the existing belief tree structure, updating only the relevant particles and pruning branches related to the new state. This avoids full reconstruction.
Revised UCB Strategy:
- The action selection in MCTS uses a modified Upper Confidence Bound (UCB) that incorporates the hypersphere radius (for Lipschitz continuity) and a Belief Distance (BD) term to account for the growing state space and belief updates.

3. Key Contributions

Realistic POMDP Formulation: A complete model for object search in 3D environments with a growing state space and hybrid action domains, incorporating a "guessed target" strategy for better exploration.
Novel Solver (GNPF-kCT): An efficient online solver combining Neural Process filtering (to prune useless actions), k-center clustering (to discretize continuous actions), and belief tree reuse (to handle state growth).
Theoretical Analysis: Proofs of convergence for the solver under specific assumptions (Lipschitz continuity, hierarchical partitioning) and bounds on the performance loss due to belief tree reuse.
Comprehensive Evaluation: Extensive validation in Gazebo simulations (Fetch and Stretch robots) and real-world experiments, demonstrating superiority over both classical POMDP solvers and state-of-the-art non-POMDP methods (including LLM-based approaches).

4. Experimental Results

The method was tested in diverse scenarios (Loose, Hidden, Covered, Complex) with varying numbers of objects and occlusion levels.

Comparison with POMDP Baselines: GNPF-kCT outperformed classical solvers (POMCP, GPOMCP) and continuous-action solvers (POMCPOW, VOMCPOW) in terms of discounted cumulative reward, number of steps, and success rate.
- Example: In the "Complex1" scenario (15 objects), GNPF-kCT achieved a 95% success rate within 50 steps, while POMCP only achieved 25%.
Comparison with Non-POMDP/LLM Methods: The paper compared GNPF-kCT against Random, Greedy, SGoLAM, SayPlan, and MoMa-LLM.
- Result: GNPF-kCT significantly outperformed LLM-based methods (SayPlan, MoMa-LLM), which struggled with physical constraints, occlusion, and the need for precise manipulation in cluttered single-room environments. LLMs often failed to generate optimal long-horizon plans under uncertainty.
Real-World Validation: Tested on a Stretch robot in an office environment. While primitive action failures (due to hardware/perception limits) reduced the success rate slightly compared to simulation, the framework successfully located targets and demonstrated practical applicability.
Ablation Studies: Confirmed that both the Neural Process filtering and k-center clustering are essential for performance. Belief tree reuse was shown to be critical for complex scenarios with many new objects but less impactful in simple, open scenarios.

5. Significance and Conclusion

Bridging the Gap: The work bridges the gap between theoretical POMDP planning and real-world robotic execution by handling continuous control, dynamic state growth, and physical interactions (removing obstacles).
Efficiency: By filtering actions with Neural Processes and refining the search space with clustering, the method achieves high performance within strict computational budgets (60 seconds per step).
Robustness: The approach does not rely on pre-defined geometric models of unknown objects or QR codes; it uses only onboard sensors (RGB-D, LiDAR) and a target photo, making it highly transferable to real-world settings.
Future Outlook: The authors suggest that while their method excels at planning under uncertainty, future work could integrate Vision-Language-Action (VLA) models to improve the success rate of complex primitive actions (e.g., grasping and removing objects).

In summary, GNPF-kCT represents a significant advancement in autonomous object search, offering a robust, efficient, and theoretically grounded solution for mobile robots operating in unstructured, cluttered, and partially observable environments.