混合自適應動態(tài)規(guī)劃和蟻群算法的agent路徑規(guī)劃

周麗娟

(山西財經大學 實驗教學中心， 山西 太原 030006)

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

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

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

為了解決該問題， 本文提出一種基于動態(tài)規(guī)劃和混合蟻群算法的多agent路徑規(guī)劃方法， 采用蟻群算法來初始化經過柵格化的各個位置點處的信息素， 針對每個agent的初始位置和目標位置， 采用動態(tài)規(guī)劃方法實時規(guī)劃出一條最優(yōu)路徑， 從而實現多條路徑的并行實時規(guī)劃.

1 agent輸入輸出設置

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

圖 1 agent傳感器設置圖Fig.1 Setting of the sensors of agent

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

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

(1)

式中：l是測量距離的最大值， 因此， 距離值xi經過歸一化后， 將會位于[-1，1]之間， 當xi=-1時， 表示機器人撞到障礙物； 當xi=1時， 表示機器人到達了終點； 當xi=0表示未檢測到障礙物或目標. 目標傳感器主要讀取的兩個值θ1和θ2， 分別為移動機器人前進方向和水平方向夾角和目標與機器人前進方向的夾角. 目標傳感器的測量值為： Δθ=θ1-θ2， 則目標測量值可以表示為

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

歸一化后的目標傳感器值可以表示為

(3)

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

2 基于蟻群的值函數初始化

2.1 蟻群算法

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

在初始時刻， 螞蟻位于相同的初始位置處， 場景中的每個可能的位置點處都分布一定的初始信息素， 假設某條較短的路徑為S， 較長的路徑為L， 經過S和L的螞蟻數量分別為M1和M2， 經過這兩條路徑的螞蟻總和為

M=M1+M2.(4)

當M只螞蟻行走過后， 則第M+1只螞蟻選擇路徑S的幾率為

(5)

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

2.2 信息素更新

螞蟻在路徑上留下的信息素會使得這些區(qū)域對螞蟻來說具有吸引力， 而信息素會隨著時間揮發(fā)， 采用GBA/stlb信息素更新策略

(6)

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

2.3 基于蟻群算法的值函數初始化

采用蟻群算法更新值函數的方法為：

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

初始化： 環(huán)境模型， 對環(huán)境場景中所有位置點的信息素進行初始化， 當前螞蟻數量N=1；

1) 設定螞蟻的初始位置和目標位置， 將蟻群的位置置于初始位置點；

2) 螞蟻根據各路徑上的信息素， 根據轉移概率來移動到下一個位置點；

3) 根據式(6)來更新信息素；

4) 當螞蟻沒有達到目標位置時候， 則重新下一位置的移動概率， 并根據移動概率來移動到一個位置， 同時更新信息素； 否則， 就從蟻群中派出下一只螞蟻， 并使得螞蟻從步驟1)開始繼續(xù)執(zhí)行；

5) 當所有螞蟻都找出最優(yōu)路徑時， 根據各位置點上的信息素來初始化和更新值函數；

6) 算法結束.

輸出： 將求出的信息素τi,j轉換為初始的值函數.

采用蟻群算法來初始化值函數的流程， 如圖 2 所示.

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

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

3.1 自適應動態(tài)規(guī)劃

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

Q學習作為一種基于樣本的值迭代算法來求解， 能在無需動態(tài)性模型的情況下， 僅需在線獲取樣本就能實現值函數的學習. 在采用Q學習值函數學習時， 需要設定獎賞函數和遷移函數.

獎賞函數的設置為學習到目標狀態(tài)后， 獲得一個值為0的立即獎賞， 而在其它位置獲得值為-1的立即獎賞. 遷移函數的設置是根據agent距離傳感器測量出的距離來確定x方向的坐標值和y方向的坐標值.

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

采用自適應動態(tài)規(guī)劃來實現agent路徑規(guī)劃的算法如算法1所示， 即采用改進的Q學習來求解agent最優(yōu)路徑的規(guī)劃算法.

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

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

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

1) 根據狀態(tài)x處Q值來確定最優(yōu)動作

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

3) 根據遷移函數來獲得當前狀態(tài)和動作執(zhí)行后獲得的后續(xù)狀態(tài)x′和立即獎賞r；

4) 根據狀態(tài)x′處Q值來確定最優(yōu)動作

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

6) 更新當前狀態(tài)動作對(x,u)的Q值

Q(x,u)=

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

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

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

u←u′;

9) 更新當前時間步S=S+1， 如果S不超過Smax， 則轉入1)繼續(xù)執(zhí)行；

10) 更新當前情節(jié)數E=E+1， 如果E不超過Emax， 則轉入1)繼續(xù)執(zhí)行；

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

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

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

4 仿真實驗

4.1 實驗描述

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

4.2 場景柵格化

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

圖 4 迷宮仿真場景圖Fig.4 Setting of the maze

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

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

為了獲得agent從初始位置到目標位置的最優(yōu)路徑， 首先采用蟻群算法來對場景中各個狀態(tài)處的值函數進行初始化， 然后再通過自適應的動態(tài)規(guī)劃算法來求取各個狀態(tài)動作處的最優(yōu)動作之后的函數， 從而獲得各狀態(tài)處最優(yōu)動作.

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

下面在障礙物分布固定和障礙物分布隨機兩種情況下對迷宮場景進行分析， 障礙物固定是指障礙物的位置是在實驗初始化時就固定， 而障礙物分布隨機是指障礙物在初始時刻的位置是隨機分布的(通過隨機函數在當前迷宮狀態(tài)空間中隨機生成的位置)， 較固定情況時更能對算法的魯棒性進行測試.

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

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

2) 當初始時刻的障礙物隨機分布時， 此時的場景如圖 7 所示.

圖 7 隨機障礙物下的仿真場景Fig.7 Maze scenario with the random barrier

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

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

4.4 比較與分析

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

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

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

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

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

三種方法在固定障礙物和隨機障礙物情況下對應的收斂性能如表 1 所示.

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

表 1 收斂性能比較

5 結 論

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