Pairwise Approximation Can Select the Wrong Multi-Robot Plan

arXiv:2609.29929v1 Announce Type: new 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 Mobius truncation F_2, which depends only on the singleton and pair values, and an equal-weight least-squares two-additive fit G. Ranking by F_2 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_1, 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_2. We also find that lower average reconstruction error does not guarantee lower selection regret.

Source: arXiv cs.RO | 2026-09-25