速度障碍法 / ORCA

Velocity Obstacles / Optimal Reciprocal Collision Avoidance进阶

在速度空间里划出「会撞」的速度集合，选一个不撞且最接近期望的速度。

速度障碍（VO）由 Fiorini 与 Shiller 提出，1998 年发表于 IJRR：假设障碍物保持当前速度，把本机器人所有会在未来某时刻与它相撞的速度收集起来，在速度空间里形成一个锥形区域，只要选锥外的速度就不会撞。多个机器人都这么做时，双方会同时躲开、又同时回来，来回摆动。2008 年 van den Berg 等提出互惠速度障碍（RVO），假设对方也会躲；之后 van den Berg、Guy、Lin、Manocha 提出 ORCA（最优互惠避碰，论文 2011 年正式出版），规定每一对智能体各承担一半避让责任，把每个邻居的约束写成速度空间里的一个半平面，再解一个低维线性规划，选出离期望速度最近的可行速度。它不需要通信，能实时处理上千个智能体，开源库 RVO2 被用于人群仿真、游戏和多机器人导航。它只考虑速度和几何形状，不处理复杂动力学。