想象一下，你是一位指挥着布满 32 个不同机器人的巨大、混乱舞池的导演。你的目标是让每一个机器人从起始位置移动到特定目的地，同时确保它们互不碰撞，也不与家具相撞。
这就是多机器人运动规划问题。
旧方法：“群体拥抱”与“独角戏”
过去，规划器主要有两种处理方式来应对这一挑战，但两者都存在重大缺陷：
- “群体拥抱”（耦合规划）： 想象一下试图将 32 名舞者作为一个巨大的、纠缠在一起的团块同时编排。你同时计算整个群体的每一种可能移动。
- 问题： 这极其缓慢。随着机器人数量的增加，数学计算呈爆炸式增长。这就像试图解决一个谜题，每增加一名舞者，拼图碎片数量就翻倍。这对计算机来说过于沉重，无法快速处理。
- “独角戏”（解耦规划）： 在这里，你告诉每个机器人：“你走你的路，如果别人挡了你的道，我会叫你停下。”你逐个为它们制定计划。
- 问题： 这很快，但风险很高。如果机器人 A 决定穿过一条狭窄的走廊，它可能会完全阻挡机器人 B。规划器没有预见到这一点，因为它没有纵观全局。
新解决方案：CIPHER
这篇论文介绍了一种名为CIPHER（基于分层扩展与细化的协调增量规划）的新方法。将 CIPHER 想象成一个智能交通控制系统，它使用的是社区地图，而非单条街道的地图。
以下是其逐步工作原理：
1. 社区地图（工作空间分解）
CIPHER 不关注每个机器人的精确坐标，而是将整个房间划分为由大型“社区”（单元格）组成的网格。
- 类比： 想象舞池是一个巨大的棋盘。规划器并不关心机器人脚的确切位置；它只关心机器人站在棋盘的哪个方格上。
2. 高层计划（多智能体路径规划 MAPF）
首先，系统使用一种快速算法为每个机器人分配一系列要穿过的方格（社区）路径。
- 类比： 交通指挥官说：“机器人 1，从方格 A 走到方格 B，再到方格 C。机器人 2，从方格 X 走到方格 Y。”他们确保两个机器人不会被分配到同一时间占据同一个方格。这很快，因为数学计算很简单。
3. “微调”（引导规划）
一旦机器人获得了它们的社区路径，它们就开始移动。规划器引导它们保持在分配的方格内。
- 类比： 这就像导游告诉机器人：“待在这个社区里，但你可以随意在这个社区内的咖啡馆或公园周围走动。”
4. 魔法技巧：“细化地图”（冲突解决）
这是该论文最大的创新点。如果两个机器人试图挤进同一个社区并陷入僵局，会发生什么？
- 旧方法： 规划器会惊慌失措，转而使用缓慢的“群体拥抱”方法来解决整个混乱局面。
- CIPHER 方法： 规划器说：“等等，这个社区太拥挤了。让我们放大！”
- 它选取那个特定的拥挤方格，将其分割成四个更小的方格。
- 它仅针对该微小区域重新运行交通计划。
- 突然间，机器人 1 可以通过左上角的小方格，机器人 2 可以通过右下角的小方格。它们安全地互相穿过，而无需计算机进行繁重的“群体拥抱”数学计算。
为什么这很重要？
该论文声称，通过采用这种“放大”策略，CIPHER 比其他顶级方法快达 10 倍。
- 它很灵活： 它在空旷房间（旧方法容易在此处困惑）和充满障碍物的杂乱房间中都能发挥作用。
- 它很智能： 只有在绝对必要时，它才进行繁重的工作（即“群体拥抱”数学计算）。大多数时候，它通过仅放大机器人发生碰撞的具体位置来解决问题。
总结
CIPHER 就像一位不试图一次性控制整个城市的交通警察。相反，他们按社区指挥交通。如果一个社区发生拥堵，他们就放大画面，将街道一分为二，让车辆通过。只有在那种方法失败时，他们才会呼叫重型交通管制团队。这使得移动机器人集群变得更加快速和可靠。
技术摘要：基于分层子问题扩展与工作空间分解细化的可扩展多机器人运动规划
问题陈述
多机器人运动规划（MRMP）面临着协调性与计算效率之间的根本权衡。为实现足够的协调以避免机器人间冲突，通常需要在机器人组的联合构型空间（复合空间）中进行搜索，这会带来显著的计算成本，且该成本随机器人数量呈指数级增长。相反，为机器人分别规划的解耦方法虽然提供了高可扩展性，但往往缺乏解决复杂冲突所需的协调性，特别是在密集环境或具有运动学动力学约束的环境中。现有的混合方法试图通过使用工作空间拓扑（例如骨架）来引导规划以平衡这一矛盾，但这些表示方法在开放环境中往往难以奏效，或迫使机器人进入不必要的近距离，从而导致冲突解决成本增加。
方法论：CIPHER
作者提出了CIPHER（具有分层扩展与细化的协调增量规划），这是一种混合 MRMP 算法，它利用分辨率引导在高层协调机器人，从而减少在计算昂贵的复合空间中进行规划的需求。
核心框架
CIPHER 基于规划 - 检查 - 解决范式运行，分为五个阶段：
- 分解与 MAPF（高层）： 工作空间被划分为均匀网格的矩形单元格。多智能体路径寻找（MAPF）算法（具体为基于冲突的搜索）为每个机器人计算无冲突的区域转换序列。这提供了一个独立于特定机器人动力学的顶层拓扑引导。
- 引导规划（底层）： 每个机器人独立使用基于采样的规划器计算动力学可行的轨迹（几何系统使用 RRT Connect；运动学动力学系统使用区域引导的 DB-RRT）。高层区域路径作为启发式信息，将采样偏向特定区域，而不严格约束路径，从而保持概率完备性。
- 冲突检测： 生成的轨迹被离散化为固定时长的片段。系统在每个时间步检查所有机器人对是否存在几何冲突。
- 分层冲突解决： 如果检测到冲突，CIPHER 采用逐级升级的策略层级来解决冲突，而无需立即诉诸复合空间规划：
- 分解细化： 将发生冲突的特定网格单元格细分为更高分辨率。在该细化单元格内重新求解 MAPF 问题，以寻找冲突机器人的替代子区域。
- 空间扩展： 如果细化失败，则将解决区域扩展以包含相邻单元格（包括对角线）。在该更大区域上重新求解 MAPF 问题，以发现替代路线。
- 回退规划： 如果在耗尽分层解决策略后冲突仍然存在，规划器将回退到标准复合规划器（Composite RRT），在联合构型空间中解决问题。
关键区别
与使用基于骨架的引导（可能在开放空间中限制移动）或反应式冲突解决的先前工作不同，CIPHER 使用迭代区域分解细化。这允许规划器通过仅在必要时增加工作空间表示的分辨率，主动将机器人分离到不同的路径中。
主要贡献
本文确定了三个主要贡献：
- CIPHER 算法： 一种混合规划算法，通过在区域分解上搜索来在高层协调机器人，显著降低了复合空间规划的频率。
- 分辨率引导： 一种新颖的过程，在规划过程中迭代细化工作空间表示。这允许系统在更精细的层面上引导机器人运动以解决冲突，而不是仅仅依赖静态引导。
- 实验验证： 广泛的评估，将 CIPHER 与最先进的几何和运动学动力学 MRMP 方法（包括 Coupled RRT、Decoupled RRT、sRRT、ARC 和 WG-DaSH）在各种环境中进行了比较。
实验结果
作者在从空旷空间到高度杂乱房间的各种环境中，对几何和运动学动力学系统评估了 CIPHER，机器人数量扩展至 32 个。
- 成功率： CIPHER 在所有测试环境和机器人数量下，对于几何和运动学动力学变体均实现了100% 的成功率。相比之下，由于骨架约束，WG-DaSH 等方法在开放环境中表现挣扎，而解耦规划器（如 PP-RG-RRT）则因未解决的冲突在高密度场景中失败。
- 规划时间： 与其他最先进的方法相比，CIPHER 展示了高达一个数量级的规划时间改进。
- 与Coupled RRT相比，CIPHER 避免了联合空间搜索的指数级成本。
- 与Decoupled RRT和PP-RG-RRT相比，CIPHER 在其他方法失败的情况下保持了高成功率，同时仍比仅在冲突发生后扩展到复合空间的反应式混合方法（如 sRRT 和 ARC）快得多。
- 运动学动力学性能： 对于运动学动力学规划器，CIPHER 优于 K-ARC 和运动学动力学 WG-DaSH。虽然一种朴素的引导规划器（PP-RG-RRT）速度更快，但它在密集场景中成功率较低，突显了 CIPHER 成功驾驭的速度与鲁棒性之间的权衡。
意义与主张
本文声称，CIPHER 通过将协调负担从高维联合构型空间转移到分层工作空间表示，解决了多机器人规划中的可扩展性瓶颈。通过使用分辨率引导，该方法通过自适应细化主动避免冲突，而不是被动地解决冲突。
作者断言，这种方法允许实现：
- 鲁棒性： 在开放环境（骨架引导失效之处）和狭窄通道中均能有效运行。
- 效率： 降低了与复合空间规划相关的计算开销，实现了高达 10 倍的加速。
- 完备性： 理论上的概率完备性得到保证，因为如果所有分层策略都失败，算法会回退到概率完备的复合规划器。
这项工作表明，细化工作空间表示本身可以作为一种强大的冲突解决机制，为传统的耦合或纯解耦规划策略提供了一种可扩展的替代方案。
每周获取最佳 computer science 论文。
受到斯坦福、剑桥和法国科学院研究人员的信赖。
请查收邮箱确认订阅。
出了点问题，再试一次？
无垃圾邮件，随时退订。