⚡ electrical engineering

Motion planning for hundreds of floating robots

本文提出了一种可扩展的运动规划流水线，该流水线将大规模浮动机器人集群的避障问题分解为并行交互簇，从而能够快速生成在多达 500 个机器人的仿真及实际部署中得到验证的无碰撞轨迹。

原作者： Jan Kamm, Antonio Terpin, Raffaello D'Andrea, Aswin Ramachandran

发布于 2026-06-09

📖 1 分钟阅读☕ 轻松阅读

原作者： Jan Kamm, Antonio Terpin, Raffaello D'Andrea, Aswin Ramachandran

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位在湖面上指挥一场大规模漂浮舞蹈表演的导演。你拥有数百只微型自主小船（机器人），需要让它们从一种队形变换到另一种队形，比如从一个心形变换成“Water”这个单词。

问题在于，如果你试图同时告诉这 500 只船各自该去哪里，数学计算会变得极其复杂。每只船都需要避免撞到其他每一只船。随着机器人数量的增加，避障规则的数量会呈爆炸式增长，导致计算机需要花费极长的时间来计算出一条安全的路径。

这篇论文介绍了一种全新的、超快速的舞蹈规划方法，使得人类设计师可以实时调整动作并即时看到结果，即使是面对庞大的机群也是如此。

以下是他们实现这一目标的步骤，通过简单的逻辑进行了拆解：

1. “交通拥堵”问题

通常情况下，为机群进行规划就像是在解一个所有碎片都相互连接的巨大拼图。如果你有 500 个机器人，计算机必须检查数百万种潜在的碰撞情况。这就像是在指挥城市交通，而城里的每一辆车都在同时与其他每一辆车进行沟通。这太慢了，人类无法等待。

2. “群聊”策略（分层规划）

作者的系统并没有制定一份涵盖所有人的巨型规则清单，而是像一位聪明的组织者，将人群划分为更小的组。

第 1 步：粗略草图。 首先，计算机为每只机器人绘制一条从起点到终点的快速、粗略的线条。这条线可能会发生碰撞，但它提供了一个起点。
第 2 步：寻找集群。 计算机观察这个粗略草图，并询问：“谁实际上正在撞到谁？”它建立了一张图谱（图论中的图），仅显示那些彼此靠近的机器人。
第 3 步：拆分。 它将这些“发生碰撞”的机器人分组为小的集群。距离较远的机器人不需要互相交流。
第 4 步：并行求解。 现在，系统不再由一台超级计算机试图解决整个湖面的问题，而是将每个小组发送到不同的处理器，让它们同时解决各自的小谜题。这就像是有 50 个人同时在处理 50 个不同的交通拥堵点，而不是一个人一个接一个地处理所有的拥堵。

3. “安全缓冲”

有时，当你修复了一个小组内的碰撞时，可能会意外导致相邻小组发生碰撞。为了处理这种情况，系统在各组周围添加了一个“安全缓冲”（额外的空间和时间）。如果两个小组重叠过多，系统会聪明地在特定时刻将它们合并，解决更大的问题，然后再将其拆分回去。这防止了系统陷入不断重复修复同一个错误的死循环。

4. “智能数学”技巧

在每个小组内部，计算机使用一种特定的数学方法（称为顺序凸优化，Sequential Convex Programming）来平滑路径。作者通过改变方程的编写方式改进了这种数学方法。这就像是从杂乱的手写笔记切换到整洁有序的电子表格。这种改变使计算机求解数学问题的速度更快、更可靠，尤其是在机器人排列非常紧密的情况下。

现实世界的验证

团队不仅在计算机上进行了模拟，还在现实世界中进行了测试：

苏黎世湖： 他们成功指挥 24 只漂浮机器人 进行了一场表演。
威尼斯双年展 (2025)： 他们将其用于一个包含 8 只机器人 的艺术装置。
模拟实验： 他们证明了该系统在计算机模拟中可以支持多达 500 只机器人。

核心结论

主要的成就在于速度与可靠性。在此之前，为数百个机器人规划一场表演可能需要数小时，或者完全失败。有了这个全新的流程，设计师只需移动几个“关键帧”（舞蹈的起始和结束位置），就能在秒级时间内获得一个安全且无碰撞的规划方案。这使得创作复杂且具有交互性的机器人表演成为可能，人类可以在不等待计算机漫长计算的情况下，实时调整编舞细节。

技术摘要：数百台浮动机器人运动规划

问题陈述
本文探讨了为大规模全向浮动机器人（水面机器人）编队规划无碰撞、符合动力学可行性的轨迹这一挑战。这些机器人在平面流形上运行。与可以利用垂直维度进行避障的无人机不同，水面机器人的运动受限于二维空间，这使得协调和避障在本质上更加困难。该规划场景属于交互式表演设计，设计师指定稀疏的关键帧（起始和结束配置），并要求获得近乎即时的反馈（秒级），以生成可能跨越数分钟、包含数千个时间步长的轨迹。

核心难点在于避障的可扩展性。随着机器人数量 ( $N$ ) 的增加，智能体之间的耦合迅速增长（通常呈二次方关系），导致对两两碰撞约束的数量呈 $\binom{N}{2}K$ 比例增长（其中 $K$ 是时间步数）。对于较大的 $N$ （例如 500）和 $K$ （例如 1000），标准的顺序凸规划 (SCP) 公式会导致产生具有数亿个非零项的二次规划 (QP) 问题，从而使迭代设计循环在计算上变得不可行。

方法论
作者提出了一种可扩展的分层规划流水线，将全局耦合问题分解为较小的、独立的子问题。该流水线由四个主要阶段组成：

初始化与分配：
- 过程始于一个最小代价分配问题，用于将机器人匹配到目标位置。对于“有标签”的机器人（即拥有用户定义固定目标的机器人），其代价设为零或无穷大，以强制执行特定匹配。对于“无标签”机器人，则使用欧几里得距离作为代价，以最小化总位移，减少不必要的交换。
- 通过在起始位置和结束位置之间进行线性插值来生成初始轨迹。该初始化过程通常不是无碰撞的。
碰撞图构建：
- 构建一个时空图，其中的节点代表“机器人-时间”对。
- 空间边连接同一时间步内处于安全半径 $R$ 以内的机器人。
- 时间边连接在连续时间步中发生碰撞的同一机器人。
- 该图的连通分量定义了“碰撞簇（collision clusters）”。作者利用 KD-tree 数据结构高效地检测成对违反情况，实现了比朴素的两两检查快近 2000 倍的速度。
聚类与分解：
- 为了给优化器提供规划绕行路径的自由度，每个簇的时间窗口通过超参数 $B$ （设置为 3 秒）进行扩展（缓冲）。
- 重叠的缓冲簇通过并查集（union-find）程序进行合并。为了防止创建过大的子问题（从而抵消并行化的优势），系统实施了复杂度上限控制。如果合并导致的 QP 矩阵非零项超过阈值，则使用一种评分机制将该组拆分为多个子问题，以最小化结果子问题的最大复杂度。
子问题求解与合并：
- 每个簇都使用 SCP 框架独立且并行地进行求解。
- 公式改进： 本文引入了一种“直接转录（direct transcription）”公式，其决策向量同时包含位置和速度 ( $\chi = [p, v]$ )。这通过将动力学转化为局部等式约束，显著提高了约束矩阵的稀疏性（将复杂度从 $O(N^2K^2)$ 降低到 $O(N^2K)$ ），相比于先前研究中使用的“直接射击（direct shooting）”公式，这种改进效果显著。
- 鲁棒性： 机制包括对对称配置进行扰动初始化、在求解不可行时自适应地粗化离散化程度，以及轻量级的精修步骤。
- 环路检测： 流水线能够检测由于合并簇而导致的循环依赖问题（即产生振荡碰撞模式）。一旦检测到，冲突的子问题将被锁定为一个统一的联合子问题，并在后续迭代中处理。
- 最后，局部解被合并为全局轨迹，并且循环重复，直到找到无碰撞解。

核心贡献

可扩展的分层流水线： 一种构建碰撞图、将问题分解为交互簇并并行求解的方法，实现了在数秒内为数百台机器人进行规划。
鲁棒的分解机制： 处理常见病态情况的技术，包括快速图更新、缓冲策略、防止子问题爆炸的复杂度上限，以及防止振荡的环路检测。
优化公式重构： 在簇级轨迹优化中转向直接转录公式，这提高了 QP 的稀疏性和求解器的鲁棒性，特别是在具有高比例有标签机器人的配置下。

结果与验证
系统通过模拟和两次实际部署进行了验证：

模拟： 该流水线成功为多达 500 台机器人、1000 个时间步的规模生成了无碰撞轨迹。在一个 500 台机器人的案例研究中，当有标签机器人比例在 30% 以下时，求解器达到了 100% 的收敛率；比例更高时为 99%，计算时间通常在几秒钟内。
实际部署 1（苏黎世湖）： 一支 24 台机器人 的编队完成了跨度为 1–2 分钟（400+ 时间步）的过渡过程。设计师可以迭代调整关键帧并在数秒内重新生成轨迹。
实际部署 2（2025 年威尼斯双年展）： 一支 8 台机器人 的编队执行了跨越 2000 多个时间步的过渡。一个包含 2491 个步骤的轨迹在 1.23 秒 内完成计算。

意义
本文声称，这种以工程为导向的流水线解决了二维表面多机器人运动规划中的核心可扩展性瓶颈。通过分解问题并优化求解器公式，该方法比传统的单体式 SCP 流水线快了数个数量级。这种速度实现了流畅的交互式用户体验，允许设计师迭代调整稀疏的关键帧，并立即获得无碰撞、符合动力学可行性的轨迹反馈，而此前由于计算限制，这种能力在二维表面环境中是受到限制的。