一种恐慌人群逃生模拟方法

摘要

本发明提供了一种恐慌人群逃生模拟方法，旨在真实地模拟恐慌情况下人群逃生的特点。本发明使用社会力模型进行人群建模，针对恐慌人群的特性，发明了新的交互力，并且引入性格模型，通过调整人群模拟参数来模拟不同性格个体的行为特征。在逃生路径规划技术方面，发明了非均匀网格技术，使得Agent可以更加准确地感知周围环境，并且在路径选择上呈现多样性。在路径规划中，针对真实情况下人群视野往往会被障碍物等阻挡的情况，发明局部视野技术，使得人群仅以视野范围内的点作为目标点来进行导航，从而保证了模拟的真实性。

说明书

技术领域

本发明属于虚拟现实技术领域，尤其涉及一种恐慌状态下的人群逃生模拟 方法。

背景技术

在面临灾难和其他紧急情况时，人群往往会出现恐慌的特性，而这种恐慌 很容易引起群体性灾难，所以人们一直在针对恐慌人群的特性进行研究，而对 恐慌人群的模拟则是研究中举足轻重的一部分。伴随着计算机动画技术的高速 发展，特别是群体动画的发展，对于恐慌人群的模拟不再是纸上谈兵。

群体动画是模拟群体中单个个体与其他个体以及单个个体与周围环境之间 交互的动画形式。而路径规划技术作为群体动画的核心技术，不仅仅大量使用 在图形学领域，同样在机器人、自动化和国防等领域有广泛应用，目前的研究 已经提出了众多的路径规划算法，其中针对大规模人群模拟的情况，时间复杂 度与Agent(人群模拟中个体)数不相关的自顶向下的方法，例如：Continuum (连续统一体)方法，被越来越多地应用到人群模拟中。Continuum方法能够产 生一个全局最优导航速度，在很多情况下，这是一大优势，例如：救灾机器人 寻径中，要找到一条前往目标点的最短路径。但是在这并不总是优势，例如在 恐慌人群模拟中，恐慌人群往往不够冷静和理性，并不总能够找到全局的最优 路径，更重要的是：恐慌人群在撤离的过程中，视线往往会被地形，建筑以及 其他Agent遮挡，因此恐慌人群始终按照全局最优路径运动并不符合现实情况。 另外，传统的Continuum方法，使用均匀网格技术，这在小场景人群模拟的情 况下，表现良好，但是针对大场景人群模拟时，如果要保证Agent准确感知环 境，则网格尺寸越小越好，但是针对大场景，小网格意味着大维度，而Continuum 方法的复杂度与网格数正相关，大维度会导致模拟效率极低，而大网格则导致 Agent不能准确感知环境。

另一方面在人群建模上，社会力方法被广泛地应用，并且被证明能够较好 地模拟人群运动的特性。但是在恐慌人群模拟中，人群往往会在逃生出口处形 成极高的人群密度，此时，社会力模型中原有的排斥力也不能保证Agent间不 发生碰撞。此外，社会力模型中，每个Agent所受的力只考虑了外界因素，例 如：周围其他Agent的位置，目标点的位置，而没有考虑Agent的内在属性， 例如：性格特征。而这一点对于逼真地模拟恐慌人群是很重要的。

发明内容

鉴于上述不足之处，为了较为真实地模拟恐慌状态下人群的特征，本发明 提供了一种恐慌人群逃生模拟技术方法。本发明根据恐慌人群在逃生过程中往 往不具备全局视野特征，发明局部视野技术，同样根据逃生场景中Agent密度 分布不均的特点，发明非均匀网格技术。根据恐慌人群中会出现的人群密度极 高的情况，发明一种新的交互力，为了体现人群中不同个体的性格特征，通过 性格特征与人群模拟参数的映射关系引入性格模型。

本发明总体包括三个模块，人群建模，路径规划和碰撞避免，具体为：

步骤1,建立全局的网格，并在容易出现拥挤的瓶颈区域添加密集网格，根 据每个Agent所处的初始位置及初始速度来得到一个密度场和平均速度场；

步骤2.根据步骤1所求出的密度场和平均速度场，就可以进一步求解每个 网格各方向上的速度和单位花费(从一个网格移动到相邻网格引起的势能变 化)。

步骤3.从选定的目标点开始，使用快速行进算法，求解全局势能场，其中 目标点的选择，根据局部可见性的特性而定。

使用局部视野技术，将目标点限制在Agent可见范围内。在所有可见网格 中，具体选择哪一个网格作为目标点，则依照实际情况而定，根据我们对现实 生活的观察，我们往往选择可见范围边界的路口或出口处作为目标点。当Agent 将要前往目标点时，我们暂不使用最终目标点进行全局导航，而是在当前位置 的视野可见范围内选择一个目标点，例如边界的路口或出口处。待Agent到达 该目标点之后，我们再在可见范围内选择下一个目标点，如此往复直到最终目 标点出现在视野中，此时再选择该目标点进行导航。这样的行进过程，更符合 我们对于日常生活的观察，具有更高的真实性。

步骤4.在得到势能场后，计算每个网格与自己的上风网格的势能差，然后 用这个势能差乘以网格对应方向的速度，然后将各个上风方向计算得到的速度 合成，从而得到该网格的导航速度。

步骤5.对密集网格单独计算势能场和导航速度，因为我们采用非均匀网格 技术，因此我们全局采用一张稀疏网格，然后对于人口密集区域，在原有的稀 疏网格的基础上叠加一张密集网格，Agent处在该区域外时，利用稀疏网格的导 航速度运动，而进入到密集区域时，则忽略稀疏网格，而采用密集网格的导航 速度运动。整个密集网格的势能独立计算，以密集区域的出口为目标点，计算 过程同步骤1-4，因为Continuum方法的计算复杂度只与网格数相关，而密集网 格只集中在狭窄通道的入口处，网格数并不多，因此并不会带来计算量的骤增。

在场景中Agent密集的区域使用密集网格，而在场景中Agent稀疏的区域使 用稀疏网格，而场景中Agent密集的区域的确定，可以根据对于实际生活的观 察来确定。我们发现在场景中的瓶颈区域，例如：狭窄的通道入口处，容易出 现人员聚集，因此我们在这样的位置使用密集网格。由于完全处于同一网格中 的Agent都具有相同的导航速度，并且无法通过势能感知同一网格中的其他 Agent，因此通过细分网格，可以使得Agent更加清楚准确地了解周围环境，并 且呈现出运动方向的多样性。

步骤6.将得到的导航速度作为想要到达的速度传递给人群建模模块，想要 达到的速度是社会力模型中的公式的一个参数，而此处的导航速度指的并不是 网格的导航速度，而是Agent的导航速度，区别在于如果Agent完全位于某一个 网格中，则Agent的导航速度就是该网格的导航速度，如果Agent处在多个网格 的交界处，则Agent的速度就是这几个网格根据Agent距离它们中心的距离的倒 数作为权重求和得到的速度值。

步骤7.通过社会力公式，以及交互力公式计算出首选速度，传递给碰撞避 免模块；

在原有的社会力模型中，Agent之间存在一个排斥力，但是在人群密度急剧 增高的情况下，这个排斥力并不能保证Agent之间不发生接触；接触的定义为： 两个Agent圆心间的距离小于它们的半径之和；因此针对这种非常拥挤的情况， 提出一种新的交互力，可以在接触发生的情况下，使Agent之间的距离恢复到 未发生接触的情况，这个交互力我们用符号表示：

$f_{\mathrm{ij}}^I=f_{\mathrm{ij}}^e+f_{\mathrm{ij}}^t---\left(1\right)$

其中作用于Agent圆心间连线方向：

$f_{\mathrm{ij}}^e=\left(\begin{array}{cc}\delta (r_{\mathrm{ij}}-d_{\mathrm{ij}})n_{\mathrm{ij}}& (r_{\mathrm{ij}}-d_{\mathrm{ij}}>0)\\ 0& (r_{\mathrm{ij}}-d_{\mathrm{ij}}\le 0)\end{array}\right)---\left(2\right)$

其中n_ij表示Agent j圆心到Agent i的圆心单位方向向量，δ表示强度系数；

r_ij＝r_i+r_j        (3)

r_ij表示Agent i的半径和Agent j的半径之和，而d_ij表示Agent i的圆心与 Agent j的圆心之间的距离。所以可以表示为：

$d_{\mathrm{ij}}=\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2}---\left(4\right)$

但是如果只有一个在两个Agent连线方向的力仍然可能出现Agent刚 恢复到未发生接触的情况后，又马上重新发生接触，所以我们考虑沿着两者圆 心连线方向的垂直方向添加一个力，我们将这个力表示为

$f_{\mathrm{ij}}^t=\left(\begin{array}{cc}\gamma (r_{\mathrm{ij}}-d_{\mathrm{ij}})t_{\mathrm{ij}}& (r_{\mathrm{ij}}-d_{\mathrm{ij}}<0)\\ 0& (r_{\mathrm{ij}}-d_{\mathrm{ij}}\ge 0)\end{array}\right)---\left(5\right)$

其中t_ij是垂直于n_ij的单位向量，定义为：

t_ij＝(-n_ij.y,n_ij.x)     (6)

而公式(5)中的γ的定义为：

γ＝μ(v_j-v_i)·t_ij      (7)

其中μ为强度系数，v_i和v_j表示Agent i和Agent j当前的速度。

步骤8.根据不同的个体的性格预先设定好人群模拟参数，使用最优相互碰 撞避免算法，得到一个保证碰撞避免情况下的最优速度；

通过设定碰撞避免算法中使用的参数可以模拟不同的性格特征，这些参数 包括：最大相邻距离，最大相邻Agent数，时长数，半径，想要达到的速度； 对应的性格特征用著名的Eysenck3-factor模型表示，包括：精神质，外倾性， 神经质；参数和性格特征间符合如下映射关系：

对M_p使用最小线性二乘的方法，可以求得：

$M_p=\left(\begin{array}{ccccc}0& 0.08& 0.08& -0.32& 0.63\\ -0.02& 0.13& 0.08& -0.22& 1.06\\ 0.03& -0.01& -0.03& 0.39& -0.37\end{array}\right)---\left(9\right)$

我们可以进一步对M_p求伪逆：

$M_{\mathrm{pi}}=\left(\begin{array}{ccc}11.754& -4.564& 7.127\\ 10.52& -3.865& 6.615\\ 14.204& -5.529& 8.361\\ -1.958& 1.850& 1.977\\ -2.547& 2.133& -0.898\end{array}\right)---\left(10\right)$

有了公式(10)，我们就可以根据我们对于Agent性格特征的需求预先计算出 它们所对应的人群模拟参数值。表1给出了一种可行的取值方式：

表1

步骤9.使用Agent当前的位置加上最优速度来更新Agent的位置，对所有 的Agent更新位置之后，重新回到步骤1，进入下一次的迭代。

本发明的有益效果是：通过使用局部视野技术，Agent每次只在视野可见范 围内选择当前目标点，到达当前目标点后，再选择新的当前目标点，如此反复， 直到到达最终目标点。这样的行进过程更符合实际情况。我们针对Agent密集 的区域使用密集网格，而相反在Agent稀疏的区域使用稀疏网格，因此一方面 保证了在Agent密集的区域，Agent能够准确的感知周围环境并具有行为多样性， 另一方面在Agent稀疏的区域使用稀疏网格，减少了程序的计算量，保证了效 率。此外，针对人口特别密集的情况，我们提出的新的交互力公式，能够将碰 撞的Agent分开，并且通过添加圆心连线切向方向速度，避免了重复碰撞的发 生。不仅如此，我们引入的性格模型，能够弥补原有社会力模型仅用外部因素 决定Agent的运动的不足，通过添加不同性格的Agent，使得Agent的行为特征 多样化。

附图说明

图1示出了本发明恐慌人群逃生模拟方法的流程图；

图2示出了本发明局部视野技术的示例图；

图3示出了本发明非均匀网格技术的示例图；

图4示出了本发明Agent间的新交互力的示例图；

图5示出了本发明Agent密度影响取值参数示例图；

图6示出了本发明中碰撞避免算法中速度障碍示例图；

图7示出了本发明中最优碰撞避免构造示例图；

具体实施方式

下面结合附图和实施例对本发明优先实施方式进一步说明：

在算法实现前，本实施预先计算各个Agent个体的人群模拟参数值。确定 需要的性格特征值，通过公式(10)所示的伪逆矩阵来求解对应的人群模拟参数。 然后作为Agent的初始参数写入到程序代码中。本实施总体包括三个模块，人 群建模，路径规划和碰撞避免，具体过程如图1所示，在下述步骤1至9中， 将分别对这些模块进行说明。

步骤1,建立全局的网格，并在容易出现拥挤的瓶颈区域添加密集网格。根 据Agent所处的初始位置及初始速度来求场景的密度场，而每个Agent引起的周 围网格的密度变化需要满足两个条件，1.Agent引起的密度变化随着距离Agent 圆心距离的变化而连续变化；2.Agent在自身所处网格引起的密度最大，并且存 在一个阈值ρ，使得Agent在自身所在网格引起的密度大于等于ρ，而在周围其 他网格引起的密度小于等于ρ。在本实施中，Agent的密度影响范围被设定为周 围四个网格，具体的取值如公式(11)所示：

ρ_leftdown＝min(1-Δx,1-Δy)ρ_rightdown＝min(Δx,1-Δy)

                (11)

ρ_rightup＝min(Δx,Δy)ρ_leftup＝min(1-Δx,Δy)

其中Δx和Δy表示Agent的圆心到x,y坐标均小于Agent圆心的最接近Agent 的网格的中心坐标。如图5所示。

将所有Agent的密度影响计算完成后，就得到总的密度场，在计算密度场 的同时还可以计算平均密度场，平均密度场的计算公式如下：

$\bar{v}=\frac{\underset{i}{\Sigma }{\rho }_i{v}_i}{\rho }---\left(12\right)$

其中ρ_i表示第i个Agent对该网格的影响，用公式(11)求出，v_i表示第i个 Agent的速度，ρ表示该网格上的总密度。

步骤2,根据步骤1所求出的密度场和平均速度场，就可以进一步就解每个 网格各方向上的速度和单位花费。

步骤2.1,网格各方向上的速度因网格在该方向上的相邻网格的速度不同而 不同。首先需要设定两个阈值，ρ_min和ρ_max，当在该方向上的相邻网格的密度小 于ρ_min时，速度由地形因素决定：

$f_T=f_{\max }+\left(\frac{▿h\left(x\right)·n_{\theta }-s_{\min }}{s_{\max }-s_{\min }}\right)(f_{\min }-f_{\max })---\left(13\right)$

其中表示地形在x处，沿着θ方向的坡度，θ方向也就是当前网格到 该相邻网格的方向。

步骤2.2，当密度大于ρ_max时，密度由该相邻网格的平均速度决定，如公式(14) 所示：

$f_v=\bar{v}(x+r{n}_{\theta })·n_{\theta }---\left(14\right)$

r是一个偏移量，之所以使用这个偏移量，是为了避免使用当前网格的平均 速度来决定向各个方向移动的速度，由于对当前网格的影响最大的就是处在该 网格的Agent，而由Agent自身的速度决定它向各个方向运动的速度，显然与我 们的期望不符，我们希望用处在相邻网格的Agent的速度来影响当前网格中的 Agent朝该方向的运动速度，从而在一定程度上避免碰撞。

步骤2.3,如果密度处在两个阈值之间，那么不仅要考虑地形因素的影响， 还应该考虑相邻网格的平均速度，因此在该方向上的速度为：

$f=f_T+\left(\frac{\rho (x+r{n}_{\theta })-{\rho }_{\min }}{{\rho }_{\max }-{\rho }_{\min }}\right)(f_{\bar{v}}-f_T)---\left(15\right)$

在得到向各方向的运动速度后，就可以求解向各个方向运动的单位花费， 求解公式如下：

$C=\frac{\mathrm{\alpha f}+\beta +\mathrm{\gamma g}}{f}---\left(16\right)$

步骤3.从目标点开始，使用快速行进算法，求解全局势能场，其中目标点 的选择，根据局部可见性的特性而定，如图2所示。快速行进算法的过程类似 于迪杰斯特拉算法，先将目标点的势能值设定为0，并将其添加到“已知”队列 中。所有其他网格添加到“未知”队列中。然后将所有与目标点相邻的网格添 加到“候选”队列，然后对每一个“候选”队列中的网格计算势能，首先计算 该网格的上风方向，使用公式(17)：

其中C_M→i表示从当前网格到i方向的单位花费。

使用有限微分近似eikonal等式，所以该网格的势能可以通过解如公式(18) 所示的一元二次方程来求得，公式(18)如下所示：

${\left(\frac{{\phi }_M-{\phi }_{m_x}}{C_{M\to m_x}}\right)}^2+{\left(\frac{{\phi }_M-{\phi }_{m_y}}{C_{M\to m_y}}\right)}^2=1---\left(18\right)$

公式(18)可能有两个解，势能值为两个解中的较大解。如果m_x或m_y对应的 网格不属于“已知”网格，则将公式(18)中m_x或m_y对应的一项消除掉。

步骤4，在得到势能场后，计算每个网格与自己的上风网格的势能差，然后 用这个势能差乘以网格对应方向的速度，然后将各个上风方向计算得到的速度 合成，从而得到该网格的导航速度。

步骤5，对密集网格单独计算势能场和导航速度，因为我们采用非均匀网格 技术，因此我们全局采用一张稀疏网格，然后对于人口密集区域，在原有的稀 疏网格的基础上叠加一张密集网格，Agent处在该区域外时，利用稀疏网格的导 航速度运动，而进入到密集区域时，则忽略稀疏网格，而采用密集网格的导航 速度运动，如图3所示。整个密集网格的势能独立计算，以密集区域的出口为 目标点，计算过程同步骤1-4，因为Continuum方法的计算复杂度只与网格数相 关，而密集网格只集中在狭窄通道的入口处，网格数并不多，因此并不会带来 计算量的骤增。

步骤6，将得到的导航速度作为想要到达的速度传递给人群建模模块，想要 达到的速度是社会力模型中的公式的一个参数，而此处的导航速度指的并不是 网格的导航速度，而是Agent的导航速度，区别在于如果Agent完全位于某一个 网格中，则Agent的导航速度就是该网格的导航速度，如果Agent处在多个网格 的交界处，则Agent的速度就是这几个网格根据Agent距离它们中心的距离的倒 数作为权重求和得到的速度值。

步骤7，通过社会力公式，以及交互力公式计算出首选速度，传递给碰撞避 免模块；

社会力模型可以通过公式(19)来表示：

$m_i\frac{d{v}_i}{\mathrm{dt}}=f_i\left(t\right)+{\xi }_i\left(t\right)---\left(19\right)$

其中m_i表示第i个Agent的质量，f_i(t)表示第i个Agent受到的合力，而ξ_i(t) 表示作用于Agent的其他不确定因素的合力。

步骤7.1，作用于Agent上的各种力中最核心的就是一个内在的驱动力，这 是由于Agent想要向目标点移动的意愿而产生的驱动Agent向目标点移动的力。 这个驱动力可以表示为：

$f_i^d\left(t\right)=m_i{a}_i\left(t\right)---\left(20\right)$

其中a_i(t)的定义为：

$a_i\left(t\right)=\frac{[v_i^0\left(t\right)e_i^0\left(t\right)-v_i\left(t\right)]}{{\tau }_i}---\left(\text{21}\right)$

其中，表示Agent i想要达到的速率，表示Agent i想要达到的速度 的方向的单位向量。这两个参数可以通过步骤6传递的导航速度来确定。v_i(t)表 示Agent i的当前速度。τ_i表示Agent i期望用多长时间达到

步骤7.2，人群中Agent之间都要保持一定的距离，当Agent之间的距离小 于一定的值时，他们之间将产生一个排斥力。这个排斥力可以使用公式(22)来表 示：

其中，r_ij表示Agent i和Agent j的半径之和，d_ij表示Agent i和Agent j之间 的圆心距。R_i表示该排斥力的作用半径。δ_i表示强度系数。λ_i的选择可以因具体 的模拟场景的不同而不同，但一般情况下，λ_i＝0，因为这样Agent i和Agent j 之间的排斥力互为作用力和反作用力，即两者等大反向。n_ij表示从Agent i的圆 心指向Agent j的圆心的单位向量，如公式(23)所示：

$n_{\mathrm{ij}}\left(t\right)=\frac{x_i\left(t\right)-x_j\left(t\right)}{d_{\mathrm{ij}}\left(t\right)}---\left(23\right)$

而表示当前速度方向e_i(t)与-n_ij方向的夹角，如公式(24)所示：

步骤7.3，除了排斥力之外，在同一组的Agent之间还存在吸引力，即同一 组的人总是希望走在一起，这一点与我们对实际生活的观察相符，这个吸引力 可以用公式(25)来表示：

$f_{\mathrm{ij}}^{\mathrm{att}}\left(t\right)=-C_{\mathrm{ij}}{n}_{\mathrm{ij}}\left(t\right)---\left(25\right)$

从公式(25)可以看出，处于同一组的Agent即使被障碍物或相向而行的其他 行人分开之后，仍然会重新聚集在一起。

将前面描述的各种作用力求合力，就得到每个Agent所受到的社会力，该 社会力表达式如公式(26)所示：

$f_i\left(t\right)=m{a}_i\left(t\right)+\underset{j\ne i}{\Sigma }{f}_{\mathrm{ij}}^{\mathrm{rep}}\left(t\right)+\underset{k}{\Sigma }{f}_{\mathrm{ik}}^{\mathrm{att}}\left(t\right)---\left(26\right)$

步骤7.4，在原有的社会力模型中，Agent之间存在一个排斥力，但是在人 群密度急剧增高的情况下，这个排斥力并不能保证Agent之间不发生接触；接 触的定义为：两个Agent圆心间的距离小于它们的半径之和；因此针对这种非 常拥挤的情况，提出一种新的交互力，可以在接触发生的情况下，使Agent之 间的距离恢复到未发生接触的情况，这个交互力我们用符号表示：

$f_{\mathrm{ij}}^I=f_{\mathrm{ij}}^e+f_{\mathrm{ij}}^t---\left(1\right)$

其中作用于Agent圆心间连线方向：

$f_{\mathrm{ij}}^e=\left(\begin{array}{cc}\delta (r_{\mathrm{ij}}-d_{\mathrm{ij}})n_{\mathrm{ij}}& (r_{\mathrm{ij}}-d_{\mathrm{ij}}>0)\\ 0& (r_{\mathrm{ij}}-d_{\mathrm{ij}}\le 0)\end{array}\right)---\left(2\right)$

其中n_ij表示Agent j圆心到Agent i的圆心单位方向向量，δ表示强度系数；

r_ij＝r_i+r_j          (3)

r_ij表示Agent i的半径和Agent j的半径之和，而d_ij表示Agent i的圆心与 Agent j的圆心之间的距离。所以可以表示为：

$d_{\mathrm{ij}}=\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2}---\left(4\right)$

但是如果只有一个在两个Agent连线方向的力仍然可能出现Agent刚 恢复到未发生接触的情况后，又马上重新发生接触，所以我们考虑沿着两者圆 心连线方向的垂直方向添加一个力，我们将这个力表示为

$f_{\mathrm{ij}}^t=\left(\begin{array}{cc}\gamma (r_{\mathrm{ij}}-d_{\mathrm{ij}})t_{\mathrm{ij}}& (r_{\mathrm{ij}}-d_{\mathrm{ij}}<0)\\ 0& (r_{\mathrm{ij}}-d_{\mathrm{ij}}\ge 0)\end{array}\right)---\left(5\right)$

其中t_ij是垂直于n_ij的单位向量，定义为：

t_ij＝(-n_ij.y,n_ij.x)          (6)

而公式(5)中的γ的定义为：

γ＝μ(v_j-v_i)·t_ij          (7)

其中μ为强度系数，v_i和v_j表示Agent i和Agent j当前的速度。

公式(26)所示是传统社会力模型得到的合力，由于我们的发明添加了一个新 的交互力，因此在公式(26)的基础上还要将f_i(t)与总的交互力相加，如图4所示。 交互力的求解由公式(1)、公式(2)和公式(5)。因此总的合力如公式(27)所示：

$f_i^{\mathrm{soc}}\left(t\right)=f_i\left(t\right)+\underset{j\ne i}{\Sigma }{f}_{\mathrm{ij}}^I\left(t\right)---\left(27\right)$

步骤7.5，得到了总的合力之后，还需要将这个合力转化为首选速度，然后 传递给碰撞避免模块。因此我们使用公式(28)，将合力转化为首选速度：

$v_i^{\mathrm{pref}}=v_i+\frac{f_i^{\mathrm{soc}}\left(t\right)}{m_i}---\left(28\right).$

步骤8，根据不同的个体的性格预先设定好人群模拟参数，使用最优相互碰 撞避免算法，得到一个保证碰撞避免情况下的最优速度；

通过设定碰撞避免算法中使用的参数可以模拟不同的性格特征，这些参 数包括：最大相邻距离，最大相邻Agent数，时长数，半径，想要达到的速度； 对应的性格特征用著名的Eysenck3-factor模型表示，包括：精神质，外倾性， 神经质；参数和性格特征间符合如下映射关系：

对M_p使用最小线性二乘的方法，可以求得：

$M_p=\left(\begin{array}{ccccc}0& 0.08& 0.08& -0.32& 0.63\\ -0.02& 0.13& 0.08& -0.22& 1.06\\ 0.03& -0.01& -0.03& 0.39& -0.37\end{array}\right)---\left(9\right)$

我们可以进一步对M_p求伪逆：

$M_{\mathrm{pi}}=\left(\begin{array}{ccc}11.754& -4.564& 7.127\\ 10.52& -3.865& 6.615\\ 14.204& -5.529& 8.361\\ -1.958& 1.850& 1.977\\ -2.547& 2.133& -0.898\end{array}\right)---\left(10\right)$

有了公式(10)，我们就可以根据我们对于Agent性格特征的需求预先计算出 它们所对应的人群模拟参数值。

使用ORCA碰撞避免算法，求解满足碰撞避免的速度，ORCA算法是基于 速度障碍的概念。速度障碍的定义如下：如果Agent A相对于Agent B的速 度位于中，那么在接下来的t时间内中的某个时刻Agent A将和Agent B发 生碰撞。可以使用公式(29)表示：

${\mathrm{VO}}_{A|B}^t=\left\{v\right|\mathrm{vT}\in D(p_B-p_A,r_A+r_B),T\in [0,t]\}---\left(29\right)$

其中D(p_B-p_A,r_A+r_B)表示以p_B-p_A为圆心，以r_A+r_B为半径的圆，如图6 所示。

如果Agent B的速度范围为V_B，那么Agent B对于Agent A造成的速度障碍 就可以表示为公式(30)：

$C_{A|B}^t\left(V_B\right)=\left\{v\right|v=a+b,a{\in \mathrm{VO}}_{A|B}^t,b\in V_B\}---\left(30\right)$

也就是说如果Agent A的速度如果位于中，那么在接下来的t时间内， Agent A和Agent B就可能发生碰撞，那么与之相反，如果Agent A的速度不位 于中，那么就能保证在接下来的t时间内，Agent A不与Agent B碰撞。 我们可以通过公式(31)来表示这个集合。

${\mathrm{CA}}_{A|B}^t\left(V_B\right)=\left\{v\right|v\ne a+b,a\in {\mathrm{VO}}_{A|B}^t,b\in V_B\}---\left(31\right)$

如果并且那么Agent A和Agent B在自己的取值 范围中无论取什么值都可以保证在接下来的t时间内它们之间不会发生碰撞。如 果并且则被称为相互碰撞最大化。

在相互碰撞最大化的基础上，我们定义最优碰撞避免：

${\mathrm{ORCA}}_{A|B}^t={\mathrm{CA}}_{A|B}^t\left({\mathrm{ORCA}}_{B|A}^t\right),$

${\mathrm{ORCA}}_{B|A}^t={\mathrm{CA}}_{B|A}^t\left({\mathrm{ORCA}}_{A|B}^t\right)$

$|{\mathrm{ORCA}}_{A|B}^t\cap D(v_A^{\mathrm{opt}},r)|=|{\mathrm{ORCA}}_{B|A}^t\cap D(v_B^{\mathrm{opt}},r)|\ge \min \left(\right|V_A\cap D(v_A^{\mathrm{opt}},r)|,|V_B\cap D(v_B^{\mathrm{opt}},r)\left|\right)---\left(32\right)$

其中$V_A\subseteq {\mathrm{CA}}_{A|B}^t\left(V_B\right),V_B\subseteq {\mathrm{CA}}_{B|A}^t\left(V_A\right),$从公式(32)可以看出，和除 了满足相互最大化的条件以外，还满足比任何一组碰撞避免速度V_A和V_B都包含 更多接近和的速度，和通常可以取当前速度，这样可以减少速度的 突变，这与对现实生活的观察相符。

和可以使用几何方式构造，首先假设Agent A和Agent B都 取最优速度和定义向量u为从到速度障碍边缘上最近点的 向量。如公式(33)所示：

$u=\left(\underset{v\in {\partial \mathrm{VO}}_{A|B}^t}{\arg \min }\right||v-(v_A^{\mathrm{opt}}-v_B^{\mathrm{opt}})|\left|\right)-(v_A^{\mathrm{opt}}-v_B^{\mathrm{opt}})---\left(33\right)$

定义n为从到速度障碍边缘上最近点处向外的法向量。有公式 (33)可知，如果要避免碰撞，的值至少需要改变u，因为要满足最优碰撞 避免的条件，所以Agent A和Agent B的速度各改变0.5u。

因此我们可以通过如下方法构造和是通过点 方向为n的一个半平面，是通过点方向为-n的一个半平 面，如图7所示。

可以使用公式(34)表示和的构造方法：

${\mathrm{ORCA}}_{A|B}^t=\left\{v\right|(v-(v_A^{\mathrm{opt}}+0.5u))·n\ge 0\}$

${\mathrm{ORCA}}_{B|A}^t=\left\{v\right|(v-(v_B^{\mathrm{opt}}-0.5u))·(-n)\ge 0\}---\left(34\right)$

在实现过程中，首先需要求解的值，然后求解到边缘上 最近的点P，由于边缘是由一段圆弧和两条射线组成，因此要确定P位于 圆弧上还是射线上需要先求解三条直线，第一条是坐标原点到的连线， 用这条线来判断点是位于这条线的左侧还是右侧。另外需要求解到两条射线的垂点，这个可以通过该点到的向量与该点到坐标原点的向 量垂直来求得。因此可以得到这两条垂线的直线方程，如果位于垂线的 内侧(靠近坐标原点一侧)，则P位于圆弧上，通过经过的半径与圆弧的 交点可以得到P。如果位于垂线的外侧，则P位于射线上，通过点向射线做垂线可以得到P。

P确定之后，u和n都可以确定，然后根据公式(34)，就可以得到对应的半 平面，Agent A对于其他每一个Agent B都会得到一个半平面，因此如果Agent A 最后的取值位于所有半平面的交集之中，那么在接下来的t时间内Agent A就不 会与其他任何Agent发生碰撞。因此接下来的工作，就是求解所有半平面的交 集，并在这个交集中找到一个最接近的速度，其中由步骤7给出。

而这个求解过程就转变成了一个求解线性规划的过程，可以使用随机增量 算法来求解，算法过程可以大致描述为：

(1)将最优解设定为边界上一点s₀；

(2)检查第一个半平面，看s₀是否处于第一个半平面中，如果是，则s₁＝s₀， 然后检查第二个半平面。

(3)如果不是，检查第一个半平面边界线于当前边界的交点，如果没有交点， 则该线性规划无解，如果有一个解，那么这个解就是s₁。如果有两个解，则比较 这两个解中取得目标函数值，较小值的那个为s₁。然后检查第二个半平面。

这个过程直到检查了所有n个平面之后，s_n就是的最优解。

当然可能出现无解的情况，此时我们求解一个“最可能的”安全速度，假 设d表示速度v到边界线的距离，因此(v,d)就变成了三维空间中的一个 点。所以所用的v对应的(v,d)就构成了一个平面。因此Agent A对于其他所有 Agent B都对应一个平面，而我们要求的“最可能的”安全速度就是一个满足位 于所有平面上方条件的具有最小高度值的点，而这个点可以同样通过随机线性 规划方法解一个三维线性规划来求得。

步骤9，得到最优速度之后，使用Agent当前的位置加上最优速度来更新 Agent的位置，对所有的Agent更新位置之后，重新回到步骤1，进入下一次的 迭代。