虛擬行人仿真最低能耗動(dòng)態(tài)避障①

劉景昊,李遠(yuǎn)志,王 雷

(中國科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院 自動(dòng)化系,合肥 230027)

碰撞避免是計(jì)算機(jī)虛擬行人仿真的一個(gè)基本問題,通常我們可以將其定義為:仿真行人在虛擬環(huán)境中朝目標(biāo)點(diǎn)的運(yùn)動(dòng)過程中,需在每個(gè)仿真周期內(nèi)感知其他靜態(tài)及動(dòng)態(tài)實(shí)體的存在,若有碰撞可能則采取一定的措施(如調(diào)整速度等)避免碰撞[1].

碰撞避免問題在機(jī)器人,虛擬智能體仿真,實(shí)時(shí)交通模擬等領(lǐng)域均有廣泛的研究.現(xiàn)有的方法一般分成集中式與分布式兩種.前者將環(huán)境中所有運(yùn)動(dòng)實(shí)體當(dāng)成一個(gè)完整的系統(tǒng),通過理論分析的方法計(jì)算所有的碰撞可能,并協(xié)調(diào)統(tǒng)一地完成避碰操作,但是由于原理的限制,這種方法僅限應(yīng)用于單智能體或者少量行人仿真中[2].分布式的方法則將每一個(gè)運(yùn)動(dòng)實(shí)體建模為獨(dú)立感知周圍環(huán)境以此指導(dǎo)決策,最終采取相應(yīng)動(dòng)作的智能體.很顯然,分布式的方法可以方便且直觀地模擬虛擬人群的運(yùn)動(dòng)過程.許多碰撞避免算法都是基于速度障礙模型(velocity obstacles),通過計(jì)算相對速度的閩科夫斯基矢量和,確定行人的可行速度域,從而選擇合適新速度避免碰撞.這一類的方法在各領(lǐng)域的研究均有廣泛的應(yīng)用[3-5].Berg等人提出的優(yōu)化相互速度障礙模型(ORCA)算法[6]即為經(jīng)典的基于速度障礙模型的n-body碰撞避免算法,該算法將行人動(dòng)態(tài)避碰問題轉(zhuǎn)化為線性規(guī)劃進(jìn)行求解.因其高效的性能和逼真的仿真結(jié)果而被廣泛地應(yīng)用于動(dòng)態(tài)避碰中[7,8].

然而現(xiàn)實(shí)中行人的運(yùn)動(dòng)往往存在著天然的差異性,不同行人因年齡,性格,速度等特性差異,導(dǎo)致實(shí)際的避碰策略存在著個(gè)性化特征.為獲得更為逼真的仿真效果,提升人群仿真的真實(shí)性和科學(xué)性,本文在ORCA算法的基礎(chǔ)上加以拓展,并引入行人最低能耗的概念,設(shè)計(jì)并實(shí)現(xiàn)了行人最低能耗的動(dòng)態(tài)避障算法.

1 速度障礙模型概述

1.1 速度障礙定義

本文所討論的行人動(dòng)態(tài)避障問題定義如下:仿真平面存在n個(gè)仿真行人,每一個(gè)行人均從自身的出發(fā)點(diǎn)按照一定的物理限制(最大速度,最大加速度,不能碰撞等)在一個(gè)平面內(nèi)朝目標(biāo)點(diǎn)移動(dòng).為簡化分析起見,我們將行人簡化為具有一定半徑的圓模型.我們使用D(p,r)表示圓心為p半徑為r的圓模型.

對于位置分別在pA和pB處的兩個(gè)行人速度分別為vA和vB,為衡量在未來兩行人是否有可能發(fā)生碰撞,對于行人A,我們可以在速度平面將其考慮成質(zhì)點(diǎn),圖1中的陰影扇形區(qū)域即表示行人B以速度vB對于行人A的相對速度障礙VOAB(vB),而只要兩行人的相對速度落在這一扇形區(qū)域內(nèi),則未來一定會發(fā)生碰撞.公式定義如下:

圖1 速度障礙模型

簡單地,我們可以對上述情況進(jìn)行拓展,即考慮行人A周圍若干個(gè)行人分別求出對應(yīng)的速度障礙,此時(shí)只需調(diào)整速度使其新的相對速度落于所有其他行人相對速度障礙區(qū)域外即可.

1.2 改進(jìn)ORCA算法

原始的速度障礙法在計(jì)算自身的速度障礙時(shí)均假定其他智能體按照之前的速度前進(jìn),彼此之間并無合作策略;且不考慮時(shí)間窗口,只要有碰撞可能均需調(diào)整速度方向,因此會出現(xiàn)軌跡振蕩、抖動(dòng)等不真實(shí)現(xiàn)象[9].為解決這一問題,RVO及ORCA等算法相繼被提出,作為行人仿真的底層避障算法被廣泛使用.

首先智能體在計(jì)算速度障礙時(shí)應(yīng)當(dāng)考慮未來最近一段時(shí)間窗口 τ內(nèi),類似地如圖2(b)所示的陰影區(qū)域的類扇形即為考慮時(shí)間窗口后的速度障礙區(qū)域,數(shù)學(xué)表示為:

ORCA算法假設(shè)所有的虛擬行人按照相同的避障策略調(diào)整速度進(jìn)行避障,其核心在于將速度障礙約束調(diào)整為線性直線約束.對照圖2(c),具體步驟可以描述為:

4)與其他周圍所有智能體求得由直線約束所包圍的可行速度域,從中求解與優(yōu)化目標(biāo)最接近的最優(yōu)速度.

圖2 ORCA示意圖

在每一步仿真迭代中,智能體獲取自身及其視野范圍內(nèi)其他智能體的位置和速度,基于這些信息可以計(jì)算出該智能體A與其他所有智能體的優(yōu)化相互半平面約束速度集合;此外,行人還受到自身最大速度的限制.因此在ORCA模型下受到的速度選擇約束可以表示為:

為了體現(xiàn)行人避障策略采取中存在的差異性,我們將式(5)改寫成:

類似地,靜態(tài)障礙物可以視為速度為0的障礙物,因此同樣的約束構(gòu)造方法也適用于靜態(tài)障礙物.

2 虛擬行人動(dòng)態(tài)避障算法

我們將仿真行人建模為在一個(gè)仿真周期 Δt內(nèi)不停感知周圍環(huán)境并采取相應(yīng)動(dòng)作的自治智能體.基于改進(jìn)ORCA算法,結(jié)合行人運(yùn)動(dòng)最低能耗函數(shù),為仿真行人設(shè)計(jì)了動(dòng)態(tài)避障算法.

2.1 基于最低能耗的行人運(yùn)動(dòng)模型

最小能耗這一概念最早由Zipf[10]提出用于描述生物的運(yùn)動(dòng),可簡單概括為:“自然環(huán)境中的生物體在達(dá)到自己目標(biāo)的運(yùn)動(dòng)中傾向于采用估計(jì)能量消耗最低的方式”.Guy[11]等人將這一原則引入仿真行人的建模提出了經(jīng)典的Pledestrian模型.在他的研究中指出,在沒有外部因素干擾的條件下,行人的運(yùn)動(dòng)按照能耗最低方式進(jìn)行.考慮這一點(diǎn),Pledestrian所采用的行人能耗方程如下:

式中,P為單位質(zhì)量的瞬時(shí)能耗,m為行人的質(zhì)量,τ為時(shí)間窗口,Eqd為行人按照當(dāng)前速度運(yùn)動(dòng)一段時(shí)間 τ后到達(dá)到位置q,從q再運(yùn)動(dòng)到目標(biāo)d所耗費(fèi)的能量.對于運(yùn)動(dòng)中的仿真行人而言,P的計(jì)算方式表示如下:

式中,v為行人瞬時(shí)速度,es表示行人靜止能耗參數(shù),ed為運(yùn)動(dòng)能耗參數(shù),對于具體的行人是一個(gè)常數(shù).Whittle等人[12]通過對行人在不同運(yùn)動(dòng)速度下的單位時(shí)間耗氧量研究測算出普通行人的es和ed的平均值分別為2.23 J·(kgs)?1和1.26 Js·(kg?1m?2).

在對行人的觀察研究中,人們發(fā)現(xiàn)行人還有保持自身運(yùn)動(dòng)方向的“慣性趨勢”[13],因此在變換運(yùn)動(dòng)方向時(shí)理論上行人應(yīng)消耗額外的能量,而這在原始的最小能耗方程中并無考慮.且行人在進(jìn)行動(dòng)態(tài)避障時(shí),主要應(yīng)考慮的為對速度方向的改變量;因此我們可以將行人的瞬時(shí)能耗方程修改為:

式中,ω為行人在變換速度方向時(shí)的瞬時(shí)角速度大小,同理er為轉(zhuǎn)動(dòng)能耗參數(shù),前人研究表明[13]這一參數(shù)的取值約為0.5 ～ 2.0 Js·kg?1rad?2.

式(11)使得我們可以對虛擬行人變換方向的轉(zhuǎn)動(dòng)能量加以量化.er的數(shù)值越大,表示行人在角速度較大時(shí)所消耗的能量也越多.本文的瞬時(shí)能耗方程修改可以對虛擬行人動(dòng)態(tài)避障時(shí)在速度方向的變化量上給出理論依據(jù),因此更適用于大規(guī)模人群仿真行人速度方向變更比較頻繁時(shí)的場景.

行人的動(dòng)態(tài)避障是一個(gè)局部動(dòng)態(tài)過程,往往并沒有一個(gè)確切的目標(biāo)點(diǎn),因此不能直接采用式(9)來計(jì)算行人的局部避障過程中最低能量消耗.另外,我們注意到行人在完成動(dòng)態(tài)避障后會回歸頂層尋路模塊得到的期望速度,一般為指向最終目標(biāo)點(diǎn)的方向.因此我們可以參照文獻(xiàn)[13]的處理方法,考慮如圖3所示情況,即行人在時(shí)間t0時(shí)刻位于pA從速度vt?1=vpref轉(zhuǎn)為vt,并經(jīng)過一段時(shí)間τ 后到達(dá)qA,然后行人經(jīng)過一段以o為圓心,轉(zhuǎn)彎半徑為 ρ =vmax/ωmin的勻速圓周運(yùn)動(dòng)盡快將速度轉(zhuǎn)換為期望速度vpref,最終到達(dá)q′A,完成整個(gè)局部避障過程.

圖3 行人避障速度調(diào)整

代入式(7)和式(9),并考慮到圖3所示的幾何關(guān)系可得:

因此行人動(dòng)態(tài)避障選擇新速度時(shí),可以將可行的速度域代入式(13)中得到當(dāng)前條件下的最優(yōu)避障速度,并據(jù)此更新位置.

2.2 最低能耗局部動(dòng)態(tài)避障算法

如前文所述,我們需要選擇在可選速度范圍內(nèi)使得完成局部避障最低能耗的速度,即

目標(biāo)行人的ORCA半平面交集組成了速度可行域,從中選取最優(yōu)的點(diǎn)問題是計(jì)算幾何中典型的二維線性規(guī)劃問題,使用文獻(xiàn)[14]中的隨機(jī)算法已被證明可以在O(n)的期望時(shí)間內(nèi)對這一問題高效求解,n為約束個(gè)數(shù).因此我們對每一段線性約束以隨機(jī)的順序逐個(gè)求解,在每一段可行線性約束邊界進(jìn)行m次采樣分別計(jì)算額外的能耗值 ΔE,最終選擇能耗最優(yōu)的新速度,仿真行人并依此到達(dá)新位置,即:

綜上,我們可以將我們的仿真行人動(dòng)態(tài)避障算法總結(jié)如下:

算法1.最低能耗局部動(dòng)態(tài)避障算法輸入:虛擬行人位置pi,速度vi,采樣數(shù)量m輸出:更新速度vinew.(1)獲取鄰近障礙物線性約束:通過kd-tree等數(shù)據(jù)結(jié)構(gòu)獲取虛擬行人周圍的虛擬行人狀態(tài)信息,按照式(6)和式(7)計(jì)算障礙物約束集L.(2)依次對L中每一條直線進(jìn)行線性分析得到的可選速度上下限,并在所選區(qū)域進(jìn)行m次采樣,分別計(jì)算式(13)得到最優(yōu)避碰速度.(3)將上一步得到的最優(yōu)避碰速度作為虛擬行人的新速度,并更新位置(4)重復(fù)(1)-(3)步,直到虛擬行人到達(dá)其目的地.

通過對上述算法的分析可知,我們的算法時(shí)間復(fù)雜度為 O (n·m),其中n為智能體周圍障礙物的個(gè)數(shù),m為計(jì)算能耗最優(yōu)的離散采樣點(diǎn)數(shù)量.在算法1第(1)步獲取動(dòng)態(tài)障礙物時(shí),我們可以只考慮最近N個(gè)障礙物的影響.現(xiàn)實(shí)世界中超高密度人群大約為5～7人/m2[15],因此我們將N設(shè)定為10,m設(shè)定為100,計(jì)算量對于當(dāng)前計(jì)算機(jī)硬件計(jì)算能力而言足以接受,第3節(jié)中通過實(shí)驗(yàn)分析表明本文提出的避障算法可以滿足虛擬大規(guī)模人群仿真的實(shí)時(shí)性要求(～30 fps).

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

實(shí)驗(yàn)首先驗(yàn)證虛擬行人的動(dòng)態(tài)避障過程,然后衡量了我們方法在性能上的表現(xiàn),最后驗(yàn)證本文方法可以通過簡單的參數(shù)設(shè)置得到差異化的行人的避障效果.

3.1 虛擬行人動(dòng)態(tài)避障實(shí)驗(yàn)

我們在小規(guī)模的場景下驗(yàn)證了行人動(dòng)態(tài)避障的效果.場景一如圖4(a)所示的,為行人分別從左右迎面前進(jìn);場景二如圖4(b)所示,兩列行人分別朝斜對角的目標(biāo)點(diǎn)前進(jìn);可以看出我們的算法可以讓行人正確完成避障并到達(dá)目的地.

圖4 行人動(dòng)態(tài)避障過程

3.2 性能實(shí)驗(yàn)

在大規(guī)模的行人仿真中,在比較擁擠的情況下依然需要確保行人之間不存在碰撞.為了衡量我們的方法在大規(guī)模人群下的表現(xiàn),我們設(shè)計(jì)了Circle場景,即行人建模為半徑0.5 m的圓,行人均勻分布在半徑為500 m的大圓上,每個(gè)行人目標(biāo)點(diǎn)設(shè)置為經(jīng)過圓心的圓對面一點(diǎn).仿真行人開始會往圓心匯聚,在圓心附近達(dá)到避碰高峰,行人調(diào)整自身速度避免碰撞,之后平滑地往目標(biāo)點(diǎn)前進(jìn).圖5比較了我們的方法與原始ORCA算法在相同場景,不同智能體的數(shù)目下人群仿真時(shí)間.可以看出由于我們采用最低能耗的方式可以顯著降低總仿真時(shí)間,也即可以獲得更為流暢的仿真結(jié)果,提升仿真效率.我們的方法使用C#編寫,運(yùn)行在普通PC (CPU Intel i7-7700HQ 2.8 GHz雙核,RAM 8 GB)上,圖6給出了我們的方法和原始的ORCA算法在不同智能體個(gè)數(shù)時(shí)每幀計(jì)算時(shí)間.可以看出我們的方法因?yàn)橛?jì)算量的增加,每幀運(yùn)算時(shí)間大概是原始ORCA算法的兩倍左右.

圖5 Circle場景不同智能體個(gè)數(shù)程序仿真時(shí)間

圖6中橫虛線為30 fps的每幀計(jì)算時(shí)間要求,可以看出我們的算法在智能體數(shù)量為幾千到一萬時(shí)依然可以達(dá)到～30 fps的要求.

圖6 Circle場景不同智能體每幀計(jì)算時(shí)間

3.3 差異性避障實(shí)驗(yàn)

引入行人最優(yōu)能耗的方法來進(jìn)行動(dòng)態(tài)避障的好處除了可以加快仿真進(jìn)程,同時(shí)也可以通過參數(shù)設(shè)置的不同來區(qū)分不同類別的行人.

為了對這一點(diǎn)進(jìn)行簡要的驗(yàn)證,我們考慮一個(gè)簡單的嫌疑人動(dòng)態(tài)抓捕的場景,即安保人員沿右方追捕往右逃竄的嫌疑人,同時(shí)普通行人正迎面走來.在這樣一個(gè)場景中,按照常識,安保人員與嫌疑人速度較快,且處于動(dòng)態(tài)抓捕過程中將承擔(dān)更少的避障責(zé)任,而普通行人則將的承擔(dān)更多的避障責(zé)任.我們按照表1設(shè)定不同人員的能耗參數(shù),最終仿真得到行人軌跡圖如圖7所示.

表1 抓捕場景中行人參數(shù)

圖7 抓捕場景下不同行人的避碰軌跡

從圖7中可以看出,行人能耗參數(shù)與速度的不同將影響行人的避障行為,而這些特點(diǎn)在大規(guī)模的人群仿真中可以加以利用,從而獲得更為真實(shí)科學(xué)的仿真效果.

4 結(jié)論與展望

本文拓展了經(jīng)典的分布式虛擬行人避障算法ORCA,并引入行人最低能耗模型指導(dǎo)虛擬行人最優(yōu)速度的選取.通過實(shí)驗(yàn)驗(yàn)證,本文的方法可以縮短仿真進(jìn)程,在性能上也可以滿足實(shí)時(shí)仿真的要求,并且可以為差異化的行人仿真提供參考.下一步計(jì)劃采用現(xiàn)有方法精細(xì)化研究不同類別行人動(dòng)態(tài)避障策略與效果.