基于馬爾可夫決策過程的群體動畫運動軌跡生成①

劉俊君,杜艮魁

(北京工業大學 信息學部 計算機學院,北京 100124)

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

本文后續結構安排如下:第1 節介紹基于馬爾可夫決策過程的群體動畫建模；第2 節介紹本文提出的改進的值迭代算法和群體動畫運動軌跡生成算法；第3 節介紹實驗部分,并對實驗結果進行分析；第4 節給出結論與展望.

1 基于馬爾可夫決策過程的群體動畫建模

馬爾可夫決策過程常被用來作為序列決策問題的框架,在近些年來得到了大量的研究與應用,如路徑規劃[12]、深度強化學習[11]等.本節將對馬爾可夫決策過程進行形式化描述,并利用馬爾可夫決策過程對群體動畫進行建模,最后介紹求解馬爾可夫決策過程狀態-值的值迭代算法.

1.1 馬爾可夫決策過程

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

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

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

當vπ(s)≥vπ′(s) 對 所有的s∈S和π′成立時,π為最優策略(后文用v?(s)表示最優策略對應的狀態-值函數),即智能體在每個狀態都采取的最優動作,如式(3)所示.

求解最優策略常見的方法有策略迭代和值迭代[13]算法.因值迭代方法在本文所研究的問題中具有更高的計算效率,本文采用值迭代方法進行求解,并在1.3 節給出針對群體動畫模型特點的值迭代算法,在第2 節中給出本文所提出的改進的值迭代算法.

1.2 群體動畫建模

利用馬爾可夫決策過程對群體動畫進行建模,即對群體動畫的運動環境和在每個環境狀態下智能體所能采取的動作進行建模.本小節首先介紹對群體動畫的運動環境進行建模,然后再利用上一小節介紹的馬爾可夫決策過程對群體動畫的運動行為進行刻畫.

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

對環境狀態進行建模后,即可利用馬爾可夫決策過程對智能體的運動行為進行建模,形式化表示如下:

S:環境中所有的柵格區域及障礙物信息,即本文所采用的矩陣表示中矩陣的各元素坐標和值；

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

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

R:當動作a使智能體在自由區域移動時,我們將柵格之間的歐氏距離的相反數作為智能體移動所得到的回報；當動作a使智能體進入障礙物所在區域或穿越邊界時,智能體得到負無窮大的回報(-Inf)；當智能體原來所在狀態為障礙物區域或目標狀態所在區域時,任何動作a均使智能體收獲值為0 的回報；

γ:我們取折扣因子為1.0,以使每個狀態的狀態-值的絕對值近似于此狀態到目標狀態的真實最短路徑距離,同時在值迭代算法求解中可省略此折扣因子,以簡化計算.

此時我們便完成了對群體動畫運動環境狀態的柵格法建模和智能體運動行為的馬爾可夫決策過程建模.群體相當于多個智能體,當我們通過上述模型求解出環境中每個柵格區域所對應的狀態的最優狀態-值,即v?(s)時,每個智能體都可根據式(3)確定其在當前狀態采取的最優策略(即最優動作),從而間接完成了對群體動畫運動行為的建模.

1.3 值迭代算法

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

算法1.值迭代算法1) 對每個柵格區域初始化狀態-值為v (s)=-Inf,初始化目標狀態區域的狀態-值為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可到達的下一狀態7) Δ =max(Δ,|v-v(s)|)；8) end for；9) if Δ ＜θ :10) break ；11) end if ；12) endwhile；13)輸出 v(s)；

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

2 改進的值迭代算法和運動軌跡生成算法

基于第1 節中使用馬爾可夫決策過程對群體動畫的建模,利用算法1 求出每個環境狀態的狀態-值,利用式(3)已可以實現群體中每個智能體向目標運動,同時可以有效地避開障礙物(即矩陣中值為1 所對應的柵格區域).在此基礎上,本文提出了一種可實現智能體間無碰撞的運動軌跡生成算法,同時該算法可保證智能體的運動具有多樣性.為了進一步提升算法1 的收斂速度,本文同時提出了一種改進的值迭代算法,本節將分別予以介紹.

2.1 改進的值迭代算法

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

因群體動畫涉及多個智能體的運動,并且智能體初始位置不確定,使用啟發式信息作為狀態-值的初始值,再利用算法1 進行迭代更新可求出每個環境狀態的狀態-值,進而可方便求出隨機初始狀態的所有智能體的運動策略.

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

算法2.初始狀態-值 v(s)估計算法1) 初始化所有的狀態-值 v (s)=-In f ,初始化優先列 pq(按從大到小順序),初始化集合 block 為空集,初始化目標狀態的狀態-值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)；//獲取狀態 s 可到達的鄰近區域5) fors′ inns:6) ifnot s′inblock:7) v (s′)=v(s)+R(s,a,s′) ；// R為負數8) pq.put((v(s′),s′))；9) block.add(s′)；10) end i f；11) end for；12) endwhile；13) 輸出 v (s)；

從算法2 的偽代碼中可以看出使用集合block存儲每次計算的環境狀態,實現了每個環境狀態的狀態-值僅計算一次,同時使用優先隊列(基于堆的數據結構實現) 存儲每次計算的狀態,可快速地實現狀態按狀態-值大小排序.

2.2 運動軌跡生成算法

通過算法1 求出每個環境狀態的狀態-值v(s)后,即可根據(3)式求出每個智能體在當前狀態的最優策略,即最優動作a,但此時智能體之間可能會發生碰撞.為了避免智能體之間發生碰撞,同時為了保證智能體的運動具有多樣性,本文設計了一種運動軌跡生成算法(如算法3 所示).

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

對于所有的待選取狀態st+1,我們引入Boltzmann分布和輪盤賭方法從中選擇一個狀態作為智能體運動的下一個狀態(Boltzmann 分布如公式(4)所示).

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

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

為了使智能體可以在有運動的障礙物環境中進行無碰撞運動,我們每隔一段時間檢測障礙物位置是否發生變化,如果發生變化,我們將障礙物當前位置及一定幀數后的位置所覆蓋的區域均作為障礙物處理,更新表示柵格環境狀態的矩陣,再重新根據算法1 計算各狀態的狀態-值,然后再按上述步驟繼續規劃各智能體的運動軌跡.

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

當獲取執行算法3 輸出的各智能體的運動軌跡后,在仿真軟件中只需將各智能體的運動軌跡映射到柵格環境中各狀態區域的真實坐標并讓智能體按此真實坐標進行運動即可實現群體運動目的.

3 實驗分析

本節將對本文提出的改進的值迭代算法進行實驗,并將其與以歐氏距離作為啟發式的值迭代算法和經典的最短路徑算法Dijkstra 算法的計算時間進行比較分析.同時利用maya 2009 軟件在三維動畫場景中對本文提出的運動軌跡生成算法進行群體動畫仿真實驗.

3.1 改進的值迭代算法實驗及分析

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

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

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

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

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

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

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

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

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

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

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

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

實驗環境為:Intel? Core? i5-4590 @ 3.30GHz,win7 操作系統,使用Python 語言實現.

每次實驗均運行3 次,取平均時間作為算法求解結束所需時間(值迭代算法均取閾值 θ=1.0,在算法2 具體實現時,我們采取初始化除目標狀態外的所有狀態的狀態-值為In f和每步移動的真實距離作為回報,即回報取正值,在最終返回全部狀態的狀態-值時統一取相反數供算法1 進行迭代優化).二維平面空間的實驗 結果見表1,三維立體空間的實驗結果見表2.

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

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

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

3.2 群體動畫仿真實驗及分析

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

從圖1和圖2可以看出,各智能體均能自動避開障礙物,同時各智能體之間沒有發生碰撞,最終智能體均聚集在目標點附近.實驗效果體現了本算法實現群體動畫的有效性,不同時間運行的程序,各智能體在相同時間幀時所處的位置略有不同,體現了本算法可實現群體運動的多樣性.

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

4 結論與展望

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

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