Suppose a team of robots must find something in an unfamiliar building, such as an exit, a victim, or a specific object, but only one of them matters. That one is a "queen," for example a robot carrying a person or a payload. The others are scouts whose only job is to get the queen to the target quickly. Theory for an idealized version of this problem, an empty disk, says the queen should neither rush nor sit still. It should hedge: stay where it can reach every still-unsearched region about equally fast, and commit only once the scouts have narrowed the possibilities. Vision-language models (VLMs, models that answer questions about images in natural language) now navigate unseen buildings well without task-specific training, and they know common-sense facts such as "front doors open off foyers, not bedrooms." So far, though, they have been used for single robots or for symmetric teams in which every robot is just another searcher.
This note proposes a semantic hedging planner. The VLM does only one thing: it estimates, for each boundary of explored space, how likely the target is to lie beyond it. Geometry does everything else. The queen moves toward the point that minimizes its expected walking distance, through walls and doorways, to the target under those probabilities. Scouts are sent to the boundaries whose resolution most shortens that expected walk. Because the VLM is queried per boundary and never asked to coordinate the team, the cost of adding scouts does not show up as a cluttered prompt. Our central prediction is that the queen's arrival time improves with team size the way disk theory predicts, but only until the number of scouts reaches the number of distinct corridor branches around the queen, at which point it saturates for structural reasons. A VLM that coordinates the whole team in one call should saturate earlier, for cognitive reasons.
Core Claim
The disk analysis in Priority evacuation from a disk: The case of n ≥ 4 gives the queen a worst-case evacuation time below $2 + 4(\sqrt{2}-1)\pi/n$ with $n$ servants. Its IntersectChase algorithm keeps the queen at the center for a computed time and then chases the shrinking unsearched arc. That beats the naive wait-at-center time of $2 + 2\pi/n$ and sits within about $0.657\pi/n$ of the lower bound. The result assumes three things: free space, a target that is equally likely anywhere on the boundary, and coordination that costs nothing. Real buildings break all three. Walls make walking distance differ from straight-line distance. Semantics make some frontiers far likelier than others. A language-model coordinator pays for every added agent: Understanding Agent Scaling in LLM-Based Multi-Agent Systems via Diversity reports that 2 diverse agents match 16 homogeneous ones, and LLM-MCoX names visual prompt clutter as its own obstacle to scaling the team.
Our claim is that, for the priority objective, these three problems separate cleanly. Semantics enter only as a probability $p_f$ over the current frontiers $f$, the boundaries between mapped and unmapped space. Coordination becomes a geometric optimization whose cost grows with the number of frontiers rather than the number of robots. The queen's target position is
$$q^\star = \arg\min_{q \in \mathcal{X}} \; \sum_{f} p_f \, d_G(q, f) \;+\; \lambda \max_{f:\, p_f > \tau} d_G(q, f),$$
where $\mathcal{X}$ is the mapped free space, $d_G$ is the shortest walking distance through the occupancy map, the first term is the queen's expected remaining walk, the second term guards the worst case over any frontier with probability above a threshold $\tau$, and $\lambda$ trades the two. Setting uniform $p_f$ on an empty disk recovers the hedge-at-center logic of IntersectChase. The new ingredient is a nonuniform, VLM-derived $p_f$ on a non-convex map. Scouts are assigned greedily: each goes to the frontier whose resolution most reduces the expected walk, discounted by the scout's own travel time to reach it.
The structural prediction is as follows. Let $B$ be the number of distinct branches of the building's topological skeleton (its corridor-and-room graph) that leave the queen's current region. The marginal benefit of the $n$-th scout should track the disk's $\pi/n$ trend for $n < B$ and flatten for $n \ge B$, because extra scouts can only queue behind each other in the same branch. If the curve flattens well before $B$, the bottleneck is perceptual or semantic, not structural, and the claim is wrong.
Research Program
We build three components in Habitat-Lab on HM3D and MP3D scenes. The library supports multi-agent tasks, but it is unmaintained past v0.3.4, so we pin that version.
The first component is a shared mapper. It fuses all robots' depth observations into one 2D occupancy grid and extracts frontier clusters and a skeleton by thinning, following LLM-MCoX.
The second is a frontier scorer. For each frontier cluster, it shows the VLM a crop of the nearest robot's view toward that frontier, plus a short text description of the target. The VLM returns a likelihood, and the likelihoods are normalized into $p_f$. This borrows the "intuition value map" idea from InstructNav, which scores unmapped room openings with GPT-4V for a single robot, and the frontier exploration-value scoring in MerNav. Both papers use these scores to steer one agent. We use them as a belief that a second, geometric layer optimizes against.
The third is the hedging and assignment layer. It solves the objective above over sampled candidate positions using precomputed shortest paths, then dispatches waypoints to a local A* controller. Because VLM replanning in physical systems takes 20 to 50 seconds per cycle (as reported for LLM-MCoX), the scorer runs asynchronously. The geometric layer replans every step using the most recent $p_f$.
The analysis follows the scaling prediction directly. We sweep the number of scouts, measure the gain from each added scout, and plot it against $n/B$ per scene. We also check whether the VLM's frontier probabilities are well calibrated, using the frontier the target actually lay behind. The answer determines how much $\lambda$ needs to protect against overconfident semantics.
We also revisit the asymmetric rendezvous result of Multi-robot exploration and rendezvous on graphs. Its anchor strategy beat symmetric search on abstract graphs, but its ranking weight $\alpha = 1 - e^{-2n/N}$ needs the total graph size $N$ in advance. Our expected walking distance replaces that blend with a quantity computable from the current map alone. This motivates the anchor-style asymmetry. We do not reuse its ranking rule.
Baselines
The naive reference point is "queen waits, then goes." All robots except the queen run greedy nearest-frontier exploration. The queen stays at its start and walks the shortest path once the target is seen. This is the building analogue of the $2 + 2\pi/n$ wait-at-center strategy. Beating it shows that hedging movement helps at all.
The strongest existing system is an LLM-MCoX-style coordinator. Following LLM-MCoX, a single VLM call per replanning cycle receives the composite map (frontiers, skeleton, all robot poses) and assigns waypoints to every robot. We add the priority objective and the queen's identity to the prompt, so it is not handicapped by being unaware of the task. LLM-MCoX reports a 10.2% improvement in exploration completion speed over RACER and AEP+DVC, and 55.7% higher efficiency at finding objects in large maps when given language hints. No reported result was found on Lacuna for any system on a priority, single-asset arrival objective, so we establish this number ourselves.
For a fair comparison, both systems use the same VLM, the same mapper and low-level controller, and the same scenes and seeds. Each gets the same total number of VLM tokens per episode, and each gets the same small budget of prompt-tuning iterations on a held-out set of 20 scenes. Beating it means a lower mean queen arrival time at equal or lower token cost, with a gap that widens as the number of scouts grows.
Two ablations isolate the key ingredient. The first, a geometric hedge, sets $p_f$ to uniform: classical minimax-and-expected walking-distance hedging with no VLM. It tests whether semantics matter. The second, semantic rushing, keeps the VLM probabilities but sends the queen straight to the highest-probability frontier rather than the hedge point. It tests whether hedging matters once semantics are available.
A single-robot reference runs the queen alone with a MerNav-style zero-shot navigator. MerNav reports 45.7% success on HM3D_OVON with one agent, which anchors what one competent robot achieves without scouts.
Why not just…?
Why not just compute a geometric hedge point and skip the VLM? This is the most serious threat, and the uniform-$p_f$ ablation exists to settle it. If target placement in HM3D scenes is semantically weak relative to geometry, or if VLM probabilities are poorly calibrated, the geometric hedge will match our method and the contribution reduces to "port IntersectChase to buildings." That would still be a useful result, but a different paper. The evidence that semantics should matter is indirect: LLM-MCoX's 55.7% target-search gain came specifically from language hints. We will report the gap separately for scenes with strong semantic structure, such as exits and kitchen objects, and for weakly structured targets. We expect the benefit to concentrate in the former.
Why not just let the VLM coordinate everything, as LLM-MCoX does? It might work at small team sizes, and we expect it to be competitive with two or three scouts. The authors themselves report that dozens of poses and paths overwhelm the VLM's spatial grounding. The text-agent evidence in Understanding Agent Scaling in LLM-Based Multi-Agent Systems via Diversity and the 55-fold token penalty for six-agent voting in Compositional Skill Execution in LLM Multi-Agent Systems both indicate that asking a language model to coordinate more agents degrades early. The scout sweep tests this directly. The prediction fails if the full-VLM coordinator keeps pace beyond eight scouts.
Why not just make the queen another searcher? Symmetric search adds one more explorer, which could find the target sooner, and it avoids a special-case robot. The disk theory answers this partly: the queen's optimal behavior is a hedge, not a search, because it bears the full cost of being far from wherever the target turns out to be. Multi-robot exploration and rendezvous on graphs also found asymmetric anchoring beat symmetric movement. We include a "queen explores greedily" baseline, which differs from the naive one in that the queen moves. If it wins on HM3D, the hedging premise does not transfer to buildings.
Why not just send one robot? A single robot avoids every coordination cost, and solo agents beat teams under truncated context in the cybersecurity setting (98% versus 67%) studied by Compositional Skill Execution in LLM Multi-Agent Systems. But that task had no spatial parallelism. In a building, one robot cannot be in two wings at once. The single-robot reference measures how much scouts buy in arrival time.
Proposed Experiments
The first experiment is a sanity check on an empty circular map with the target placed uniformly on the boundary. There, our planner with uniform $p_f$ should achieve a worst-case queen arrival close to the disk bounds: below $2 + 2\pi/n$ and approaching $2 + 1.657\pi/n$ for $n \ge 4$. Failing this would indicate implementation error before any semantic claim is made.
The main experiment uses roughly 200 held-out HM3D and MP3D scenes. In each, the target is either an exterior door or an object category from HM3D_OVON. The queen and scouts spawn together. The number of scouts is swept over 1, 2, 4, 8, and 16. The primary metric is the queen's arrival time, normalized by its oracle shortest-path length from the start to the target, the building analogue of the disk's "1." Secondary metrics are worst-decile arrival time, queen success within a step budget, total VLM tokens, and wall-clock VLM latency.
The decisive check is the scaling plot. If the main hypothesis holds, three things appear together. Our planner's gain per added scout follows a roughly $1/n$ trend and flattens near $n \approx B$ per scene. The LLM-MCoX-style coordinator flattens earlier and at higher token cost. Semantic rushing has a worse worst-decile than our hedge even when its mean is similar.
Two further checks stress the method. First, we perturb $p_f$ by deliberately misleading target descriptions to measure how much $\lambda$ protects the queen when semantics are wrong. Second, we report calibration curves of the VLM's frontier probabilities, since the whole decomposition rests on those numbers meaning what they say.
References
- Priority evacuation from a disk: The case of n ≥ 4
- Understanding Agent Scaling in LLM-Based Multi-Agent Systems via Diversity
- LLM-MCoX: Large Language Model-based Multi-robot Coordinated Exploration and Search
- InstructNav: Zero-shot System for Generic Instruction Navigation in Unexplored Environment
- MerNav: A Highly Generalizable Memory-Execute-Review Framework for Zero-Shot Object Goal Navigation
- Multi-robot exploration and rendezvous on graphs
- Compositional Skill Execution in LLM Multi-Agent Systems: A Comparative Study of Collaboration Architectures for Long-Horizon Tasks