Reciprocal n-body Collision Avoidance 译文

前言：

本篇译文使用有道翻译进行辅助。译者并不保证翻译的正确性，请大家谨慎甄别（至少译者是看懂了部分）。文中出现的[1]表示引用，其中的数字对于引用的编号。本来我是想去掉这些的，但是文中部分如“ A more thorough solution would be to take these factors intrinsically into account in the derivation of the permitted velocities for the robots. [27] and [19] provide some interesting ideas in this direction.”，直接用引用来特指一些东西。所以我后面又补上了，大多数时候是忽略掉也没什么关系。

如果你有发现我翻译错误的地方，我欢迎你来指正。

摘要：在本文中，我们提出了一种多个物体互相避免碰撞方法，即当多个移动机器人需要在一个共同的工作空间中移动时，避免它们相互碰撞。在我们的公式中，每个机器人都是完全独立行动，不与其他机器人通信。其基于速度障碍[5]的定义，我们将问题简化为求解一个低维线性规划问题，从而推导出无碰撞运动的充分条件。我们在几个密集和复杂的模拟场景中测试了我们的方法，涉及数千个机器人，并在几毫秒内计算出所有机器人的无碰撞动作。据我们所知，该方法是第一个能够保证在杂乱的工作空间中大量机器人的局部无碰撞运动的方法

介绍

碰撞避免是机器人技术的一个基础性问题。这个问题通常可以定义为在有障碍物和（或）其他移动实体的环境中，导航的自主移动机器人，其中机器人采用感知和行动连续的循环。在每个循环中，机器人的行为必须基于对环境的局部观察来计算，使自身既能避免与障碍物和其他移动物体发生碰撞，又能朝着目标不断前进。

单个机器人躲避静态或移动障碍物的避碰问题已得到充分研究。而本文聚焦于更为复杂且研究较少的多个物体互相避免碰撞的问题，即需避免多个机器人（或任何具备决策能力的实体）之间发生碰撞。该问题在机器人技术的许多领域都有重要的应用，如多机器人导航和机器人群[20]之间的协调。它也是计算机图形学和VR[11,21]的人群模拟、AI中的非玩家角色（NPC）建模、生物学中的鸟群和鱼群研究[23]，以及实时（空中）交通管制[16]的关键组成部分。在本文中，我们提出了一种快速而新颖的方法，这个方法可以同时决定多个（可以多达上千个）有着不同目标的机器人行为。每个机器人的行为是独立计算的，不需要机器人之间的通信或中心协调。且我们证明了我们的方法保证了每个机器人的无碰撞运动。

我们使用了一个简化的机器人模型，其中每个机器人都假定具有在二维工作空间中移动的简单形状（圆形或凸多边形）。此外，我们假设机器人是完整的。即它可以向任何方向移动，这样每个机器人的控制输入就简单地由一个二维速度矢量给出。此外，我们假设每个机器人都有完美的感知能力，能够推断出环境中障碍物和其他机器人的确切形状、位置和速度。

1 主要结果：

我们提出了一种严格的多个物体互相避免碰撞方法，该方法为每个机器人在未来至少固定时间内无碰撞提供了充分条件，仅假设其他机器人使用相同的避碰协议。我们的方法是基于速度的。这意味着，每个机器人会考虑其他被观察的机器人速度以避免与它们发生碰撞，同时机器人会从其速度空间中选择自身速度，其中由于其他机器人的存在，某些区域会被标记为“禁止进入”。我们的公式，“最优互避碰撞”，为每个机器人推断出允许选择的速度半平面（在速度空间中），以保证避免碰撞。机器人从所有允许的半平面的交点中选择其最优速度，这可以通过线性规划有效地完成。在机器人密集分布的特定条件下，所得到的线性规划可能是不可行的，在这种情况下，我们使用三维线性规划选择“最安全可能”的速度。

我们在几个包含数千个机器人的复杂模拟场景中试验了我们的方法。由于每个机器人都是独立的，我们可以完全并行计算每个机器人的动作，在实时系统中达到了极快的运行速度。此外，我们的实验表明，我们的方法实现了令人信服的平滑和无碰撞的运动。

本文的其余部分组织如下。我们从第2节讨论之前的工作开始。在第3节中，我们正式定义了我们在本文中要解决的问题。在第4节中，我们推导了机器人相对于另一个机器人的最佳互避碰撞的允许速度的半平面，并在第5节中展示了如何使用这种方法在多个机器人之间导航。我们在第6节报告实验结果，并在第7节总结。

2 准备工作

碰撞避免问题已经得到了广泛的研究。许多方法假设观察到的障碍物是静态的（即不移动）[2,4,6,7,13,14,24]，并计算机器人避免与障碍物碰撞的立即动作，在许多情况下考虑到机器人的运动学和动力学。如果障碍物也在移动，这种方法通常会根据对障碍物位置的新读数反复“重新规划”。如果障碍物的移动速度比机器人慢，这可能会很有效，但在快速障碍物中（比如穿过高速公路），障碍物的速度需要特别考虑。这个问题通常被称为“小行星规避”（原文为“asteroid avoidanc”），并且方法通常推断观察到的速度，以便估计障碍物的未来位置[8,9,12,19,22,28]。

当障碍物不仅仅是在不考虑其环境的情况下移动，而且也是试图避免碰撞的智能决策实体时，避免碰撞的问题变得更加困难。如果另一个实体将所有其他机器人也视为移动的障碍物，那么简单地将它们视为移动的障碍物可能会导致振荡现象（译者注释：即双方来回调整路径，无法稳定避碰）[15,26]。因此，必须特别考虑其他实体的反应性，以保证避免冲突。然而，机器人可能无法与其他实体交流，也可能不知道它们的意图。我们称之为互相碰撞避免，是本文的研究重点。

速度障碍（Velocity Obstacles, VO）是一种成功的基于速度的避免与移动障碍物碰撞的方法；它们为机器人选择速度以避免与已知速度移动的障碍物发生碰撞提供了充分必要条件。通过定义互相速度障碍（Reciprocal Velocity Obstacles, RVO）[10,26]，将该方法扩展到机器人-机器人避碰问题，其假设两个机器人都选择由另一个机器人引起的RVO之外的速度。然而，这一表述仅保证了特定条件下的避碰，并没有为一般情况下的避碰提供充分条件。在本文中，我们提出了克服这一限制的最佳互相碰撞避免（Optimal Reciprocal Collision Avoidance, ORCA）原理；ORCA为多个机器人之间避免碰撞提供了充分条件，从而保证了无碰撞导航

我们注意到，通过在所有n个机器人的速度的2n维空间中定义一个复合速度障碍[1]，可以为多个（例如n个）机器人选择避免碰撞的速度提供充要条件。然而，这不仅在计算上不切实际，而且还需要机器人之间的中心协调。这与我们研究的分布式多机器人导航类型不兼容，在分布式多机器人导航中，每个机器人独立地同时从自己的二维速度空间中选择速度

3 问题定义

本文讨论的问题正式定义如下：假设有n个机器人共享一个环境。为了简单起见，我们假设机器人是圆盘状的，在平面\(R^2\)上移动（我们在本文中提出的定义和算法可以很容易地扩展到转换多边形，也可以扩展到更高的维度）。每个机器人A都有一个当前位置\(P_A\)（其圆盘的中心），当前速度\(V_A\)和半径\(r_A\)。这些参数是机器人外部状态的一部分，即我们假设它们可以被其他机器人观察到。此外，每个机器人都有一个最大速度\(v^{max}_A\)和一个首选速度\(v^{pref}_A\)，这是机器人在没有其他机器人挡道的情况下假设的速度（例如，指向机器人目标的速度，其大小等于机器人的预期速度）。我们认为这些参数是机器人内部状态的一部分，因此不能被其他机器人观察到。

任务是让每个机器人A独立地（并同时）为自己选择一个新的速度\(v^(new)_A\)，使得当所有机器人都以各自的新速度持续移动时，至少在预设的时间段τ内能够确保无碰撞。作为次要目标，机器人应该尽可能选择接近他们的预期速度的新速度。机器人之间不允许相互通信，仅能通过观察其他机器人的当前位置和速度来做出决策。不过，每个机器人可以假定其他机器人采用与自身相同的策略来选择新速度。

我们将这个问题命名为“n个对象互相碰撞避免（reciprocal n-body collision avoidance）”。注意，这个问题不能用中心协调来解决，因为每个机器人的首选速度只有机器人自己知道。在第4节中，我们提出了每个机器人选择（至少）τ时间内无碰撞的速度的充分条件。在第5节中，我们将展示如何在多机器人导航的连续循环中使用此原则。

4 互相碰撞避免

4.1 预备知识

对于两个机器A和B，速度障碍为\(VO^{τ}_{A|B}\)（读作：B在时间窗τ下引起的A的速度障碍）是A相对于B的所有相对速度的集合，它会导致A和B在τ[5]时间之前的某个时间内发生碰撞。其正式定义如下。令D(p,r)表示以p为圆心半径为r的开口圆盘。

\[D(p,r)=\{q| |q-p| < r\},(1)\]

然后：

\[VO^τ_{A|B}=\{\textbf{v}|\exists t \in [0,τ]::t \textbf{v} \in D(p_B - p_A,r_A + r_B)\} (2)\]

图1

上图a中定义了两个机器人A和B。图b中，\(VO^{τ}_{A|B}\)（灰色部分）几何上可以被当做是（速度空间系下）一个顶点在原点的被删减的圆锥体，且它的边缘正切于半径为\(r_A+r_B\)中心点在\(p_A-p_B\)。缩减的数量依赖于τ的值。圆锥体被半径为\((r_A+r_B)/τ\)圆心在\((p_A-p_B)/τ\)圆盘的弧度裁剪。这里以τ=2展示的VO。图c中,当机器人B从某个集合VB（深灰色）中选择速度时，机器人A的避撞速度集\(CA^τ_{A|B}(V_B)\)是\(VO^{τ}_{A|B}\)于\(V_B\)的闵可夫斯基和（ Minkowski sum）（亮灰部分）外的部分。

速度障碍的几何解释如上图(b)所示。注意到，\(VO^{τ}_{A|B}\)和\(VO^{τ}_{B|A}\)是在原点对称的。

令\(v_A\)和\(v_B\)是分别是当前机器人A和B的速度。VO的定义意味着如果\(v_B-v_A \in VO^{τ}_{B|A}\)，或相当于\(v_A-v_B \in VO^{τ}_{A|B}\)，则A和B如果持续以当前的速度移动则将在τ时间之前的某一个时刻碰撞。反过来说，如果\(v_A-v_B \notin VO^{τ}_{A|B}\)，则机器人A和B在至少τ时间内可以保证不碰撞。

更一般而言，令\(X \oplus Y\)表示集合X和集合Y的闵可夫斯基和；

\[X \oplus Y=\{x+y|x \in X,y \in Y\} (3)\]

然后对于任意\(V_B\)集合，如果\(v_B \in V_B\)且\(v_A \notin VO^τ_{A|B} \oplus V_B\)，则A和B至少在τ时间内以他们当前的速度移动不会发生碰撞。这就得到了A考虑B在它从\(V_B\)中选择速度的避免碰撞的速度集合\(CA^τ_{A|B}(V_B)\)的定义。

\[CA^τ_{A|B}(V_B)=\{v|v \notin VO^τ_{A|B} \oplus V_B\} (4)\]

如果\(V_A ⊆ CA^τ_{A|B}(V_B),V_B⊆CA^τ_{B|A}(V_A)\)，我们称这对\(V_A\)和\(V_B\)是A和B互相避免碰撞的速度集合。如果\(V_A = CA^τ_{A|B}(V_B),V_B=CA^τ_{B|A}(V_A)\)，我们称\(V_A\)和\(V_B\)互相最大。

4.2 最佳互相碰撞避免

根据上述定义，我们希望选择可供给A的速度集合\(V_A\)和B的速度集合\(V_B\)，就像是\(CA^τ_{A|B}(V_B) = V_A,CA^τ_{B|A}(V_A) = V_B\)。也就是说他们是互相避免碰撞的最大值，且保证了A和B在至少τ时间内不会发生碰撞。而且，因为A和B是独立的机器人，他们应该无需和其他机器人交流就可以推导出他们被允许的速度集合。这里会有无限对\(V_A\)和\(V_B\)集合遵循这些要求，从中我们选择一对最大允许速度给A的最优速度\(v^(opt)_A\)和给B的最优速度\(V^(opt)_B\)。我们令集合\(ORCA^τ_{A|B}\)给A和\(ORCA^τ_{B|A}\)给B，且他们正式定义如下。令\(|V|\)是集合\(V\)的长度。

定义1（最佳互相碰撞避免）。\(ORCA^τ_{A|B}\)和\(ORCA^τ_{B|A}\)被定为他们互相避免的最大值，也就是说\(CA^τ_{A|B}(ORCA^τ_{B|A})=ORCA^τ_{A|B}\)且\(CA^τ_{B|A}(ORCA^τ_{A|B})=ORCA^τ_{B|A}\)，以至于对于所有其他互相碰撞避免的速度集合\(V_A\)和\(V_B\)（即\(V_A⊆CA^τ_{A|B}(V_B)\)和\(V_B⊆CA^τ_{B|A}(V_A)\)）对，且半径 r > 0,

\[\begin{aligned} |ORCA^τ_{A|B}\cap D(V^{opt}_A,r)|&= \\&|ORCA^τ_{B|A}\cap D(V^{opt}_B,r)|\ge min(|V_A \cap D(V^{opt}_A,r)|,|V_B\cap D(V^{opt}_A,r)|) \end{aligned}\]

这意味着\(ORCA^τ_{A|B}\)和\(ORCA^τ_{B|A}\)分别包含比其他任何一对互相碰撞避免的速度集合更接近\(v^{opt}_A\)和\(v^{opt}_B\)的速度。此外，被认可的速度的分布是“公平的”，因为A和B接近优化速度的速度数量是相等的。

我们能够几何构建\(ORCA^τ_{A|B}\)和\(ORCA^τ_{B|A}\)如下：我们假设A和B分别获得了速度\(v^{opt}_A\)和\(v^{opt}_B\)，且我们假设这会引起A和B在碰撞轨道上，也就是\(v^{opt}_A-v^{opt}_B∈ VO^τ_{A|B}\)。设\(\textbf{u}\)为从\(v^{opt}_A-v^{opt}_B\)到速度障碍边缘上最近点的向量。（可以看下文的图片）

\[\textbf{u}=(arg min||v-(v^{opt}_A - v^{opt}_B)||)- (v^{opt}_A-v^{opt}_B),v∈VO^τ_{A|B}(5)\]

且设\(\textbf{n}\)为\(VO^τ_{A|B}\)边界在点（\(v^{opt}_A-v^{opt}_B\)）+\(\textbf{u}\)向外的法线。则，\(\textbf{u}\)是让A和B相对速度避免在τ时间内的最小变化量。为了避免碰撞的“共摊责任”在几个机器人间以公平的方式，机器人A(至少)用1/2的\(\textbf{u}\)来获取它自身的速度并假设B考虑了另外一半。因此，被允许给A速度的\(ORCA^τ_{A|B}\)集合是在以点\(v^{opt}_A+\frac{1}{2}\textbf{u}\)为开始指向\(\textbf{n}\)方向的半平面点。更正式的：

\[ORCA^τ_{A|B}=\{v|(v-(v^{opt}_A+\frac{1}{2}u))\cdot n \ge 0\},(6)\]

图2

图2，A与B最优互避的允许速度集\(ORCA^τ_{A|B}\)是一个由垂直于u的线通过点\(b^{opt}_A+\frac{1}{2}\)的半平面，u为从\(v^{opt}_A-v^{opt}_B\)到\(VO^τ_{A|B}\)边缘上最近点的向量。

对于B的集合\(ORCA^τ_{B|A}\)对称定义（请看上图）。前面的等式也能应用，如果A和B在采用其优化速度时不在碰撞轨迹上，即\(v^{opt}_A-v^{opt}_B \notin VO^τ_{A|B}\)。在这样的情况下，双方机器人各自会承担一半的责任去保留无碰撞轨迹。

可以看出，根据定义1的准则，上述构造的\(ORCA^τ_{A|B}\)和\(ORCA^τ_{B|A}\)实际上是最优的。代理A和B可以各自推断出\(ORCA^τ_{A|B}\)和\(ORCA^τ_{B|A}\)，无需和其他机器人交流，只要机器人能够观察到其他人的位置，半径，预期速度。在5.2节，我们探讨合理的机器人最佳速度选择。

5 n个对象的碰撞避免

在本节中，我们将展示如何应用上述定义的ORCA原理在多个移动机器人之间执行n个个体碰撞避免，并讨论如何将静态障碍物纳入该框架。

图3

上图，由每个机器人独立执行的感知和行动的连续循环的示意图概述。

5.1 基本方法

整体方法如下所示。每个机器人A以时间步长∆t进行一个连续的感知和行动循环。在每一次迭代中，机器人获取到其他机器人（和它自己）的半径，当前的位置和当前预期速度。基于这些信息，机器人推断出相对于其他机器人B允许速度半平面\(ORCA^τ_{A|B}\)。A相对于所有机器人的允许速度集合是由其他机器人推导出的允许速度半平面的交点。我们称这个集合为\(ORCA^τ_A\)。（看下图）

\[ORCA^τ_A=D(0,v^{max}_A)\cap \bigcap_{B \neq A} ORCA^τ_{A|B} \quad (7)\]

图4

上图a中是八个机器人的布局。他们当前的速度用箭头展示。图(b)：对于所有机器人，由τ = 2且\(v^{opt}_∗=v_∗\)（也就是最佳速度等于当前速度）的其他机器人形成的机器人A的允许速度的半平面。半平面E（\(ORCA^τ_{A|E}\)）和C（\(ORCA^τ_{A|C}\)）重合。虚线区域是\(ORCA^τ_{A}\)，包含了所有考虑到全部其他机器人后A可允许的速度。箭头指向了A的当前速度。

注意到定义也包含了在机器人A上的最大速度限制。接下来，机器人给他自己选择一个在允许速度区域内的所有速度中最接近其首选速度\(v^{pref}_A\)的新速度\(v^{new}_A\):

\[v^{new}_A=argmin||v-v^{pref}_A|| \space \space \space v\in ORCA^τ_A (8)\]

我们将在下面展示出如何有效地计算这个速度。最终机器人到达它的新位置；

\[ p^{new}_A =p_A+v^{new}_A*∆t, (9)\]

且重复感知-行动循环。（看图3）

在前面的步骤的中关键的阶段是去计算被公式(7)和(8)定义的新速度\(v^{new}_A\)。其可以用线性规划有效地完成，因为\(ORCA^τ_A\)是一个凸区域，由相对于其他每个机器人的允许速度的半平面所引起的线性约束所界定（看图四）。优化方程是里预期速度的距离。尽管这是一个二次优化函数，但它并没有使线性规划特性失效，因为它只有一个局部最小值。

我们使用[3]的高效算法，在跟踪当前最优新速度的同时，按随机顺序逐个添加约束。n个物体互相避免碰撞算法预测运行时间是O(n)，其中n是线性规划中约束的总数（在我们的情况下，n等于机器人的数量）。实际上，我们包含了一个以最大速度的圆形约束，其并不会改变算法且不会影响到运行时间。算法返回在\(ORCA^τ_A\)中最接近\(v^pref_A\)的速度，且如果线性规划失败，其会报告错误，也就是当\(ORCA^τ_A = 0\)(译者注释：原文是数字0中加一个斜杆，我查了资料这好像是为了和字母O进行区分，但是我没找到如何书写，因此我这边直接写0)。如果机器人小心地选择最佳速度（我们将在5.2节讨论），\(ORCA^τ_A\)将不会为空，因此，总会有一个解决方案，保证机器人在至少τ时间内不会发生碰撞。

通过不包含所有其他机器人的限制，而是仅选择近的机器人限制，我们可以提高选择速度的效率。实际上，机器人B到机器人A的距离（\(v^{max}_A+v^{max}B\)）大于τ，机器人B在τ时间内不会和机器人A碰撞。所以当计算给A的新速度时，他们可以安全地移除线性规划外。一个主要的问题是机器人A并不知道其他机器人的最大速度，但是这可以通过猜测其他机器人的最大速度和A自身一致来起效。通过使用KD-Tree，我们可以更有效地找到约束条件的近距离机器人集合。

图5

上图中（a）：一个有三个机器人向机器人A移动的密集构型。当前机器人速度使用箭头展示；机器人A的速度为0。（b）通过以τ = 2且\(v^{opt}_∗ =v_∗\)所有的每个其他机器人形成给A的被允许速度的半平面。\(ORCA^τ_A\)区域为空，所以无法保证在τ时间内避免碰撞。（c）：通过以τ = 2且\(v^{opt}_∗ =0\)所有的每个其他机器人形成给A的被允许速度的半平面。虚线区域是\(ORCA^τ_A\)。

5.2 选择最佳速度

我们没有解决的一个问题是如何为每个机器人A选择\(v^{opt}_A\)。为了每一个机器人不需要焦虑就推导出半平面，\(v^{opt}_A\)必须可以被其他的机器人观察到。这里，我们讨论一些合理的可能性：

  • 对于所有机器人A\(v^{opt}_A = 0\)。如果我们给所有机器人设定其最佳速度为0，这保证了对所有的机器人A的\(ORCA^τ_A\)不为空（看图五的c）。因此，上文描述的线性规划算法将会给所有机器人找到一个速度保证他们在时间τ内不会碰撞。这可以看出如下。对于任意其他的机器人B，点0总是在速度障碍\(VO^τ_{A|B}\)（对于有限τ）之外。因此，半平面\(ORCA^τ_{A|B}\)总是至少包含速度0。事实上，划定\(ORCA^τ_{A|B}\)的线与连接A和B当前位置的线是垂直的。
    将优化速度设置为零的缺点是机器人的行为不令人信服，因为它们只考虑其他机器人的当前位置，而不是它们当前的速度。在被稠密包裹的情况下，这可能导致全局范围的死锁，因为当机器人彼此非常接近时，机器人所选择的速度收敛为零。

  • 对于所有机器人A\(v^{opt}_A = v^{pref}_A\)（也就是最佳速度为期望速度）。期望速度是机器人内部状态的一部分，所以他们不能被其他的机器人所观察。为了讨论方便，让我们假设有可能推断出其他机器人的首选速度，并且将优化速度设置为所有机器人的首选速度。这在低稠密度的条件下工作得很好，但随着最佳速度的大小增长，线性规划不可行的可能性越来越大。因为在大多数情况下，预期速度是一个固定大小，忽略稠密条件，即使在中等密度的条件下，这也会导致不安全的航行。

  • 对于所有机器人A\(v^{opt}_A = v_A\)。设定最佳为当前速度是上面两个选择的权衡，因为当前速度自动适应这情况：它（非常）指示低密度情况下的首选速度，且在稠密场景下靠近0。且，当前的速度可以被其他机器人观察到。不过，在高度稠密的条件下，线性规则可能不可行（看图5（b））。在这样的情况下，不能保证选择一个避免碰撞的速度。相反，我们使用三维线性程序（我们在第5.3节中讨论）为机器人选择“最安全”的速度。

5.3 拥挤的环境

对于所有的机器人A，如果我们选择\(v^{opt}_A = v_A\)，在机器人的密度非常高的情况下，这可能不会有一个满足所有线性规划限制条件的速度。用另外的话说，集合\(ORCA^τ_A\)为空（看图5（b）），且章节5.1的算法会返回线性规划不可行。在这样的情况下，不能保证选择一个避免碰撞的速度，也就是说，最小限度地“突破”其他机器人所带来的限制的速度。更正式的，令\(d_{A|B}(v)\)表示速度v到半平面\(ORCA^τ_{A|B}\)边缘的有符号距离（欧几里得）。如果\(v∈ORCA^τ_{A|B}\)，且\(d_{A|B}(v)\)为负。我们现在选择的速度是到任何由其他机器人形成的半平面的最大距离的最小值：

\[ v^{new}_A = argmin\space max\space d_{A|B}(v).v∈D(0,v^{max}_A), B\neq A\]

从几何上讲，这可以解释为以相同的速度垂直向外移动半平面\(ORCA^τ_{A|B}\)的边缘，直到恰好有一个速度有效。

我们可以用3维线性规划来找到这些速度。对于每一个机器人B，\(d_{A|B}(v)\)的距离方程是一个在3维\((v,d)\)空间下的平面。我们现在寻找一个点\((v^*,d^*)\)，其坐落在上面所有由距离方程导致的平面上，且有一个最小的值d-value。我们的新速度\(v^{new}\)即为\(v^*\)。

我们可以使用与上面相同的随机算法来解决这个三维线性程序。它仍可以以O(n)的预期时间运行，其中n是其他机器人的数量。实际上，我们可以将问题向下投射到v（速度）平面中，这样所有几何运算可以都可以在二维上进行。三维线性规划总是可行的，所以他啊总是会返回一个解。

图6

上图(a)：一个机器人A和一个线段障碍O的定义。(b)：速度障碍\(VO^τ_{A|O}\)在τ = 2的几何定义。(c)：半平面\(ORCA^τ_{A|O}\)的分割线在其边界上离\(v^{opt}_A\)最近的点与\(VO^τ_{A|O}\)相切，在有障碍物的情况下等于0。

注意在拥挤的环境下，给机器人新速度的选择不能依靠机器人的预期速度。这意味着机器人“随波逐流”，它的行为完全由周围的机器人决定。

5.4 静态障碍物

现在我们仅考虑机器人如何避免和其他机器人碰撞吗，但是经典的多机器人环境也包含（静态）障碍物。在上面的框架下，我们可以简单将其包含起来。我们基本上遵循与上面相同的方法，关键的区别是障碍物不会移动，所以机器人应该承担避免与它们碰撞的全部责任。

我们通常地假设障碍物被建模为线段的集合。令O为其中一个线段片段，且令A为有着半径为\(r_A\)坐落在\(p_A\)的机器人。然后包含障碍物O的速度障碍\(VO^τ_{A|O}\)被定义为：（看图6的（a）和（b））

\[VO^τ_{A|O} = {v|∃t ∈[0,τ] :: tv ∈ O \oplus −D(pA,rA)},(11)\]

代理A将在τ时间内与障碍物O发生碰撞，如果它自身速度\(v_A\)在\(VO^τ_{A|O}\)内，如果它的速度在速度障碍外，那么它在在τ时间内不会发生碰撞。因此我们可以定义A考虑到O的被允许的速度范围是\(VO^τ_{A|O}\)的补充。然而这会不允许我们使用章节5.1的高效的线性规划算法，因为\(VO^τ_{A|O}\)的补充不是一个多边形区域。因此我们定义A考虑到O的允许速度集合当做是半平面\(ORCA^τ_{A|O}\)，\(ORCA^τ_{A|O}\)的分隔线为\(VO^τ_{A|O}\)边界上离\(v^{opt}_A\)最近点处与\(VO^τ_{A|O}\)的切线（见图6(c)）。

如果有障碍物，我们给机器人A选择\(v^{opt}_A=0\)。这保证了总是有一个有效的速度给机器人在τ时间内避免碰撞。我们一般可以使用比考虑其他机器人更小的τ值考虑障碍物，因为如果有必要避开其他机器人，机器人通常不应该“害羞”地朝障碍物移动。另一方面，在考虑到障碍物后允许速度上给机器人的限制是很难的，因为无论如何都要避免与障碍物相撞。因此，当5.1节的线性规划由于机器人密度大而不可行时，障碍物的约束并没有放松。

我们注意到上面定义相对于障碍物的被允许速度半平面仅确保机器人避免和障碍物碰撞；他们不会使机器人绕着他们移动。绕过障碍物向机器人目标移动的方向应该反映在机器人的首选速度上，这可以通过（有效的）全局路径规划技术得到。

6 实验结果

为了测试我们的技术，我们进行了几次模拟。我们进行了小规模模拟来测试本地行为，并进行了大规模模拟来分析性能扩展。

图7

上图，在两个小行为模拟中机器人的痕迹。机器人被显示为彩色圆盘，它们在初始位置是亮的，随着时间的推移而变暗。图（a）两个模拟机器人互相经过的痕迹。图（b）五个模拟机器人在一个圆中互相穿过对映点的轨迹。

行为结果：我们首先展示了两个设想，其突出了机器人互相在局部水平中丝滑地避免相互碰撞。在第一个设想中，如图7（a）中所示，两个机器人交换位置。当机器人注意到碰撞即将发生（也就是他们将要在τ时间内发生碰撞），他们会改变速度来流畅地避免碰撞。在第二个设想中展示了五个机器人，他们的目标是穿过圆环到达对映的点位。正如图7（b）所示，机器人平滑地绕着彼此旋转以避免碰撞。

图8

上图，模拟1000个代理试图通过一个圆的中心移动到对映位置。机器人顺利地穿过在中心形成的拥堵。

图9

上图，在人群模拟中，1000个虚拟代理疏散办公室的模拟快照。

性能结果：为了测试我们方法的性能，我们运行了两个大规模模拟。第一个测试我们模拟了1000个代理在一个巨大的圆环中移动到对映点位，如图8所示。从第二个测试，展示在图9，我们将我们的最佳互相避免方法合并到现存人群模拟[10]的框架。在这个模拟中，虚拟代理人 尝试去疏散一个办公环境。对于每一个代理的预期速度被设置为遵循的路径离开办公室。

图10

上图，性能曲线图：(a) 1 ~ 8核疏散模拟的性能变化。(b) 8核上不同数量代理的运行时间（越低越好）。这两种模拟都与代理的数量近似成线性关系。

因为每一个代理都会做出独立决定，因此我们能够通过将代理的计算分布在多个处理器上来有效地并行化模拟。我们使用openMp多线程去在8个Intel Xeon 2.66GHz（Clovertown）核上并行化关键计算。图10（a）展示在办公室场景下，我们方程在不同数量核上如何变化。在所有场景中都有相当好的变化——对于大量的代理来说，观察到的最佳结果是近乎线性相关，其中恒定的系统开销在总体计算时间中变得不那么重要。

在绝对性能方面，图10（b）展示两种模拟不同数量代理的运行时间。对于5000个代理在8核上，它划分了8毫秒（每秒125帧）去解决每一个代理在巨环模拟中碰撞避免的线性规划，且在办公室疏散模拟中，花费了15.6毫秒（每秒64帧）去更新每一个代理。

7 结论和未来的工作

本文，我们提出了一个高效的方程，其提供了一个充分的条件给多个机器人去选择一个避免与其他机器人碰撞的行为，尽管每一个机器人无需和其他机器人交流独立执行。在我们的实验中，我们的方法给互相多物体碰撞避免展示了快速、平稳且令人信服的行为。

我们使用一个简单的机器人模型，其运动学和运力学是被忽略的。一个未来工作的重要扩展是去加上一些约束。今后工作的一个重要延伸是考虑到这些制约因素。我们也可以将其作为后处理步骤，即计算出的新速度被“限制”在运动学和动态约束允许的范围内。这将不再严格保证避免碰撞，但它可能在实践中工作得很好。更彻底的解决办法是在推导机器人的允许速度时考虑这些内在因素。[27]和[19]在这个方向上提供了一些有趣的想法。

本文，我们仅在2维环境中证明了结果。然而，所有的定义和算法也可以被扩展到三维 在本文中，我们只展示了二维环境的结果。然而，所有的定义和算法都可以扩展到三维。这对于自动飞行器或鸟类或鱼类的群集模拟等应用来说可能很有趣。未来工作的另一个重要方向是在真实机器人上实现所提出的框架并纳入感知不确定性。这是对[25]中的互反速度障碍所做的。我们相信，在该实现中，我们可以相对容易地用我们的ORCA公式代替RVO公式。

引用

  1. Y. Abe, M. Yoshiki. Collision avoidance method for multiple autonomous mobile agents by implicit cooperation. IEEE RSJ Int. Conf. Intell. Robot. Syst., pp. 1207-1212, 2001.

  2. J. Borenstein, Y. Koren. The vector field histogram- fast obstacle avoidance for mobile robots.IEEE Journal of Robotics and Automation 7(3):278-288, 1991.Jur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh Manocha

  3. M.deBerg,O.Cheong, M.vanKreveld, M.Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2008.

  4. B. Faverjon, P. Tournassoud. A local based approach for path planning of manipulators with a high number of degrees of freedom. IEEE Int. Conf. Robot. Autom., pp. 1152–1159, 1987.

  5. P. Fiorini, Z. Shiller. Motion planning in dynamic environments using Velocity Obstacles. Int. Journal of Robotics Research 17(7), pp. 760-772, 1998.

  6. D. Fox, W. Burgard, S. Thrun. The dynamic window approach to collision avoidance. IEEE Robot. Autom. Mag. 4:23-33, 1997.

  7. T. Fraichard, H. Asama. Inevitable collision states- a step towards safer robots? Advanced Robotics 18(10):10011024, 2004. 8. C.Fulgenzi, A.Spalanzani, C.Laugier. Dynamic obstacle avoidance in uncertain environment combining PVOs and occupancy grid. IEEE Int. Conf. Robot. Autom., pp. 1610-1616, 2007.

  8. J. Gil de Lamadrid. Avoidance of Obstacles With Unknown Trajectories: Locally Optimal Paths and Periodic Sensor Readings. Int. Journal of Robotics Research 13(6):496–507, 1994.

  9. S. Guy, J. Chhugani, C. Kim, N. Satish, P. Dubey, M. Lin, D. Manocha. Highly parallel collision avoidance for multi-agent simulation. University of North Carolina at Chapel Hill, Tech. Rep., 2009.

  10. D. Helbing, I. Farkas, T. Vicsek. Simulating dynamical features of escape panic. Nature 407:487–490, 2000.

  11. D. Hsu, R. Kindel, J. Latombe, S. Rock. Randomized kinodynamic motion planning with moving obstacles. Int. J. Robot. Res. 21(3):233-255, 2002.

  12. F. Kanehiro, F. Lamiraux, O. Kanoun, E. Yoshida, J.-P. Laumond. A local collision avoidance method for non-strictly convex polyhedra. Robotics: Science and Systems, 2008.

  13. O. Khatib. Real-Time Obstacle Avoidance for Manipulators and Mobile Robots. Int. Journal of Robotics Research 5(1):90–98, 1986.

  14. B. Kluge, E. Prassler. Reflective navigation: Individual behaviors and group behaviors. IEEE Int. Conf. Robot. Autom., pp. 4172-4177, 2004.

  15. J. Kuchar, L. Chang. Survey of conflict detection and resolution modeling methods. AIAA Guidance, Navigation, and Control Conf., 1997.

  16. M. Lin. Efficient collision detection for animation and robotics. PhD thesis, University of California, Berkeley, 1993.

  17. S. LaValle, Planning Algorithms. Cambridge University Press, 2006.

  18. L. Martinez-Gomez, T. Fraichard. Collision avoidance in dynamic environments: an ICSbased solution and its comparative evaluation. IEEE Int. Conf. on Robotics and Automation, 2009.

  19. J. McLurkin, E. Demaine. ADistributed Boundary DetectionAlgorithm for Multi-Robot Systems. (under review), 2009.

  20. J. Pettr´e, P. de Heras Ciechomski, J. Ma¨ım, B. Yershin, J.-P. Laumond, D. Thalmann. Realtime navigating crowds: scalable simulation and rendering. Computer Animation and Virtual Worlds 17:445–455, 2006.

  21. S. Petti, T. Fraichard. Safe motion planning in dynamic environments. IEEE RSJ Int. Conf. Intell. Robot. Syst., pp. 2210-2215, 2005.

  22. C. Reynolds. Flocks, herds and schools: A distributed behavioral model. Int. Conf. on Computer Graphics and Interactive Techniques, pp. 25–34, 1987.

  23. R. Simmons. The curvature-velocity method for local obstacle avoidance. IEEE Int. Conf. on Robotics and Automation, pp. 3375–3382, 1996.

  24. J. Snape, J. van den Berg, S. Guy, D. Manocha. Independent navigation of multiple mobile robots with hybrid reciprocal velocity obstacles. IEEE/RSJ Int. Conf. Intell. Robot. Syst., 2009.

  25. J. van den Berg, M.Lin,D. Manocha. Reciprocal Velocity Obstacles for real-timemulti-agent navigation. IEEE Int. Conf. on Robotics and Automation, pp. 1928–1935, 2008.

  26. D. Wilkie, J. van den Berg, D. Manocha. Generalized velocity obstacles. IEEE RSJ Int. Conf. Intell. Robot. Syst., 2009.

  27. M. Zucker, J. Kuffner, M. Branicky. Multipartite RRTs for rapid replanning in dynamic environments. IEEE Int. Conf. on Robotics and Automation, pp. 1603-1609, 2007

原文地址

闲言碎语

我也不知道自己的翻译的是否正确。我不得不说，这篇文章的翻译确实困难，一堆长难句真的让人头疼。文章中有些话翻来覆去的说，我不知道这到底是他们有字数要求还是说为了严谨。不过我花了半个月的时间才把这些全部翻译完，实在是对翻译作品没什么动力，再加上想锻炼自己的英语水平，所以才花了这么久。实际上即使翻译完了，我感觉自己对RVO2的了解也并没有提示多少，倒是英语翻译的水平有点提高了。上面我就提到了我用‘有道翻译’来辅助我翻译，实际上我还使用了文心一言帮忙。大多数时候文心一言翻译的出来的比有道翻译好许多，但是后面我实在没兴趣了，大多数我就没做验证且也放弃了多使用文心一言来矫正。如果你发现我翻译有问题，可以发邮件或是私信给我，我再用AI或是其他工具做一下验证。希望这篇翻译可以对你有所帮助。