碰撞避免是计算机虚拟行人仿真的一个基本问题, 通常我们可以将其定义为: 仿真行人在虚拟环境中朝目标点的运动过程中, 需在每个仿真周期内感知其他静态及动态实体的存在, 若有碰撞可能则采取一定的措施(如调整速度等)避免碰撞^[1].

碰撞避免问题在机器人, 虚拟智能体仿真, 实时交通模拟等领域均有广泛的研究. 现有的方法一般分成集中式与分布式两种. 前者将环境中所有运动实体当成一个完整的系统, 通过理论分析的方法计算所有的碰撞可能, 并协调统一地完成避碰操作, 但是由于原理的限制, 这种方法仅限应用于单智能体或者少量行人仿真中^[2]. 分布式的方法则将每一个运动实体建模为独立感知周围环境以此指导决策, 最终采取相应动作的智能体. 很显然, 分布式的方法可以方便且直观地模拟虚拟人群的运动过程. 许多碰撞避免算法都是基于速度障碍模型(velocity obstacles), 通过计算相对速度的闽科夫斯基矢量和, 确定行人的可行速度域, 从而选择合适新速度避免碰撞. 这一类的方法在各领域的研究均有广泛的应用^[3–5]. Berg等人提出的优化相互速度障碍模型(ORCA)算法^[6]即为经典的基于速度障碍模型的n-body碰撞避免算法, 该算法将行人动态避碰问题转化为线性规划进行求解. 因其高效的性能和逼真的仿真结果而被广泛地应用于动态避碰中^[7,8].

然而现实中行人的运动往往存在着天然的差异性, 不同行人因年龄, 性格, 速度等特性差异, 导致实际的避碰策略存在着个性化特征. 为获得更为逼真的仿真效果, 提升人群仿真的真实性和科学性, 本文在ORCA算法的基础上加以拓展, 并引入行人最低能耗的概念, 设计并实现了行人最低能耗的动态避障算法.

1 速度障碍模型概述 1.1 速度障碍定义

本文所讨论的行人动态避障问题定义如下: 仿真平面存在n个仿真行人, 每一个行人均从自身的出发点按照一定的物理限制(最大速度, 最大加速度, 不能碰撞等)在一个平面内朝目标点移动. 为简化分析起见, 我们将行人简化为具有一定半径的圆模型. 我们使用 $D({{p}},r)$ 表示圆心为p半径为r的圆模型.

$ D{\rm{(}}{{p}}{{,r) = \{ }}{{q}}|\left\| {{{q}} - {{p}}} \right\| \le r{\rm{\} }} $

(1)

对于位置分别在 ${{{p}}_A}$ 和 ${{{p}}_B}$ 处的两个行人速度分别为 ${v_A}$ 和 ${v_B}$ , 为衡量在未来两行人是否有可能发生碰撞, 对于行人A, 我们可以在速度平面将其考虑成质点, 图1中的阴影扇形区域即表示行人B以速度 ${v_B}$ 对于行人A的相对速度障碍 $VO_B^A({v_B})$ ,而只要两行人的相对速度落在这一扇形区域内,则未来一定会发生碰撞. 公式定义如下:

$ VO_B^A({v_B}{\rm{) = }}\left\{ {{v_A}|\lambda ({{p}_A},{v_A} - {v_B}) \cap B \oplus - A \ne \emptyset } \right\} $

(2)

式中, $VO_B^A{\rm{(}}{v_B}{\rm{)}}$ 为行人B速度为 ${v_B}$ 对行人A的速度障碍, 其中 $\lambda ({{{p}}_A},{v_A} - {v_B})$ 为从出发沿 ${v_A} - {v_B}$ 方向出发的射线, $B \oplus - A$ 为集合B与集合–A的闵可夫斯基矢量和, 数学定义如下:

$ A \oplus B = \left\{ {a + b|a \in A,b \in B} \right\}, - {\rm{A}} = \{ - a|{{a}} \in A\} $

(3)

简单地, 我们可以对上述情况进行拓展, 即考虑行人A周围若干个行人分别求出对应的速度障碍, 此时只需调整速度使其新的相对速度落于所有其他行人相对速度障碍区域外即可.

1.2 改进ORCA算法

原始的速度障碍法在计算自身的速度障碍时均假定其他智能体按照之前的速度前进, 彼此之间并无合作策略; 且不考虑时间窗口, 只要有碰撞可能均需调整速度方向, 因此会出现轨迹振荡、抖动等不真实现象^[9]. 为解决这一问题, RVO及ORCA等算法相继被提出, 作为行人仿真的底层避障算法被广泛使用.

首先智能体在计算速度障碍时应当考虑未来最近一段时间窗口 $\tau $ 内, 类似地如图2(b)所示的阴影区域的类扇形即为考虑时间窗口后的速度障碍区域, 数学表示为:

$ VO_{A|B}^\tau = \left\{ {v|\exists {{t}} \in [0,\tau ],{{t}} \cdot v \in D\left({{{p}}_B} - {{{p}}_A},{r_A} + {r_B}\right)} \right\} $

(4)

ORCA算法假设所有的虚拟行人按照相同的避障策略调整速度进行避障, 其核心在于将速度障碍约束调整为线性直线约束. 对照图2(c), 具体步骤可以描述为:

(1)求解相对速度 $v_A^{opt} - v_B^{opt}$ , ${v^{opt}}$ 为优化速度, 一般初始值选取为虚拟行人的当前速度;

(2)求解 $VO_{A|B}^\tau $ 边界上离相对速度最近的一点x, 获得从 $v_A^{opt} - v_B^{opt}$ 指向x的矢量u.

(3)假设智能体都按照相同策略避障, 求解与 $v_A^{opt} + {{u}}{\rm{/}}2$ 相垂直的直线分成两个半平面, 与第(2)步中经过点x的 $VO_{A|B}^\tau $ 边界法向量n同向的半平面作为优化相互半平面约束速度集合 $ORCA_{A|B}^\tau $ , 数学定义见式(5), 同理求解 $ORCA_{B{\rm{|}}A}^\tau $ .

4)与其他周围所有智能体求得由直线约束所包围的可行速度域, 从中求解与优化目标最接近的最优速度.

$ ORCA_{A|B}^\tau = \left\{ {v|\left(v - \left(v_A^{opt} + {u}/2\right)\right) \cdot {n} \ge 0} \right\} $

(5)

在每一步仿真迭代中, 智能体获取自身及其视野范围内其他智能体的位置和速度, 基于这些信息可以计算出该智能体A与其他所有智能体的优化相互半平面约束速度集合; 此外, 行人还受到自身最大速度 $v_A^{max}$ 的限制. 因此在ORCA模型下受到的速度选择约束可以表示为:

$ ORCA_A^\tau = D\left({{0}},v_A^{max}\right) \cap \mathop \cap \limits_{B \ne A} ORCA_{A|B}^\tau $

(6)

为了体现行人避障策略采取中存在的差异性, 我们将式(5)改写成:

$ORCA_{A|B}^\tau = \left\{ {v|\left(v - \left(v_A^{opt} + \alpha _{A|B}^\tau \cdot {{u}}\right)\right) \cdot {{n}} \ge 0} \right\} $

(7)

其中, $\alpha _{A|B}^\tau $ 为调节系数, 我们将其定义为:

$ \alpha _{A|B}^\tau = - {2^{ - (|{{{v}}_{{B}}}|/|{{{v}}_A}| + 1)}}{\rm{ + }}\frac{3}{4} $

(8)

式中, $\alpha _{A|B}^\tau \in \left[ {0.25{\rm{, }}0.75} \right)$ , 如果虚拟行人在进入局部避障时速度相同, $\alpha _{A|B}^\tau $ =1/2, 则退化成普通的ORCA模型; 而当虚拟行人的速度存在差异时, 不失一般性, 我们令 ${v_A} < {v_B}$ , 则有 $\alpha _{A|B}^\tau \in \left( {0.5,{\kern 1pt} {\kern 1pt} 0.75} \right)$ , $\alpha _{{{B}}|A}^\tau \in \left( {0.25,{\kern 1pt} {\kern 1pt} 0.5} \right)$ , 且 $\alpha _{A|B}^\tau {\rm{ + }}\alpha _{B|A}^\tau \approx 1$ . 也即速度较小的行人因为速度低, 可以更为方便地调整速度方向, 因此承担更多的“主动避障”的责任. 通过调节系数引入, 我们可以得到差异化的仿真结果.

类似地, 静态障碍物可以视为速度为0的障碍物, 因此同样的约束构造方法也适用于静态障碍物.

2 虚拟行人动态避障算法

我们将仿真行人建模为在一个仿真周期 $\Delta t$ 内不停感知周围环境并采取相应动作的自治智能体. 基于改进ORCA算法, 结合行人运动最低能耗函数,为仿真行人设计了动态避障算法.

2.1 基于最低能耗的行人运动模型

最小能耗这一概念最早由Zipf^[10]提出用于描述生物的运动, 可简单概括为: “自然环境中的生物体在达到自己目标的运动中倾向于采用估计能量消耗最低的方式”. Guy^[11]等人将这一原则引入仿真行人的建模提出了经典的Pledestrian模型. 在他的研究中指出, 在没有外部因素干扰的条件下, 行人的运动按照能耗最低方式进行. 考虑这一点, Pledestrian所采用的行人能耗方程如下:

$ {{E}} = P{{m}}\tau + {E_{qd}} $

(9)

式中, P为单位质量的瞬时能耗, m为行人的质量, $\tau $ 为时间窗口, ${{{E}}_{qd}}$ 为行人按照当前速度运动一段时间 $\tau $ 后到达到位置q, 从q再运动到目标d所耗费的能量. 对于运动中的仿真行人而言, P的计算方式表示如下:

$ P = {e_s} + {e_d}{\left| v \right|^2} $

(10)

式中, $v$ 为行人瞬时速度, ${e_s}$ 表示行人静止能耗参数, ${e_d}$ 为运动能耗参数, 对于具体的行人是一个常数. Whittle等人^[12]通过对行人在不同运动速度下的单位时间耗氧量研究测算出普通行人的 ${e_s}$ 和 ${e_d}$ 的平均值分别为 $2.23\;{\rm{J}} \cdot {({\rm{kgs}})^{ - 1}}$ 和 $1.26\;{\rm{Js}} \cdot ({{\rm{kg}}^{ - 1}}{{\rm{m}}^{ - 2}})$ .

在对行人的观察研究中, 人们发现行人还有保持自身运动方向的“惯性趋势”^[13], 因此在变换运动方向时理论上行人应消耗额外的能量, 而这在原始的最小能耗方程中并无考虑. 且行人在进行动态避障时, 主要应考虑的为对速度方向的改变量; 因此我们可以将行人的瞬时能耗方程修改为:

$ P = {e_s} + {e_d}{\left| v \right|^2} + {e_r}|\omega {|^2} $

(11)

式中, $\omega $ 为行人在变换速度方向时的瞬时角速度大小, 同理 ${e_r}$ 为转动能耗参数, 前人研究表明^[13]这一参数的取值约为 $0.5 \sim 2.0\;{\rm{Js}} \cdot {\rm{k}}{{\rm{g}}^{ - 1}}{\rm{ra}}{{\rm{d}}^{ - 2}}$ .

式(11)使得我们可以对虚拟行人变换方向的转动能量加以量化. ${e_r}$ 的数值越大, 表示行人在角速度较大时所消耗的能量也越多. 本文的瞬时能耗方程修改可以对虚拟行人动态避障时在速度方向的变化量上给出理论依据, 因此更适用于大规模人群仿真行人速度方向变更比较频繁时的场景.

行人的动态避障是一个局部动态过程, 往往并没有一个确切的目标点, 因此不能直接采用式(9)来计算行人的局部避障过程中最低能量消耗. 另外, 我们注意到行人在完成动态避障后会回归顶层寻路模块得到的期望速度, 一般为指向最终目标点的方向. 因此我们可以参照文献[13]的处理方法, 考虑如图3所示情况, 即行人在时间 ${{{t}}_0}$ 时刻位于 ${{{p}}_A}$ 从速度 ${v_{t - 1}} = {v^{pref}}$ 转为 ${v_t}$ , 并经过一段时间 $\tau $ 后到达 ${q_A}$ , 然后行人经过一段以o为圆心, 转弯半径为 $\;\rho = {v_{max}}/{\omega _{min}}$ 的匀速圆周运动尽快将速度转换为期望速度 ${v^{pref}}$ , 最终到达 ${q'_A}$ , 完成整个局部避障过程.

$ \begin{split} \Delta E =& {E_{{p_A} \to {q'_A}}} - {E_{{p_A} \to {q'_{pref}}}} \\ = &\left({E_{{p_A} \to {q_A}}} + {E_{{q_A} \to {q'_A}}}\right) - \left({E_{{p_A} \to {q_{pref}}}} + - {E_{{q_{pref}} \to {q'_{pref}}}}\right) \\ \end{split} $

(12)

代入式(7)和式(9), 并考虑到图3所示的几何关系可得:

$ \begin{split} \Delta E({v_t}) =& 2m\sqrt {2{e_s}{e_d}(\theta - \sin \theta )} - 2m\sqrt {{e_s}{e_r}} \left| {{v_t}} \right|\tau \cdot \cos \theta \\ & + m({e_s} + {e_d}{\left| {{v_t}} \right|^2})\tau \end{split} $

(13)

因此行人动态避障选择新速度时, 可以将可行的速度域代入式(13)中得到当前条件下的最优避障速度, 并据此更新位置.

2.2 最低能耗局部动态避障算法

如前文所述, 我们需要选择在可选速度范围内使得完成局部避障最低能耗的速度, 即

$ v_A^{new} = \mathop {\arg {\kern 1pt} \min }\limits_{v \in ORCA_A^\tau } \Delta E(v) $

(14)

目标行人的ORCA半平面交集组成了速度可行域, 从中选取最优的点问题是计算几何中典型的二维线性规划问题, 使用文献[14]中的随机算法已被证明可以在O(n)的期望时间内对这一问题高效求解, n为约束个数. 因此我们对每一段线性约束以随机的顺序逐个求解, 在每一段可行线性约束边界进行m次采样分别计算额外的能耗值 $\Delta E$ , 最终选择能耗最优的新速度, 仿真行人并依此到达新位置, 即:

$ {{p}}_A^{new} = {{{p}}_A} + v_A^{new}\Delta t $

(15)

综上, 我们可以将我们的仿真行人动态避障算法总结如下:

算法1. 最低能耗局部动态避障算法

输入: 虚拟行人位置p_i, 速度v_i, 采样数量m

输出: 更新速度v_i^new.

(1)获取邻近障碍物线性约束: 通过kd-tree等数据结构获取虚拟行人周围的虚拟行人状态信息, 按照式(6)和式(7)计算障碍物约束集L.

(2)依次对L中每一条直线进行线性分析得到的可选速度上下限, 并在所选区域进行m次采样, 分别计算式(13)得到最优避碰速度.

(3)将上一步得到的最优避碰速度作为虚拟行人的新速度, 并更新位置

(4)重复(1)–(3)步, 直到虚拟行人到达其目的地.

通过对上述算法的分析可知, 我们的算法时间复杂度为 ${\rm{O}}({{n}} \cdot {{m}})$ , 其中n为智能体周围障碍物的个数, m为计算能耗最优的离散采样点数量. 在算法1第(1)步获取动态障碍物时, 我们可以只考虑最近N个障碍物的影响. 现实世界中超高密度人群大约为5~7人/m^2[15], 因此我们将N设定为10, m设定为100, 计算量对于当前计算机硬件计算能力而言足以接受, 第3节中通过实验分析表明本文提出的避障算法可以满足虚拟大规模人群仿真的实时性要求(~30 fps).

3 实验分析

实验首先验证虚拟行人的动态避障过程, 然后衡量了我们方法在性能上的表现, 最后验证本文方法可以通过简单的参数设置得到差异化的行人的避障效果.

3.1 虚拟行人动态避障实验

我们在小规模的场景下验证了行人动态避障的效果. 场景一如图4(a)所示的, 为行人分别从左右迎面前进; 场景二如图4(b)所示, 两列行人分别朝斜对角的目标点前进; 可以看出我们的算法可以让行人正确完成避障并到达目的地.

3.2 性能实验

在大规模的行人仿真中, 在比较拥挤的情况下依然需要确保行人之间不存在碰撞. 为了衡量我们的方法在大规模人群下的表现, 我们设计了Circle场景, 即行人建模为半径0.5 m的圆, 行人均匀分布在半径为500 m的大圆上, 每个行人目标点设置为经过圆心的圆对面一点. 仿真行人开始会往圆心汇聚, 在圆心附近达到避碰高峰, 行人调整自身速度避免碰撞, 之后平滑地往目标点前进. 图5比较了我们的方法与原始ORCA算法在相同场景, 不同智能体的数目下人群仿真时间. 可以看出由于我们采用最低能耗的方式可以显著降低总仿真时间, 也即可以获得更为流畅的仿真结果, 提升仿真效率.

我们的方法使用C#编写, 运行在普通PC (CPU Intel i7-7700HQ 2.8 GHz双核, RAM 8 GB)上, 图6给出了我们的方法和原始的ORCA算法在不同智能体个数时每帧计算时间. 可以看出我们的方法因为计算量的增加, 每帧运算时间大概是原始ORCA算法的两倍左右. 图6中横虚线为30 fps的每帧计算时间要求, 可以看出我们的算法在智能体数量为几千到一万时依然可以达到~30 fps的要求.

3.3 差异性避障实验

引入行人最优能耗的方法来进行动态避障的好处除了可以加快仿真进程, 同时也可以通过参数设置的不同来区分不同类别的行人.

为了对这一点进行简要的验证, 我们考虑一个简单的嫌疑人动态抓捕的场景, 即安保人员沿右方追捕往右逃窜的嫌疑人, 同时普通行人正迎面走来. 在这样一个场景中, 按照常识, 安保人员与嫌疑人速度较快, 且处于动态抓捕过程中将承担更少的避障责任, 而普通行人则将的承担更多的避障责任. 我们按照表1设定不同人员的能耗参数, 最终仿真得到行人轨迹图如图7所示.

从图7中可以看出, 行人能耗参数与速度的不同将影响行人的避障行为, 而这些特点在大规模的人群仿真中可以加以利用, 从而获得更为真实科学的仿真效果.

4 结论与展望

本文拓展了经典的分布式虚拟行人避障算法ORCA, 并引入行人最低能耗模型指导虚拟行人最优速度的选取. 通过实验验证, 本文的方法可以缩短仿真进程, 在性能上也可以满足实时仿真的要求, 并且可以为差异化的行人仿真提供参考. 下一步计划采用现有方法精细化研究不同类别行人动态避障策略与效果.