无通信、无先验,机器人靠共享结果自适应分配任务
Acting on the Unseen: Communication-Free Collaborative Filtering for Decentralized Multi-Robot Task Allocation
- 每台机器人仅通过公开的队友结果流,实时进行低秩协同过滤
- 在任务远多于尝试次数时,仍能精准匹配未尝试过的任务对
- 适合无通信、无中心协调的分布式机器人团队,抗干扰强
多机器人任务分配通常依赖通信、已知任务模型或协调器。本文研究相反场景——零知识多机器人任务分配(ZK-MRTA):机器人团队既无任务模型,也无潜在秩信息,完全无通信(无消息、无参数共享、无协调者),仅能观测到队友行为结果的局部噪声广播。隐藏的低秩结构决定机器人与任务的适配性,且任务数远超轮次,多数(机器人,任务)组合从未尝试。但每台机器人可通过在广播上运行在线低秩协同过滤(SwarmCF),在未尝试的任务和新任务上表现良好。相比无结构学习者,其性能优势是根本性的:后者在未见组合上被锁定在先验均值误差水平。理论证明了匹配的每机器人样本复杂度(Θ(d) vs Θ(n),d为秩,n为任务数)、任务稀缺下的即时累积奖励分离,以及在确定条件下可精确恢复被遮蔽广播的充分条件(经实验验证)。实验量化了广播的价值,显示正向规模效应(单机未见任务技能随团队规模上升),并优于现有低秩方法的鲁棒性与即时性能,在容量为1的竞争下及真实机器人感知实例中仍保持高效,恢复了约80%的集中式全通信上限能力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。