Pairwise scores can lead to poor multi-robot plan choices indoors
Pairwise Approximation Can Select the Wrong Multi-Robot Plan
RoboticsMultiagent Systems
Summary
Choosing the best plan for multiple robots working together often relies on simple scores that look only at pairs of robots, ignoring larger groups. The authors show that these pair-based scores can pick worse plans compared to knowing how every group of robots performs exactly. They tested this on indoor robot exploration and found that ignoring bigger group effects can lead to worse coverage and wrong plan choices. Surprisingly, even methods with less error in approximating scores don’t always pick better plans.
What this means in practice
- •For robotics engineers: Improve multi-robot exploration plans by avoiding pairwise-only scoring to reduce coverage losses in indoor environments.
- •For autonomous system developers: Design better plan evaluation methods for multiple robots by accounting for group interactions beyond pairs to enhance mission success.
Authors
William Teo
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_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.