Dispersive Tree Agreements for Multi-Robot Coordination
作者: Shashank A. Deshpande, Blake T. Edwards, Jonathan P. How
分类: cs.RO, cs.MA, math.OC
发布日期: 2026-10-22
备注: 19 pages, 5 figures, 7 tables. Submitted to IEEE Transactions on Robotics
💡 一句话要点
提出分散树协议以解决多机器人协调问题
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 多机器人协调 去中心化规划 实时算法 分散树 最优控制
📋 核心要点
- 现有的多机器人协调方法多为中心化且离线，无法满足实时性和去中心化的需求。
- 本文提出了一种去中心化的实时规划器WarpWeaver，通过分散树搜索实现多机器人团队的近似最优协调。
- 实验结果表明，WarpWeaver在Dynobench测试套件中比中心化离线规划器减少最多22%的总旅行时间。
📝 摘要（中文）
多机器人协调非线性系统自然可以被表述为在机器人组的约束下进行联合空间的最优控制。现有方法大多集中于中心化、离线且局限于无碰撞运动规划，而去中心化的实时方法则专注于安全导航而不追求联合最优性。本文开发了一种去中心化的实时规划器，作为一种随时可用的过程接近联合最优。我们扩展了最近的单机器人框架，通过前向传播命令的分散树搜索来协调多机器人团队。我们首先证明，机器人间的耦合可以有效地被一些局部约束替代，在这些约束下，局部生长的分散树包含近似最优的协议。我们的协议WarpWeaver实现了这种协商，展示了即使在实时截止时间缩短的情况下，也能有效地达成静态协议。
🔬 方法详解
问题定义：本文旨在解决多机器人系统的协调问题，现有方法主要集中于中心化的离线规划，缺乏实时性和去中心化的特性。
核心思路：论文提出的WarpWeaver协议通过局部约束替代机器人间的耦合，利用分散树搜索实现多机器人团队的近似最优协调。
技术框架：WarpWeaver的整体架构包括分散树的生成、局部约束的应用以及基于协商的协议达成，形成一个异步的实时循环。
关键创新：最重要的创新在于将机器人间的耦合转化为局部约束，使得每个机器人能够独立搜索其分散树，从而实现去中心化的近似最优协调。
关键设计：在设计中，WarpWeaver采用了异步协商机制，允许机器人在实时截止时间内进行有效的协议达成，确保即使在时间限制下也能实现协议的闭合。
🖼️ 关键图片
📊 实验亮点
实验结果显示，WarpWeaver在Dynobench测试套件中相比于中心化离线规划器减少了最多22%的总旅行时间，相比于去中心化实时基线提升了最多37%的效率，并且在图连接性任务中几乎将成功率翻倍。
🎯 应用场景
该研究的潜在应用领域包括无人机编队、自动驾驶车辆协调以及工业机器人协作等场景。通过实现去中心化的实时规划，WarpWeaver能够在动态环境中有效地协调多机器人系统，提升任务执行效率，具有重要的实际价值和未来影响。
📄 摘要（原文）
Multi-robot coordination of nonlinear systems is naturally formulated as joint-space optimal control subject to constraints over groups of robots. Existing methods that approach joint optimality remain largely centralized, offline, and confined to collision-free motion planning, while decentralized, real-time counterparts target safe navigation without pursuing the joint optimum. This paper develops a decentralized, real-time planner that approaches the joint optimum as an anytime process. We extend a recent single-robot framework that searches dispersive trees of forward-propagated commands for differentially flat systems to coordinate a multi-robot team near-optimally. We first show that the inter-robot coupling can be effectively replaced by some local constraints, under which locally grown dispersive trees contain a near-optimal agreement. It is this structure that the robots pursue by decentralized column generation, negotiating rents on the shared space that guide the search of each robot's tree. The negotiation settles on an agreement whose near-optimality is certified at quiescence. Our protocol, WarpWeaver, implements this negotiation as an asynchronous real-time loop over a receding horizon, and demonstrates effective closure to quiesced agreements even when real-time deadlines cut the negotiation short. In simulation, WarpWeaver reduces total travel time by up to 22% against centralized offline planners on the Dynobench suite and by up to 37% against a decentralized real-time baseline, and nearly doubles the success rate of a task-specific planner on graph connectivity. Hardware experiments on six robots planning onboard demonstrate real-world implementability.