大规模人群模拟中的碰撞避免研究与实现

谢凯丽

（四川大学计算机系，成都610065）

0 引言

近年来随着人们生活水平和计算机图形技术的广泛发展与影响，人们对大规模人群运动模拟也提出了越来越高的要求，例如人们需要更为真是贴切的虚拟现实场景，在这样的一个场景中，在更为真实快速的渲染中，每个个体需要流畅地避开所有其他个体或者是静态障碍物，真实稳定地实现虚拟现实中的人群模拟运动的实时性、真实感与科学合理性。

本文主要介绍了笔者研究该课题过程中所做的相关算法分析和实现、碰撞避免的实现与数据处理过程中针对于算法求解的优化分析。基于RVO 算法的大规模人群模拟中的碰撞避免问题的实现和分析过程中，在第一步构建简单属性机器人模型的过程中，初始化所有模型的速度、位置、目标点和最大速度范围，静态障碍物的位置。在我们进行RVO 计算前，我们考虑到对实验效率和真实感的要求，可以尝试用一些寻路算法和搜索算法进行每个模型的路径的设置和其他需要纳入计算的相关模型的搜索。在通过RVO 算法计算出速度可行域之后，我们需要通过一些方法来求得最终解，这也是笔者认为本实验中最具考验的阶段。在本实验中首先运用ORCA 方法求出每个模型的最终可行速度范围，进而通过线性分析方法详释了在速度的各种分析情况下进行最终解的计算。

1 RVO算法实现

1.1 算法描述

碰撞避免已经很好地通过基于速度的方法解决了目标个体与动态障碍物之间的碰撞问题，它为目标实体和移动障碍物之间的碰撞避免提供了一种十分有效的方法。当我们把这种方法扩展到大规模人群模拟中的碰撞避免实现中，每一组参与计算的机器人模型都需要计算新速度和新位置。这个新速度能够实现目标模型与其他机器人模型之间的碰撞避免，这是一种相互的碰撞避免的实现，它是在计算出不可行速度区域之后选择出的可实行速度范围。以上可以简单地理解成基于RVO 实现碰撞检测和避免的过程。

1.2 RVO 的碰撞检测避免

本小节对碰撞避免的整个算法流程进行简单的概述。首先对于机器人A 我们需要获取当前机器人的位置p、初速度V、最大速度Vmax、最优速度Vpref以及周边机器人的位置和初速度，模型A 不断地对其他机器人的数据进行检测获取和计算，从而得到实现碰撞避免的新速度范围，获得这些范围之后我们需要对n 个速度范围运用一定的方法从而得到最终解决方案。

所以：

在公式（2）中，t 代表将来的一段时间，pm和pn分别表示模型m 和模型n 的位置，rm和rn表示两模型的半径。可通过图1 分析得到：

图1（a）表示模型m 和n 的结构和位置。图1（b）中将二维平面中抽象的速度问题线性化，将速度表示为坐标系中的二维矢量，VOtm|n即为我们要求的m 和n之间会产生碰撞的m 的相对速度范围，其范围是由一段半圆弧和两条切线构成，半圆弧的圆心为，半径为，所以灰色区域即为我们实现m 与n 之间的碰撞避免的m 的速度的不可行区域，并且在模型的属性一定的情况下，该范围是由参与计算的时间t 决定的。图1（c）表示在机器人n 速度为区域Vn中时，通过图1（b）中方法的多次分析而得到的在时间t 范围内，实现模型m 与模型n 之间碰撞避免的m 的绝对速度的不可行区域。首先我们在公式（3）用X⊕Y 表示闵可夫斯基和（闵可夫斯基和是两个欧几里得空间的点集的和，以德国数学家闵可夫斯基命名）

对于机器人n 的可行速度的计算，其相对速度不可行线性化的结果与图1（b）关于原点对称的，详细原因与上述分析步骤一致,所以：

其中Vm为模型m 的速度。

综上所述，模型m 与模型n 不发生碰撞所要产生的新动作（即它们的新速度）的可选范围已被求出。当，并且时，则Vm和Vn为m与n 避免相互碰撞的速度。

2 碰撞避免的实现与优化

2.1 ORCA— —基于RVO 的碰撞避免的实现与优化

图1

图2

因为本课题研究的碰撞避免方法对于任何一个实例模型都是高效且平等地处理，所以模型m 和模型n的速度需要分别增加来进行新动作的计算。

因为模型m 有最大速度限制，所以要求出最优速度中符合固定属性的范围：

更新机器人m 的位置：

通过讨论我们得出了在机器人m 避免与机器人n发生碰撞所需要的新速度的优化范围。然而在大规模人群模拟中机器人m 需要避开其他多个机器人，所以我们最终求解出了多个ORCA,并且需要求解出多个半平面的交集，当多个半平面没有交集时，我们需要对模型的初速度进行修改。

需要注意的是，多个半平面不存在交集的情况是存在的。在我们进行RVO 的实现时，我们需要每个机器人的速度位置大小来进行计算，位置和大小是固定不变的属性，我们需要合适的初速度来进行计算（需要注意的是为了进行更高效率的计算，最优地实现碰撞避免，我们的初速度不一定要选择机器人当前的速度来进行计算）。对于初速的合理选择有助于我们算法的高效实现。

2.2 碰撞避免实现中的相关分析与优化求解

前文我们讨论了RVO 的实现和优化，讨论过程中我们将模型m 视为有着确切目标的移动中的实体。那么当场景中存在静态障碍物时，我们研究和计算的方法是一致的。我们可以将静态障碍物视为由一些线性片段构成的物体，如图3 所示，假设O 为静态障碍物，m 为处于pm一点半径为rm的移动的实体。通过前两节算法的分析，我们可以得出如果m 的速度在范围中，那么m 将会在时间t 内与障碍物O 发生碰撞，反之如果m 的速度不在区域内，那么m 与障碍物O 之间的碰撞避免就可以得到实现。单纯求出并不能使我们通过线性分析从而求出m 最后的初速度，因此我们需要求出可行域半平面进而求出初速度vopt到距离最短的点。

在讨论与静态障碍物的碰撞避免时，我们将初速度vopt设为0，因为考虑障碍物不会动，而其他模型会动，所以其他移动中的模型的对新速度v 的偏差影响要远远大于障碍物的，所以在考虑障碍物的时候我们可以允许尽量的靠近障碍物来避免与其他模型碰撞。当vopt=0 时，能够最大限度地保证m 存在一个速度能够和所研究静态障碍物在时间t 内实现碰撞避免。在与静态障碍物作讨论时，我们计算的时间t 可以远小于与其他模型作讨论时的时间，因为为了实现与其他移动中的模型实现碰撞避免，我们可以极大地靠近静态障碍物。

图3

3 实验结果和分析

为了展示我们的算法结果，我们将数据通过OpenGL 绘制算法将数据直观地展示出来。

如图4。

图4

图4 （a）表示各个模型的初始位置包括障碍物的位置，图4（b）展示了各个模型在运动过程中某个时刻的位置，图4（c）表示运动趋于结束。这个实验将各个模型的初始位置和目标位置分别初始化为障碍物两边的位置。

在上述实验中，我们给实验场景初始化了两个静态障碍物，注意在这种情况下，如果不进行Dijkstra 寻路规划，每个机器人都有可能为了避免彼此的碰撞而从障碍物的两侧移动到达我们的目的地,而我们的实验结果是每个机器人都从两个静态障碍物之间的空隙中运动至对面的目的地，这样便使我们的研究结果更加科学美观。

4 结语

对具有真实感典型的大规模人群模拟是计算机图形学虚拟现实领域研究的热点和难点之一，实时的大规模人群模拟的相关研究成为最为关注的话题之一。基于RVO 算法的碰撞避免是一种有效地大规模人群模拟的研究方法实现时数学线性分析和计算机图形学的交叉结合。RVO 算法是一种能够有效实现大规模人群模拟中碰撞避免的方法之一，本文对RVO 算法进行了基本的算法概述和实现，并通过各种寻路和搜索算法，结合线性分析的方法求出了碰撞避免的相关数据范围，最后通过OpenGL 绘制算法实现了在保证实时性下得到碰撞避免的动画效果。在RVO 算法实时的模拟出无碰撞的大规模人群运动的基础上，通过理论以及前人的相关研究，对最后结果的求解过程及其各种特殊情况以及结果的通过线性规划进行优化分析进行了充分的考虑和研究并得出分析结果。