劉 楊, 王 雷, 盛 捷

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

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

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

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

1 熵度量概述

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

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

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

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

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

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

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

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

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

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

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

圖1 仿真失真情況示意

2 評估算法描述

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

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

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

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

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

值得注意的是, 算法1與算法2出現(xiàn)了循環(huán)依賴問題: 估計(jì)人群真實(shí)狀態(tài), 需要誤差估計(jì)方差, 而估計(jì)誤差方差, 又需要知道真實(shí)人群狀態(tài).為了解決此問題,本文采用了EM算法, 通過迭代的方式交替使用算法1和算法2, 直至結(jié)果收斂.關(guān)于EM算法的收斂性證明可以參考McLachlan等人[11]的研究.

算法2.誤差分布方差估計(jì)算法images/BZ_348_1644_2980_1669_3005.png images/BZ_348_1720_2980_1745_3005.pngimages/BZ_348_1964_2972_1985_3010.png輸入: 真實(shí)人群狀態(tài)估計(jì),…, 人群仿真模型, 失真情況懲罰值 images/BZ_348_1575_3031_1595_3052.png輸出: 誤差估計(jì)方差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是個(gè)體狀態(tài)維數(shù).式(6)給出了熵度量的最終結(jié)果.

3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

圖2 失真情況評估實(shí)驗(yàn)軌跡示意

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

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

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

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

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

4 結(jié)論與展望

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