基于熵度量的人群模型评估方法①

刘 杨, 王 雷, 盛 捷

(中国科学技术大学 信息科学技术学院, 合肥 230027)

近年来, 随着虚拟人群仿真技术在公共安全、城市规划、智能交通等领域的广泛应用, 人群仿真模型的评估方法成为研究人员关注的问题.人群是一个复杂系统[1], 个体行为具有随机性, 同时个体之间又会互相影响.众所周知, 描述复杂系统时, 不能只依赖确定的微观信息, 而应该同时考虑系统宏观特征, 所以, 评估人群仿真模型的主要挑战在于复杂系统间相似性的全面度量.

当前模型评估算法研究主要分为定性和定量两类.定性评估方法主要包括视觉比较[2]和感知实验[3]等,但是这类方法依赖主观因素, 随着模型复杂度提升, 难以得到有效的评估结果.定量方法分为两类: 主要有数据驱动评估方法和非参估计评估方法.其中, 数据驱动的方法基于人群微观信息和低级特征的比较来评估模型, 如Pettré等[4]通过对比轨迹间的误差来评估模型准确性, Seyfried等[5]利用速度和密度相似程度对于模型进行评估.但是数据驱动评估方法缺少对于人群运动随机性和环境噪声的综合考虑, 所以评估指标缺乏全面性和鲁棒性.非参估计方法则是通过微观信息和人群低级特征进行人群运动分布的估计.如Wang等[6]通过建模人群路径模式来对比评估模型效果, Guy等[7]通过估计人群运动分布, 来对于误差建模分析仿真模型的效果.但是, 这类方法侧重从宏观角度分析人群高级特征, 过程中忽略了微观现象的处理, 使得在一些仿真情况下评估效果并不理想.

针对上述问题, 本文在相关研究的基础上, 应用熵度量模型评估方法, 提出了一种有效的人群仿真模型的定量评估算法, 在宏观分析人群运动特征的同时, 添加了典型微观问题的判断与处理, 能够全面地对于人群仿真模型进行精确的定量评估.

1 熵度量概述

人群具有复杂系统的特性, 对于某一场景下t时刻的人群状态, 可以用符号st表示, 其包含人群随时间变化的各项信息.st的维度取决于t时刻场景中人群的数量以及人群状态信息, 如位置, 速度等.通常采用抽象函数f表示人群的演变规则, 那么人群状态随时间的演变可以表示为:

这与大多数基于连续空间的人群仿真方法类似:仿真从某一时刻人群状态开始, 根据人群演变规则的建模, 来得到下一时刻人群的状态信息.可以将人群仿真模型用抽象函数表示为.那么, 人群仿真的目标就是期望能够近似f, 即:

基于上述分析, 人群仿真模型的评估问题可以被定义为: 给定真实人群状态st, 如何衡量不同模型预测的人群状态与真实人群状态st+1的接近程度.

模型评估问题主要存在两点挑战: (1) 人群属于复杂系统, 状态变化具有随机性, 某一时刻人群的真实状态st并不唯一.(2) 人群真实状态信息获取困难.常见的人群数据来源于视频数据集, 但是视频数据集不能完整反映人群真实状态.

熵度量方法从信息论角度出发解决了上述问题.与数据驱动方法直接对比人群信息不同, 熵度量方法认为真实人群状态和仿真人群状态分别服从某种分布, 通过估计两者间的误差分布来评估模型.即在式(2)的基础上, 定义单一时间步上的模型误差为et,可得:

假设整个仿真时间段上的et符合误差分布 ε, 即et∈ε.熵度量方法通过衡量误差的分布给出模型的评估结果.

在估计真实人群状态分布时, 熵度量方法将真实人群数据集作为观测数据, 记为z1,z2, … ,zt.假设真实人群状态st和zt的关系由函数h给出, 则有:

其中,qt表示数据中的噪声.熵度量方法采用卡尔曼滤波的相关方法估计每个时间步的真实人群状态分布,将仿真任务分解.然后利用估计的真实人群状态分布来进行熵度量评估.

可以看到, 熵度量通过估计状态分布从宏观角度解决了人群仿真模型的评估问题, 但是, 上述的熵度量方法仍然存在局限性.完全依赖宏观角度的评价, 使得熵度量方法在评估模型时忽略了一些可能的微观失真情况.

微观失真情况的研究来源于多种人群仿真实验的观察.在一些仿真任务中, 当仿真模型或者模型参数的选择不合适时, 仿真过程会出现失真的情况, 如个体抖动和异常静止.图1给出了失真情况的示意.图中是个体穿越的不同大小路口的仿真运动轨迹, ped1, ped2,ped3自上而下, ped4自下而上.图1(a)中路口为4 m时, 个体轨迹正常, 当图1(b)中路口变为2 m时, 个体轨迹出现了失真情况, ped1与ped4出现了抖动, ped2和ped3出现了异常静止.

失真情况会严重影响仿真的效果, 甚至导致仿真过程无法正常进行, 如图1中的异常静止现象使得个体无法到达目的位置.而原始熵度量方法对于失真情况并不敏感, 因为将仿真任务分解的步骤淡化了失真情况对于评估结果的影响.所以, 本文创新性地在人群状态估计的过程中添加了失真情况的判断与处理规则,并对于失真情况进行合理惩罚, 使得熵度量方法在宏观评价模型时能够合理综合微观信息.同时, 本文方法对于失真情况的程度也能给出准确的评价.

图1 仿真失真情况示意

2 评估算法描述

本文提出的评估算法主要分为如下几步: 首先, 根据人群的观测数据估计真实人群状态信息, 将仿真任务分解为单个时间步.在这个过程中, 采用失真判断规则来判断失真情况并记录惩罚.其次, 对于每个时间步的任务进行仿真以估算误差分布的影响.然后, 通过期望极大算法(EM)算法[8]最大程度接近估计的真实人群状态得到误差分布的熵度量大小.最后, 将误差分布的熵度量结果与失真情况的惩罚进行综合, 最终的结果反映了仿真模型重现真实人群状态的能力.

在估计真实人群状态时, 本文采用了集合卡尔曼平滑(EnKS)的方法[9].EnKS大致分为两个步骤, 首先根据仿真模型得到下一个时间步的状态, 然后利用观测数据来修正预测状态.计算时, 在每个时间步上对于给定的仿真模型进行n次仿真, 每次仿真过程中使用高斯模型进行噪声的建模.在先前的相关研究中,Karamouzas等人[10]的工作证明了选用高斯模型建模噪声的合理性.此外, 为了在分步估计状态时保留微观失真情况的信息, 对于待评估模型会先行进行仿真以获得完整的仿真数据作为微观参照数据.算法1给出了伪代码实现.

从算法1可以看出, 算法中添加了微观失真情况的判断.本文方法主要关注两种失真情况: 抖动和异常静止.失真情况借助仿真数据的上下文速度信息以及人群观测数据的状态信息进行判断.仿真人群的抖动主要来源于个体速度方向的反复剧烈变化, 因此对于每个时间步的仿真个体, 算法重点考察其相邻时间步的速度信息.抖动情况的判定规则为: 如果仿真个体在当前时间步与前后时间步的速度夹角均大于90°, 将其判定为发生了抖动, 然后将此步的误差记为:

即用下一时间步模型预测的观测状态信息与此步参照信息的差作为惩罚, 等同于认为此步仿真失效, 对于严重影响仿真效果的失真情况给出足够的惩罚.异常静止的惩罚与上述抖动情况相同, 不同之处在于判断规则.异常静止的判断规则为: 以人群观测数据的速度信息作为参照, 如果仿真轨迹在当前时间步以及前后时间步均出现速度异常为零的情况, 将其判定为发生了异常静止.

算法1.包含失真判断的人群状态估计算法images/BZ_348_1585_1339_1610_1364.png images/BZ_348_1663_1343_1684_1368.pngimages/BZ_348_1909_1331_1929_1368.pngimages/BZ_348_2154_1339_2175_1360.pngimages/BZ_348_1424_1390_1449_1415.png images/BZ_348_1499_1394_1524_1419.pngimages/BZ_348_1741_1386_1757_1415.png输入: 人群观测数据,…,, 人群仿真模型, 误差估计方差, 完整参照数据 ,…, 失真惩罚函数images/BZ_348_1641_1440_1666_1465.png images/BZ_348_1717_1440_1742_1465.png images/BZ_348_1992_1436_2017_1469.png输出: 真实人群状态估images/BZ_348_1599_1440_1600_1443.png计,…,, 失真情况惩罚值images/BZ_348_1432_1509_1461_1538.pngimages/BZ_348_1461_1517_1474_1538.pngt 1.foreach,…, doimages/BZ_348_1465_1563_1490_1588.pngimages/BZ_348_1490_1563_1515_1588.pngimages/BZ_348_1549_1567_1574_1588.png2.foreach… do //状态预测images/BZ_348_1390_1600_1615_1650.pngimages/BZ_348_1632_1600_1720_1650.png3., images/BZ_348_1390_1655_1582_1705.png4.images/BZ_348_1357_1709_1528_1759.png5.6.if 判定失真:images/BZ_348_1390_1821_1553_1855.png7.//记录失真惩罚 images/BZ_348_1390_1863_1753_1913.png8.images/BZ_348_1465_1929_1494_1959.pngimages/BZ_348_1494_1934_1507_1954.pngimages/BZ_348_1557_1925_1574_1954.png9.foreach,… do //状态修正 images/BZ_348_1407_1969_1582_2023.png10.images/BZ_348_1407_2026_1782_2080.png11.images/BZ_348_1515_2094_1540_2119.pngimages/BZ_348_1540_2098_1553_2119.pngimages/BZ_348_1603_2098_1620_2119.png12.foreach,… doimages/BZ_348_1440_2134_1749_2188.png13.

在通过算法1得到真实人群状态分布后, 可以估计噪声方差E，本文采用最大似然估计的方法, 来最大化仿真数据重现真实人群状态的可能性.伪代码如算法2所示.

值得注意的是, 算法1与算法2出现了循环依赖问题: 估计人群真实状态, 需要误差估计方差, 而估计误差方差, 又需要知道真实人群状态.为了解决此问题,本文采用了EM算法, 通过迭代的方式交替使用算法1和算法2, 直至结果收敛.关于EM算法的收敛性证明可以参考McLachlan等人[11]的研究.

算法2.误差分布方差估计算法images/BZ_348_1644_2980_1669_3005.png images/BZ_348_1720_2980_1745_3005.pngimages/BZ_348_1964_2972_1985_3010.png输入: 真实人群状态估计,…, 人群仿真模型, 失真情况惩罚值 images/BZ_348_1575_3031_1595_3052.png输出: 误差估计方差images/BZ_348_1324_3081_1382_3106.png1.images/BZ_348_2237_2976_2262_3010.png

2.foreachimages/BZ_349_351_443_389_477.png,…,images/BZ_349_456_443_497_477.png doimages/BZ_349_389_448_405_473.png3.foreach ,…, doimages/BZ_349_393_498_418_523.png1images/BZ_349_481_502_497_523.png4.foreach,… doimages/BZ_349_426_548_455_577.pngimages/BZ_349_455_552_468_573.pngimages/BZ_349_518_552_543_573.png5.images/BZ_349_351_586_910_636.png6.images/BZ_349_251_644_360_690.png7.images/BZ_349_251_701_351_735.png

最终, 得到收敛的误差方差后, 利用下式测算误差分布大小:

其中,d是个体状态维数.式(6)给出了熵度量的最终结果.

3 实验分析

本文选取SFM (Social Force Model)模型[12]、RVO(Reciprocal Velocity Obstacles)模型[13]、以及ORCA(Optimal Reciprocal Collision Avoidance)模型[14]检验上述熵度量评估方法.这3种模型是目前应用广泛的经典人群仿真模型, 有很多变体和拓展应用.

为了全面地分析评估方法的效果, 实验选取了几种典型的仿真场景.这些场景代表不同人群运动情况,分别为: 1) 交换场景: 反映了两个个体交换彼此的位置, 记为swap-1.同时还有swap-1的镜像场景, 用swap-2表示; 2) 街道场景: 反映了街道上购物的人群运动, 记为street; 3) 狭窄路口场景: 反映了相向通过狭窄路口的人群运动, 用passage表示.

作为对比, 本文选取两种基于数据驱动的评估方法.分别为: 1) L2距离方法[15].通过计算模型预测轨迹与视频数据集轨迹的距离误差来评估仿真模型; 2) 最近邻距离方法[16].通过计算个体与最近邻个体的距离来评估仿真模型.

实验一对比了本文方法与上述方法的评估效果.在swap-1, swap-2, street三种场景下, 分别使用社会力模型, RVO模型以及ORCA模型进行人群仿真实验,然后利用本文方法与上述两种方法对于仿真效果进行评估.实验结果如表1所示, 3种评估方法都是结果越小表示模型的仿真效果越好.在实验一中, swap-1与swap-2为镜像场景.对于个体交换的场景, 原始路径与镜像路径都应该是个体正确的避让选择, 所以模型在swap-1和swap-2上的评估结果应该尽可能接近.

从表1中可以看出, L2距离方法在镜像场景的表现较差, 相对于swap-1场景, swap-2场景下的评估结果明显升高, 同时不同模型的差异性也有所下降.说明L2距离方法局限于固定的状态信息, 不能宏观地评估模型的能力.而最近邻距离方法由于只考查个体与最近个体的距离, 所以在镜像实验下保持了结果的一致性.但是在较为复杂的street场景下的评估效果急剧下降, 这可能与其评估依据较为单一有关.本文提出的熵度量方法在镜像场景中保持了较好的相似性以及区分度.这说明熵度量方法在一定程度上反映了仿真模型捕获真实人群行为模式的能力.同时, 熵度量方法在street场景下也保持了较好的评估效果.评估结果区分度明显而且与另外两种经典方法给出的模型排名一致.

表1 评估方法对比结果

为了反映本文方法与先前熵度量研究的区别, 实验二针对微观失真情况下的模型评估进行了实验.在passage场景下, 选取了两种不同参数的社会力模型进行仿真, 模型分别记为SFM-1和SFM-2.两种模型在仿真过程中都出现了不同程度的失真现象.图2给出了仿真实验的人群轨迹.最后, 分别采用Guy[7]的熵度量方法与本文方法对于仿真结果进行评估, 实验结果见表2.

表2 失真情况评估结果

图2 失真情况评估实验轨迹示意

从图2可以看出, 实验选取的两种不同参数的社会力模型都出现了明显的失真情况, 但是两者的失真程度不同.SFM-1中的个体在出现抖动情况后, 很快脱离了异常并到达了目标点, 而SFM-2中的个体抖动情况严重, 甚至出现了静止的情况, 导致部分个体并没有成功到达目标点.表2中, 与原始熵度量方法的结果相比, 在添加了失真情况的判断与处理后, 本文方法能更为显著的区分两种模型参数组合的优劣.

此外, 本文方法还可以对于模型的参数选择进行指导, 实验三中给出了验证.在street场景下, 参照Xue等[17]的研究选取了ORCA模型的3种参数组合,分别对应不同规模人群仿真任务的推荐模型参数.表3中给出了3种参数组合的具体信息, Min, Max和Default分别对应小规模人群仿真, 大型人群仿真以及中等人群仿真的推荐参数.实验采用上述3组参数进行仿真,并使用本文方法进行评估.实验结果如表4所示.

表3 3种模型参数组合

表4 3种参数组合的评估结果

从表4可以看出, 本文方法的评估结果表明, ORCAMin的参数组合的仿真效果最好, ORCA-Default效果次之, 而ORCA-Max的效果最差.这符合文献[17]中的模型参数分析, 证明了本文方法在模型参数选择时能提供有效的指导.

4 结论与展望

本文针对人群仿真模型难以精确评估的问题, 应用熵度量评估方法, 采用合理的途径、规则及算法,实现了精确的人群仿真模型定量评估, 在宏观对比人群特征的同时引入了微观失真情况的判断与惩罚规则.通过实验验证, 本文提出的算法可以对于人群仿真模型进行合理而准确的评估, 同时也可以为模型参数的选择给出有价值的指导.下一步将考虑更为精确的微观信息参照方法以及完整的模型评估框架开发.