一. 任务流程

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 Allocation，MRTA）形式化分类学。利用运筹学（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 算力爆炸，且完全无法应对动态未知的通信中断 

三. 节点2：CBBA算法（任务分配，逻辑冲突消解） 

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）定义了任务分配问题（组合优化问题，在满足约束的前提下，怎么分配能最大化收益），拍卖算法（计算如何分配）和共识问题（解决冲突消解）

（2）CBAA（Consensus-Based Auction Algorithmic）基于共识的拍卖算法，单任务分配，每台机器人同一时间只能接一个任务

（3）CBBA（Consensus-Based Bundle Algorithm）基于共识的捆绑拍卖算法，每台机器人可以接一系列任务（任务捆绑包），并在时间窗上有前后依赖关系,算法解决了当多个机器人在没有中央控制器的情况下，如何快速可靠地完成任务分配  

3.CBBA创新点

（1）Auction-->Bundle

机器人一次拍卖一个任务-->机器人一次拍卖一串任务（任务捆绑包）

（2）Consensus共识

每个机器人都有一个三元变量：Winning Bid Winning Agent Timestamp

机器人互相通信时如果别人价格更高，自己放弃；如果别人信息更新，自己也跟着更新。

（3）Bundle Release

之前机器人拍卖没抢到任务，只删除这一个任务--> 现在机器人删除任务表中后面所有任务（因为边际收益变了，原来的边际收益都是建立在已经抢到了这个任务的基础上的）

（4）边际收益DMG（Diminishing Marginal Gain）

任务越往后做收益越来越小，即随着前置任务的增加，边际收益会减小

文章证明了只要满足DMG，CBBA一定收敛 

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.评价指标

全局总效能 / 行驶成本：全场所有机器人完成任务的总电量损耗和绕路距离

计算时间 / 算力开销：算完一次分配需要多少毫秒

通信消息量：达成共识一共需要机器人之间发多少个数据包

收敛时间 

四. 节点3：CBS算法（时空冲突消解）

1. 奠基文章

文献： Conflict-Based Search for Optimal Multi-Agent Path Finding (2015, Artificial Intelligence) 作者： Gini Sharon, Roni Stern, Ariel Felner, & Nathan R. Sturtevant

2. 亮点工作与核心方法

提出了经典的 CBS（Conflict-Based Search，基于冲突的搜索）算法，它采用双层搜索架构：底层独立规划单个机器人的导航路径，高层（一面服务器）一旦发现两个机器人时空轨迹冲突，直接给其中一台机器人增加一条“时空硬约束”（例如：强制机器人A在第12s到15s内在路口原地等待，或者强行规划新路径）

任务规划-->任务分配CBBA-->路径规划CBS

CBS是求解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-->直到没有Conflict

5.评价指标

（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 Song

2. 亮点工作与核心方法

提出了基于大语言模型（LLM/VLA）的分布式辩论与动态任务重规划机制（RoCo）。它让多个机器人通过大模型的高维语义理解能力，自发地将人类的模糊宏观指令拆解为带有时间窗的原子动作序列。同时，它引入了环境反馈的文本流，允许大模型在环境发生突发变化时，通过“对话形式”进行在线重新规划与任务重分配（Dynamic Rescheduling）

解决大模型时代多机器人的协同决策

3. 承前启后关系

承前：(1)RoCo 赋予了集群理解高维语义和处理复杂任务时序依赖（这个期间干什么，那个期间干什么）的能力，利用LLM对话实现多机器人协同决策

(2)加入反馈闭环：不是一次规划，而是通过环境反馈不断修正计划，提高执行成功率

启后：RoCo更多解决的是高层协同与推理，底层仍依赖传统规划器，并没有替代CBBA、CBS这类经典算法。 

4.创新点

(1)Dialogue-style Task Coordination

原本机器人不知道别的机器人看到什么-->每个机器人对应一个LLM，大家聊天得到一致计划

(2)Feedback-based Replanning

LLM规划错误-->系统告诉LLM重新讨论，重新规划直到通过

验证方法：文本格式解析；任务约束检查；IK可达性检查；碰撞检测

(3)论文自己提出RoCoBench这个实验平台，包括六个任务，用于评估多机器人协作能力

5.评价指标（消融实验）

(1)任务完成率

(2)环境交互步数

(3)冲规划次数  

6.RoCo技术架构

RoCo 系统由以下三个环环相扣的核心模块组成：

(1)基于文本的具身场景表示（Text-based Environment Representation）

RoCo 首先将三维物理仿真环境中的信息翻译为结构化的文本 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 秒出发，你先走”），从而消解了物理时空冲突