想象一个这样的世界：机器人、自动驾驶汽车和无人机不仅仅是在执行剧本，而是在彼此之间进行一场高风险的国际象棋比赛，以确定如何移动而不发生碰撞。这就是多智能体机器人领域，在这里，每个机器人都是一名试图赢得属于自己的比赛，同时又要避免与其他人发生碰撞的玩家。为了实时做出这些决策，工程师们使用了一种名为“混合互补问题”（Mixed Complementarity Problem, MCP）的数学工具。你可以把 MCP 想象成一本巨大的、复杂的规则手册，它精确地描述了每个玩家应该如何行动，从而达到一种完美的平衡——在这种平衡下，没有任何一个玩家可以通过单独改变自己的动作来改善自己的处境。多年来，阅读这本规则手册的唯一方法是使用一个非常强大但封闭的软件，叫做 PATH。这就像是拥有一位能够烹饪完美佳肴的大厨，但你不能看到食谱，不能更改食材，而且必须等大厨做完一顿饭后才能开始下一顿。

现在，迎来了一支全新的研究团队，他们建造了一个全新的开源厨房——MixedComplementarityProblems.jl。他们不再是一顿饭一顿饭地做，而是想出了如何同时烹饪数百顿饭的方法，无论他们是使用标准炉灶（计算机的 CPU）还是超快速的工业烤箱（图形卡或 GPU）。他们的重大发现是：通过批量烹饪，他们可以比旧方法快大约 100 倍来解决这些复杂的机器人游戏，而且他们可以在普通的计算机上完成，无需特殊的昂贵硬件。他们还实现了在运行过程中随时调整食谱，这对于教机器人从错误中学习至关重要。

问题所在：机器人的交通拥堵

在机器人领域，当多个智能体（例如高速公路上的汽车或仓库中的无人机）需要同时移动时，情况会变得复杂。每个智能体都想尽可能快地到达目的地，但它们必须遵守交通规则并避免碰撞。在数学上，这是一个“非合作博弈”。这个博弈的解是一组特定的动作，即在给定其他所有人行为的情况下，每个人都对自己的路径感到满意的状态。

为了找到这个解，机器人需要解决一个混合互补问题（MCP）。你可以把 MCP 想象成一个巨大的、纠缠在一起的数学结。有些部分说：“如果你在车道中间，你的速度必须为零。”其他部分说：“如果你撞到了墙，你必须停止。”当你加入一个“参数”（例如改变汽车的起始位置或限速）时，这个结会变得更加复杂。在机器人技术中，你经常需要同时解决数千个这样的“结”，以规划不同的场景（例如，“如果车从这里开始？如果它从那里开始？”）。

长期以来，该行业处理这些“结”的标准程序是名为 PATH 的程序。它可靠且强大，但有三个主要缺陷：

1. 它是闭源的，这意味着开发者无法窥视其内部机制，以针对其特定的机器人进行修复或定制。
2. 它一次只能解决一个问题。如果你有 1,000 个场景需要检查，它会按顺序一个接一个地处理，这非常耗时。
3. 它与机器学习配合得不好。现代 AI 通常需要知道如果稍微微调输入，解会如何变化（这个过程称为微分），但 PATH 让这变得非常困难。

解决方案：批量化厨房

本文作者构建了 MixedComplementarityProblems.jl，这是一个完全用 Julia 编程语言编写的新型求解器。他们的做法就像是从一个一次只能做一个菜的单人厨师，升级到了一个可以同时准备整场宴席的大型厨房团队。

以下是他们是如何实现的：

1. “批量化”魔法
与其解决一个机器人游戏，然后再解决下一个，再下一个，新求解器会接收一整“批”游戏——例如，1,024 个不同的交通场景——并同时解决它们。

• 在 CPU（计算机处理器）上： 他们利用计算机的多核性能（就像有 32 名厨师在并行工作）。
• 在 GPU（图形卡）上： 他们利用图形卡数以千计的微小核心（就像一条超快速的流水线）。

聪明之处在于，所有这些游戏都共享相同的基本结构（相同的“结”形状），即使其中的数字不同。求解器意识到了这一点，并重复利用了这些工作，仅针对每个场景改变特定的数值。

2. “开源”食谱
由于代码是开源的并且是用 Julia 编写的，任何人都可以查看它、修改它，或者将其接入自己的机器人软件。它还支持自动微分，这意味着求解器可以立即告诉你：“如果我将汽车的起始点移动一英寸，整个交通模式会随之改变多少。”这是训练 AI 机器人的超能力。

3. “智能暂停”
批量求解面临的一个巨大挑战是：有些问题容易，有些难，有些则是不可能解决的。如果你等待最难的问题完成，简单的那些问题就会在那里干等着。
新求解器足够聪明，能够识别出某个特定场景是否卡住或无法解决。它会“冻结”那个问题并停止在它上面浪费时间，让批次中的其他问题继续运行。这防止了某个顽固的问题拖慢整个小组的进度。

结果：到底有多快？

研究人员使用两种类型的题目（随机数学谜题/二次规划，以及一个现实的“换道”游戏，即两辆车尝试在不发生碰撞的情况下变换车道）将新求解器与旧标准（PATH）进行了对比测试。

• 可靠性： 首先，他们检查了新求解器是否与旧版本一样出色。结果显示，它表现一致。它解决了与 PATH 相同数量的问题，证明了它不仅快，而且准确。
• 速度： 然后，他们测量了速度。
  • 对于换道游戏，新求解器在约 0.44 秒内完成了 1,024 个场景的批量处理。而旧的 PATH 方法需要 46.4 秒。这就是 105 倍的加速。
  • 即使在 CPU 上（使用 32 个线程），新求解器也比逐个运行 PATH 快 100 倍。
  • GPU 也非常快，但有趣的是，它并不总是赢家。

转折点：何时 GPU 胜出（以及何时不胜）

论文发现了一个关于使用哪种硬件的有趣细节。

• CPU 之王： 对于换道游戏，CPU（带有 32 个线程）实际上比 GPU 更快。为什么？因为换道游戏的数学特性是“稀疏”的（大部分是空白区域）。CPU 足够聪明，可以跳过空白部分，只处理活跃的部分。而 GPU 则试图同时处理整个批次，甚至包括那些被冻结或已完成的部分，这浪费了能量。
• GPU 冠军： 只有当问题变得非常大且“稠密”（充满了数字）时，GPU 才会脱颖而出。例如，当他们增加随机数学谜题的规模时，GPU 比 CPU 快了 3 倍。

这告诉我们，并没有唯一的“最佳”机器。如果你的机器人问题规模较小且稀疏，拥有许多核心的标准计算机是最好的选择。如果你的问题庞大且复杂，图形卡则会占据领先地位。

为什么这很重要

这篇论文不仅仅提供了一个更快的计算器；它提供了一种全新的思考方式。通过展示我们可以使用开源工具在眨眼之间解决数千个机器人场景，它消除了机器人技术中的一个主要瓶颈。

• 实时规划： 机器人现在可以立即为许多“假设如果”的场景进行规划，使其更安全、更具适应性。
• 学习： 由于求解器可以进行微分，工程师现在可以直接通过这些游戏来训练机器人学习更好的策略。
• 可及性： 由于它是开源的，世界各地的研究人员都可以使用这些工具，而无需支付昂贵的许可费用，也不必在开始下一个问题前等待单个问题的结束。

简而言之，作者在复杂的数学与现实世界的机器人技术之间架起了一座桥梁，证明了通过正确的批量处理策略，我们可以比以往任何时候都更快地解决多智能体机器人的混乱舞蹈。