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

劉 楊, 王 雷, 盛 捷

(中國科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院, 合肥 230027)

近年來, 隨著虛擬人群仿真技術(shù)在公共安全、城市規(guī)劃、智能交通等領(lǐng)域的廣泛應(yīng)用, 人群仿真模型的評估方法成為研究人員關(guān)注的問題.人群是一個復(fù)雜系統(tǒng)[1], 個體行為具有隨機性, 同時個體之間又會互相影響.眾所周知, 描述復(fù)雜系統(tǒng)時, 不能只依賴確定的微觀信息, 而應(yīng)該同時考慮系統(tǒng)宏觀特征, 所以, 評估人群仿真模型的主要挑戰(zhàn)在于復(fù)雜系統(tǒng)間相似性的全面度量.

當前模型評估算法研究主要分為定性和定量兩類.定性評估方法主要包括視覺比較[2]和感知實驗[3]等,但是這類方法依賴主觀因素, 隨著模型復(fù)雜度提升, 難以得到有效的評估結(jié)果.定量方法分為兩類: 主要有數(shù)據(jù)驅(qū)動評估方法和非參估計評估方法.其中, 數(shù)據(jù)驅(qū)動的方法基于人群微觀信息和低級特征的比較來評估模型, 如Pettré等[4]通過對比軌跡間的誤差來評估模型準確性, Seyfried等[5]利用速度和密度相似程度對于模型進行評估.但是數(shù)據(jù)驅(qū)動評估方法缺少對于人群運動隨機性和環(huán)境噪聲的綜合考慮, 所以評估指標缺乏全面性和魯棒性.非參估計方法則是通過微觀信息和人群低級特征進行人群運動分布的估計.如Wang等[6]通過建模人群路徑模式來對比評估模型效果, Guy等[7]通過估計人群運動分布, 來對于誤差建模分析仿真模型的效果.但是, 這類方法側(cè)重從宏觀角度分析人群高級特征, 過程中忽略了微觀現(xiàn)象的處理, 使得在一些仿真情況下評估效果并不理想.

針對上述問題, 本文在相關(guān)研究的基礎(chǔ)上, 應(yīng)用熵度量模型評估方法, 提出了一種有效的人群仿真模型的定量評估算法, 在宏觀分析人群運動特征的同時, 添加了典型微觀問題的判斷與處理, 能夠全面地對于人群仿真模型進行精確的定量評估.

1 熵度量概述

人群具有復(fù)雜系統(tǒng)的特性, 對于某一場景下t時刻的人群狀態(tài), 可以用符號st表示, 其包含人群隨時間變化的各項信息.st的維度取決于t時刻場景中人群的數(shù)量以及人群狀態(tài)信息, 如位置, 速度等.通常采用抽象函數(shù)f表示人群的演變規(guī)則, 那么人群狀態(tài)隨時間的演變可以表示為:

這與大多數(shù)基于連續(xù)空間的人群仿真方法類似:仿真從某一時刻人群狀態(tài)開始, 根據(jù)人群演變規(guī)則的建模, 來得到下一時刻人群的狀態(tài)信息.可以將人群仿真模型用抽象函數(shù)表示為.那么, 人群仿真的目標就是期望能夠近似f, 即:

基于上述分析, 人群仿真模型的評估問題可以被定義為: 給定真實人群狀態(tài)st, 如何衡量不同模型預(yù)測的人群狀態(tài)與真實人群狀態(tài)st+1的接近程度.

模型評估問題主要存在兩點挑戰(zhàn): (1) 人群屬于復(fù)雜系統(tǒng), 狀態(tài)變化具有隨機性, 某一時刻人群的真實狀態(tài)st并不唯一.(2) 人群真實狀態(tài)信息獲取困難.常見的人群數(shù)據(jù)來源于視頻數(shù)據(jù)集, 但是視頻數(shù)據(jù)集不能完整反映人群真實狀態(tài).

熵度量方法從信息論角度出發(fā)解決了上述問題.與數(shù)據(jù)驅(qū)動方法直接對比人群信息不同, 熵度量方法認為真實人群狀態(tài)和仿真人群狀態(tài)分別服從某種分布, 通過估計兩者間的誤差分布來評估模型.即在式(2)的基礎(chǔ)上, 定義單一時間步上的模型誤差為et,可得:

假設(shè)整個仿真時間段上的et符合誤差分布 ε, 即et∈ε.熵度量方法通過衡量誤差的分布給出模型的評估結(jié)果.

在估計真實人群狀態(tài)分布時, 熵度量方法將真實人群數(shù)據(jù)集作為觀測數(shù)據(jù), 記為z1,z2, … ,zt.假設(shè)真實人群狀態(tài)st和zt的關(guān)系由函數(shù)h給出, 則有:

其中,qt表示數(shù)據(jù)中的噪聲.熵度量方法采用卡爾曼濾波的相關(guān)方法估計每個時間步的真實人群狀態(tài)分布,將仿真任務(wù)分解.然后利用估計的真實人群狀態(tài)分布來進行熵度量評估.

可以看到, 熵度量通過估計狀態(tài)分布從宏觀角度解決了人群仿真模型的評估問題, 但是, 上述的熵度量方法仍然存在局限性.完全依賴宏觀角度的評價, 使得熵度量方法在評估模型時忽略了一些可能的微觀失真情況.

微觀失真情況的研究來源于多種人群仿真實驗的觀察.在一些仿真任務(wù)中, 當仿真模型或者模型參數(shù)的選擇不合適時, 仿真過程會出現(xiàn)失真的情況, 如個體抖動和異常靜止.圖1給出了失真情況的示意.圖中是個體穿越的不同大小路口的仿真運動軌跡, ped1, ped2,ped3自上而下, ped4自下而上.圖1(a)中路口為4 m時, 個體軌跡正常, 當圖1(b)中路口變?yōu)? m時, 個體軌跡出現(xiàn)了失真情況, ped1與ped4出現(xiàn)了抖動, ped2和ped3出現(xiàn)了異常靜止.

失真情況會嚴重影響仿真的效果, 甚至導(dǎo)致仿真過程無法正常進行, 如圖1中的異常靜止現(xiàn)象使得個體無法到達目的位置.而原始熵度量方法對于失真情況并不敏感, 因為將仿真任務(wù)分解的步驟淡化了失真情況對于評估結(jié)果的影響.所以, 本文創(chuàng)新性地在人群狀態(tài)估計的過程中添加了失真情況的判斷與處理規(guī)則,并對于失真情況進行合理懲罰, 使得熵度量方法在宏觀評價模型時能夠合理綜合微觀信息.同時, 本文方法對于失真情況的程度也能給出準確的評價.

圖1 仿真失真情況示意

2 評估算法描述

本文提出的評估算法主要分為如下幾步: 首先, 根據(jù)人群的觀測數(shù)據(jù)估計真實人群狀態(tài)信息, 將仿真任務(wù)分解為單個時間步.在這個過程中, 采用失真判斷規(guī)則來判斷失真情況并記錄懲罰.其次, 對于每個時間步的任務(wù)進行仿真以估算誤差分布的影響.然后, 通過期望極大算法(EM)算法[8]最大程度接近估計的真實人群狀態(tài)得到誤差分布的熵度量大小.最后, 將誤差分布的熵度量結(jié)果與失真情況的懲罰進行綜合, 最終的結(jié)果反映了仿真模型重現(xiàn)真實人群狀態(tài)的能力.

在估計真實人群狀態(tài)時, 本文采用了集合卡爾曼平滑(EnKS)的方法[9].EnKS大致分為兩個步驟, 首先根據(jù)仿真模型得到下一個時間步的狀態(tài), 然后利用觀測數(shù)據(jù)來修正預(yù)測狀態(tài).計算時, 在每個時間步上對于給定的仿真模型進行n次仿真, 每次仿真過程中使用高斯模型進行噪聲的建模.在先前的相關(guān)研究中,Karamouzas等人[10]的工作證明了選用高斯模型建模噪聲的合理性.此外, 為了在分步估計狀態(tài)時保留微觀失真情況的信息, 對于待評估模型會先行進行仿真以獲得完整的仿真數(shù)據(jù)作為微觀參照數(shù)據(jù).算法1給出了偽代碼實現(xiàn).

從算法1可以看出, 算法中添加了微觀失真情況的判斷.本文方法主要關(guān)注兩種失真情況: 抖動和異常靜止.失真情況借助仿真數(shù)據(jù)的上下文速度信息以及人群觀測數(shù)據(jù)的狀態(tài)信息進行判斷.仿真人群的抖動主要來源于個體速度方向的反復(fù)劇烈變化, 因此對于每個時間步的仿真?zhèn)€體, 算法重點考察其相鄰時間步的速度信息.抖動情況的判定規(guī)則為: 如果仿真?zhèn)€體在當前時間步與前后時間步的速度夾角均大于90°, 將其判定為發(fā)生了抖動, 然后將此步的誤差記為:

即用下一時間步模型預(yù)測的觀測狀態(tài)信息與此步參照信息的差作為懲罰, 等同于認為此步仿真失效, 對于嚴重影響仿真效果的失真情況給出足夠的懲罰.異常靜止的懲罰與上述抖動情況相同, 不同之處在于判斷規(guī)則.異常靜止的判斷規(guī)則為: 以人群觀測數(shù)據(jù)的速度信息作為參照, 如果仿真軌跡在當前時間步以及前后時間步均出現(xiàn)速度異常為零的情況, 將其判定為發(fā)生了異常靜止.

算法1.包含失真判斷的人群狀態(tài)估計算法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輸入: 人群觀測數(shù)據(jù),…,, 人群仿真模型, 誤差估計方差, 完整參照數(shù)據(jù) ,…, 失真懲罰函數(shù)images/BZ_348_1641_1440_1666_1465.png images/BZ_348_1717_1440_1742_1465.png images/BZ_348_1992_1436_2017_1469.png輸出: 真實人群狀態(tài)估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 //狀態(tài)預(yù)測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 //狀態(tài)修正 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得到真實人群狀態(tài)分布后, 可以估計噪聲方差E，本文采用最大似然估計的方法, 來最大化仿真數(shù)據(jù)重現(xiàn)真實人群狀態(tài)的可能性.偽代碼如算法2所示.

值得注意的是, 算法1與算法2出現(xiàn)了循環(huán)依賴問題: 估計人群真實狀態(tài), 需要誤差估計方差, 而估計誤差方差, 又需要知道真實人群狀態(tài).為了解決此問題,本文采用了EM算法, 通過迭代的方式交替使用算法1和算法2, 直至結(jié)果收斂.關(guān)于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輸入: 真實人群狀態(tài)估計,…, 人群仿真模型, 失真情況懲罰值 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是個體狀態(tài)維數(shù).式(6)給出了熵度量的最終結(jié)果.

3 實驗分析

本文選取SFM (Social Force Model)模型[12]、RVO(Reciprocal Velocity Obstacles)模型[13]、以及ORCA(Optimal Reciprocal Collision Avoidance)模型[14]檢驗上述熵度量評估方法.這3種模型是目前應(yīng)用廣泛的經(jīng)典人群仿真模型, 有很多變體和拓展應(yīng)用.

為了全面地分析評估方法的效果, 實驗選取了幾種典型的仿真場景.這些場景代表不同人群運動情況,分別為: 1) 交換場景: 反映了兩個個體交換彼此的位置, 記為swap-1.同時還有swap-1的鏡像場景, 用swap-2表示; 2) 街道場景: 反映了街道上購物的人群運動, 記為street; 3) 狹窄路口場景: 反映了相向通過狹窄路口的人群運動, 用passage表示.

作為對比, 本文選取兩種基于數(shù)據(jù)驅(qū)動的評估方法.分別為: 1) L2距離方法[15].通過計算模型預(yù)測軌跡與視頻數(shù)據(jù)集軌跡的距離誤差來評估仿真模型; 2) 最近鄰距離方法[16].通過計算個體與最近鄰個體的距離來評估仿真模型.

實驗一對比了本文方法與上述方法的評估效果.在swap-1, swap-2, street三種場景下, 分別使用社會力模型, RVO模型以及ORCA模型進行人群仿真實驗,然后利用本文方法與上述兩種方法對于仿真效果進行評估.實驗結(jié)果如表1所示, 3種評估方法都是結(jié)果越小表示模型的仿真效果越好.在實驗一中, swap-1與swap-2為鏡像場景.對于個體交換的場景, 原始路徑與鏡像路徑都應(yīng)該是個體正確的避讓選擇, 所以模型在swap-1和swap-2上的評估結(jié)果應(yīng)該盡可能接近.

從表1中可以看出, L2距離方法在鏡像場景的表現(xiàn)較差, 相對于swap-1場景, swap-2場景下的評估結(jié)果明顯升高, 同時不同模型的差異性也有所下降.說明L2距離方法局限于固定的狀態(tài)信息, 不能宏觀地評估模型的能力.而最近鄰距離方法由于只考查個體與最近個體的距離, 所以在鏡像實驗下保持了結(jié)果的一致性.但是在較為復(fù)雜的street場景下的評估效果急劇下降, 這可能與其評估依據(jù)較為單一有關(guān).本文提出的熵度量方法在鏡像場景中保持了較好的相似性以及區(qū)分度.這說明熵度量方法在一定程度上反映了仿真模型捕獲真實人群行為模式的能力.同時, 熵度量方法在street場景下也保持了較好的評估效果.評估結(jié)果區(qū)分度明顯而且與另外兩種經(jīng)典方法給出的模型排名一致.

表1 評估方法對比結(jié)果

為了反映本文方法與先前熵度量研究的區(qū)別, 實驗二針對微觀失真情況下的模型評估進行了實驗.在passage場景下, 選取了兩種不同參數(shù)的社會力模型進行仿真, 模型分別記為SFM-1和SFM-2.兩種模型在仿真過程中都出現(xiàn)了不同程度的失真現(xiàn)象.圖2給出了仿真實驗的人群軌跡.最后, 分別采用Guy[7]的熵度量方法與本文方法對于仿真結(jié)果進行評估, 實驗結(jié)果見表2.

表2 失真情況評估結(jié)果

圖2 失真情況評估實驗軌跡示意

從圖2可以看出, 實驗選取的兩種不同參數(shù)的社會力模型都出現(xiàn)了明顯的失真情況, 但是兩者的失真程度不同.SFM-1中的個體在出現(xiàn)抖動情況后, 很快脫離了異常并到達了目標點, 而SFM-2中的個體抖動情況嚴重, 甚至出現(xiàn)了靜止的情況, 導(dǎo)致部分個體并沒有成功到達目標點.表2中, 與原始熵度量方法的結(jié)果相比, 在添加了失真情況的判斷與處理后, 本文方法能更為顯著的區(qū)分兩種模型參數(shù)組合的優(yōu)劣.

此外, 本文方法還可以對于模型的參數(shù)選擇進行指導(dǎo), 實驗三中給出了驗證.在street場景下, 參照Xue等[17]的研究選取了ORCA模型的3種參數(shù)組合,分別對應(yīng)不同規(guī)模人群仿真任務(wù)的推薦模型參數(shù).表3中給出了3種參數(shù)組合的具體信息, Min, Max和Default分別對應(yīng)小規(guī)模人群仿真, 大型人群仿真以及中等人群仿真的推薦參數(shù).實驗采用上述3組參數(shù)進行仿真,并使用本文方法進行評估.實驗結(jié)果如表4所示.

表3 3種模型參數(shù)組合

表4 3種參數(shù)組合的評估結(jié)果

從表4可以看出, 本文方法的評估結(jié)果表明, ORCAMin的參數(shù)組合的仿真效果最好, ORCA-Default效果次之, 而ORCA-Max的效果最差.這符合文獻[17]中的模型參數(shù)分析, 證明了本文方法在模型參數(shù)選擇時能提供有效的指導(dǎo).

4 結(jié)論與展望

本文針對人群仿真模型難以精確評估的問題, 應(yīng)用熵度量評估方法, 采用合理的途徑、規(guī)則及算法,實現(xiàn)了精確的人群仿真模型定量評估, 在宏觀對比人群特征的同時引入了微觀失真情況的判斷與懲罰規(guī)則.通過實驗驗證, 本文提出的算法可以對于人群仿真模型進行合理而準確的評估, 同時也可以為模型參數(shù)的選擇給出有價值的指導(dǎo).下一步將考慮更為精確的微觀信息參照方法以及完整的模型評估框架開發(fā).