一. 任务流程1.接入多源数据机器人电量 是否空闲 存活 有哪些能力 当前位置2.指令解析大模型转义 任务拆解 状态及能力筛选3.分配任务/决策时序规划,解决逻辑与资源冲突谁去干基于共识的分布式拍卖算法CBBA 抢占同一个位置 电量低的优先 高任务紧急度优先4.状态分析反向分析机器人的具身行为安全性及时性碰撞风险 指令下发状态 执行反馈 单机是否接受到任务正常--持续检测 优化下一个任务流程 最短时间内完成/异常--启动异常检测与告警 快速动态重分配重调度5.冲突消解时空逻辑冲突 怎么走不撞基于冲突搜索算法CBS或其变体ECBS 用CBS算法在一面给一个机器人增加一条“时空硬约束”多少秒到多少秒原地等待 或者规划新路径 总控台还可以给最高级别的指令消除冲突6.动态分配重调度利用大模型的自然语言常识推理和多轮对话能力来解决多机器人的复杂任务规划与协同二. 节点1领域的开山奠基之作分类学与形式化建模1. 奠基文章文献 A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems (2004, IJRR) 作者 Brian P. Gerkey Maja J. Matarić2. 亮点工作与核心方法提出了全球公认的多机器人任务分配Multi-Robot Task AllocationMRTA形式化分类学。利用运筹学Operations Research和组合优化理论将复杂的机器人协同行为抽象为数学上的“最优指派问题”并划分为三个维度SR/MR单机器人任务 vs 多机器人协同任务ST/MT单任务机器人 vs 多任务机器人IA (Instantaneous Assignment)/TA(Time-Extended assignment)即时任务指派 vs 时间窗规划如你关心的“哪个期间干什么事”通过这三个维度的组合任何多机器人任务分配问题都可以被精确归类为一个三字代码如最简单的 ST-SR-IA到最复杂的 MT-MR-TA,这个分类方法成为了后续 机器人调度领域的行业标准语言3.意义它利用运筹学Operations Research和组合优化Combinatorial Optimization理论为这些机器人场景找到了对应的数学母题。它向学术界证明机器人集群调度问题不需要从头创造它们在数学上等价于人类已经研究了几十年的经典优化问题将具体机器人协作架构和抽象运筹学理论联系在一起机器人集群调度问题--经典优化问题--已有算法4. 承前启后关系承前 在此之前多机器人的调度都是针对特定场景如踢足球、工厂搬运临时编写的代码这篇文章建立MRTA数学模型并且给出统一分类Taxonomy将MRTA映射到经典优化问题 启后 它是纯宏观的数学规划它假设算力由中央服务器统一承担集中式。如果园区内有几十台机器人中央服务器计算这种组合优化问题会遭遇 NP-hard 算力爆炸且完全无法应对动态未知的通信中断三. 节点2CBBA算法任务分配逻辑冲突消解1. 奠基文章文献 Consensus-Based Decentralized Auction Algorithms for Multi-Agent Task Allocation (2009, IEEE TRO)作者 Han-Lim Choi, Luc Brunet, Jonathan P. How (MIT 团队)2. 亮点工作与核心方法1定义了任务分配问题组合优化问题在满足约束的前提下怎么分配能最大化收益拍卖算法计算如何分配和共识问题解决冲突消解2CBAAConsensus-Based Auction Algorithmic基于共识的拍卖算法单任务分配每台机器人同一时间只能接一个任务3CBBAConsensus-Based Bundle Algorithm基于共识的捆绑拍卖算法每台机器人可以接一系列任务任务捆绑包并在时间窗上有前后依赖关系,算法解决了当多个机器人在没有中央控制器的情况下如何快速可靠地完成任务分配3.CBBA创新点1Auction--Bundle机器人一次拍卖一个任务--机器人一次拍卖一串任务任务捆绑包2Consensus共识每个机器人都有一个三元变量Winning Bid Winning Agent Timestamp机器人互相通信时如果别人价格更高自己放弃如果别人信息更新自己也跟着更新。3Bundle Release之前机器人拍卖没抢到任务只删除这一个任务-- 现在机器人删除任务表中后面所有任务因为边际收益变了原来的边际收益都是建立在已经抢到了这个任务的基础上的4边际收益DMGDiminishing Marginal Gain任务越往后做收益越来越小即随着前置任务的增加边际收益会减小文章证明了只要满足DMGCBBA一定收敛4.CBAA基于共识的拍卖算法第一阶段拍卖选单Auction Process每台机器人扫描全场任务,它会看自己本地记录的“全场最高出价表 y”。如果它发现自己对任务 j 能投出的出价 cj 高于 yj它就把这个任务加入自己的意向单并把自己的出价更新进去第二阶段共识对账Consensus Process小车和周围邻居交换各自的最高出价表 y对账逻辑如果机器人A 发现邻居 B 对任务 1 的出价高达 95 分而自己只出价 80 分机器人 A 就必须自愿认输把本地记录的赢家改为邻居 B惩罚机制如果机器人 A 发现自己唯一选中的那个任务被邻居拍卖走了它在本地就变成了“空闲状态”释放该任务并在下一轮重新参与竞拍5.CBBA基于共识的捆绑拍卖算法第一阶段捆绑包构建Bundle Construction每台机器人不再只选一个任务而是维护两个列表捆绑包列表 bi按照执行的先后顺序排列的任务序列如先去 A 点再去 B 点。路径列表 pi对应任务的精确物理轨迹航路点边际效益递减Diminishing Marginal Return, DMR这是 CBBA 能收敛的数学根基。论文证明了如果一个机器人的捆绑包里已经有了任务[A、B]此时它再把任务C插进去任务 C 能带来的新收益一定小于或等于它在一个空包里直接做任务 C 的收益。因为绕路会耗电、耽误时间。ji会利用贪心算法不断把能带来最大边际效益的任务塞进包里直到自己塞不动或者出价无法超过全场最高价为止第二阶段共识消解Consensus Stage当两个机器人交汇对账时它们不只对一个出价而是对比一个三元组信息谁接了任务 (Winner),出了多少价 (Bid)什么时间知道的 (Timestamp)规则示例如果机器人A 记录的赢家是自己但邻居 B 带来了一条更新的时间戳证明在 2 秒前任务已经被机器人 C 以更高的价格抢走了连锁弃单此时机器人 A 必须认输。但最关键的是由于边际效益递减特性任务的收益是和它的先后顺序绑定的。一旦排在前面的任务被抢走了后面所有任务的收益全变了处理动作机器人 A 会把这个落选任务以及在它之后加入捆绑包的所有后续任务全部无条件从包里扔掉退回市场让全场重新竞拍6.承前启后关系承前 解决了 Gerkey (2004) 留下的集中式算力爆炸和单点故障隐患它把计算压力分散给各个机器人在去中心化网络中达成了全局最优的任务指派。启后(1)它是静态拍卖 一旦一面的总控台有最高级别指令或者生单机故障离线原版 CBBA 必须推倒全场重新拍卖通信开销巨大(2)只管“逻辑”不管“时空” 它只决定了把任务分给谁谁干什么但无法解决多台机器人在交叉路口的死锁与撞车问题7.评价指标全局总效能 / 行驶成本全场所有机器人完成任务的总电量损耗和绕路距离计算时间 / 算力开销算完一次分配需要多少毫秒通信消息量达成共识一共需要机器人之间发多少个数据包收敛时间四. 节点3CBS算法时空冲突消解1. 奠基文章文献 Conflict-Based Search for Optimal Multi-Agent Path Finding (2015, Artificial Intelligence) 作者 Gini Sharon, Roni Stern, Ariel Felner, Nathan R. Sturtevant2. 亮点工作与核心方法提出了经典的CBSConflict-Based Search基于冲突的搜索算法它采用双层搜索架构底层独立规划单个机器人的导航路径高层一面服务器一旦发现两个机器人时空轨迹冲突直接给其中一台机器人增加一条“时空硬约束”例如强制机器人A在第12s到15s内在路口原地等待或者强行规划新路径任务规划--任务分配CBBA--路径规划CBSCBS是求解MAPF(Multi-Agent Path Finding多智能体路径规划)问题的一种经典最优算法3.承前启后关系承前1补齐了 CBBA (2009) 忽略的“时空碰撞矛盾”它让跑在一面的 Supervisor 能够实施确定性的交通决策消除了机器人集群的死锁和碰撞风险(2保证最优搜索更加灵活启后(1)组合爆炸当机器人数量突破数十台或场景极大横向扩展时高层的冲突树会发生指数级爆炸算法直接卡死(2)执行与控制脱节它假设软件层规划的物理轨迹4.创新点1高层搜索High-Level Search高层不找路。只处理Conflict。2低层搜索Low-Level Search发现Conflict节点重新规划3根节点--发现Conflict--分裂子结点--重新规划--继续寻找Conflict--直到没有Conflict5.评价指标1生成节点个数算法为了寻找最优解一共生成了多少搜索节点越少速度越快2运行时间3成功率规定时间内各算法随着机器人数量增加时的求解成功率6.CBS算法基于冲突的搜索算法CBS 提出了一个“分工明确”的双层Two-Level搜索架构不是一开始就考虑所有机器人而是先让每个机器人自己走只有发生冲突再解决阶段一高层搜索 ── 管理一棵“冲突树”Conflict Tree, CT高层节点冲突树的每个节点都包含一组时空硬约束所有机器人的路径集合以及当前的总成本寻找冲突从根节点开始 Supervisor 检查所有机器人的路径。如果发现机器人 a1 和机器人a2 在第 t秒同时到达了坐标V这就是一个“时空冲突”形式化记为 (a1, a2, V, t)树的分裂一旦发现冲突该高层节点就会分裂出两个子节点分别把这个冲突化解为两条对立的硬约束左或右子节点增加约束限制机器人 a1在第 t秒不允许进入坐标 V阶段二底层搜索 ── 单机受约束路径规划当高层塞给某个机器人一条新约束后底层的单机路径规划器就会被激活机器人只需要重新规划自己的路径在规划时把那个“特定时间不能去的特定坐标”当成一个临时障碍物比如在第 t秒原地等待一秒或者绕开该点重新规划后更新该节点的总成本高层继续扩展冲突树直到找到一个没有任何时空冲突的节点此时该节点对应的路径就是全局绝对最优解五. 节点4大模型时代的复杂任务规划与动态重分配1. 经典前沿文章文献 RoCo: Dialectical Multi-Robot Collaboration with Large Language Models (2023)作者 Zhao Mandi Shreeya Jain Shuran Song2. 亮点工作与核心方法提出了基于大语言模型LLM/VLA的分布式辩论与动态任务重规划机制RoCo。它让多个机器人通过大模型的高维语义理解能力自发地将人类的模糊宏观指令拆解为带有时间窗的原子动作序列。同时它引入了环境反馈的文本流允许大模型在环境发生突发变化时通过“对话形式”进行在线重新规划与任务重分配Dynamic Rescheduling解决大模型时代多机器人的协同决策3. 承前启后关系承前(1)RoCo 赋予了集群理解高维语义和处理复杂任务时序依赖这个期间干什么那个期间干什么的能力利用LLM对话实现多机器人协同决策(2)加入反馈闭环不是一次规划而是通过环境反馈不断修正计划提高执行成功率启后RoCo更多解决的是高层协同与推理底层仍依赖传统规划器并没有替代CBBA、CBS这类经典算法。4.创新点(1)Dialogue-style Task Coordination原本机器人不知道别的机器人看到什么--每个机器人对应一个LLM大家聊天得到一致计划(2)Feedback-based ReplanningLLM规划错误--系统告诉LLM重新讨论重新规划直到通过验证方法文本格式解析任务约束检查IK可达性检查碰撞检测(3)论文自己提出RoCoBench这个实验平台包括六个任务用于评估多机器人协作能力5.评价指标消融实验(1)任务完成率(2)环境交互步数(3)冲规划次数6.RoCo技术架构RoCo 系统由以下三个环环相扣的核心模块组成(1)基于文本的具身场景表示Text-based Environment RepresentationRoCo 首先将三维物理仿真环境中的信息翻译为结构化的文本 Prompt将机器人的状态电量、位置、环境突变转化为文本 Prompt 状态流比如它会告诉 LLM 大脑“你现在是机器人 A你的右侧是箱子你的左侧是机器人 B当前箱子上面叠加着一个盖子”。这就为大模型提供了运行前的上下文In-context(2)多智能体辩论与协商Dialectic Multi-Agent Discussion当人类下发一个复杂的宏观任务时全场的机器人大模型大脑被拉进同一个“群聊对话流”中。多轮辩论Dialectic Debate机器人 A 在群里说“我打算先去拿面包你负责拿西红柿。” 机器人 B 结合自己的文本具身状态发现自己拿不到西红柿就会在群里反驳Debate“不行我距离西红柿太远了我应该先去开冰箱你去拿面包。”生成时序动作表经过 2-3 轮对话后大模型达成共识并直接输出高度结构化的任务步骤空间关键航路点Waypoints以及时间上的先后依赖约束这个期间谁干什么那个期间谁干什么(3)环境碰撞过滤器与上下文反馈Environment Feedback In-Context大模型在文本里聊得天衣无缝但实际物理空间可能还是会相撞RoCo 引入了一个底层的多物理体运动规划正向反馈环Feedback Loop规划器拿到大模型开会讨论出的航路点后在后台算一下如果按照这个走第 3 秒两条机械臂会撞关节反向提示词修改规划器不会直接卡死而是把这个物理碰撞结果翻译成一句大白话反馈给大模型的群聊“提示如果执行该方案机器人 A 和 B 会在坐标 X 发生碰撞。” 大模型看到这句反馈后瞬间触发 In-context Learning在下一轮对话中自发修改方案比如“那我延迟 2 秒出发你先走”从而消解了物理时空冲突