劉俊君,杜艮魁

(北京工業(yè)大學(xué) 信息學(xué)部 計(jì)算機(jī)學(xué)院,北京 100124)

群體動(dòng)畫是群體行為動(dòng)畫的簡稱[1],是指在特定環(huán)境下對(duì)群體行為的模擬.群體動(dòng)畫在近些年來得到了廣泛的研究和應(yīng)用,如機(jī)器人學(xué)[2]、社會(huì)學(xué)[3]、交通工程[4]、電影[1]、游戲[5]等.目前實(shí)現(xiàn)群體動(dòng)畫的方法主要有基于力的方法[6]、基于速度的模型[7]、基于場(chǎng)的模型[8]、基于梯度的方法[9]、基于群智能的方法[10]、基于深度強(qiáng)化學(xué)習(xí)的方法[11]等.這些方法在對(duì)智能體的每一步動(dòng)作進(jìn)行規(guī)劃時(shí),均需大量的計(jì)算對(duì)智能體進(jìn)行碰撞檢測(cè)或獲取當(dāng)前智能體的環(huán)境狀態(tài)以引導(dǎo)智能體向目標(biāo)運(yùn)動(dòng),當(dāng)智能體的數(shù)量很大時(shí),大量的計(jì)算會(huì)導(dǎo)致效率較低.針對(duì)這一問題,本文提出了一種基于馬爾可夫決策過程(Markov Decision Processes,MDPs)的群體動(dòng)畫運(yùn)動(dòng)軌跡生成算法,該算法在規(guī)劃智能體的每一步動(dòng)作時(shí),無需進(jìn)行碰撞檢測(cè)等大量的計(jì)算即可實(shí)現(xiàn)智能體無碰撞地向目標(biāo)運(yùn)動(dòng),因此智能體的軌跡生成效率較高.同時(shí)為了快速求解馬爾可夫決策過程的狀態(tài)-值,本文提出了一種改進(jìn)的值迭代算法,該算法利用貪婪的思想計(jì)算出每個(gè)狀態(tài)的初始狀態(tài)-值,再將該初始狀態(tài)-值輸入經(jīng)典的值迭代算法進(jìn)行迭代優(yōu)化,以保證每個(gè)狀態(tài)最終的狀態(tài)-值能滿足預(yù)先設(shè)定的閾值要求.在柵格環(huán)境中對(duì)改進(jìn)的值迭代算法進(jìn)行實(shí)驗(yàn),結(jié)果顯示此算法的計(jì)算效率明顯高于使用歐氏距離作為啟發(fā)式的值迭代算法和Dijkstra 算法.在三維(3D)動(dòng)畫場(chǎng)景中對(duì)本文提出的運(yùn)動(dòng)軌跡生成算法進(jìn)行仿真實(shí)驗(yàn),結(jié)果表明此算法可實(shí)現(xiàn)群體無碰撞地朝向目標(biāo)運(yùn)動(dòng),并具有多樣性.

本文后續(xù)結(jié)構(gòu)安排如下:第1 節(jié)介紹基于馬爾可夫決策過程的群體動(dòng)畫建模；第2 節(jié)介紹本文提出的改進(jìn)的值迭代算法和群體動(dòng)畫運(yùn)動(dòng)軌跡生成算法；第3 節(jié)介紹實(shí)驗(yàn)部分,并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析；第4 節(jié)給出結(jié)論與展望.

1 基于馬爾可夫決策過程的群體動(dòng)畫建模

馬爾可夫決策過程常被用來作為序列決策問題的框架,在近些年來得到了大量的研究與應(yīng)用,如路徑規(guī)劃[12]、深度強(qiáng)化學(xué)習(xí)[11]等.本節(jié)將對(duì)馬爾可夫決策過程進(jìn)行形式化描述,并利用馬爾可夫決策過程對(duì)群體動(dòng)畫進(jìn)行建模,最后介紹求解馬爾可夫決策過程狀態(tài)-值的值迭代算法.

1.1 馬爾可夫決策過程

馬爾可夫決策過程常被用來作為序列決策問題的框架,可以用一個(gè)五元組 (S,A,P,R,γ) 來 表示.其中S代表環(huán)境狀態(tài)的集合,A代表智能體所有動(dòng)作的集合,P(s,a,s′) 表 示智能體在狀態(tài)s執(zhí)行動(dòng)作a到 達(dá)狀態(tài)s′的概率,R(s,a,s′)表示智能體在狀態(tài)s執(zhí)行動(dòng)作a到達(dá)狀態(tài)s′所 得到的回報(bào),γ表示折扣因子.

當(dāng)馬爾可夫決策過程用來表示序列決策問題后,求解馬爾可夫決策過程即可表示為求解最優(yōu)策略(π)的問題,即智能體在所處狀態(tài)采取最優(yōu)動(dòng)作以使智能體所獲得的累積回報(bào)最大.累積回報(bào)可形式化表示為智能體所處狀態(tài)的價(jià)值(即狀態(tài)-值函數(shù)vπ(s)),如式(1)所示.

為了方便計(jì)算狀態(tài)-值函數(shù)vπ(s),可利用貝爾曼方程表示如式(2)所示.

當(dāng)vπ(s)≥vπ′(s) 對(duì) 所有的s∈S和π′成立時(shí),π為最優(yōu)策略(后文用v?(s)表示最優(yōu)策略對(duì)應(yīng)的狀態(tài)-值函數(shù)),即智能體在每個(gè)狀態(tài)都采取的最優(yōu)動(dòng)作,如式(3)所示.

求解最優(yōu)策略常見的方法有策略迭代和值迭代[13]算法.因值迭代方法在本文所研究的問題中具有更高的計(jì)算效率,本文采用值迭代方法進(jìn)行求解,并在1.3 節(jié)給出針對(duì)群體動(dòng)畫模型特點(diǎn)的值迭代算法,在第2 節(jié)中給出本文所提出的改進(jìn)的值迭代算法.

1.2 群體動(dòng)畫建模

利用馬爾可夫決策過程對(duì)群體動(dòng)畫進(jìn)行建模,即對(duì)群體動(dòng)畫的運(yùn)動(dòng)環(huán)境和在每個(gè)環(huán)境狀態(tài)下智能體所能采取的動(dòng)作進(jìn)行建模.本小節(jié)首先介紹對(duì)群體動(dòng)畫的運(yùn)動(dòng)環(huán)境進(jìn)行建模,然后再利用上一小節(jié)介紹的馬爾可夫決策過程對(duì)群體動(dòng)畫的運(yùn)動(dòng)行為進(jìn)行刻畫.

本文采用柵格法[14,15]對(duì)環(huán)境狀態(tài)進(jìn)行建模,即用矩陣(grid)的形式對(duì)環(huán)境狀態(tài)進(jìn)行存儲(chǔ)表示,其中將二維平面空間環(huán)境用二維矩陣進(jìn)行存儲(chǔ)表示,將三維立體空間環(huán)境用三維矩陣進(jìn)行存儲(chǔ)表示.首先將環(huán)境狀態(tài)按參與群體運(yùn)動(dòng)的智能體的包圍盒(二維平面空間為圓形包圍盒,三維立體空間為球體包圍盒)的直徑大小進(jìn)行柵格化分,使每個(gè)柵格區(qū)域的尺寸大小相同且大于包圍盒直徑的倍.然后在柵格區(qū)域中將障礙物所在區(qū)域在矩陣中標(biāo)記為值1,自由區(qū)域在矩陣中標(biāo)記為值0,如grid[i][j]=1表示坐標(biāo)為(i,j)的柵格區(qū)域含有障礙物,智能體不可進(jìn)入此區(qū)域,grid[i][j]=0表示表示坐標(biāo)為(i,j)的柵格區(qū)域?yàn)樽杂蓞^(qū)域,智能體可進(jìn)入.

對(duì)環(huán)境狀態(tài)進(jìn)行建模后,即可利用馬爾可夫決策過程對(duì)智能體的運(yùn)動(dòng)行為進(jìn)行建模,形式化表示如下:

S:環(huán)境中所有的柵格區(qū)域及障礙物信息,即本文所采用的矩陣表示中矩陣的各元素坐標(biāo)和值；

A:智能體的動(dòng)作空間,對(duì)于二維平面空間,A=(0,1,2,···,7),即8 個(gè)移動(dòng)方向?qū)?yīng)的動(dòng)作,每個(gè)動(dòng)作可使智能體在單位時(shí)間移動(dòng)到對(duì)應(yīng)方向的下一個(gè)柵格區(qū)域；對(duì)于三維立體空間,A=(0,1,2,3,···,25)共26 個(gè)移動(dòng)方向?qū)?yīng)的動(dòng)作,其中與智能體在同一高度含8 個(gè)移動(dòng)方向?qū)?yīng)的動(dòng)作,上下方各9 個(gè)移動(dòng)方向?qū)?yīng)的動(dòng)作；

P:本文假設(shè)智能體的運(yùn)動(dòng)不受除自身動(dòng)作以外的因素影響,即智能體在每個(gè)柵格區(qū)域s,采取任何動(dòng)作a所能達(dá)到的柵格區(qū)域s′是 確定的,即P(s,a,s′)=1.0,同時(shí)我們規(guī)定當(dāng)動(dòng)作a可使智能體進(jìn)入障礙物所在區(qū)域或穿越環(huán)境邊界時(shí)s′=s,即智能體保持在原位置,當(dāng)智能體在障礙物所在區(qū)域或目標(biāo)狀態(tài)區(qū)域時(shí),智能體將永久停留在此區(qū)域,即障礙物所在區(qū)域和目標(biāo)狀態(tài)所在區(qū)域均為吸收狀態(tài).基于此規(guī)則和假設(shè),在使用值迭代算法求解馬爾夫決策過程的狀態(tài)-值時(shí)可省略概率P；

R:當(dāng)動(dòng)作a使智能體在自由區(qū)域移動(dòng)時(shí),我們將柵格之間的歐氏距離的相反數(shù)作為智能體移動(dòng)所得到的回報(bào)；當(dāng)動(dòng)作a使智能體進(jìn)入障礙物所在區(qū)域或穿越邊界時(shí),智能體得到負(fù)無窮大的回報(bào)(-Inf)；當(dāng)智能體原來所在狀態(tài)為障礙物區(qū)域或目標(biāo)狀態(tài)所在區(qū)域時(shí),任何動(dòng)作a均使智能體收獲值為0 的回報(bào)；

γ:我們?nèi)≌劭垡蜃訛?.0,以使每個(gè)狀態(tài)的狀態(tài)-值的絕對(duì)值近似于此狀態(tài)到目標(biāo)狀態(tài)的真實(shí)最短路徑距離,同時(shí)在值迭代算法求解中可省略此折扣因子,以簡化計(jì)算.

此時(shí)我們便完成了對(duì)群體動(dòng)畫運(yùn)動(dòng)環(huán)境狀態(tài)的柵格法建模和智能體運(yùn)動(dòng)行為的馬爾可夫決策過程建模.群體相當(dāng)于多個(gè)智能體,當(dāng)我們通過上述模型求解出環(huán)境中每個(gè)柵格區(qū)域所對(duì)應(yīng)的狀態(tài)的最優(yōu)狀態(tài)-值,即v?(s)時(shí),每個(gè)智能體都可根據(jù)式(3)確定其在當(dāng)前狀態(tài)采取的最優(yōu)策略(即最優(yōu)動(dòng)作),從而間接完成了對(duì)群體動(dòng)畫運(yùn)動(dòng)行為的建模.

1.3 值迭代算法

求解馬爾可夫決策過程通常采用策略迭代或值迭代[13]算法,其中策略迭代需在每個(gè)狀態(tài)-值收斂后再進(jìn)行策略提升,不斷地迭代直到策略收斂,而值迭代在狀態(tài)-值每更新一次之后即進(jìn)行策略提升,再重復(fù)進(jìn)行狀態(tài)-值更新和策略提升直至狀態(tài)-值收斂[16],此時(shí)智能體按式(3)即可輸出最優(yōu)策略.因值迭代算法在本文所研究的問題(即柵格環(huán)境狀態(tài)所對(duì)應(yīng)的狀態(tài)-值的求解)上的效率明顯高于策略迭代算法,本文采用值迭代算法求解環(huán)境狀態(tài)的狀態(tài)-值.本小節(jié)在算法1 中給出了結(jié)合1.2 節(jié)中群體動(dòng)畫模型特點(diǎn)的值迭代算法,與經(jīng)典的值迭代算法相比,省略了對(duì)于概率P和折扣因子γ的考慮.收斂后每個(gè)狀態(tài)的狀態(tài)-值的絕對(duì)值可近似看作此狀態(tài)與目標(biāo)狀態(tài)的實(shí)際最短距離,因此可以方便的與經(jīng)典的最短路徑算法Dijkstra 算法的計(jì)算效率進(jìn)行對(duì)比.

算法1.值迭代算法1) 對(duì)每個(gè)柵格區(qū)域初始化狀態(tài)-值為v (s)=-Inf,初始化目標(biāo)狀態(tài)區(qū)域的狀態(tài)-值為v (g)=0 ,初始化閾值 θ＞0；2) whiletrue:3) Δ =0；4) for sinS:5) v =v(s)；6) v (s)=max(R(s,a,s′)+v(s′))；// s′為 s可到達(dá)的下一狀態(tài)7) Δ =max(Δ,|v-v(s)|)；8) end for；9) if Δ ＜θ :10) break ；11) end if ；12) endwhile；13)輸出 v(s)；

由于本文的群體動(dòng)畫模型中智能體采取每步動(dòng)作所能獲得的回報(bào)R的絕對(duì)值除0 外最小的為1,即智能體水平、垂直或豎直方向移動(dòng)一個(gè)柵格的歐氏距離,因此當(dāng)算法1 中的閾值 θ取值為1.0 時(shí),智能體也可以有效地避開障礙物,同時(shí)基于式(3)可實(shí)現(xiàn)智能體向目標(biāo)運(yùn)動(dòng),本文將在第3 節(jié)實(shí)驗(yàn)部分的值迭代算法中均取閾值θ 為1.0,以加快收斂速度.

2 改進(jìn)的值迭代算法和運(yùn)動(dòng)軌跡生成算法

基于第1 節(jié)中使用馬爾可夫決策過程對(duì)群體動(dòng)畫的建模,利用算法1 求出每個(gè)環(huán)境狀態(tài)的狀態(tài)-值,利用式(3)已可以實(shí)現(xiàn)群體中每個(gè)智能體向目標(biāo)運(yùn)動(dòng),同時(shí)可以有效地避開障礙物(即矩陣中值為1 所對(duì)應(yīng)的柵格區(qū)域).在此基礎(chǔ)上,本文提出了一種可實(shí)現(xiàn)智能體間無碰撞的運(yùn)動(dòng)軌跡生成算法,同時(shí)該算法可保證智能體的運(yùn)動(dòng)具有多樣性.為了進(jìn)一步提升算法1 的收斂速度,本文同時(shí)提出了一種改進(jìn)的值迭代算法,本節(jié)將分別予以介紹.

2.1 改進(jìn)的值迭代算法

對(duì)于算法1 進(jìn)行改進(jìn)以進(jìn)一步提升收斂速度,一般采用基于啟發(fā)式信息作為狀態(tài)-值v(s)的初始值[17],或者采用啟發(fā)式信息引導(dǎo)智能體進(jìn)行探索以縮小狀態(tài)-值進(jìn)行更新的區(qū)域[12].

因群體動(dòng)畫涉及多個(gè)智能體的運(yùn)動(dòng),并且智能體初始位置不確定,使用啟發(fā)式信息作為狀態(tài)-值的初始值,再利用算法1 進(jìn)行迭代更新可求出每個(gè)環(huán)境狀態(tài)的狀態(tài)-值,進(jìn)而可方便求出隨機(jī)初始狀態(tài)的所有智能體的運(yùn)動(dòng)策略.

本文根據(jù)貪婪思想設(shè)計(jì)了一種新的可計(jì)算出每個(gè)環(huán)境狀態(tài)的估計(jì)狀態(tài)-值v(s)的算法(如算法2 所示),將此估計(jì)值作為算法1 中狀態(tài)-值v(s)的初始值,再利用算法1 進(jìn)行迭代計(jì)算,可使計(jì)算效率明顯高于使用歐氏距離作為啟發(fā)式信息的值迭代算法和經(jīng)典的最短路徑算法Dijkstra 算法,本文將在第3 部分給出實(shí)驗(yàn)結(jié)果.

算法2.初始狀態(tài)-值 v(s)估計(jì)算法1) 初始化所有的狀態(tài)-值 v (s)=-In f ,初始化優(yōu)先列 pq(按從大到小順序),初始化集合 block 為空集,初始化目標(biāo)狀態(tài)的狀態(tài)-值v (g)=0,pq.put((v(g),g)),block.add(g)；2) whilenot pq.empty():3) s =pq.get()[1]；4) ns=get_neighbors(s)；//獲取狀態(tài) s 可到達(dá)的鄰近區(qū)域5) fors′ inns:6) ifnot s′inblock:7) v (s′)=v(s)+R(s,a,s′) ；// R為負(fù)數(shù)8) pq.put((v(s′),s′))；9) block.add(s′)；10) end i f；11) end for；12) endwhile；13) 輸出 v (s)；

從算法2 的偽代碼中可以看出使用集合block存儲(chǔ)每次計(jì)算的環(huán)境狀態(tài),實(shí)現(xiàn)了每個(gè)環(huán)境狀態(tài)的狀態(tài)-值僅計(jì)算一次,同時(shí)使用優(yōu)先隊(duì)列(基于堆的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)) 存儲(chǔ)每次計(jì)算的狀態(tài),可快速地實(shí)現(xiàn)狀態(tài)按狀態(tài)-值大小排序.

2.2 運(yùn)動(dòng)軌跡生成算法

通過算法1 求出每個(gè)環(huán)境狀態(tài)的狀態(tài)-值v(s)后,即可根據(jù)(3)式求出每個(gè)智能體在當(dāng)前狀態(tài)的最優(yōu)策略,即最優(yōu)動(dòng)作a,但此時(shí)智能體之間可能會(huì)發(fā)生碰撞.為了避免智能體之間發(fā)生碰撞,同時(shí)為了保證智能體的運(yùn)動(dòng)具有多樣性,本文設(shè)計(jì)了一種運(yùn)動(dòng)軌跡生成算法(如算法3 所示).

為了保證智能體向目標(biāo)狀態(tài)所在區(qū)域運(yùn)動(dòng)并且保證智能體之間不發(fā)生碰撞,在智能體當(dāng)前狀態(tài)st采取動(dòng)作at所有可到達(dá)狀態(tài)st+1(將其他智能體當(dāng)前所在狀態(tài)作為該智能體的臨時(shí)障礙物區(qū)域,即算法3 第6 行矩陣block中 元素為1的位置)中我們優(yōu)先考慮滿足v(st+1)＞v(st)的所有狀態(tài)st+1,當(dāng)智能體沒有滿足此條件的狀態(tài)st+1時(shí) ,我們考慮其他的可到達(dá)狀態(tài)st+1以及智能體的當(dāng)前狀態(tài)st,即當(dāng)智能體有更接近目標(biāo)的狀態(tài)時(shí)選取更接近的目標(biāo)狀態(tài),否則智能體選取其他的可到達(dá)狀態(tài)進(jìn)行探索,以便在將來可能進(jìn)入一個(gè)更好的狀態(tài).

對(duì)于所有的待選取狀態(tài)st+1,我們引入Boltzmann分布和輪盤賭方法從中選擇一個(gè)狀態(tài)作為智能體運(yùn)動(dòng)的下一個(gè)狀態(tài)(Boltzmann 分布如公式(4)所示).

取v′(k)=v(k)-max(v(0),v(1),···,v(K)),v′(i)=v(i)-max(v(0),v(1),···,v(K)) 以消除狀態(tài)-值v(s)之間的數(shù)量級(jí)差異,同時(shí)取τ 為常數(shù)1,方便計(jì)算同時(shí)不影響效果.

為了計(jì)算同一時(shí)間群體中每個(gè)智能體可采取的動(dòng)作,即下一個(gè)單位時(shí)間各智能體所能達(dá)到的狀態(tài),我們對(duì)每個(gè)智能體按當(dāng)前所在狀態(tài)的狀態(tài)-值v(s)對(duì)智能體進(jìn)行排序,其中狀態(tài)-值越大的智能體優(yōu)先級(jí)越高,按此優(yōu)先級(jí)順序依次為智能體按上述方法選取下一個(gè)狀態(tài)并添加到此智能體的運(yùn)動(dòng)軌跡隊(duì)列中,當(dāng)所有智能體下一個(gè)狀態(tài)均計(jì)算完畢后,再重復(fù)此過程,直到達(dá)到最大的軌跡長度.按此方法可為每個(gè)智能體生成一條運(yùn)動(dòng)軌跡,同時(shí)可保證智能體按運(yùn)動(dòng)軌跡進(jìn)行運(yùn)動(dòng)時(shí)不會(huì)發(fā)生碰撞.

為了使智能體可以在有運(yùn)動(dòng)的障礙物環(huán)境中進(jìn)行無碰撞運(yùn)動(dòng),我們每隔一段時(shí)間檢測(cè)障礙物位置是否發(fā)生變化,如果發(fā)生變化,我們將障礙物當(dāng)前位置及一定幀數(shù)后的位置所覆蓋的區(qū)域均作為障礙物處理,更新表示柵格環(huán)境狀態(tài)的矩陣,再重新根據(jù)算法1 計(jì)算各狀態(tài)的狀態(tài)-值,然后再按上述步驟繼續(xù)規(guī)劃各智能體的運(yùn)動(dòng)軌跡.

算法3.動(dòng)軌跡生成算法1) 隨機(jī)初始化各智能體的初始狀態(tài)(均在自由區(qū)域),為每個(gè)智能體agent 設(shè)置一個(gè)數(shù)組用于存儲(chǔ)智能體的軌跡 L [agent],將各智能體初始狀態(tài)存入對(duì)應(yīng)的 L [agent]中,初始化矩陣block(大小同環(huán)境狀態(tài)矩陣grid),在block 中將各智能體初始狀態(tài)對(duì)應(yīng)位置的元素置為1,其余位置的元素置為0,初始化軌跡長度計(jì)數(shù)length=0；2) whilelength＜maxLength:3) 根據(jù)算法1 中輸出的 v(s) 對(duì) 各智能體排序,獲取排序結(jié)果 Agents；4) foragentin Agents:5) 在block 中將L[agent]的尾部狀態(tài)對(duì)應(yīng)位置的元素置為0；6) 根據(jù) L[agent] 的 尾部狀態(tài)及矩陣block 獲取agent的可到達(dá)區(qū)域neighbors0 (滿足v (s′)＞v(s)) 和neighbors1(滿足v (s′)≤v(s))；7) 當(dāng)neighbors0不 為空時(shí),按式(4)在neighbors0中選取下一狀態(tài),否則在 neighbors1中按式(4) 選取下一狀態(tài),將下一狀態(tài)存入L[agent]尾部；8) 在block 中將選取的下一狀態(tài)對(duì)應(yīng)位置的元素置為1；9) end for ；10) 檢測(cè)是否有障礙物位置發(fā)生變化,若有則更新環(huán)境狀態(tài)矩陣grid,重新執(zhí)行算法1 獲取最新的狀態(tài)-值v (s)；11) length=length+1；12) endwhile；13) 輸出各智能體的運(yùn)動(dòng)軌跡 L [agent]；

當(dāng)獲取執(zhí)行算法3 輸出的各智能體的運(yùn)動(dòng)軌跡后,在仿真軟件中只需將各智能體的運(yùn)動(dòng)軌跡映射到柵格環(huán)境中各狀態(tài)區(qū)域的真實(shí)坐標(biāo)并讓智能體按此真實(shí)坐標(biāo)進(jìn)行運(yùn)動(dòng)即可實(shí)現(xiàn)群體運(yùn)動(dòng)目的.

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

本節(jié)將對(duì)本文提出的改進(jìn)的值迭代算法進(jìn)行實(shí)驗(yàn),并將其與以歐氏距離作為啟發(fā)式的值迭代算法和經(jīng)典的最短路徑算法Dijkstra 算法的計(jì)算時(shí)間進(jìn)行比較分析.同時(shí)利用maya 2009 軟件在三維動(dòng)畫場(chǎng)景中對(duì)本文提出的運(yùn)動(dòng)軌跡生成算法進(jìn)行群體動(dòng)畫仿真實(shí)驗(yàn).

3.1 改進(jìn)的值迭代算法實(shí)驗(yàn)及分析

我們用矩陣表示二維平面空間和三維立體空間分別對(duì)本文提出的改進(jìn)的值迭代算法(記作IVI)、以歐氏距離作為啟發(fā)式的值迭代算法(記作HVI) 和Dijkstra 算法進(jìn)行實(shí)驗(yàn),每組各取5 個(gè)不同大小的矩陣,在矩陣邊界的中心處取一點(diǎn)作為目標(biāo)點(diǎn),在矩陣的中間部分區(qū)域設(shè)置障礙物區(qū)域,以使測(cè)試模型具有一定的代表性.其中表示二維平面空間的矩陣分別為:

1) 大小:10×10,目標(biāo):(9,5),障礙物區(qū)域:(5,3)到(5,7)所在直線區(qū)域；

2) 大小:20×20,目標(biāo):(19,10),障礙物區(qū)域:(10,5)到(10,14)所在直線區(qū)域；

3) 大小:30×30,目標(biāo):(29,15),障礙物區(qū)域:(15,10)到(15,19)所在直線區(qū)域；

4) 大小:40×40,目標(biāo):(39,20),障礙物區(qū)域:(20,15)到(20,24)所在直線區(qū)域；

5) 大小:50×50,目標(biāo):(49,25),障礙物區(qū)域:(25,20)到(25,29)所在直線區(qū)域.

表示三維立體空間的矩陣為:

1) 大小:10×10×10,目標(biāo):(9,5,5),障礙物區(qū)域:(5,3,3)到(5,7,7)所在平面區(qū)域；

2) 大小:20×20×20,目標(biāo):(19,10,10),障礙物區(qū)域:(10,5,5)到(10,14,14)所在平面區(qū)域；

3) 大小:30×20×30,目標(biāo):(29,10,15),障礙物區(qū)域:(15,5,10)到(15,14,19)所在平面區(qū)域；

4) 大小:40×20×40,目標(biāo):(39,10,20),障礙物區(qū)域:(20,5,15)到(20,14,24)所在平面區(qū)域；

5) 大小:50×20×50,目標(biāo):(49,10,25),障礙物區(qū)域:(25,5,20)到(25,14,29)所在平面區(qū)域.

實(shí)驗(yàn)環(huán)境為:Intel? Core? i5-4590 @ 3.30GHz,win7 操作系統(tǒng),使用Python 語言實(shí)現(xiàn).

每次實(shí)驗(yàn)均運(yùn)行3 次,取平均時(shí)間作為算法求解結(jié)束所需時(shí)間(值迭代算法均取閾值 θ=1.0,在算法2 具體實(shí)現(xiàn)時(shí),我們采取初始化除目標(biāo)狀態(tài)外的所有狀態(tài)的狀態(tài)-值為In f和每步移動(dòng)的真實(shí)距離作為回報(bào),即回報(bào)取正值,在最終返回全部狀態(tài)的狀態(tài)-值時(shí)統(tǒng)一取相反數(shù)供算法1 進(jìn)行迭代優(yōu)化).二維平面空間的實(shí)驗(yàn) 結(jié)果見表1,三維立體空間的實(shí)驗(yàn)結(jié)果見表2.

表1 二維平面空間計(jì)算效率對(duì)比(單位:秒)

表2 三維立面空間計(jì)算效率對(duì)比(單位:秒)

通過表1和表2我們可以看出,我們提出的改進(jìn)的值迭代算法僅有一項(xiàng)較Dijkstra 算法慢1.1 毫秒,而其他測(cè)試結(jié)果與以歐氏距離作為啟發(fā)式的值迭代算法和經(jīng)典的最短路徑算法Dijkstra 算法的計(jì)算效率相比均具有明顯提升.同時(shí)我們通過設(shè)置閾值 θ =1.0,保證了收斂后每次迭代所有狀態(tài)的狀態(tài)-值v(s)的改變量均在1.0 以內(nèi),從而保證了各種算法在對(duì)各智能體進(jìn)行運(yùn)動(dòng)軌跡規(guī)劃時(shí)具有相近的性能.因而在滿足群體運(yùn)動(dòng)規(guī)劃目標(biāo)的前提下,我們?cè)O(shè)計(jì)的算法具有明顯優(yōu)勢(shì).

3.2 群體動(dòng)畫仿真實(shí)驗(yàn)及分析

我們用C++語言結(jié)合maya 2009 軟件自帶的mel 語言和api 接口對(duì)運(yùn)動(dòng)軌跡生成算法在三維動(dòng)畫場(chǎng)景中進(jìn)行群體動(dòng)畫仿真實(shí)驗(yàn),將三維動(dòng)畫場(chǎng)景中的地面作為二維平面環(huán)境,立體空間作為三維環(huán)境各進(jìn)行3 次實(shí)驗(yàn),二維平面環(huán)境中以地面上的機(jī)器人作為智能體,共30 個(gè),各智能體的對(duì)應(yīng)的起始位置和目標(biāo)地點(diǎn)均相同,三維立體環(huán)境中以無人機(jī)作為智能體,共30 個(gè),各智能體對(duì)應(yīng)的起始位置和目標(biāo)點(diǎn)均相同(機(jī)器人和無人機(jī)模型下載于3D 溜溜網(wǎng):https://www.3d66.com/).實(shí)驗(yàn)效果見圖1和圖2.

從圖1和圖2可以看出,各智能體均能自動(dòng)避開障礙物,同時(shí)各智能體之間沒有發(fā)生碰撞,最終智能體均聚集在目標(biāo)點(diǎn)附近.實(shí)驗(yàn)效果體現(xiàn)了本算法實(shí)現(xiàn)群體動(dòng)畫的有效性,不同時(shí)間運(yùn)行的程序,各智能體在相同時(shí)間幀時(shí)所處的位置略有不同,體現(xiàn)了本算法可實(shí)現(xiàn)群體運(yùn)動(dòng)的多樣性.

圖1 2D 群體動(dòng)畫仿真結(jié)果部分片段截圖(機(jī)器人模型下載網(wǎng)址https://www.3d66.com/reshtml/4768/476880.html)

4 結(jié)論與展望

本文通過使用馬爾可夫決策過程對(duì)群體動(dòng)畫進(jìn)行建模,同時(shí)設(shè)計(jì)了一種新的改進(jìn)的值迭代算法和運(yùn)動(dòng)軌跡生成算法,通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)的值迭代算法的計(jì)算效率明顯高于用歐氏距離作為啟發(fā)式信息的值迭代算法和經(jīng)典的最短路徑算法Dijkstra 算法,并通過三維群體動(dòng)畫仿真實(shí)驗(yàn)驗(yàn)證了本文設(shè)計(jì)的運(yùn)動(dòng)軌跡生成算法對(duì)于群體運(yùn)動(dòng)的有效性和多樣性.我們正在將本文所設(shè)計(jì)的算法在本實(shí)驗(yàn)室的手機(jī)短信3D 動(dòng)畫自動(dòng)生成系統(tǒng)中進(jìn)行部署.今后我們將嘗試結(jié)合深度強(qiáng)化學(xué)習(xí)算法對(duì)智能體的運(yùn)動(dòng)進(jìn)行細(xì)化以增強(qiáng)智能體運(yùn)動(dòng) 軌跡的光滑性.

圖2 3D 群體動(dòng)畫仿真結(jié)果部分片段截圖(無人機(jī)模型下載網(wǎng)址https://www.3d66.com/reshtml/5450/545028.html)