cornering：RVO和ORCA它们是如何工作的？

转自：https://www.bilibili.com/read/cv7242625

19.1 Introduction

  RVO算法以及衍生算法，如HRVO和ORCA，近年来已经成为电子游戏中解决碰撞问题的标准。这是一个了不起的成就：游戏人工智能领域对待新技术十分谨慎，特别是那些直接从学术文献中提取出来的技术。但是RVO解决了一个业内没有广泛共识解决答案的问题。此外，它很容易理解（简单的几何推理），易于学习（创造者避开了传统学术写作的晦涩难懂，而且写得很清楚很好），而且易于实现（创作者免费提供了参考源代码）。

  确实的理解它们的工作原理，是十分重要的一件事。这可以通过以下四个步骤来实现：

了解RVO做出的假设，以及确保它能正常工作所需要的保证（条件）。

认识到这些假设和保证在实践中经常遭到违反。

弄清楚为什么RVO仍然有效。

把它调整得更好。

  在本章的剩余部分，我们将带你探寻这几个步骤。我们的目标不是给你一个完美的碰撞避免系统，而是让你了解VO方法的细微差别，并帮助你迭代开发一个适合你游戏的避碰系统。不过，首先，简要介绍RVO和VO方法的历史。

19.2 History

  VO算法最初是针对可移动机器人开发出来的，也就是让现实中的真实物理机器人，在移动时不会互相碰撞。与以前的机器人转向方法相比，VO算法的目的是：

去中心化，每个机器人都有自己的决策，而不是所有的机器人都被一个中央控制器控制。

独立性，决策完全基于每个机器人对其他机器人位置和速度的观察。

  这些特性对游戏开发人员没有多大用处，但它们对于理解VO方法的优缺点非常重要。VO智能体不显式地互相通信或协作。它们之间的合作是一种随着时间推移而进行的观察、决策和行动所共同形成的。VO方法避免了多智能体规划的困境，而只关注于单个智能体的行为。但是缺乏协调意味着智能体在预测其他智能体将要执行的操作时可能会出错，从而无法进行适当的合作。

  原始的VO方法非常容易遇到这样的问题，当两个智能体处在碰撞过程中时，就会发生速度来回抖动的现象，如图19.1所示。每个智能体都假设对方是一个以恒定速度运动的无意识对象，因此当对方改变方向时，会破坏原本的计划，导致运动方向的反复变化。

19.2.1 Introducing RVO

  为了解决抖动问题，RVO算法出现了。这个算法为智能体提供一个决策行为，并假设另一个智能体也在使用相同的决策行为。在一次碰撞过程中，每个智能体只会朝自己的方向移动一半的距离，并期待其他智能体也会承担自己的责任朝自己的方向移动另一半距离。本文证明，这将消除错误的预测，并在智能体进入视野后，一步到位地将智能体设置在最佳无碰撞路径上。如图19.2所示。

19.3 Examining RVO’s Guarantees

  无碰撞运动的证明只适用于一个包含两个智能体（没有障碍物）的世界。只有两个智能体，每个智能体都可以自由选择最完美的运动速度，而不必躲避其他东西。此外，在世界上没有其他东西的情况下，每个智能体都可以假定另一个智能体的当前速度也是他们的预期速度。

  让我们加入第三个智能体，看看在图19.3中会发生什么。A和B并排向南移动，这时他们看到C向他们走来。

  此时A会向西面躲避，并认为C会向东躲避。同时B会向东躲避，并认为C会向西躲避。显然C不能同时做到这两件事。事实上，这两件事C都没有做到，相反它选择了从A和B的西面进行躲避 （图中间那种情况）。（对于C来说，躲向东面同样有效，但是这里假设它向西走。）

  现在三个智能体都不开心了。A和C由于都向西躲避而将会碰撞在一起。B虽然不会撞到任何东西，但也偏离了预期速度。这种情况下，对C来说，最好的选择是一个朝向正北的移动；它认为向东偏移是可行的，因为A向西偏移了，甚至可能会被往复运动的B所碰撞到。接着，A决定回到预期速度的正南方向上，并期待C已经朝西走了足够远的距离。B也会回到原来的方向上，因为它也认为C已经走了足够远的距离，不会导致碰撞发生。

  简而言之，在两帧之后，我们回到了原来的问题。RVO解决了的两个智能体之间的抖动问题又在三个智能体运动当中出现了。换言之，RVO不能保证在上述情况下避免碰撞，因为对智能体之间的可能速度和预期速度的看法不一致。

  理论上在真实的场景中，RVO能在上述情况下避免碰撞，让C安然的通过A和B。但是，我们看到这种情况没有发生，那么到底发生了什么？

  好吧，其实在两帧之后，问题还是有些不一样的。在这两个帧上，A和B稍微分开了。C已经稍微向西移动，现在正朝北偏西的方向移动（如19.3第三个场景）。在以后的帧中，这些细微的偏移会更加明显地影响到以后的决策。虽然最初有大量的“抖动”随着速度的变化而变化，但三者最终还是设法合作了。

  事实上，你可以争辩说，这才是合作应该的样子，每个智能体不仅猜测对方的计划，而且会在这些计划不成功时作出反应。最终，三者同时做出完全兼容的决策，然后坚持这个决策直到安全的通过。

  至此，通过完美的预测来实现完美碰撞避免的尝试已经失败了。那么，RVO在原始VO上有什么收获吗？事实证明，有的。在VO算法下模拟这个场景，这三个智能体将振荡更长时间。很容易就能构建出RVO可以实现但VO不能的场景，但RVO的意义远不止于此。

  在图19.4中，让我们看一个场景，其中B向北走向A。但是，我们假设A出现故障，处于停顿状态，而不是执行正确的回避。

  这是B完美应用VO算法的场景，也许你期待着RVO算法在此种情况下失效，但事实上它仍然很好的完成了工作，实现了AB之间的碰撞避免，即使A出了故障没有工作。在第一帧，B发现了A，因此朝自己的方向移动了一半的距离。在第二帧，B又发现了A，因此又朝自己的方向移动了一半的距离。在接下来的时间里，B不断重复执行上述决策，直到通过A。在原来的设计里，B是期待A也同时承担躲避的责任，但即使A没有这样做，B还是能很好的处理这种情况。

  RVO的神奇之处在于，它能在紧急避碰情况和正常避碰情况之间取得平衡。RVO算法下的智能体面对碰撞时会偏离一段距离，但不会太多。不像VO算法会由于偏离太多导致超过预期速度而需要修正。此外，即使它偏移的距离较短，也仍然是为了弥补未来帧的差异。这种魔力并不是RVO所独有的：所谓的梯度方法，例如寻找函数极小值的梯度下降算法，以及类似的技术，使用乘数来避免超出目标。

19.4 States, Solutions, and Sidedness

  任何梯度法的目标都是收敛到一个局部最优状态，在此状态下无法进行进一步的改进。为了避免碰撞，智能体通常看起来像是在狭小的空间中挤过去的。再近一点，它们就会相撞；再远一些，它们就会浪费时间。

  不过，RVO并不完全是一种梯度方法。在普通梯度法中，您有尽可能多的步骤来收敛到一个最佳值；您只受处理时间的限制。但是在标准的VO方法中，每次迭代后，智能体都会沿着它们选择的速度移动。因此，当RVO模拟的“状态”是所有智能体的瞬时位置和速度时，“解决方案”是智能体随时间的全部轨迹。

  不过，在我看来，有一种更明显、更有用的方式来思考避碰问题的“解决方案”：Sidedness。两个相互靠近的智能体可以向左躲闪，也可以向右躲闪；任何一种方式都是潜在的解决方案。如果这两个方案没有冲突，那么其中一个可能是更好的解决方案，因为可以更快的抵达目标；但两者都是稳定的：一旦走上其中一条轨道，除非形势发生变化，否则智能体不会改变主意。

  可以从三个方面来定义 Sidedness。所有这些方面都涉及到“最接近”这个概念。假设有两个智能体，它们现在的运动轨迹使它们逐渐相互靠近，算出在未来中使A和B最接近的那个时间点（它们之间必须有缝隙），并计算从A的中心到B的中心的向量。

  第一个概念是绝对的：如果这个向量是朝东的，那么A会从B的西面通过，B会从A的东面通过。用这种方法计算的Sidedness在A的计算和B的计算之间总是对称的。

  第二个概念是相对于现时速度的：如果这个最接近向量绕着A相对B的速度离开，则A从左侧通过B，类似地，如果向量向右离开，A从右侧通过B。此计算同样是对称的：两者都将向左偏移，或者都将向右偏移。

  第三个概念是相对于A的理想速度而言，紧靠最接近向量。这种表述最符合我们对“可通过的一侧”的直觉。但是，在A和B的当前速度与所需速度不同的情况下，这可能会不一致。结果，Sidedness作为协调工具通常使用前两种表述之一。

19.5 ORCA

  继承了原始RVO算法（实现ORCA的参考库称为RVO2）的ORCA算法（van den Berg等，2011）以这种sidedness概念为中心。但是，ORCA不太关注稳定性，而更关注最优性。 回顾图19.3中的三个智能体回避场景，一个主要问题是智能体双方对避让策略的看法不一致。

  如果一个智能体打算从左边通过，而另一个人则打算从右边通过，那么冲突是不可避免的。由于ORCA保留了其他VO方法的独立性，去中心化设计，因此无法解决同向碰撞问题。取而代之的是，ORCA强迫智能体维持其当前的通行路线。 两个不在一个精确定义的碰撞路线上的智能体一直在确定可通行路线，即使在它们的路线上没有足够的间距来避免碰撞。ORCA以扩大间距的方式来避免碰撞，同时维持行进路线。

 ORCA背后的一个隐含假设是，当智能体首次遇到对方时，“原始”可通行路线就恰好是可行的。值得注意的是，这种假设通常是正确的，特别是在没有静止障碍物的情况下。当ORCA求解成功时，它将产生一个可靠的合理的最佳碰撞避免路线，并且消除了速度抖动。

  问题在于ORCA常常求解失败。尽管一个RVO智能体生成的一组碰撞速度是一个无限锥（排除了大量的潜在速度），但是一个ORCA智能体生成的一组碰撞速度是一个无限的半空间（排除了大约一半）。少部分靠得过近的智能体很容易就排除掉所有速度。实际上，图19.3的三个智能体问题就可以做到这点。C的行进路线在A的右边B的左边；A使C无法向左移动，B使C无法向右移动，并且AB都使C无法直线移动，甚至让C无法停止或向后移动。ORCA通过解决线性约束来满足这一要求，这会产生一个能最大化最小通过距离的速度。

  同RVO的部分规避一样，ORCA的约束松弛具有解决多个帧上复杂的回避场景的效果。虽然A必须求助于“最坏”的解决方案，但B和C都有合法的速度，这会给A留下更多的空间。事实上，ORCA在一帧内就解决了这个问题，因为a的“最差”速度实际上是正北。更一般地说，当两排朝不同方向前进的智能体相遇时，ORCA的作用是扩大行距，从最外层开始。RVO也这样做，但ORCA禁止中层在发生这种情况时采取极端的规避行动，因此，通过保持原有的可通行路线设置，从而获得更简洁、更优的解决方案。

19.6 Cornering

  ORCA在现实世界中表现出更严重的问题。在大多数关于VO方法的文章中，都假设每个智能体都有一个预期的移动方向，要么是恒定的，要么是直接朝向一个固定的目标点。但在大多数比赛中，行进的方向是通过沿着一条通向目标的路径来确定的，这条路径绕着拐角旋转。

  VO方法可以适应航向偶尔的变化，没有太大问题。但在转弯时，智能体的预期的移动方向每一帧都会改变。

这违反了前面提到的假设，即每个智能体上一帧的速度是当前帧的预期速度。RVO智能体在转弯时或对附近的智能体进行反应时会出现异常的轨迹，也就是说，当智能体改变通行路线时，会出现一个独特的“急转弯”现象。

  但ORCA不允许这样的“突然”。如前所述，原始的通行路线通常是最理想的路线的近似值，但在拐弯的时候并非如此。ORCA智能体在拐角处通常会移动得更远一些，远离期望路线来保持通行路线，或者只是被卡在角落里，不愿意继续前进也无法做出其他决策。当所有智能体朝着同一个目标前进时，这种行为有时是可以接受的，因为前端智能体仍然可以继续前进，但通常会导致频繁的死锁。

19.7 Gradient Methods Revisited

  我们想从碰撞避免中得到的是让智能体快速找到一组通行路线，并且理想情况下该解决方案不会偏离最优值太多。当出现一个新智能体，或当前智能体改变了决策时，我们希望系统能够快速适应并找到新的解决方案，并使新的解决方案看起来尽可能像旧的解决方案。关键在于权重。

19.7.1 Modifying Weights

  在原始的RVO论文中，可以给智能体“赋权”，只要两个权重加起来等于1，并且两个智能体都同意这些权重是多少，那么一个智能体可以比另一个智能体多移动几个百分点或少移动几个百分点（两个智能体整体需要移动的总距离）。但是，如果我们将RVO视为一种梯度方法，而不是一个即时的、完美的碰撞解答器，那么，很明显，没有什么能强制这种约束。例如，你可以将这两个权重都设置为0.1，使智能体在多数帧上缓慢地移动。或者可以将两个权重都设置为0.9，使智能体快速闪避，表现出RVO为了避免抖动而做出的设计（事实上，原始VO可以视作RVO的一个特例，即所有权重都设置为1）。

  如前所述，RVO不完全是一种梯度方法，因为智能体在每次迭代后都会移动。除此之外，如果即将发生的碰撞还没有得到解决，每接近一点问题都会更难一些。如果两个智能体处在碰撞过程中，且他们之间的权重之和小于1，那么它们每帧的决策都不可能完全解决碰撞问题，并最终使他们发生碰撞。如果一个算法有恐慌的时候，那么这种情况就是算法恐慌时的样子。

  不过，低权重也有其优势。它们倾向于得到更好的解决方案，特别是对于大量的智能体。但我们需要一种方法来应对他们逐渐失败的趋势。

19.7.2 Substepping

  回想一下，作为一种机器人控制算法，RVO依赖于一个转向、移动和观察的循环。一个机器人不能对另一个机器人作出反应，直到另一个机器人真正转向并开始朝另一个方向移动。但有一个好处是即使不移动智能体，我们也可以在每次转向步骤后立即知道所有智能体的速度。我们可以利用这些知识来作弊，在每个动作步骤之间运行RVO的多次迭代。一个RVO子步骤的速度输出成为下一个子步骤的速度输入，且位置保持不变。

  这有很多优点，当多组智能体突然遇到彼此时，很可能会有许多帧出现速度抖动的现象，如前面所述。子步骤会让抖动在速度被呈现给动画系统之前消失，这会给人一种错觉，认为所有的智能体都在第一时间做出了一致的选择。

  子步骤还可以让设置权重更灵活，权重总和小于1无法解决碰撞问题，但他们善于找到有效解决办法的种子。在由许多子步骤组成的步骤中，可以从低权重开始平滑地寻找有效解决方案，然后将权重增加到0.5来沿着无碰撞路线融入到该解决方案中。

  如果你熟悉随机优化方法，你可能会发现，这种从保守到突然的计划是违背直觉和倒退的。然而，这里的目标是可靠地收敛到满足局部最优的约束，而不是在保持约束的同时可靠地收敛到全局最优。

19.7.3 Time Horizons

  ORCA的转弯问题（卡住而不是改变路线）是当恒定预期速度的假设被违反时，VO方法展示出来的一个更大类问题的例子。另一个更简单的形式可以用一个VO智能体向北移动到一个目标点来演示（后面有一堵墙）。所有向北的速度都被墙壁上的静态速度障碍物所阻挡，因此无法到达目标。

  原始的RVO开源库不存在这个问题，因为它没有完全按照论文来实现，并且如果它们超出了最大停止距离就忽略与静态障碍物的碰撞。其他RVO实现通过定义最大碰撞时间（TTC）来解决此问题，超过该时间的碰撞将被忽略，这会使智能体在接近障碍物时速度减慢，使其TTC保持在阈值以上。第一种方法假设未来的决策将停止；第二种方法假设超过最大TTC的轨迹太不可预测，不纳入考虑。这两种方法都是合理的，但都是相当武断的，当智能体最终挤在静态障碍物和其他智能体之间时，可能会导致碰撞。

  无论时在转弯还是接近墙前面的目标，基本的问题是智能体试图避免在他们永远无法到达的地点发生碰撞。转弯智能体将在到达碰撞点之前就会转向，接近目标的智能体会先停下来。

  那么，一个更正式的方法是计算智能体计划在其目标处停止或转弯的时间，并避开一定会在这段时间之后发生的碰撞。时间范围特定于给定的速度候选。

  时间范围在拐弯时有点棘手，因为智能体不打算在在那之后消失不见，而只是稍微转一转。一个正在转弯的智能体的时间范围接近于零，但不应完全忽略碰撞。相反，你可以构建一个平面，垂直于智能体的后转弯方向，这个智能体从未打算穿过这个平面。如图19.6所示，经过该平面的碰撞可以被安全的丢弃。

  这并不是一个完美的解决方案，因为智能体仍然没有考虑到转弯后会发生的碰撞。而且，智能体并非永远不会越过它们的转弯平面：有时它们这样做是为了避免在拐角处发生碰撞。一个更好的解决方案是由智能体的路线定义的空间中预测碰撞，而不是世界空间。但是，由于每个智能体都有自己的路径，在一般情况下，以一种能够确保可以得到预期结果的方式来做这件事是很难做到的。

19.8 Progress and Penalties

  原始的VO算法将避免碰撞视作第一要务，而沿着预期方向移动则是次要的，仅当在一组非碰撞且因此有效的轨迹中进行选择时才起作用。但正如我们所看到的，避免远距离碰撞并不总是必要的或合理的：在当前步骤和预计的碰撞之间，会发生很多事情，特别是当涉及到许多智能体时。

  RVO算法弱化了VO算法的约束，当评选候选速度时只将预计碰撞视作需要考虑的一个方面，因此让RVO算法成为一种实用方法。（ORCA不会以同样的方式弱化其约束：其约束松弛是为了产生至少一个允许的速度，而不允许在非碰撞速度可用的情况下选择碰撞速度。）

  候选速度的一个基本作用是用来计算预期速度和候选速度之间的距离。预测碰撞被视作惩罚项，降低候选速度的作用，且惩罚项会随着碰撞越加接近而增加。如果预测一个候选速度将导致多个碰撞，则可以使用最快发生的碰撞来确定惩罚，或者每个碰撞可以生成一个单独的惩罚项；后一种方法倾向于将智能体从人群中推离，从而减少拥塞。

 上面这样的附加公式是由实用性而不是理论驱动的：它不能保证避免碰撞，并且增加了用户指定参数的数量，这使得调整变得更加困难。然而，在实践中，它比纯粹的VO算法在消除拥塞方面更有效，因为它不考虑遥远的碰撞，使它对近距离的碰撞反应更强烈。

19.8.1 Putting Sidedness Back In

  加法公式不会自动保持侧性（尽管使用了子步骤的方法来帮助）。然而，没有什么能阻止我们把它作为一个额外的惩罚条款。简单地计算一下，对于每一个候选速度，它改变了多少个智能体，然后为每个代理添加一个惩罚。侧性变化惩罚项的比例应该类似于碰撞惩罚项；因为有时需要将它们应用于没有预测碰撞的智能体，但是，可以使用最接近时间法代替TTC法。

19.8.2 Progress and Energy Minimization

  在上面的加法公式中，候选速度的基本作用被计算为与预期速度的距离。

这不是唯一的选择：另一个选择是进展比率。在这个公式中，主要的度量是一个智能体朝着它们的目标前进的速度，计算为候选速度与单位长度的预期移动方向的点积。与距离指标相比，进展比率鼓励侧方躲避而不是放缓速度，并倾向于让智能体更快地达成目标。

  从人类实际行为的角度来看，进展比率是一种不切实际的效用。想想看，当从一个地方移动到另一个地方时，人类可以选择短跑，但通常以步行速度移动。生物力学研究人员解释说，这是一种能量最小化的趋势：正常的步行步态通过最大化速度与功率输出的比率，使人类以最小的能量消耗达到目标。

以非预期速度移动所浪费的能量的粗略近似值，可由预期速度和候选速度之间的平方距离计算出来；平方项将其与RVO方法区分开来。使用此公式进行计算的智能体显示出类似人类的轨迹，通常稍微减速以避免碰撞，而不是向左或向右转弯。

19.9 Putting It All Together: How to Develop a Practical Collision Avoidance System

  对基于VO的避碰系统中涉及的所有细微差别、决策和参数都有透彻的了解，并不能自动让你有能力做出完美的碰撞避免系统。我们深信，没有完美的避免碰撞系统，只有一个能很好地配合您的场景、需求和动画系统的系统。开发这样一个系统，就像开发游戏系统一样，是一个迭代过程。为了提高流程的有效性，您可以做一些重要的事情：

建立一个碰撞避免场景库，涵盖系统需要处理的各种情况。这些应该包括游戏中可能遇到的所有因素：静态障碍、转弯、多组智能体等等。当您遇到系统问题时，请创建新的场景来重现问题，并测试对系统的更改是否已解决这些问题。

建立一个碰撞避免算法库！当你做出改变时——无论是对使用中的基本算法还是参数的值——保留旧算法，不仅仅是在源代码控制中，而且是在实际运行代码中。这将允许您评估您的迭代更改在多大程度上改善了碰撞避免质量，并允许您测试解决特定问题的多种方法。通常，以后对系统的调整会使早期的调整变得不必要，保留早期版本可以帮助您识别并删除它们，从而使您的系统尽可能简单。

写一个框架，针对每个碰撞避免场景自动测试每个避碰算法。这并不像听起来那么简单：很难制定标准来确定某个特定算法是否“通过”特定的测试。作为第一步，您可以简单地检查一个算法是否最终成功地将所有智能体都带到它们的目标，而不会在路上发生碰撞。您可以比较两种算法，以确定哪种算法能更快地让智能体到达目标，但请记住，在游戏场景中，几秒钟的差异并不显著。不要孤立地测试碰撞避免，这一点很重要：如果碰撞避免输入到动画系统中，而不是直接控制代理位置，则必须使动画系统成为测试台的一部分，以确保结果准确。自动测试平台主要用于快速检查一个或多个测试场景中的显著回归。它还可以用来快速确定一组控制参数的最佳值。

不要过于依赖你的自动化测试工具，需经常亲自查看测试结果。一些避免碰撞的算法可能会出现伪像，这些伪像不会显著影响结果的客观最优性，但是对于玩家来说，这看起来是不真实的；速度抖动就是一个很好的例子。你可以试着提出一些测试，但是主观评价是无法替代的。

19.10 Conclusion

  VO算法之所以流行，是因为它将碰撞避免转化为速度空间中的问题，这使得解决问题变得简单起来。特别是RVO算法提出的让多个智能体分担碰撞避免的责任的方法。但是VO算法尤其是RVO算法在实践中的成功依赖于更微妙的因素，将RVO视为一种纯几何方法，使得利用这些因素并使其最大化变得更加困难。因此，通过多个方面来观察VO算法是很重要的：作为几何解析器，作为梯度方法，作为实用方法。这种整体方法并不是一件简单的事，但碰撞避免并不是一个简单的问题。理解问题空间的细微差别和解决方案空间的复杂性是开发适合您的系统的关键。