解决了什么问题？

RVO算法属于路径规划的其中一个部分，我们可以将路径规划分为两个部分，路径规划可以分为两部分，一部分是顶层整体移动路线选择问题，这一类算法可以有A*，dijkstra等，而另一部分是在具体移动中的障碍物躲避问题。而RVO算法就是解决这个问题的，算法的核心是速度障碍物（VO）的部分，它将将来可能发生碰撞的速度都排除在外（视为障碍物），通过假设其他对象静止，通过相对速度计算速度障碍，来避免碰撞，同时保证整体的移动路线。

类似的避战算法还有：动态窗口法（DWA），势场法（PFM）等。

论文阅读

原文
其他笔记（一）
其他笔记（二）
其他笔记（三）

内容大纲

算法关键字 ：速度障碍（Velocity Obstacle），线性规划，空间划分

1. 引言
2. 相关研究
   • 提到其他研究将移动中的物体视为静态的并在它们看起来已经移动时重新规划（可以认为仍然使用路线选择的思路解决避障问题）。而少数将其他实体的反应合并到导航中的算法却无法解决震荡问题和是否可以拓展到更复杂的场景中。
3. 速度障碍物
   • 定义：velocity obstacles的基本思想是，对于两个智能体A和B，如果它们的相对速度在某个范围内，那么它们在未来某个时刻可能会相交。为了避免相交，智能体A可以选择一个速度，使得它的相对速度不在B的velocity obstacle内。
   • 解释了为什么会出现震荡：假设这样一个场景，A,B处于对方的速度区域中，为了避开对方，双方选择了不同的方向（第一次循环），当注意到自身的速度方向不处于对方的速度区域中，便修正速度到优先预设的速度方向上（第二次循环），之后便开始重复这个过程，虽然最后他们依然不会发生碰撞，但是他们是路线会像一个斜向的楼梯一样，看起来像是在抖动。

4. RECIPROCAL VELOCITY OBSTACLES（互惠速度障碍）
   - 主要是解决抖动问题
   - RVO需要通过以下三点
   - 无碰撞
   - 同一侧
   - 无振荡

ROV算法基本思想

前置知识点

• 线性规划
  • 简言之，线性规划就是寻找线性方程或线性不等式表示的数学模型的解，它由三个部分组成，变量集，目标函数，与约束条件，我们需要在约束的数学范围内找到目标函数对于目标问题的的最优解（通常是最大值或最小值）。而本算法中的线性规划问题就是，（假设有一个质点a,在面对这个空间内的其他被视为速度障碍物的对象时如果进行速度选择的问题）
• 空间划分算法（K树）
  • 空间划分的算法有许多，比如四叉树，八叉树，R树，K-D树等，K-D树是一种多维空间划分算法，它将空间划分成多个子空间，每个子空间包含一定数量的点，然后对每个子空间进行递归划分，直到每个子空间只包含一个点。K-D树可以用于快速查找最近邻点，也可以用于快速计算空间中点的分布情况。

算法分析

代码实现