在上一次的文章介绍了绕行流场优化方法，提到了CombineCircle重叠导致Agent前进受到阻碍，无法绕开的问题。之所以无法绕行，是由于RVO2算法是局部避碰算法，全局信息的缺失导致无法得到全局最优解。此外，该算法在优化Agent的速度方向时，算法只考虑了单个Agent躲避其他Agent的最小避让方向，但却没有考虑多个避让方向之间是否存在矛盾冲突，这就是导致CombineCircle重叠问题导致的RVO2算法计算得到的速度越来越小的原因。
为了解决RVO2算法框架下，运动的Agent如何绕开静态Agent的问题，为静态的Agent建立绕行流场，并修改RVO2算法，在判断出Agent需要绕行时，从绕行流场中采样绕行方向，并朝着单一反向绕行。
Agent的绕行流场
绕行流场是一个全局的地图表示，无论是动态或静态的Agent都可以产生绕行流。如下图所示。
在尝试了使用格子地图来保存绕行流场的方法之后，进一步想了动态计算绕行流场的方法，这样可以节省保存流场所需的内存开销，避免更新流场带来的时间消耗。每个运动的Agent只需要根据Neighbor Agent来计算流场绕行方向。
在为RVO2算法引入绕行流场时，一般有以下几个问题需要解决：
绕行开始的条件
绕行方向的计算
绕行状态结束的条件
对于静态Agent所产生的绕行流场，增加了一个同流绕行的约束，这个概念通俗地说就是，最初产生绕行的方向，处在一个流场中，最理想的绕行方案是沿着该方向在同一个流场中绕行，这样可以避免流场和流场叠加，导致不符合预期的抖动。
绕行开始的条件
对于正在运动的Agent，触发绕行的条件是当Agent距离目标点比较远，且RVO2算法在解线性规划时，得到的速度小于一定阈值。满足该条件的Agent进入绕行状态。在估算绕行方向时，会记录每一次的绕行方向，因此在首次进入绕行状态时，标记LastAvoiding还未设置。
绕行方向的计算
绕行方向分为围绕静态Agent的绕行和围绕动态Agent的绕行。当不存在围绕静态Agent的绕行方向时，则计算围绕动态Agent的绕行方向。计算围绕动态Agent的绕行方向可以让RVO2算法更难阻塞。
无论是围绕静态Agent的绕行方向，还是围绕动态Agent的绕行方向， 计算绕行方向的方法和剔除条件都是一致的。如上图所示，是计算一个Agent的绕行方向的基本步骤。这里重点介绍在计算了相对方向之后，绕行方向的计算方法，剔除条件和同流条件的判断。
绕行方向的计算
绕行方向的计算很简单，就是将相对方向，顺/逆时针旋转90°
1 |
|
剔除条件
剔除条件就是筛选出那些可以绕开障碍物的绕行方向。在这里，设置了两个剔除条件，一个是绕行方向在PrefVelocity的顺时针方向，二个是绕行方向与PrefVelocity方向夹角必须大于一定阈值。如下图所示，在Agent周围有四个Neighbor Agent，红色的箭头是PrefVelocity的方向，紫色的箭头分别是四个Agent的相对方向，顺时针转90°的结果，上面的紫色箭头，由于处在逆时针方向的位置不会被选择，下面的紫色箭头中，最右边的箭头由于与PrefVelocity的夹角太小也不会被选中，最终的绕行方向如下图中蓝色箭头所示。
顺时针方向的度量值是两个方向的二阶行列式来实现。夹角的度量值是两个向量的点积。如下图所示，当行列式的值小于0时，为顺时针方向。
同流条件
同流条件指的是，一个流场的方向，总是基本一致的，在计算某个点的流场方向时，不应该有很大的差异，在多个流场交汇的部分，方向应该趋同，否则会被认为不是通一个流场。如下图所示的两个流场（黑色箭头和红色箭头），在右下角中红色和黑色部分方向趋同，可以认为是同一个流场，而在中间红色和黑色箭头的方向差异过大，会被认为不是同一个流场。
有了这个前提，规定一个Agent发生绕行时，只能在同一个流场中绕行，这样可以排除其他流场对绕行方向造成干扰。实现的方式就是记录每一次绕行方向，在计算新的绕行方向时，如果新的绕行方向与上一次绕行方向夹角太大，则不会被选择。这里只对静态Agent的绕行流场设置该剔除条件。
绕行状态结束的条件
Agent沿着绕行流场运行，何时结束也是一个需要解决的问题。如果仅仅只是判断Agent与目标点的距离小于一定阈值则停止，那么很可能Agent会环绕着静止的Agent运动，因为距离达不到阈值内。而仔细探究这个问题，需要回答的是一个Agent处于绕行状态时，在什么条件下恢复正常行进状态，沿着PrefVelocity的方向前进，并且能持续前进直到无法前进为止。因此可以肯定，是否要结束绕行状态，则要判断沿着PrefVelocity方向前进，是否可能会更好。
在本文给出的方案中，下面两个条件满足一个即可结束绕行状态：
绕行方向与
PrefVelocity方向基本一致时与目标点距离小于一定阈值
当Agent沿着PrefVelocity方向前进时，再次遇到阻碍，会重新进入绕行状态。
RVO2线性规划的最小速度限制
在RVO2算法中，增加最小速度限制。就是在求解线性规划时，当求解结果低于阈值的时候，在最大速度圆的基础上，增加一个最小速度的圆，对线性规划的结果进行修正，这样在Agent的较小的局部区域中，能降低CombineCircle带来的影响。修正的前提条件是距离目标点大于4个半径。
演示
下面是gif的演示。在这个例子中，Agent Neighbor的距离是50m，最大的Agent Neighbor数量是10，RVO2的TimeHorizon参数是15。最小速度限制为最大速度的0.05倍。
