COMBS: Concealed Object Multi-modal Bayesian Search

Taylor Bergeron, Kevin LeahyarXiv 2026 · arXiv

TL;DR

COMBS (Concealed Object Multi-modal Bayesian Search) is a new framework that allows robots to find hidden objects by fusing "common sense" from LLMs, vision-language models, and semantic networks into a principled Bayesian decision model. By treating the environment as a dynamic hierarchy and explicitly reasoning about whether containers are hiding their contents, COMBS achieves near-perfect success rates even when objects are placed in highly unusual locations.

What Problem Does This Paper Address?

Imagine asking a robot to find a fork. It knows to check the kitchen drawer. But what if the fork is hidden inside a box in the bathroom?

Most current robotic search methods struggle with two things: occlusion (objects hidden inside containers) and out-of-distribution (OOD) placements (objects in weird places). While Large Language Models (LLMs) are great at providing "common sense" priors (e.g., "forks are in kitchens"), they can be brittle, slow, and prone to "hallucinating" that an object is absent if it isn't in a typical spot.

The authors address the challenge of building a principled belief system that allows a robot to navigate a partially known environment, decide when to open a container versus when to move to another room, and ultimately determine with statistical confidence if an object is truly missing from the house.

Methods

The COMBS framework rests on three main pillars:

  1. Hierarchical Transition System (HTS): Instead of a flat map, the robot views the world as a tree. Nodes represent rooms, which contain objects, which might be containers holding more objects. Crucially, this tree grows as the robot interacts with the world—opening a drawer reveals new nodes to search.
  2. CA-MOMDP (Concealment-Adaptive Mixed-Observability MDP): This is the "brain" of the system. It’s a mathematical framework that tracks two types of hidden information: where the target is, and whether a specific object (like a closed box) is currently concealing its contents.
  3. Multi-modal Prior Fusion: To avoid over-relying on a single potentially flawed model, COMBS fuses three sources into a "COMBS-score":
  4. CLIP (VLM): Provides visual-semantic similarity.
  5. ConceptNet: A human-curated semantic network for "common sense."
    • Llama 3 (LLM): Captures linguistic patterns of where things are kept.

These are combined using log-odds pooling, ensuring that no single model can completely zero out a location's probability, which allows the robot to recover if its initial "common sense" guess was wrong.

Fig. 1: COMBS overview. Zero-shot priors initialize a belief over a hierarchical transition system that grows as the robot reveals contents. The policy selects the search with the highest expected detection per unit cost, and each observation that does not reveal the target updates the belief until the target is found or the absence test fires.

Datasets

The authors evaluated COMBS across five different simulator configurations to test everything from perfect perception to messy, real-world-style sensor noise:

  • Gridworld: Abstract testing of the core logic.
  • ProcTHOR: Procedurally generated 3D houses with interactive objects (drawers/cabinets).
  • Matterport3D (MP3D): Real-world scans of homes.
  • MP3D + Detic: Using a real open-vocabulary detector (Detic) to simulate the noisy, imperfect labels a real robot would see.

Key Insights and Ideas

  • The Power of Negative Evidence: One of the most critical features of COMBS is how it handles "not finding" an object. If a robot looks at a closed drawer and doesn't see the fork, COMBS doesn't assume the fork isn't there; it increases the probability that the drawer is concealing the fork. This prevents the robot from prematurely giving up on a room.
  • Bounded Influence: By pooling priors in log-odds space, the system ensures robustness. If the LLM is 100% sure the fork is in the kitchen but it's actually in the bathroom, the other models (and subsequent negative observations) eventually override the LLM's bias.
  • Principled Termination: Unlike many LLM-based agents that might "quit" randomly, COMBS uses a likelihood ratio to declare an object absent only when the probability of it being anywhere else falls below a specific threshold.

Key Results

COMBS demonstrated significant improvements over baselines like TidyBot and pure LLM policies:

  • Success Rate: Found 92–100% of targets across all simulators, including those in "out-of-distribution" locations (like a fork in a bathroom).
  • Efficiency: It matched or beat the search speed of baselines while being significantly cheaper to run than per-step LLM queries.
  • Robustness to Noise: Even with the noisy Detic detector, COMBS maintained a 94-98% success rate.
  • Latency: The decision time for COMBS is in the range of 1.7–3.1 ms, orders of magnitude faster than calling an external LLM at every step (which takes ~500ms).
Fig. 2: Share of present targets found within a given search cost, for in-distribution and out-of-distribution placements, pooled over the five simulator configurations.

Limitations and Future Work

The authors note that currently, the HTS treats all instances of a class in a room (e.g., three identical cabinets) as sharing the same belief. This can "dilute" the prior if one cabinet is much more likely to hold the target than the others based on spatial context (e.g., the cabinet next to the sink vs. the one by the door). Future work aims to incorporate spatial reasoning to distinguish between these individual instances. Additionally, while the system handles "absent" targets well, it assumes the target is stationary during the search.

Summary updated

Abstract

This work addresses the problem of finding a concealed object in an environment by unifying formalisms for partially observable environments with multi-modal priors drawn from a mix of ontologies, semantic networks, LLMs, and VLMs. We propose a concealment-adaptive mixed-observability MDP (CA-MOMDP), a Bayes-adaptive setting where uncertainty is over both object locations and which nodes can conceal them, held as a hypothesis with a bounded ontology prior and resolved only by interaction. We define a hierarchical transition system (HTS) to abstract the environment into room and object nodes that can be planned over via our CA-MOMDP. We further propose a COMBS-score: a multi-modal fusion of a human informed semantic network, LLM, and VLM, to initialize the belief over object locations, which grounds our abstractions and reduces reliance on a single model. Belief is maintained via Bayes' rule, which never lets a look rule out a closed container. We prove a present target is found in a bounded number of searches under exact perception and that its location is never ruled out given missed detection under noisy perception. We ablate each component to demonstrate their significance. Across five simulator configurations, from a gridworld to Matterport3D with a real detector, COMBS finds 92-100% of in-distribution and 92-100% of out-of-distribution targets, matches or beats the baselines in processing speed, significantly outperforms a per-step LLM policy at lower cost on the larger scenes, recovers more out-of-distribution placements than a TidyBot ranking, and matches an LLM-only prior at a fraction of its per-decision latency. COMBS is the only standalone method that can declare a target absent at a stated error level, and the per-step LLM policy offered a termination action abandons 12-22% of targets that were present, against 1.6-3.2% for COMBS on the same episodes.
BibTeX
@misc{bergeron2026combs,
  author = {Taylor Bergeron and Kevin Leahy},
  title = {{COMBS: Concealed Object Multi-modal Bayesian Search}},
  year = {2026},
  eprint = {2611.15964},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.15964},
}
Figure