Acting on the Unseen: Communication-Free Collaborative Filtering for Decentralized Multi-Robot Task Allocation
2026-05-25 • Robotics
RoboticsArtificial Intelligence
AI summaryⓘ
The authors explore a challenging situation in multi-robot task allocation where robots have no prior knowledge, cannot communicate, and only see noisy, partial results of others' actions. They show that by using a special method called SwarmCF, which leverages hidden low-rank patterns, robots can still learn which tasks they are good at, even if they never tried them before. This approach performs much better than methods that ignore such structure and works well even when there are many tasks and limited interactions. The authors prove theoretical guarantees and demonstrate through experiments that their method scales well with team size and is robust under difficult conditions.
multi-robot task allocationzero-knowledgelow-rank structurecollaborative filteringonline learningsample complexitydecentralized learningno-communicationtask scarcitymasking robustness
Authors
Alexander Apartsin, Yigal Meshulam, Yehudit Aperstein
Abstract
Multi-robot task allocation usually assumes some combination of communication, known task models, or a coordinator. We study the opposite extreme, a regime common in practice but overlooked in theory, which we name Zero-Knowledge MRTA (ZK-MRTA): a robot team with no prior knowledge (no task models, not even the latent rank), no communication (no messages, no parameter sharing, no coordinator), and only a partial and privately-noisy view of a public stream of teammates' outcomes. A hidden low-rank structure governs which robot suits which task, and there are far more tasks than rounds, so most (robot, task) pairs are never attempted. Yet each robot can act well on tasks it never attempted, and onboard new tasks, by running online low-rank collaborative filtering over the broadcast (SwarmCF). The advantage over any structure-free learner is categorical, not a constant factor: a structure-free learner is provably at the prior-mean error floor on unseen pairs. We prove a matching per-robot sample complexity (Θ(d) versus Θ(n), in the rank d and the task count n), an anytime (cumulative-reward) separation under task scarcity, and a deterministic condition under which decentralized recovery from the masked broadcast is exact (validated empirically). Experiments quantify the value of the broadcast, a positive scaling law (per-robot unseen-pair skill rises with team size), and the strongest masking-robustness and anytime profile among low-rank methods, recovering most (about 80% on earned skill) of a centralized full-communication ceiling, and holding under capacity-1 contention and in a robotics-grounded sensing instance.