基于RVO的人群运动路径规划

徐梓桉

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

0 引言

人群疏散对建筑设计和城市规划有重要的意义。一个设计良好的疏散方案包括一个在短时间内帮助人群到达出口的疏散指导。由于人群分布可以根据某些事件进行估计，例如音乐会和新年庆祝，因此疏散方向标志可以在人群聚集在一个地方前设置好逃生方向标志。此外,随着监测照相机和传感器网络变得越来越多最近，对人群的动态估计分布允许我们的系统动态反应,提高其有效性。

人群模拟比较典型的做法是通过全局寻路确定到目标点宏观的路径，然后通过局部的导航点和碰撞避免来获取实际的速度[1]。我们在本文中提出了一个全新的策略来规划全局路径。我们的方法产生的结果比基于智能体的单纯的目标导向的导航模型更有可信度。该模型有一个额外的过程阶段，实验表明，该系统具有较好的仿真效果，甚至在拥挤的场景中也能提高效率提前避免拥挤。

1 系统概述

在我们的研究中，我们使用了互利速度障碍（RVO）模型[2]和由全局信息决定的修改后的A*算法[3]，作为我们的基础控制算法。我们使用改进后的A*算法来计算一个个体在均匀网格上从当前位置到目标位置的长期路径。然后计算路径的首要步骤就是使用RVO来计算最佳速度来避免附近的碰撞。我们提出的这个系统的关键方面在于我们修改了了A*算法的代价方程，将个体的现在和将来可能出现的位置纳入路径计算的代价考虑。为了实现这个，在每个个体的路径计算完成之后，我们将保存路径的信息用来帮助其他个体规划他们的路径。值得注意的是，我们不直接使用这些信息，这些信息是用在改进的A*算法上的。因此，我们的算法不会受到局部最小值问题的影响。

2 RVO算法

我们使用寻路算法规划得到的路径能够使得人群能够在全局范围内通过阶段性的导航位置来找到合适的路径和倾向速度。但是，路径规划是以人群个体为计算单位的，路径规划过程中并没有将其他的运动个体作为障碍物来考虑，因此路径规划的结果并不能保证人群之间的路径不会有交叉而导致运动过程中的碰撞和穿透重叠。因此，需要碰撞避免算法在运动过程中对路径规划的结果进行修正。碰撞避免算法是通过将速度修正的逻辑使得所有在△t时间内的人群个体的速度运动位置不会发生碰撞和穿透重叠的现象[3]。

在所有碰撞避免的实现方法中，Fiorini等人提出遇障速度空间算法Velocity Obstacles[4]来解决该问题。人群个体A以速因此当个体A继续以速度运动将会与人群个体B发生碰撞。在遇障速度算法作用下，人群个体A在人群个体B的遇障速度空间作用下得到修正速度，即；同理人群个体B也在人群个体A的遇障速度空间的作用下得到修正速度，即。

不同于遇障速度算法（VO）从其他个体的遇障速度空间获得最优速度，互利速度障碍算法（RVO）结合当前速度和其他个体的遇障速度空间，取求解结果的平均值作为最优速度，数学表达式如下所示。

人群个体B相对于人群个体A的互利速度障碍空间是所有人群个体A当前速度和处于速度障碍空间的速度均值的集合。

3 A＊算法

A*算法是一种启发式的路径搜索算法，使用启发函数来指导最短路径的计算。和Dijkstra算法一样都能用于最短路径的计算。但Dijkstra算法以起始节点为中心，无差别的扩展邻居节点，而A*算法则使用启发函数h(n)来筛选邻居，指导最短路径的搜索过程，具有比Dijkstra算法更高的搜索效率。

A*算法的最短路径的估值函数如下所示。

f（n）表示从出发点s出发经过节点n，到达目标点d的路径长度的预估值。g（n）表示的是从出发点s到节点n的路径长度，h（n）表示从节点n到目标点d的估计路径长度，h（n）的值通常为节点n与目标点d之间的曼顿距离。在A*算法中g（n）的计算通常如下所示。

A*算法的优点是当从起始点出发存在到目标点的路径时，A*算法一定能找到一条最优的路径。相比于Dijkstra算法对邻居节点无差别的扩展方式，可以很大程度上减少冗余节点，在效率上有很大提升。更适合于起始节点、目标节点都明确的计算场景。但是g（n）的计算方式只考虑了静态的距离的因素影响，而没有考虑其他人群个体的位置分布和运动方向对路径规划的影响，因此我们对A*算法的做了修改。

4 改进的A＊算法

为了让我们的系统能够将人群运动方向和人群未来的位置分布纳入考虑，我们将A*算法的代价方程由公式（3）改成公式（4）。

在公式（1）和公式（2）中，Cs是 A*算法正在处理的当前所在的网格，Cd是网格Cs的邻居网格，dist函数表示的是这两个网格之间的欧氏距离。fuhao（Cd）代表了在网格Cd处的额外的潜在代价值。k是一个常数，用于调节额外代价的影响系数。

我们假设人群个体可以从水平，垂直4个方向进入和离开网格。每个网格保存4个方向的权重值，对于相邻的网格表示人群个体从Cs到Cd的单位向量。那么网格Cd在方向上的权值记为的公式如下所示。

因此，当考虑人群的移动方向时，网格Cs移动到网格Cd的代价函数更新为：

我们在考虑将来的人群分布对全局路径规划的影响时，考虑到当前规划的路径对其他人的路径规划的影响越小。因此，假设人群个体i规划的全局路径为，对于Pathi上的任意网格，都表明人群个体i会在将来的某个时刻到达该网格。因此，我们将影响从网格Ci0到网格Cin路径上网格的权值依次递减，其递减值为：

其中BPrice为基准值，Pathi对路径上网格Ci权值的影响为：

因此，我们的网格Cs到Cd的代价函数为：

5 实验结果分析

本文在相同的硬件环境下使用了普通的A*算法（图1）和经本文改进后的A*算法（图2），对相同的初始场景和数量同为2000人的实验条件进行疏散模拟。

图1

图2

[1]黄鹏，刘箴.一种RVO碰撞避免的人群仿真研究[J].计算机仿真，2012，29（11）:34-37.

[2]Jur Van den Berg,Ming Lin,Dinesh Manocha.Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation.In Robotics and Automation,2008.ICRA 2008.IEEE International Conference on,pages 1928-1935.IEEE,2008.

[3]Hart P E,Nilsson N J,Raphael B.A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J].Systems Science and Cybernetics,IEEE Transactions on,1968,4（2）:100-107.

[4]Paolo Fiorini and Zvi Shiller.Motion Planning in Dynamic Environmentsusing Velocity Obstacles.The International Journal of Robotics Research,17（7）:760-772,1998.