Search papers, labs, and topics across Lattice.
This paper introduces Zero-Knowledge Multi-Robot Task Allocation (ZK-MRTA), a challenging setting where robots must collaboratively allocate tasks without communication, prior knowledge, or a coordinator, relying only on a partial and noisy view of teammates' outcomes. They propose SwarmCF, an online low-rank collaborative filtering algorithm, and prove a per-robot sample complexity of 螛(d) compared to 螛(n) for structure-free learners, demonstrating its advantage in task scarcity. Empirical results validate the algorithm's robustness to masking and its ability to recover a significant portion of the performance achieved with centralized full-communication.
Robots can collaboratively allocate tasks with near-optimal performance even with *zero* communication, prior knowledge, or coordination, by exploiting low-rank structure in task suitability.
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.
