[论文阅读笔记] Reciprocal n-body Collision Avoidance(ORCA/RVO2)

[论文阅读] Reciprocal n-body Collision Avoidance(ORCA/RVO2)

论文地址

Optimal Reciprocal Collision Avoidance (ORCA) (unc.edu)

Introduction

本文讨论多个agent相互避障的方法（agent与agent之间，而非agent与障碍物之间避障），并提出ORCA-即最优的多体碰撞回避算法。每个agent为了避障，速度空间中有一些部分是不可选的，通过解线性规划为每个agent选出当前的最优速度（每个agent的计算可并行），假设每个agent完全清楚其他agent的速度。在人群密度高的情况下，线性规划可能没有解，此时通过三维线性方程选择“最安全的速度”。

Previous Work

• VO

  1998年P. Fiorini, Z. Shiller. Motion planning in dynamic environments using Velocity Obstacles，不可达区域是圆锥形的；两个moving agent相互避障，避障路径容易产生抖动oscillate

• RVO

  2008年gamma :Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation (unc.edu)，agent在避障时，假设对方也会使用RVO，而非保持原来的速度矢量匀速运动，即二人共同避障，从而解决VO的抖动问题；但RVO避障时所有agent都假设对方只考虑自己，在特定情境下（比如二对一相向）还是会产生抖动

• ORCA

  优化VO模型，不再采用锥形，而是使用有向平面来分隔空间

具体的分析可以看：

论文笔记《Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation》 | 陪你度过漫长岁月 (meltycriss.com)

Problem Definition

数学化、形式化地定义了“Reciprocal n-body Collision Avoidance”问题。并作假设：

每个agent的当前位置、当前速度、半径属于外部变量，可以被其他agent观测到；最大速度、偏好速度（如当前位置到目标的连线）属于内部变量，无法被其他agent观测到。

Reciprocal Collision Avoidance

定义和求解ORCA。

一个agentA对agentB的可行速度空间：$V_B$和$V{O}_{A|B}^t$的minkowski空间和

ORCA：选包含最多与$v_A^{opt}$接近的速度的集合（半平面）

ORCA论文解读 - 知乎 (zhihu.com)

证明：论文笔记《Reciprocal n-body Collision Avoidance》 | 陪你度过漫长岁月 (meltycriss.com)

n-Body Collision Avoidance

ORCA怎么应用在实际人群仿真中。

对于每一个其他agent，分别计算与其避障的ORCA半平面，联立r=最大速度的圆形约束，通过解线性规划问题获取当前agent的可选择速度空间。在可选择速度空间中，选择与偏好速度最近的，然后更新位置。

在$(v_A^{max}+v_B^{max})t$ 之外的agent可以认为绝对不会碰撞，不需要计算其ORCA。查找需要计算的ORCA可以使用KD-tree。

解线性规划时算法使用 M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2008中的方法，时间复杂度O(N)，N为方程数目。

• 如何选择$v_A^{opt}$

  1. $v_A^{opt}=0$，那么可行速度空间一定有解，但是这样只考虑了其他agent的位置，没有考虑其他agent的速度，在人群密度高的情况下容易deadlock
  2. $v_A^{opt}=v_A^{pref}$，在人群密度比较低的情况下，会工作的很好。 但是稠密环境下容易无解，因为agent速度一般比较大；而且其他agent的偏好速度在假设中属于内部变量
  3. $ v_A^{opt}=v_A$，设置最优速度等于当前速度，是前两者的一个折中，当前速度根据情形自动适配的，也有可能无解

• ORCA线性规划无解的情况：dense situation

  选择的新速度是在同时与多个ORCA半平面的欧式距离最大化时的速度中，选择一个长度最短的速度。这种情况下，和$v_A^{opt}$没有什么关系，agent“goes with the flow”

• 关于静态障碍

  对于静态的障碍物，我们设置 $v_A^{opt}=0$ ，这可以保证总存在一个有效的速度使得机器人可以在 t 时间内避开障碍物。对于障碍物的t一般设置的比对于agent的t小，所以为了避障，agent会“更加敢”靠近障碍物。

Experimental Results

1000agent圆环经过圆心交换到对面；撤离办公室（类迷宫）

OpenMP多线程并行计算 2.66GHZ intel XEON

迷宫场景-5000人8核，125FPS解线性规划；64FPS update

（迷宫场景使用的framework也是gamma的，ClearPath:Highly parallel collision avoidance for multi-agent simulation，主要idea似乎是RVO+并行）

收获

• 形式化的数学表述

• 严谨的论文阐述过程：定义的提出、推广、实现……