Pairwise Approximation Can Select the Wrong Multi-Robot Plan

William Teo

MARMoT Lab, National University of Singapore
NEAR Lab, AI.Robotics Strategic Technology Centre, ST Engineering

IROS 2026 Workshop on Intelligent Information Gathering

arXiv CodeBlog post (soon)

Picked by F

Delivered — · explored —

Picked by F₂

Delivered — · explored —

Delivered to base
Explored, not yet delivered
Unknown
Wall
●●●●Robots 1–4
▲Base station

Loading replay…

Figure 1. Env1 at 15 m. Left: the plan F ranks first. Right: the plan F₂ ranks first, from the same eight candidates. Press Play to watch what each team explores and delivers to the base (map shading is saved every 5 steps). Map: env1 of the BYU FROST Lab indoor exploration benchmark.

Abstract

Multi-robot coordination methods often score a joint plan from singleton and pairwise terms, leaving out the terms that involve three or more robots. We measure the plan-selection regret of two pairwise approximations to delivered coverage using frozen multi-robot trajectories. For each four-robot plan on an indoor exploration benchmark, replaying all 16 robot subsets gives the exact delivered-coverage set function F. From the same subset values we compute two pairwise scores: the exact order-2 Möbius truncation F₂, which depends only on the singleton and pair values, and an equal-weight least-squares two-additive fit G. Ranking by F₂ instead of F changes the selected plan on six of seven maps at the 15 m candidate-generation range in each of two candidate families, with regret up to 0.337 of map coverage. Switching to G reduces the regret but still changes the selection on three of seven maps in each family. The additive score F₁, which keeps only the singleton terms, selects the exact winner on six of seven maps in one family and four of seven in the other, against one of seven for F₂. We also find that lower average reconstruction error does not guarantee lower selection regret.

How it works

Four robots map a building by driving to frontiers, the edges between mapped and unmapped space. A map counts only once it reaches the base station, either directly or through a teammate in communication range. The score of a plan is its delivered coverage F, the share of the map the base knows at the end.

Figure 2. Schematic of the benchmark's rules. The two plan families differ in how a robot picks its next frontier.

Within a family, the eight plans differ in three settings, shown in their names:

Relay 100 / 300: Every 100 or 300 steps, each robot stops exploring and heads back to deliver its map to the base.
Handoff on: A returning robot can pass the delivery to a connected teammate closer to the base.
Crowding on: Nearest-frontier plans only: robots avoid frontiers near where teammates have been or are heading, as far as they know through communication.
Seed 0 / 1: Random-frontier plans only: the seed of the random frontier choice.

To see how the robots interact, each plan is replayed with every subset of its four robots, 16 replays in all, with each robot following its original path. Each approximate score combines some of these subset values into an estimate of F.

Figure 3. The 15 subset replays of one env1 plan at 15 m, from single robots (bottom) to the full team (top). Dots show which robots are in each replay, colored as in Figure 1. Each box gives the replay's coverage and its term, the part not explained by its smaller subsets (for a pair, its value minus its two single values). F₁, F₂ and F₃ add up the terms of the rows they keep, and G refits single-robot and pair terms instead. Highlighted boxes are the values a score reads, and dashed rows are the terms it leaves out.

Results

	Nearest-frontier plans			Random-frontier plans
Map	F₁	F₂	G	F₁	F₂	G

Figure 4. Coverage lost, in percentage points, when each score picks the plan at 15 m. Ticks mark the average loss of a random pick. Click a bar to see that case.

One case in detail

Candidate family Map Communication range Score used to pick

Loading recorded results…

Figure 5. The eight plans, ordered by delivered coverage (left) and by the score used to pick (right). ✓ = on, – = off.

Scope: four robots, seven maps, fixed starts and eight frozen plans per map and family. We did not test online replanning. G is fitted to all 15 subset values of each plan, including the full team.

Reproduce

The analysis uses only the Python standard library. From a clone of the code repository, run:

python -m unittest discover -s .
python analyze.py --output docs/data.json
python -m http.server 8000 --directory docs --bind 127.0.0.1

This recomputes the paper's scores and selections from the recorded subset values. It does not rerun the simulator. The results on this page are in data.json.

Data provenance

Cite

@misc{teo2026pairwise,
  title         = {Pairwise Approximation Can Select the Wrong Multi-Robot Plan},
  author        = {Teo, William},
  year          = {2026},
  eprint        = {2609.29929},
  archivePrefix = {arXiv},
  primaryClass  = {cs.RO},
  note          = {IROS 2026 Workshop on Intelligent Information Gathering}
}