基于強化學習的多Agent路徑規劃方法研究

王毅然 經小川 田 濤 孫運乾 從帥軍

(中國航天系統科學與工程研究院 北京 100048)

0 引 言

隨著科學技術的不斷發展，路徑規劃技術的研究成果已經廣泛應用人類生產和生活的各個方面。如在地震救災中，無人機能夠自主躲避障礙物，規劃一組較優的路徑到達指定災區，完成災情獲取任務；在軍事領域中，無人機和機器人在完成情報偵察以及作戰打擊任務過程中，要躲避敵方威脅和避免相撞，規劃一條較優路徑完成任務[1-4]。隨著工作任務變得越來越復雜，往往需要多個智能體協同完成任務，每個智能體均是環境中的一部分，個體采取行動均會造成環境的改變，此時在動態環境中，單個智能體和其他智能體之間的協調與避障是多個智能體路徑規劃亟需解決的問題。路徑規劃的目標是尋找一條從給定的起始點到終止點的較優的運動路徑。單智能體的路徑規劃在一個環境中的狀態是有限的，目前解決的方法主要有Dijkstra算法[5]、粒子群算法[6]、A*算法[7]、遺傳算法、模擬退火算法、蟻群算法[8]等。多智能體系統與單個智能體相比，往往能夠完成復雜艱巨任務，且通常能夠付出更小的代價收獲更大的整體效益，因此多個智能體的路徑規劃研究具有十分重要的意義。

多智能體系統是由具有一定自主性、能夠在共同目標窗口內協作、競爭和通信的協作智能Agent組成的[9]。單個Agent解決問題的能力是有限的，復雜任務需要多個Agent協同合作，共同完成整體或局部目標。如果在同一環境中存在多個Agent同時移動，對其進行路徑規劃將會變得十分困難。目前解決多智能體的路徑規劃問題取得了一些進展，文獻[10]提出了免疫協同進化算法并仿真實現靜態障礙物環境中多個機器人避障、避碰的最短路徑；文獻[11]提出了一種主從結構的并行多水下機器人協同路徑規劃算法，子層結構應用粒子群并行算法，生成各個機器人當前的最優路徑，同時主層結構應用微分進化算法實時給出當前考慮機器人與障礙物、機器人與機器人之間避碰情況下，總系統運行時間最短的路徑組合方案；文獻[12]提出了一種基于分層強化學習及人工勢場的多Agent路徑規劃算法，首先將多Agent的運行環境虛擬為一個人工勢能場，根據先驗知識確定每點的勢能值，它代表最優策略可獲得的最大回報，其次利用分層強化學習方法的無環境模型學習進行策略更新;文獻[13]提出了首先利用A-Star算法啟發式地得到多個智能體到達目標點的臨時最短路徑，同時計算訪問節點的時間，通過動態地對時間窗進行精確計算和加鎖來重置路線以避免沖突。

為解決未知環境下多個Agent路徑規劃問題，上述算法隨著Agent的數量以及環境規模變大時，算法的效率會變得很低。本文提出了一種基于強化學習的多Agent路徑規劃方法(Multi-agent path planning based on reinforcement learning，MAPP-RL)，該方法中的多個Agent不斷地與環境交互，當采取一個動作后，Agent會從環境中得到一個反饋，用來評估該動作的好壞，然后把評估結果作為歷史經驗，不斷地進行優化決策，最后找到一個可以得到最大獎勵的動作序列，完成復雜未知環境下的多Agent路徑規劃任務。

1 整體框架

多智能體的路徑規劃整體框架主要包括四個層次：環境建模層、算法層、任務分配層、多Agent系統層，如圖1所示。

圖1 整體框架圖

在圖1中，首先對環境進行建模，包括對環境中障礙、目標點等信息設置，其次通過任務分配層主要根據實際任務劃分多個子任務，然后算法層接收環境信息以及多個Agent信息和任務分配情況，并進行計算，將結果返回給Agent。多Agent系統層與環境建模層、任務分配層、算法層進行交互，每個Agent均能執行動作與環境交互，同時也和任務分配模塊的任務進行匹配，通過執行算法層，不斷地更新策略，最后得到一組較優策略完成多個Agent的路徑規劃任務。

1.1 環境建模

對環境地圖的建模常用的方法主要有三種：柵欄地圖建模、拓撲地圖建模和可視地圖建模。本文采用的是柵欄建模法，如圖2所示將環境分成n2個面積相同的方格，每個方格均攜帶不同0～3的參數信息，當格子參數為0時表示該區域無障礙物，當格子參數為1時表示該區域含有障礙物，當格子參數為2時表示智能體的位置信息，當格子參數為3時表示目標點的位置信息。通過構建柵欄地圖，能夠很好地獲取環境的信息。

圖2 柵欄環境圖

1.2 任務分配

任務分配是多智能體協同合作中的一個重要研究內容。多Agent的路徑規劃的任務分配問題為：現假設系統環境中存在m個目標點，每個目標點至少一個Agent到達，所有目標點都有Agent到達時任務完成。該任務分配的目標是將多個目標點分別分配給Agent，以實現整體Agent到達目標點的路徑總和最短。

1.3 多Agent路徑規劃算法

多Agent路徑規劃算法主要解決的問題是多個Agent的路徑規劃問題。本文采用的是基于強化學習的多Agent路徑規劃方法，多個Agent在同一環境中，不斷與環境交互，根據環境的反饋進一步優化動作，完成整體的路徑規劃。對多個Agent進行路徑規劃主要有三個目標：一是對多個Agent進行路線規劃時要考慮Agent間的路徑沖突問題，避免多個Agent相撞；二是多個Agent進行路線選擇時要避開障礙物；三是多個Agent到達目標點的路徑總和盡可能的短。

2 基于強化學習的多Agent路徑規劃

2.1 強化學習相關理論

強化學習是一種無監督學習方法，Agent通過與動態環境的反復交互，學會選擇最優或近最優的行為以實現其長期目標[14]。Sutton和Barto定義了強化學習方法的四個關鍵要素：策略、獎賞函數、價值函數、環境模型[15]。強化學習的基本模型主要包括環境和智能體兩部分，如圖3所示。

圖3 強化學習基本模型

在圖3中，Agent根據當前所處的環境狀態，執行一個動作與環境交互，從環境中得到一個獎勵，同時到達新的狀態，進行學習更新策略，接著再執行一個動作作用于環境，不斷重復此過程，優化策略完成任務。

很多強化學習問題可以形式化為馬爾可夫決策過程(Markov decision process,MDP)。MDP是由〈S,A,P,R,γ〉構成的一個元組，其中：

S是一個有限狀態集；

A是一個有限行為集；

P是集合中基于行為的狀態轉移概率矩陣：

R是基于狀態和行為的獎勵函數：

γ是一個衰減因子：γ∈[0,1]。

2.2 多Agent路徑規劃

在多Agent的強化學習過程中，每個Agent獲得的獎勵不僅僅取決于Agent自身的動作，同時還依賴于其他Agent的動作。因此本文將強化學習的MDP模型擴展為多馬爾科夫決策過程(MDPs)。現假設有n個智能體，每個Agent可以選擇的動作m個(即ai,i=1,2,…,m)，每個Agent的狀態個數為k個(即sj,j=1,2,…,m)，則多個Agent采取的聯合動作可以表示為Ai，多個Agent的聯合狀態可以表示為Si。基于強化學習的基本模型，結合本文的任務目標，本文定義了多Agent的路徑規劃學習框架，具體情況如圖4所示。

圖4 多Agent路徑規劃學習框架

在圖4中，為了提高Agent的學習速度，本文中我們首先對多Agent所處的環境進行了預處理操作，剔除了一些無關的環境狀態，同時將先驗信息更新到知識庫，提高了多Agent的學習效率。在該模型中，多個Agent基于當前所處的狀態St，每個Agent根據知識庫的歷史經驗，按照一定的策略規則采取動作集中的一個動作at，所有的Agent的動作組合成一次聯合動作At作用于環境。當聯合動作At執行完畢后，環境將轉化為一個新的狀態St+1，并且得到一個新的獎勵值Rt+1。然后進行學習，更新歷史經驗，進一步完善知識庫。接著根據Agen所處的新狀態St+1和Rt+1選擇新的聯合動作At+1。多個Agent與環境進行周期性交互，不斷重復“探索-學習-決策-利用”過程，從歷史動作中進行學習更新自己的知識庫，作為歷史經驗指導下次動作選擇。

2.3 多Agent路徑規劃學習算法實現

2.3.1聯合狀態設定準則

2.3.2聯合動作

2.3.3獎勵函數

獎勵函數定義了Agent的學習目標，并確定了Agent基于環境的感知狀態即時行動的價值。由于Agent試圖最大限度地獲得總報酬，因此獎勵函數本質上是用來指導Agent實現其目標的。獎勵函數的設置會決定強化學習算法的收斂速度和程度。常用的獎勵函數設置方法有：稀疏獎勵、形式化獎勵、獎勵系數變化獎勵等。本文采用的是稀疏獎勵的形式定義獎勵函數，設置情況如下式所示：

式中：a,b,c>0。

如式(1)所示，多Agent的路徑規劃目標是讓多個Agent采取一組可以獲得最大獎勵的動作序列，到達指定的目標點。當Agent完成目標時，賦予一個正的獎勵；當Agent碰到靜態障礙物時，賦予一個負的獎勵；當有兩個或以上的Agent相互碰撞時，賦予一個負的獎勵；其他情況的獎勵值為0。

2.3.4價值更新函數

多Agent的路徑規劃采用的是Q-learning算法，在確定所有聯合環境狀態S和聯合動作A后，要生成一個nm×km維的矩陣Q，矩陣中的元素Q(S,A)表示為多個Agent在環境狀態St下選擇動作At的價值。

更新的過程：當多個Agent在環境狀態St下，按照既定的動作選擇策略，選擇一個聯合動作At，執行完動作后Agent到達一個新的環境狀態St+1，這時我們開始更新矩陣Q中的Q(S,A)值。Agent在狀態St+1時選擇Q矩陣對應Q值最大的Q(St+1,At+1)，然后把Q(St+1,At+1)乘上一個衰減值γ并加上到達St+1時所獲取的獎勵R作為現實中Q(S,A)的值,然后減去之前的Q(S,A)，接著乘以一個學習效率α累加上最初的Q(S,A)的值則更新為新的Q(S,A)。具體Q(S,A)值的更新公式如下式所示：

Q(St,At)←Q(St,At)+α[R+

γmaxAt+1Q(St+1,At+1)-Q(St,At)]

(2)

2.3.5動作選擇策略

在強化學習問題中，探索和利用是一對矛盾：探索意味著Agent必須嘗試不同的行為繼而收集更多的信息，利用則是Agent做出當前信息下的最佳決定[15]。探索可能會犧牲一些短期利益，通過搜集更多信息而獲得較為長期準確的利益估計；利用則側重于根據已掌握的信息而做到短期利益最大化。探索不能無止境地進行，否則就犧牲了太多的短期利益進而導致整體利益受損；同時也不能太看重短期利益而忽視一些未探索的可能會帶來巨大利益的行為。

目前，常用的探索方法有：ε-貪婪探索、不確定優先探索以及利用信息價值進行探索等。本文采用的是ε-貪婪探索，這里的ε是Agent隨機選擇的概率(0≤ε≤1)，在概率為1-ε的情況下，Agent使用貪婪的Q值方法選擇Q值最大所對應的一個動作，當存在多個Q值相同的動作時隨機選擇一個；在概率為ε的情況下，Agent從動作集合中隨機選擇動作。

2.3.6多Agent路徑規劃算法步驟

在多Agent的路徑規劃中，多個Agent根據當前所處的環境狀態，不斷地與環境進行交互，在學習過程中對學習結果進行更新修正，用于指導Agent的動作選擇，最終通過不斷的學習，找到一組可以最大化獎勵的動作序列，完成多Agent路徑規劃任務。該方法的偽代碼如算法1所示。

算法1多Agent路徑規劃算法

Initialize：St,Q(s,a)

Repeat(for each episode): InitializeS

WhileStis notST

If (Probability<ε)

chooseAt=maxQ(St)

Else

Random chooseAt

Take actionAt，returnR和S’

UpdateQ(s,a)

S←S’

IfStisST

Break

該算法的具體學習過程的形式化描述如下：

(1) 初始化設置：地圖生成，設置Agent和目標點的數量及初始位置，獎勵函數設置，Q表初始化。

(2) 參數設置：終止學習周期Tmax，學習效率α、衰減度γ和探索度ε。

(3) 根據ε-貪婪策略選擇動作At。

(4) 執行At，返回獎勵值R和下一個狀態St+1。

(5) 按式(2)更新Q值。

(6) 判斷是否滿足終止條件：若滿足終止條件，執行(7)；否則，執行(3)。

(7)T：=T+1，判斷T>Tmax：若成立，則學習結束；否則轉(3)。

3 實驗仿真與分析

3.1 實驗設置

為了驗證該方法的有效性，本文多個Agent的路徑規劃設置了一個虛擬的環境。與文獻[16]一樣，本文創造了不同大小的柵欄地圖環境，其中障礙和目標點是隨機生成的。如圖5所示，我們設置了包含7個障礙、兩個智能體、兩個目標點的7×7大小的原始環境地圖。

圖5 實驗環境

針對同一任務目標，將文獻[16]的方法與本文方法進行實驗對比。其中文獻[16]智能體的動作集合為{U,D,L,R,S}，其中U代表向上，D代表向下，L代表向左，R代表向右，S代表靜止不動。本文方法的兩個Agent的聯合動作集為：

其中文獻[16]的獎勵函數R′設置如式(3)所示，本文方法的獎勵函數R具體設置如式(4)所示。

文獻[16]和本文方法采用同一的學習更新函數的參數設置，如表1所示。

表1 更新函數的參數設置

本次實驗假設兩個智能體在環境中同時運動，不會出現故障情況，每次只能選擇動作集合中的一個，環境是有邊界的，當Agent選擇超出邊界的動作時，強制Agent留在環境內。任務目標是第2行第2列的Agent1到達第5行第6列的目標點，同時第2行第4列的Agent2到達第6行第4列的目標點，在Agent移動期間要避免相撞和避開障礙物。

3.2 實驗結果與分析

為了驗證本文方法的有效性，針對上述同一任務目標，進行兩組實驗，將本文方法與文獻[16]方法進行對比，兩組實驗均訓練4 000次。

本文運用文獻[16]方法進行仿真實驗，該方法分為兩個階段，首先分別對每個智能體進行路徑規劃，其次對發生碰撞的Agent進行動態調整。實驗環境在圖5基礎上，分別進行單個智能體和目標點實驗。首次實驗時其中第2行第2列的Agent1運動軌跡如圖6(a)所示。在圖6(a)中，Agent1在第5個步長時與靜態障礙物發生碰撞，Agent1的動作序列分別為：{D→R→R→D→D}，這是由于首次實驗，Agent并沒有歷史經驗作為決策依據，而是隨機的選擇動作，不斷“試錯”。經過Agent不斷與環境交互，更新Q表，進行動作選擇，Agent的最終路徑規劃路線結果如圖6(b)所示，Agent1到達目標點的總步長為7。

(a) 首次實驗軌跡 (b) 最終運動軌跡圖6 Agent1實驗結果圖

類似地，第2行第4列的Agent2運動軌跡如圖7(a)所示，Agent2在第4個步長時與靜態障礙物發生碰撞，Agent2的動作序列為{L→U→R→R}，經過4 000次學習，得到的最終路徑規劃結果如圖7(b)所示，Agent2到達目標點的總步長為6。

(a) 首次實驗軌跡(b) 最終運動軌跡圖7 Agent2首次實驗運動軌跡

從圖6(b)和圖7(b)可以看出，當兩個Agent在同一環境同時移動時，會在第2行第3列的位置相撞，運用動態規劃思想對Agent的路徑重新調整，最終的路徑規劃如圖8所示。在圖8中兩個Agent在同一環境中同時移動，且能夠躲避障礙物，兩個Agent不會發生相撞，到達目標點路徑最短。

圖8 最終路徑規劃結果

運用本文的方法，在圖5所示的環境中進行實驗。首次實驗時，兩個Agent經過18個步長發生了相撞。這是由于本文的方法加入了先驗信息，有歷史經驗作為決策支持，首次實驗時避免了對障礙的學習，使Agent進行試錯時避開了障礙。經過499次回合訓練后，兩個Agent第一次到達目標點，完成任務的總步長為50。訓練4 000次后最終的路徑規劃結果如圖9所示，總步長為14，其中聯合動作序列為：

{DL→RS→DD→RD→RD→RD→DR}

圖9 回合訓練結果

為了驗證本文的有效性，本文從總探索步數、完成任務的平均步數做了對比，具體情況如圖10、圖11所示。在圖10中，文獻[16]的總探索步數是65 810步，本文方法的總探索步數是54 375步，由于本文方法兩個Agent采取動作時要考慮雙方的位置信息，引入聯合動作，避免了對單個Agent相撞后的路徑重新規劃，減少了17.4%的總探索步數。從圖11得出，本文完成任務的平均步數與文獻[16]相比減少了5步。

圖10 總探索步數

4 結 語

為解決復雜任務下多個Agent路徑規劃問題，本文提出一種基于強化學習的多Agent路徑規劃方法。首先建立了多Agent路徑強化學習模型，并詳細描述了各個基本要素，以及多個Agent如何從歷史數據中積累經驗優化決策。通過仿真實驗表明，該方法是可行、有效的。為了提高該方法的學習效率，本文提出了2種解決方案：(1) 環境預處理，根據實際任務以及多Agent的信息，剔除一些無關的環境狀態；(2) 加入先驗信息的Agent決策Q表，基于先驗信息更新Q表，作為歷史經驗提供給Agent，大大提高了Agent的學習效率，與文獻[16]方法相比，減少了17.4%的總探索步數。下一步將研究多Agent動態目標的路徑規劃問題，實現多Agent在復雜任務下的自主路徑決策。