[论文阅读] Reciprocal n-body Collision Avoidance(ORCA/RVO2)
文章目录
- [论文阅读] Reciprocal n-body Collision Avoidance(ORCA/RVO2)
- 论文地址
- Introduction
- Previous Work
- Problem Definition
- Reciprocal Collision Avoidance
- n-Body Collision Avoidance
- Experimental Results
- 收获
论文地址
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_B
VB和
V
O
A
∣
B
t
VO_{A|B}^t
VOA∣Bt的minkowski空间和
ORCA：选包含最多与
v
A
o
p
t
v_A^{opt}
vAopt接近的速度的集合（半平面）
ORCA论文解读 - 知乎 (zhihu.com)
证明：论文笔记《Reciprocal n-body Collision Avoidance》 | 陪你度过漫长岁月 (meltycriss.com)
n-Body Collision Avoidance
ORCA怎么应用在实际人群仿真中。
对于每一个其他agent，分别计算与其避障的ORCA半平面，联立r=最大速度的圆形约束，通过解线性规划问题获取当前agent的可选择速度空间。在可选择速度空间中，选择与偏好速度最近的，然后更新位置。
在
(
v
A
m
a
x
+
v
B
m
a
x
)
t
(v_A^{max}+v_B^{max})t
(vAmax+vBmax)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
o
p
t
v_A^{opt}
vAopt
-
v
A
o
p
t
=
0
v_A^{opt}=0
vAopt=0，那么可行速度空间一定有解，但是这样只考虑了其他agent的位置，没有考虑其他agent的速度，在人群密度高的情况下容易deadlock
-
v
A
o
p
t
=
v
A
p
r
e
f
v_A^{opt}=v_A^{pref}
vAopt=vApref，在人群密度比较低的情况下，会工作的很好。 但是稠密环境下容易无解，因为agent速度一般比较大；而且其他agent的偏好速度在假设中属于内部变量
- $ v_A^{opt}=v_A$，设置最优速度等于当前速度，是前两者的一个折中，当前速度根据情形自动适配的，也有可能无解
-
ORCA线性规划无解的情况：dense situation
选择的新速度是在同时与多个ORCA半平面的欧式距离最大化时的速度中，选择一个长度最短的速度。这种情况下，和
v
A
o
p
t
v_A^{opt}
vAopt没有什么关系，agent“goes with the flow”
-
关于静态障碍
对于静态的障碍物，我们设置
v
A
o
p
t
=
0
v_A^{opt}=0
vAopt=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+并行）
收获
-
形式化的数学表述
-
严谨的论文阐述过程：定义的提出、推广、实现……
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
