VO(Velocity Obstacle)
VO其实本身并不能算是一种算法，他只是一种解决避障问题的思路，而后续的RVO以及ORCA其实都是基于这个设定。
它提出了一种叫做Velocity Obstacle的东西，其实它也非常见文知意，其实它就相当于将一系列可能会发生碰撞的速度在速度域（几何空间内表示为以横纵速度为基的坐标系）中划分出来作为一个需要避免的区域，在选择下一帧的速度时，避免这个区域内的速度就好了。
拥有VO这个概念以后，我们最容易想到的算法其实很简单，这也是我们一般称为“VO算法”的最基础的逻辑。
假设一个场景，A和B在空间中偶遇，因为VO算法本身是分布式的，也就是每个物体只考虑物体自身，这样做的好处和意义这里就不赘述了，所以，我们从A的角度来考虑这次偶遇。
我们假设A和B都有自己的社交安全距离，这个距离是一个圆形的范围，半径分别是RA和RB，那自然而然想到的算法就是：我们这一帧的相对移动要保证两个人的最近距离要大于等于RA+RB。
这是显而易见的，实现这个目标的方法也很简单，在A的位置放置一个质点，然后在B的位置放置一个半径为RA+RB的大圆，这个大圆以外的位置都是A结束时安全的相对位置，所以这一帧的相对移动只要位于圆外就可以
但是又因为，虽然结束位置只要在圆外就可以，但是因为移动过程是连续的，所以我们移动的路径实际上是初始点到终点的一条直线，因此我们还应该保证我们不应该“穿过”这个大圆而到达大圆后方，即大圆相对于质点位置的后方的锥形区域也是不可达的
我们画出几何图形其实相当显而易见
如上图，灰色区域就是不可达区域，但是为了计算简单，同时有一定的预判效果，VO算法把整个三角区域全部视为“危险”区域
需要联想到，此时所说的这一帧质点的相对位移，其实就是质点的单帧速度，而质点的单帧速度，其实就是A和B的相对速度，所以其实我们可以非常容易的把上图映射到速度域内，其坐标系原点即为质点的坐标
可以看出来图形和上面那张坐标图的几何结构基本是一样的，只不过这已经映射到速度域了（红色区域在坐标域为危险区域，在速度域即为VO）
理论上当A和B的相对速度选择红色三角以外的点，即可安全错开
RVO(Reciprocal Velocity Obstacle)
VO的思想非常简单，漏洞也是非常明显的，就是会发生抖动，且两个agent的情况就有可能发生，让我们看看原文的例子
当A和B相向而行时，一开始A和B会错开，但当下一帧对方的速度发生变化时，他们又会把速度转回来，因为这个时候A会认为B就是向左上走的，所以我还是保持最佳的向下走也不会撞上，B也是这么想的，所以他们就转回来了
实际上这可能也不会造成最终的碰撞，因为在第二帧的时候，它们的速度确实是错开的，所以由于预判了碰撞，最终还是会很危险的错开
但这个过程中两个agent的反复横跳的过程还是不够优雅的，而原因也显而易见，VO算法中智能体总是默认其他智能体是稳定的恒速前进，这导致当对方的速度发生变化时，自己的行为就变得不符合预期
所以在RVO中最大的改进，就是我们假设对方也会使用和我们相同的策略，而非保持匀速运动。
在基础的VO算法中，产生抖动的原因是A在第2帧选择新速度之后，发现B的速度也变化了很多，A就会认为改回最佳速度（即直接指向目的地的速度）似乎也不会碰撞了，因为B的新速度其实就是假设A保持最佳速度也能不碰撞的情况下改变的，所以A就会认为B允许他转回来，但同时B也是这么想的。
然而在RVO中，A把自己的速度只改变1/2，也就是说，我们假设A和B想要错开，总共需要错开10cm，VO算法中A和B都会各自错开10cm，而在RVO算法中A只错开一半，也就是5cm，同时A假设B会错开另外一半，B也是这么想的，因此两者不谋而合，第二帧的时候，两个人各自错开了一半，并且发现此时转回最佳速度依然是会碰撞的（因为每个人只转了一半嘛），因此有效避免了上述抖动的现象。
ORCA(Optimal Reciprocal Collision Avoidance)
RVO虽然解决了VO算法出现的问题，并且在单对单的避障中几乎总是表现良好，但当智能体的数量增多时，还是会出现不符合预期的现象
假设下面一种情况，A和B一左一右的与C相向而行，在RVO中会遇到什么情况呢？
很简单，A认为C会向右转，因此自己向左转了1/2，而B认为C会向左转，因此自己向右转了1/2，而C实际上两种做法都没有选择，因为在VO图中，这实际上是两个锥体摆在自己的面前，所以C选择非常努力的向左或者向右转向
这个时候A、B、C三个人就都炸了，因为没有一个的预料是正确的，所以他们在第3帧时就会根据一个预料之外的对方速度修改自己的速度，从而形成抖动
其实原因也很简单，在RVO中，所有的智能体都假设对方只考虑自己
所以这次事故的原因就是，A认为C爱着自己，B也认为C爱着自己，但实际上C同时爱着对面两个人，就像是A找C约会，然后C把B带上一起了
虽然这种情况下实际上也不会发生真正的碰撞，因为A和B终究会向左右挪开，但过程中的抖动也是不符合预期的
后来ORCA就出现了，它切实的解决了上面这种抖动的问题（虽然我认为是碰巧解决了，因为ORCA相对于RVO的改进其实主要是效率原因）
ORCA与RVO最大的区别，在于VO的形状差异，在以往的VO算法中，VO都是以无限高度的锥形出现的，二维中就是同源的两条射线的夹角，但在ORCA中，我们使用一个有向平面来分割空间
因此求解最佳速度的计算也得到了优化，从一个由一堆尖角切出的空间变成了高考必考内容的线性规划问题
而ORCA是如何得到这个平面的呢？我们看图
首先我们还是得理解这张图，这张图很重要，p是两点的位置，r是两智能体半径，τ是单位时间（我也不知道他为什么要用τ这个字母，可能因为是t的字源？）
图a是位置域，智能体A和B在这里偶遇了
这时候我们从A的角度来看问题，把A的位置放到原点，那么VO算法中不可达区域在位置域中的位置就如同图b中大圆的部分及其后的锥形空间，即以pb-pa为圆心，半径为ra+rb的圆
而在速度域中，单位时间τ内移动的距离（也就是设定的帧间隔，同时也算是开始避障的预警时间）其实就可以理解为速度，所以保证τ时间后不会进入上述位置的VO区域，即为图b中的灰色区域，即VO。
这个不难理解吧？简单来讲就是你用小圆上的速度，刚好τ时间后会到大圆的位置，所以VO就如图b。
图c我们不用管它，其实就是为了方便我们理解的，不过我觉得其实想弄懂它完全没啥意义，而且对我们理解也没啥帮助，而且代码里其实完全没用上。
理解了这个之后，如果把这个VO解释成一个锥体，其实就是类似前面说的VO，但是ORCA中是把它解释成了一个二分平面，这个平面大概如下图所示
就是红色箭头指着的这个平面，马赛克掉的地方不用去管它，那是智能体B的平面，我们现在是智能体A，所以看不到
首先我解释一下图中的变量，vopt指的是两智能体的期望速度，一般就是指向目的地的速度，u是相对期望速度到上面计算出的VO区域外的最短向量，n是u指向的VO表面的位置的法线
这个时候平面就确定了，就是位于v的期望速度+u/2的方向为n的半平面
为啥这样确定咧？我相信聪明的小伙伴已经反应过来了，u是什么，u其实就是相对速度需要修改的值，相当于上面有一个例子里面的那10cm，所以vAopt+u/2其实就相当于A与B争端中的最佳修改后速度，到这里其实跟RVO是差不多的
但不同的是，我们得到这个值后并不是用它作为最终答案的一部分，而是由它确定了这个半平面
这个首先我们要说明为什么要确定一个半平面，其实之前说过了，使用半平面可以把问题转化为简单的线性规划问题，计算量断崖式下降
那么我们为什么要选择这个半平面呢？原因其实很简单，这是包含当前这次冲突最佳解决方案的半平面，相信聪明的小伙伴可以理解这句话。
所以，当A在完成多个平面的切割后，每次平面切割剩下的那个可选的半空间，都一定包含了当此冲突最佳解决方案的速度，比如与B之间的速度一定包含在第一个半空间内，与C之间的最佳速度一定包含在第二个半空间内
这样可以保证，在这么些半空间的交集内，出现与每个对手解决方案的最优速度的可能性是最大的，即使最后最佳速度被切走了，也总能选到相对更好的速度。
特殊情况
好的那么空间切割完毕之后，如果最佳速度处于当前空间内，就选择最佳速度，否则，就选择距离最佳速度最近的切割后空间内速度，这个速度一般位于空间的边界顶点处，也就转化为了一个简单的线性规划问题
这是论文中的图，注意图b中有一条曲线，这是因为论文中还有一个vmax，即智能体能达到的最大速度，这也是合理的，不过不属于算法核心，所以前面没讲。
当然需要注意的是，当对手非常多时，ORCA是非常容易把整个空间全部切光的，因为前面也说了，每次都切掉近乎一半的空间，所以很容易发生这种情况
这种情况的解决方案其实也很简单，就是增加了一个d变量，它表示速度到当前半平面的距离，d为正时表示当前速度在这个半平面以内，为负时表示被半平面切掉了，我们就是要找d的最大和时对应的速度，也就相当于是违规最小的速度
从几何上看就直观很多，可以怎么理解呢，其实就是把半平面向外挪，让半平面少切一部分，使得这些个半平面刚好能切出一个点，同时对所有半平面的平移最少，就选这个点作为目标速度
静态障碍物
除此之外，论文中还讨论了关于静态障碍物的躲避，其实也是合理的，因为你在送餐的时候不能光躲会动的东西嘛，也要躲电线杆才行
这个的逻辑其实很简单，就是因为障碍物本身没有速度是静止的，所以作为智能体要负责全部的躲避责任，而不是1/2了
代码中比较复杂主要是因为障碍物的构成不是一个会移动的圆，而是一条条线段连成的多边形，所以计算上复杂了很多
相关链接