群体寻路避障算法——RVO2

发表于 12天前 更新于 12天前

作者 Administrator 已删除用户

23~29 分钟 阅读

RVO2相关算法的提出是来自这篇文章：《Reciprocal Collision Avoidance and Multi-Agent Navigation for Video Games》

RVO2的官方代码可以在这里下载到：<https://gamma.cs.unc.edu/RVO2/publications/>

该算法基于速度障碍域，计算单个agent的避免碰撞的移动速度或者移动方向。算法证明是正确的，但在实践中，仍然需要解决一些该算法本身没有考虑到的问题。

本文将介绍算法原理和存在的问题，以及解决方案。

RVO2算法原理介绍

假设有 A、B 两个运动中的圆形物体，如下图所示。

为了判断下一时间点能不能相撞，可以简化一下上面的模型。将圆A简化成一个质点P_A，那么B就要相应地变成半径为r_{A}+r_{B}的圆。运行的下一时刻，只要点P_A不出现在下图中阴影区域，圆A和圆B就不会碰撞。

为了后续计算简便，将上面的坐标系转换为以点P_A为参照的坐标系，也就是将P_A当作坐标系原点进行计算。
计算避障的核心是控制物体的速度，因此坐标系转需要从上面的位置坐标系转换为速度坐标系。也就是说，X轴表示X方向的速度，即X方向上单位时间移动的距离，Y轴同理。因此只需要位置坐标系的所有坐标都除以单位时间 τ，就可以得到速度坐标系坐标了。

上图中，因为所有坐标都除以了 τ，因此阴影区域的形状也发生了改变，原来以P_A+P_B为圆心、r_A+r_B为半径的大圆，变成了以\frac{(P_A+P_B)}{τ}为圆心、\frac{(r_A+r_B)}{τ}为半径的小圆。图中阴影区域就是速度障碍域，RVO2算法就是计算物体A和物体B的相对速度，如何能够以最小的偏移偏离这个区域。如下图所示，假设物体A和B的相对速度为V_A^{opt}-V_B^{opt}。则修正向量u如下图所示，修正量为w。在官方提供的实现中，w为0.5，然而实际应用中，不能总假设遇到的行为体都是运动的，因此有必要调整w的值。
基于u, wV_A^{opt}，计算出下图右边的半平面，它表示在A的速度可以偏移到半平面右边的位置，都可以避免碰撞。并且，有多个物体时，计算出的所有半平面相互交织，计算偏转速度，就成了一个线性规划问题。

存在的问题

然而，所提出的RVO2算法，是存在缺点的。目前发现有如下三个：

完全对向移动的物体无法避碰。
w的权值计算。
速度障碍域的死锁区域。

完全对向移动的物体无法避碰

产生该问题的主要原因是当相对速度正好是速度障碍域的中心线时，每一轮迭代计算的速度都是中心线，速度方向不变，速度大小越来越小。解决该问题的方法是给期望速度增加一个随机的抖动，使双向移动的物体的速度，不可能在数值上完全平行。

w权值的计算

在官方提供的实现中，w为0.5，然而实际应用中，不能总假设遇到的行为体都是运动的，因此有必要调整w的值。该权值可以自定义，我测试的方法是使用速度大小来评估权值w，公式如下：

w = \frac{V_{self}}{V_{self}+V_{other}}

这样当另一个Agent速度大小为0时，w为1。

速度障碍域的死锁区域

速度障碍域的死锁区域是RVO2本身的缺陷。造成该问题的根本原因是多个速度障碍的重叠。如下图，橙色框住的部分是重叠的。左边Agent的前进速度，在上下两个速度障碍域对速度的修正，最后都会落到中间重叠的位置，越靠近右边两个Agent，线性规划的结果会越来越小。下面重点分析这个问题：

首先，第一步是以最大速度为半径画圆，表明对该Agent的修正速度，都只能落在这个圆内。
第二步，对第一个半平面进行处理，图中紫色为该直线的法线，表明在法线的区域内都是合法的速度。在这里，先计算直线与圆的交点（图中绿色的点），然后计算PrefVelocity与直线的交点，如果在色点范围之外，则选取绿色的点作为新的速度方向，否则取交点作为新速度的方向。
第三步，对第二个半平面进行处理。在这里，先计算直线与圆的交点（图中绿色的点），然后计算当前直线与之前处理的直线的交点，根据交点的方位，将绿色的点收缩到合法范围内。这里第一条直线已经将圆切成了两个部分，第二条直线的范围受第一条直线的影响，所以进行求交，收缩。最后计算PrefVelocity与第二条直线的交点，判断是否在收缩后的点的范围内，如果在可以作为新的修正速度，否则只能在边界点选择。
可以看到，第二次修正时，速度会变得非常小，这在模拟过程中可以观察得到。而圆的半径（最大速度）并不影响这个计算结果。
为了解决这个问题，在没有全局地图信息的情况下，我先后尝试了下面的方法，对于解决死锁问题是可行的，但是在进行大规模测试的时候，会出现新的问题：

最小速度限制
去掉RVO2的最小修正约束，每次都进行较大的修正
根据周围的Agent定制绕行方向
设置偏转方向约束
以PrefVelocity为中心，向周围Agent展开，获得最大绕行方向。
在评估的绕行方向上计算新的途径点

上述方法中，基本都能解决重叠区域死锁的问题，但会导致循环问题，或无目的地游走等不自然的现象等。
出现这些问题的根本原因是RVO2性质导致的：

RVO2算法本质是一个贪心策略，总是根据当前的PrefVelocity来进行规划，得到的是每一次迭代的局部最优解。
算法是没有全局信息和历史决策信息的，因此在信息缺失的情况下做决策，得到的结果必然不准确。比如循环问题的发生，是由于前一次决

策时PrefVelocity被修正较大，Agent进行绕行，绕行的距离较远时，周围的Agent信息发生了改变，新的PrefVelocity被判断为反方向绕行，所以Agent又绕回去，形成反复。如下图所示，Agent在上面的状态时，显示向右方向不可行，向下移动，紧接着新的PrefVelocity表明应该向上运动，就形成反复了。这就是由于缺少全局信息导致的。