劉景昊,李遠志,王 雷

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

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

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

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

1 速度障礙模型概述

1.1 速度障礙定義

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

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

圖1 速度障礙模型

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

1.2 改進ORCA算法

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

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

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

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

圖2 ORCA示意圖

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

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

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

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

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

2.1 基于最低能耗的行人運動模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗分析

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

3.1 虛擬行人動態(tài)避障實驗

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

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

3.2 性能實驗

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

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

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

圖6 Circle場景不同智能體每幀計算時間

3.3 差異性避障實驗

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

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

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

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

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

4 結(jié)論與展望

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