周麗娟

(山西財(cái)經(jīng)大學(xué) 實(shí)驗(yàn)教學(xué)中心， 山西 太原 030006)

多agent的路徑規(guī)劃是智能規(guī)劃領(lǐng)域的一個(gè)研究重點(diǎn)[1-2]. agent規(guī)劃任務(wù)是要尋求從初始位置到目標(biāo)位置的一條可行路徑. 多agent的動(dòng)態(tài)路徑規(guī)劃是指多個(gè)agent從不同的初始位置同時(shí)出發(fā)， 在未知的環(huán)境中通過(guò)學(xué)習(xí)， 避開(kāi)所有障礙物， 尋求到不同目標(biāo)位置的路徑.

常用的求解方法包括模糊神經(jīng)網(wǎng)絡(luò)方法[3]、 智能優(yōu)化算法[4-9]、 動(dòng)態(tài)規(guī)劃方法[10-11]以及啟發(fā)式搜索方法[12]. 錢(qián)夔[3]等提出了一種模糊神經(jīng)網(wǎng)絡(luò)方法， 采用神經(jīng)網(wǎng)絡(luò)對(duì)輸入量進(jìn)行模糊處理， 并建立基于輸出量的邏輯規(guī)則， 求解的策略是基于輸出量和邏輯規(guī)則來(lái)生成最優(yōu)規(guī)劃路徑. 伍永健[4]等提出了一種基于量子粒子群和Morphin算法的混合路徑規(guī)劃方法. 首先， 通過(guò)柵格離散化方法建立環(huán)境模型， 建立自適應(yīng)的局部搜索策略和交叉操作對(duì)粒子群算法改進(jìn)， 從而規(guī)劃出最優(yōu)路徑. 王學(xué)武[5]等將點(diǎn)焊機(jī)器人的路徑規(guī)劃問(wèn)題轉(zhuǎn)換為焊接順序的優(yōu)化問(wèn)題， 設(shè)計(jì)一種基于萊維飛行的粒子群算法來(lái)求解路徑優(yōu)化問(wèn)題. 屈鴻[6]等設(shè)計(jì)了一種改進(jìn)的蟻群算法[7-9]， 通過(guò)引入相關(guān)策略避免死鎖問(wèn)題， 通過(guò)調(diào)整轉(zhuǎn)移概率來(lái)限定信息素強(qiáng)度上下界， 并提出了相應(yīng)的碰撞避免策略. 唐振民[10]等充分考慮多機(jī)器人系統(tǒng)的動(dòng)態(tài)特征， 運(yùn)用Dijkstra算法和圖論的相關(guān)知識(shí)， 求解路徑規(guī)劃. 朱廣蔚[11]等提出了一種基于動(dòng)態(tài)規(guī)劃方法的路徑規(guī)劃方法， 首先尋找圖中的包含所有節(jié)點(diǎn)的TSP回路， 然后利用動(dòng)態(tài)規(guī)劃來(lái)對(duì)回路分段， 以最小化路徑總距離和關(guān)鍵負(fù)載為目標(biāo). 陳洋[12]等將完成目標(biāo)序列訪(fǎng)問(wèn)任務(wù)的總時(shí)間最短為代價(jià)， 建立目標(biāo)優(yōu)化模型， 將機(jī)器人路徑規(guī)劃問(wèn)題轉(zhuǎn)換為混合整數(shù)凸優(yōu)化問(wèn)題.

除了這些常見(jiàn)方法， 還有一些方法是將以上多種方法進(jìn)行結(jié)合[13-17]， 這些方法雖然提供了路徑規(guī)劃更靈活的求解方式， 但是仍然主要針對(duì)單agent的規(guī)劃場(chǎng)景， 同時(shí)大部分工作沒(méi)有考慮到障礙物的隨機(jī)動(dòng)態(tài)變化. 強(qiáng)化學(xué)習(xí)[18-19]是一種通過(guò)最大化長(zhǎng)期的累計(jì)獎(jiǎng)賞來(lái)獲取最優(yōu)策略的方法， 能通過(guò)在線(xiàn)學(xué)習(xí)快速學(xué)習(xí)到agent的最優(yōu)策略， 能適合多agent共尋優(yōu)的要求. 因此， 本文研究基于強(qiáng)化學(xué)習(xí)并立足于解決多agent的并行路徑規(guī)劃問(wèn)題， 同時(shí)場(chǎng)景動(dòng)態(tài)實(shí)時(shí)變化.

為了解決該問(wèn)題， 本文提出一種基于動(dòng)態(tài)規(guī)劃和混合蟻群算法的多agent路徑規(guī)劃方法， 采用蟻群算法來(lái)初始化經(jīng)過(guò)柵格化的各個(gè)位置點(diǎn)處的信息素， 針對(duì)每個(gè)agent的初始位置和目標(biāo)位置， 采用動(dòng)態(tài)規(guī)劃方法實(shí)時(shí)規(guī)劃出一條最優(yōu)路徑， 從而實(shí)現(xiàn)多條路徑的并行實(shí)時(shí)規(guī)劃.

1 agent輸入輸出設(shè)置

agent 附加了多個(gè)傳感器來(lái)感知環(huán)境狀態(tài)， agent 的輸入來(lái)自傳感器所感知的狀態(tài)， 而輸出則是根據(jù)自適應(yīng)動(dòng)態(tài)規(guī)劃獲得的最優(yōu)策略, 如圖 1 所示.

圖 1 agent傳感器設(shè)置圖Fig.1 Setting of the sensors of agent

agent被安置了6個(gè)傳感器， 其中5個(gè)為距離傳感器， 分別為前置傳感器、 左置傳感器、 右置傳感器、 左前傳感器、 右前傳感器， 用于對(duì)周邊環(huán)境狀態(tài)進(jìn)行檢測(cè)， 測(cè)量出機(jī)器人在當(dāng)前動(dòng)作執(zhí)行后移動(dòng)的距離值， 對(duì)應(yīng)的傳感器測(cè)量的距離值分別為：d1，d2，d3，d4和d5. 還有一個(gè)傳感器為目標(biāo)傳感器， 用于檢測(cè)目標(biāo)所在方向與機(jī)器人行進(jìn)方向的夾角θ.

所有傳感器測(cè)量的數(shù)據(jù)都將被歸一化處理， 對(duì)于距離傳感器， 其數(shù)據(jù)歸一化的方式為(i=1,2,…,5)

(1)

式中：l是測(cè)量距離的最大值， 因此， 距離值xi經(jīng)過(guò)歸一化后， 將會(huì)位于[-1，1]之間， 當(dāng)xi=-1時(shí)， 表示機(jī)器人撞到障礙物； 當(dāng)xi=1時(shí)， 表示機(jī)器人到達(dá)了終點(diǎn)； 當(dāng)xi=0表示未檢測(cè)到障礙物或目標(biāo). 目標(biāo)傳感器主要讀取的兩個(gè)值θ1和θ2， 分別為移動(dòng)機(jī)器人前進(jìn)方向和水平方向夾角和目標(biāo)與機(jī)器人前進(jìn)方向的夾角. 目標(biāo)傳感器的測(cè)量值為： Δθ=θ1-θ2， 則目標(biāo)測(cè)量值可以表示為

Δθ=θ1-θ2.(2)

歸一化后的目標(biāo)傳感器值可以表示為

(3)

歸一化的位置傳感器和目標(biāo)傳感器構(gòu)成的狀態(tài)X=(x1,x2,x3,x4,x5,θ). 在某時(shí)刻， 當(dāng)機(jī)器人以常速在環(huán)境中行駛， 根據(jù)輸出策略u(píng)的值， agent調(diào)整其前進(jìn)方向， 當(dāng)策略值u>0時(shí)， agent向左調(diào)整其前進(jìn)方向20°， 當(dāng)u<0時(shí)， agent向右調(diào)整其前進(jìn)方向-20°， 當(dāng)u=0時(shí)， agent保持前進(jìn)方向.

2 基于蟻群的值函數(shù)初始化

2.1 蟻群算法

蟻群算法是由Dorigo于20世紀(jì)90年代提出的仿生智能算法. 當(dāng)經(jīng)過(guò)某條路徑的螞蟻數(shù)量越多， 就會(huì)留下越多的信息素， 使得后面的螞蟻選擇信息素較多的路徑的可能性更大， 而這些信息素較多的路徑很可能就對(duì)應(yīng)了短路程的路徑.

在初始時(shí)刻， 螞蟻位于相同的初始位置處， 場(chǎng)景中的每個(gè)可能的位置點(diǎn)處都分布一定的初始信息素， 假設(shè)某條較短的路徑為S， 較長(zhǎng)的路徑為L(zhǎng)， 經(jīng)過(guò)S和L的螞蟻數(shù)量分別為M1和M2， 經(jīng)過(guò)這兩條路徑的螞蟻總和為

M=M1+M2.(4)

當(dāng)M只螞蟻行走過(guò)后， 則第M+1只螞蟻選擇路徑S的幾率為

(5)

式中： 參數(shù)a和b為位于[0,1]之間的數(shù). 設(shè)計(jì)一個(gè)閾值b， 如果PM(S)>h時(shí)， 將會(huì)選擇路徑S， 否則會(huì)選擇路徑L.

2.2 信息素更新

螞蟻在路徑上留下的信息素會(huì)使得這些區(qū)域?qū)ξ浵亖?lái)說(shuō)具有吸引力， 而信息素會(huì)隨著時(shí)間揮發(fā)， 采用GBA/stlb信息素更新策略

(6)

式中：ρ為信息素?fù)]發(fā)因子；Γ*(n)表示上一個(gè)周期的最優(yōu)路徑. 從式(6)可以看出， 未被選擇路徑在下一個(gè)搜索周期中， 信息素會(huì)隨著時(shí)間揮發(fā)而逐漸變少.

2.3 基于蟻群算法的值函數(shù)初始化

采用蟻群算法更新值函數(shù)的方法為：

輸入： 參數(shù)a和b， 螞蟻的數(shù)量NC， 信息素?fù)]發(fā)因子ρ， 任意位置到下一位置的信息素τi,j；

初始化： 環(huán)境模型， 對(duì)環(huán)境場(chǎng)景中所有位置點(diǎn)的信息素進(jìn)行初始化， 當(dāng)前螞蟻數(shù)量N=1；

1) 設(shè)定螞蟻的初始位置和目標(biāo)位置， 將蟻群的位置置于初始位置點(diǎn)；

2) 螞蟻根據(jù)各路徑上的信息素， 根據(jù)轉(zhuǎn)移概率來(lái)移動(dòng)到下一個(gè)位置點(diǎn)；

3) 根據(jù)式(6)來(lái)更新信息素；

4) 當(dāng)螞蟻沒(méi)有達(dá)到目標(biāo)位置時(shí)候， 則重新下一位置的移動(dòng)概率， 并根據(jù)移動(dòng)概率來(lái)移動(dòng)到一個(gè)位置， 同時(shí)更新信息素； 否則， 就從蟻群中派出下一只螞蟻， 并使得螞蟻從步驟1)開(kāi)始繼續(xù)執(zhí)行；

5) 當(dāng)所有螞蟻都找出最優(yōu)路徑時(shí)， 根據(jù)各位置點(diǎn)上的信息素來(lái)初始化和更新值函數(shù)；

6) 算法結(jié)束.

輸出： 將求出的信息素τi,j轉(zhuǎn)換為初始的值函數(shù).

采用蟻群算法來(lái)初始化值函數(shù)的流程， 如圖 2 所示.

圖 2 基于蟻群算法的值函數(shù)初始化Fig.2 Initialization of the value function based on ant colony algorithm

3 基于自適應(yīng)動(dòng)態(tài)規(guī)劃的agent路徑規(guī)劃

3.1 自適應(yīng)動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃方法是一種基于模型的強(qiáng)化學(xué)習(xí)方法， 通過(guò)不斷迭代貝爾曼方程來(lái)求解最優(yōu)值函數(shù). 然而， 在通常的強(qiáng)化學(xué)習(xí)場(chǎng)景中， 模型是未知的， 因此， 無(wú)法直接通過(guò)動(dòng)態(tài)規(guī)劃的兩類(lèi)方法， 值迭代算法和策略迭代算法， 來(lái)求解最優(yōu)值函數(shù).

Q學(xué)習(xí)作為一種基于樣本的值迭代算法來(lái)求解， 能在無(wú)需動(dòng)態(tài)性模型的情況下， 僅需在線(xiàn)獲取樣本就能實(shí)現(xiàn)值函數(shù)的學(xué)習(xí). 在采用Q學(xué)習(xí)值函數(shù)學(xué)習(xí)時(shí)， 需要設(shè)定獎(jiǎng)賞函數(shù)和遷移函數(shù).

獎(jiǎng)賞函數(shù)的設(shè)置為學(xué)習(xí)到目標(biāo)狀態(tài)后， 獲得一個(gè)值為0的立即獎(jiǎng)賞， 而在其它位置獲得值為-1的立即獎(jiǎng)賞. 遷移函數(shù)的設(shè)置是根據(jù)agent距離傳感器測(cè)量出的距離來(lái)確定x方向的坐標(biāo)值和y方向的坐標(biāo)值.

3.2 基于自適應(yīng)動(dòng)態(tài)規(guī)劃的agent規(guī)劃算法

采用自適應(yīng)動(dòng)態(tài)規(guī)劃來(lái)實(shí)現(xiàn)agent路徑規(guī)劃的算法如算法1所示， 即采用改進(jìn)的Q學(xué)習(xí)來(lái)求解agent最優(yōu)路徑的規(guī)劃算法.

算法 2 基于Q學(xué)習(xí)的agent最優(yōu)路徑規(guī)劃算法

輸入： 動(dòng)作探索因子ε， 折扣率γ， 學(xué)習(xí)率α， 最大情節(jié)數(shù)Emax， 情節(jié)的最大時(shí)間步Smax；

初始化： 設(shè)置任意狀態(tài)動(dòng)作處(x,u)的Q值為0， 即Q0(x,u)=0， 設(shè)置當(dāng)前狀態(tài)為初始狀態(tài)x=x0， 當(dāng)前情節(jié)數(shù)E=1， 當(dāng)前時(shí)間步S=1；

1) 根據(jù)狀態(tài)x處Q值來(lái)確定最優(yōu)動(dòng)作

2) 采用ε貪心策略來(lái)選擇當(dāng)前狀態(tài)處的動(dòng)作

3) 根據(jù)遷移函數(shù)來(lái)獲得當(dāng)前狀態(tài)和動(dòng)作執(zhí)行后獲得的后續(xù)狀態(tài)x′和立即獎(jiǎng)賞r；

4) 根據(jù)狀態(tài)x′處Q值來(lái)確定最優(yōu)動(dòng)作

5) 采用ε貪心策略來(lái)選擇下一狀態(tài)x′處的動(dòng)作

6) 更新當(dāng)前狀態(tài)動(dòng)作對(duì)(x,u)的Q值

Q(x,u)=

Q(x,u)+α(r+γ(Q(x′,u′*)-Q(x,u)).

7) 更新當(dāng)前狀態(tài)：x←x′

8) 更新下一個(gè)狀態(tài)處執(zhí)行的動(dòng)作

u←u′;

9) 更新當(dāng)前時(shí)間步S=S+1， 如果S不超過(guò)Smax， 則轉(zhuǎn)入1)繼續(xù)執(zhí)行；

10) 更新當(dāng)前情節(jié)數(shù)E=E+1， 如果E不超過(guò)Emax， 則轉(zhuǎn)入1)繼續(xù)執(zhí)行；

輸出： 任意狀態(tài)動(dòng)作對(duì)應(yīng)的Q值， 從而獲得沿著每個(gè)狀態(tài)處的最優(yōu)動(dòng)作， 即最優(yōu)路徑.

算法2所示的基于Q學(xué)習(xí)的agent最優(yōu)路徑規(guī)劃算法如圖 3 所示.

圖 3 基于Q學(xué)習(xí)的路徑規(guī)劃算法Fig.3 Route planning algorithm based on Q-Learning

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)描述

在Matlab仿真環(huán)境下， 對(duì)文中所提方法進(jìn)行驗(yàn)證. 仿真場(chǎng)景圖如圖 4 所示， 其中黑色陰影部分為障礙物， agent移動(dòng)的初始位置在左下角處， 而右上角則是移動(dòng)的目標(biāo)位置.

4.2 場(chǎng)景柵格化

為了對(duì)仿真場(chǎng)景進(jìn)行量化， 對(duì)二維環(huán)境場(chǎng)景進(jìn)行柵格化， 對(duì)x軸方向和y軸方向分別進(jìn)行等分成20份來(lái)進(jìn)行柵格化， 柵格化的結(jié)果如圖 5 所示.

圖 4 迷宮仿真場(chǎng)景圖Fig.4 Setting of the maze

圖 5 環(huán)境場(chǎng)景柵格化圖Fig.5 Discretization of the maze

4.3 最優(yōu)路徑的獲取

為了獲得agent從初始位置到目標(biāo)位置的最優(yōu)路徑， 首先采用蟻群算法來(lái)對(duì)場(chǎng)景中各個(gè)狀態(tài)處的值函數(shù)進(jìn)行初始化， 然后再通過(guò)自適應(yīng)的動(dòng)態(tài)規(guī)劃算法來(lái)求取各個(gè)狀態(tài)動(dòng)作處的最優(yōu)動(dòng)作之后的函數(shù)， 從而獲得各狀態(tài)處最優(yōu)動(dòng)作.

參數(shù)設(shè)置為： 參數(shù)a=0.4和b=0.6， 螞蟻的數(shù)量NC=200， 信息素?fù)]發(fā)因子ρ=0.4， 任意位置到下一位置的信息素τi,j=0.5. 動(dòng)作探索因子ε=0.05， 折扣率γ=0.9， 學(xué)習(xí)率α=0.5， 最大情節(jié)數(shù)Emax=300， 情節(jié)的最大時(shí)間步Smax=200.

下面在障礙物分布固定和障礙物分布隨機(jī)兩種情況下對(duì)迷宮場(chǎng)景進(jìn)行分析， 障礙物固定是指障礙物的位置是在實(shí)驗(yàn)初始化時(shí)就固定， 而障礙物分布隨機(jī)是指障礙物在初始時(shí)刻的位置是隨機(jī)分布的(通過(guò)隨機(jī)函數(shù)在當(dāng)前迷宮狀態(tài)空間中隨機(jī)生成的位置)， 較固定情況時(shí)更能對(duì)算法的魯棒性進(jìn)行測(cè)試.

1) 在障礙物固定的情況下， 當(dāng)算法運(yùn)行完后， 得到的agent從初始位置到目標(biāo)位置的最優(yōu)路徑為圖 6 所示.

圖 6 固定障礙物下的最優(yōu)路徑Fig.6 Optimal route with the fix barrier

2) 當(dāng)初始時(shí)刻的障礙物隨機(jī)分布時(shí)， 此時(shí)的場(chǎng)景如圖 7 所示.

圖 7 隨機(jī)障礙物下的仿真場(chǎng)景Fig.7 Maze scenario with the random barrier

算法運(yùn)行完后， 得到的agent從初始位置到目標(biāo)位置的最優(yōu)路徑為圖 8 所示.

圖 8 隨機(jī)障礙物下的最優(yōu)路徑Fig.8 Optimal route with the random barrier

4.4 比較與分析

為了進(jìn)一步驗(yàn)證文中方法的優(yōu)越性， 將文獻(xiàn)[9]中基于蟻群算法的規(guī)劃方法以及文獻(xiàn)[10]中基于動(dòng)態(tài)規(guī)劃的方法進(jìn)行比較， 在固定障礙物的情況下， 三種方法得到的收斂所需的時(shí)間步隨情節(jié)增加的變化如圖 9 所示.

圖 9 固定障礙物下的方法比較Fig.9 Comparisons of different methods with the fix barrier

從圖 9 可以看出， 本文方法的收斂速度最快， 大約在210個(gè)情節(jié)后收斂， 而文獻(xiàn)[9]和文獻(xiàn)[10]方法在240個(gè)情節(jié)和300個(gè)情節(jié)后開(kāi)始收斂， 但收斂后所需要的時(shí)間步為18， 大于本文方法所需的17個(gè)時(shí)間步.

圖 10 隨機(jī)障礙物下的方法比較Fig.10 Comparisons of different methods with the random barrier

從圖 10 可以看出， 在隨機(jī)障礙物下， 本文方法的收斂速度最快， 大約在150個(gè)情節(jié)后收斂， 收斂所需的時(shí)間步為25， 而文獻(xiàn)[9]始終未能收斂， 而文獻(xiàn)[10]方法雖然收斂， 但收斂時(shí)所需的時(shí)間步為32. 顯然， 本文方法遠(yuǎn)遠(yuǎn)優(yōu)于文獻(xiàn)[9]方法和文獻(xiàn)[10]方法.

三種方法在固定障礙物和隨機(jī)障礙物情況下對(duì)應(yīng)的收斂性能如表 1 所示.

從表 1 可以看出， 本文方法相對(duì)于文獻(xiàn)[9]和文獻(xiàn)[10]方法， 不僅具有較快的收斂速度， 而且具有更好的收斂精度.

表 1 收斂性能比較

5 結(jié) 論

為了實(shí)現(xiàn)agent的最優(yōu)路徑規(guī)劃， 提出了一種混合自適應(yīng)動(dòng)態(tài)規(guī)劃和蟻群算法的agent路徑規(guī)劃方法. 首先， 根據(jù)agent配置的傳感器對(duì)系統(tǒng)狀態(tài)的輸入和輸出進(jìn)行了定義. 然后， 采用改進(jìn)的蟻群算法來(lái)更新路徑中各個(gè)位置的信息素， 并根據(jù)更新的信息素來(lái)初始化值函數(shù). 此后， 采用改進(jìn)的自適應(yīng)動(dòng)態(tài)規(guī)劃算法來(lái)進(jìn)一步更新值函數(shù)， 直至值函數(shù)收斂. 根據(jù)最優(yōu)值函數(shù)實(shí)現(xiàn)任意狀態(tài)到動(dòng)作的映射， 從而求解出agent從初始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)路徑. 在文中對(duì)兩個(gè)算法均進(jìn)行了仔細(xì)的定義和描述. 通過(guò)仿真實(shí)驗(yàn)證明了文中方法無(wú)論是在固定障礙物還是在隨機(jī)障礙物情況下， 都具有收斂速度快和收斂精度高的優(yōu)點(diǎn).