⚡ electrical engineering

Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM

本文提出了一种基于非精确投影 ADMM 的算法，通过优化预定义路线上多智能体的路径点通过时间，在无需显式整数序列变量的情况下，有效解决了结构化交通系统中受路线约束的无碰撞速度调度问题。

原作者： Seungyeop Lee, Jong-Han Kim

发布于 2026-03-24

📖 1 分钟阅读☕ 轻松阅读

原作者： Seungyeop Lee, Jong-Han Kim

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

这篇论文讲述了一个关于如何让一群“自动驾驶小车”或“无人机”在固定的道路上安全、高效地跑完任务的故事。

想象一下，你正在指挥一场盛大的无人机编队表演，或者管理一个巨大的自动化仓库。

1. 核心难题：路是死的，车不能乱跑

在这个系统中，有一个铁律：每辆车必须走固定的路线（就像铁轨上的火车，或者机场里规划好的空中走廊）。

不能变道：如果两辆车要撞上了，你不能指挥其中一辆车“往旁边躲一下”，因为旁边可能有障碍物，或者那是别人的专属路线。
只能调时间：唯一的解决办法是调整速度。让前面的车稍微慢一点，或者让后面的车稍微快一点，让它们“错开”通过那个危险点。

这就好比早高峰的地铁：列车不能变轨，只能靠调度员控制发车时间，让车厢之间保持安全距离，避免拥挤。

2. 以前的方法 vs. 这篇论文的新方法

以前的方法（像“排座次”）：
以前的系统通常像是一个严厉的交警。当两辆车要相遇时，交警会大声喊：“你让路，还是我让路？”（这叫做“优先级排序”）。

缺点：如果车很多，交警要决定谁先谁后，就像让 100 个人排队，组合方式有无数种，算起来非常慢，甚至算不出来。而且，如果算错了，整个系统就卡住了。

这篇论文的新方法（像“交响乐指挥”）：
作者提出了一种更聪明的方法，不需要交警去喊“谁先谁后”。

核心思想：把每辆车经过每个路标的时间，看作是可以微调的“音符”。
魔法工具（可微分代理模型）：作者发明了一个数学模型，它能把“路标时间”平滑地转换成“车辆的实际运动轨迹”。这就好比把生硬的“点”连成了流畅的“线”，让计算机能像调音一样，平滑地调整速度曲线，而不是生硬地刹车或加速。
碰撞检测（距离惩罚）：系统会时刻盯着所有车之间的距离。如果两辆车靠得太近，就像两个音符太挤了，系统会自动给它们施加一个“惩罚力”，迫使它们调整时间，拉开距离。

3. 怎么解决？（ADMM 算法的通俗版）

为了解决这个复杂的数学问题，作者使用了一种叫 ADMM 的算法。我们可以把它想象成两个团队在合作：

团队 A（时间组）：负责安排每辆车什么时候到达哪里，尽量让所有车早点跑完。
团队 B（安全组）：负责检查有没有撞车。如果有撞车风险，它就告诉团队 A：“这里太挤了，你们得改改时间！”
合作过程：
1. 团队 A 先按自己的计划排时间。
2. 团队 B 检查，发现冲突，用一种“不精确但快速”的投影方法（Inexact-Projection），把冲突的时间点“推”到安全的位置。
3. 两个团队不断交换意见，互相妥协，直到找到一个既不撞车又跑得最快的完美方案。

这个过程不需要去纠结“谁先谁后”这种死板的规则，而是让所有车在时间的维度上自然地“流动”起来，避开彼此。

4. 实验结果：真的好用吗？

作者在电脑上模拟了三种很极端的场景：

随机交叉：很多车从不同方向穿过同一个十字路口。
瓶颈路段：所有车都要挤过一条狭窄的走廊（就像早高峰的地铁闸机）。
复杂路网：像城市空中交通网一样复杂的路线。

结果令人惊喜：

成功率高：即使在车很多、路很挤的情况下，这个方法也能算出方案，而且很少失败。
速度快：比传统的“先排座次再算路”的方法，算得更快，而且能让所有车更早完成任务。
更灵活：在极度拥挤的情况下，传统方法直接“死机”（算不出方案），而新方法依然能给出一个可行的调度方案。

总结

这篇论文就像是为固定路线的自动驾驶车队发明了一套高级的“时间调度交响乐”。它不再依赖生硬的“谁让谁”的规则，而是通过平滑地调整每辆车的“节奏”，让它们在固定的轨道上像流水一样自然、安全、高效地流动，完美解决了“路不能变，只能调时间”的难题。

这是一份关于论文《Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM》（基于非精确投影 ADMM 的预定义路线多智能体系统无碰撞速度调度）的详细技术总结。

1. 研究背景与问题定义 (Problem Statement)

背景：在城市空中交通 (UAM)、自动化仓储物流和走廊机器人操作等结构化多智能体运输系统中，智能体通常受限于基础设施或操作要求，必须遵循预定义路线 (Predefined Routes)。
核心挑战：
- 在这种约束下，传统的基于空间重规划（Spatial Rerouting）的避障方法不可行。
- 避障必须完全通过**协调运动的时间（速度调度）**来实现。
- 现有的全局规划方法（如混合整数规划 MIP）通常引入离散的顺序变量（如优先级），导致计算复杂度随智能体数量呈组合爆炸，且难以处理高密度场景。
- 现有的反应式局部方法在密集环境中容易陷入死锁或过于保守。
问题建模：
- 决策变量：智能体经过每个航路点（Waypoint）的时间 $t^{(i)}$ 。
- 目标：最小化无固定到达时间约束的智能体的任务完成时间总和。
- 约束：
  1. 固定的出发和到达时间。
  2. 速度边界（转化为航路段时长的线性约束）。
  3. 连续时间避障：在整个任务时间范围内，任意两个智能体之间的距离必须大于安全距离 $d_{safe}$ 。

2. 方法论 (Methodology)

本文提出了一种基于距离惩罚的速度调度框架，结合可微代理轨迹模型和非精确投影交替方向乘子法 (Inexact-Projection ADMM)。

A. 可微代理轨迹模型 (Differentiable Surrogate Trajectory Model)

传统的分段恒定速度模型在航路点处是不连续的，导致距离函数不可微，难以进行基于梯度的优化。

解决方案：用平滑的 Sigmoid 函数过渡替代硬性的分段激活。
动力学建模：引入一阶跟踪滞后（Tracking Lag），模拟智能体对速度指令的响应延迟。
数学表达：
- 速度近似为 Sigmoid 函数的线性组合。
- 位置通过 Softplus 函数 $\zeta(x) = \log(1+e^x)$ 的积分获得闭式解。
- 该模型将离散的航路点时间映射为平滑、可微的连续位置轨迹 $\tilde{p}(t, \tau)$ ，同时保留了航路点的时间结构。

B. 非精确投影 ADMM 求解器 (Inexact-Projection ADMM Solver)

由于避障约束（距离 $\ge d_{safe}$ ）引入了非凸性，直接求解困难。作者将问题重构为共识 ADMM 形式：

变量拆分：
- $t$ ：原始时间变量。
- $x$ ：用于处理速度/时长约束的辅助变量（凸集）。
- $z$ ：用于处理避障约束的辅助变量（非凸集）。
更新步骤：
1. $t$ -更新：求解一个稀疏线性方程组（二次规划），处理时间一致性、出发/到达时间及速度边界。由于系数矩阵恒定，可预先分解以提高效率。
2. $x$ -更新：对速度约束集进行简单的投影（闭式解）。
3. $z$ -更新（核心创新）：
  - 由于精确投影到非凸的无碰撞集是计算不可行的，采用非精确投影。
  - 定义一个基于密集时间网格的距离惩罚函数 $f(z)$ ，衡量安全违规程度。
  - 使用Polyak 型梯度步结合自适应动量（Adaptive Momentum）来最小化惩罚函数，从而修正碰撞。
  - 引入动量机制以跳出数值停滞状态。
优势：该方法避免了显式的整数排序变量（如优先级），将问题转化为连续优化问题，显著降低了计算复杂度。

3. 主要贡献 (Key Contributions)

问题公式化：将预定义路线下的多智能体协调问题公式化为基于航路点时间的优化问题，并在整个任务时间范围内定义了基于距离的安全约束。
算法创新：开发了一种针对非凸结构的可微代理轨迹模型和非精确投影 ADMM 求解器。该求解器结合了结构化的时间更新和基于梯度的碰撞修正，无需显式的整数序列变量。
广泛验证：在随机交叉、瓶颈（Bottleneck）和基于图的复杂网络场景中进行了数值实验，证明了该方法在不同拥堵水平下的可行性和时间效率，并优于代表性的分层基线方法（MIP-SOCP）。

4. 实验结果 (Results)

实验在随机交叉、瓶颈和图网络三种场景下进行，对比了不同智能体数量 ( $K$ ) 和占用密度 ( $\phi$ ) 下的表现。

收敛性与效率：
- 算法通常能在 400 次迭代以内 收敛，表现出快速收敛性。
- 即使在高度拥堵（ $K=11, \phi=10\%$ ）的瓶颈场景中，也能成功解决冲突，时间开销（相对于最小理论时间）约为 27%。
鲁棒性：
- 随机交叉：在 $K=3$ 和 $K=7$ 时，所有密度下的成功率（SR）接近 100%。在 $K=11$ 的高密度下，成功率略有下降，主要归因于物理速度限制导致的不可行性，而非算法失效。
- 图网络：当安全距离小于几何极限（节点与对边距离）时，成功率为 100%。
与基线对比 (Bottleneck Scenario)：
- 与基于 MIP-SOCP 的分层基线方法 [15] 相比，本文方法在相同场景下产生了更短的任务完成时间。
- 在 $\phi=10\%$ 的高密度下，基线方法在 SOCP 阶段失败（不可行），而本文方法仍能生成可行解。
- 本文方法无需显式的优先级分配，直接通过优化得到紧凑的调度方案。

5. 意义与结论 (Significance & Conclusion)

理论意义：提出了一种无需离散排序变量的连续优化框架，有效解决了预定义路线下多智能体避障的非凸性问题。可微代理模型成功地将离散的时间决策与连续的动力学约束联系起来。
应用价值：
- 特别适用于空间受限的场景（如空中走廊、仓库货架通道），在这些场景中无法进行空间重规划。
- 计算效率高，能够处理较高密度的智能体群，且对初始条件不敏感。
未来工作：计划加强代理模型的理论表征，提高在高保真车辆动力学下的鲁棒性，并扩展至具有不确定性和在线重规划的大型网络系统。

总结：该论文通过引入平滑的轨迹近似模型和创新的非精确投影 ADMM 算法，成功地将多智能体速度调度问题转化为一个高效的连续优化问题，在保持路线约束的同时，实现了比传统分层方法更优的避障性能和任务效率。