Pairwise Approximation Can Select the Wrong Multi-Robot Plan
In the authors' words
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 . From the same subset values we compute two pairwise scores: the exact order-2 M\"obius truncation , which depends only on the singleton and pair values, and an equal-weight least-squares two-additive fit . Ranking by instead of 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 reduces the regret but still changes the selection on three of seven maps in each family. The additive score , 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 . We also find that lower average reconstruction error does not guarantee lower selection regret.
Appeared: Friday, September 25. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 6 pages, 4 figures, 1 table. Accepted at the IROS 2026 Workshop on Intelligent Information Gathering. Code: https://github.com/williamteo/pairwise-regret