王毅然 經(jīng)小川 田 濤 孫運乾 從帥軍

(中國航天系統(tǒng)科學(xué)與工程研究院 北京 100048)

0 引 言

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

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

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

1 整體框架

多智能體的路徑規(guī)劃整體框架主要包括四個層次：環(huán)境建模層、算法層、任務(wù)分配層、多Agent系統(tǒng)層，如圖1所示。

圖1 整體框架圖

在圖1中，首先對環(huán)境進(jìn)行建模，包括對環(huán)境中障礙、目標(biāo)點等信息設(shè)置，其次通過任務(wù)分配層主要根據(jù)實際任務(wù)劃分多個子任務(wù)，然后算法層接收環(huán)境信息以及多個Agent信息和任務(wù)分配情況，并進(jìn)行計算，將結(jié)果返回給Agent。多Agent系統(tǒng)層與環(huán)境建模層、任務(wù)分配層、算法層進(jìn)行交互，每個Agent均能執(zhí)行動作與環(huán)境交互，同時也和任務(wù)分配模塊的任務(wù)進(jìn)行匹配，通過執(zhí)行算法層，不斷地更新策略，最后得到一組較優(yōu)策略完成多個Agent的路徑規(guī)劃任務(wù)。

1.1 環(huán)境建模

對環(huán)境地圖的建模常用的方法主要有三種：柵欄地圖建模、拓?fù)涞貓D建模和可視地圖建模。本文采用的是柵欄建模法，如圖2所示將環(huán)境分成n2個面積相同的方格，每個方格均攜帶不同0～3的參數(shù)信息，當(dāng)格子參數(shù)為0時表示該區(qū)域無障礙物，當(dāng)格子參數(shù)為1時表示該區(qū)域含有障礙物，當(dāng)格子參數(shù)為2時表示智能體的位置信息，當(dāng)格子參數(shù)為3時表示目標(biāo)點的位置信息。通過構(gòu)建柵欄地圖，能夠很好地獲取環(huán)境的信息。

圖2 柵欄環(huán)境圖

1.2 任務(wù)分配

任務(wù)分配是多智能體協(xié)同合作中的一個重要研究內(nèi)容。多Agent的路徑規(guī)劃的任務(wù)分配問題為：現(xiàn)假設(shè)系統(tǒng)環(huán)境中存在m個目標(biāo)點，每個目標(biāo)點至少一個Agent到達(dá)，所有目標(biāo)點都有Agent到達(dá)時任務(wù)完成。該任務(wù)分配的目標(biāo)是將多個目標(biāo)點分別分配給Agent，以實現(xiàn)整體Agent到達(dá)目標(biāo)點的路徑總和最短。

1.3 多Agent路徑規(guī)劃算法

多Agent路徑規(guī)劃算法主要解決的問題是多個Agent的路徑規(guī)劃問題。本文采用的是基于強(qiáng)化學(xué)習(xí)的多Agent路徑規(guī)劃方法，多個Agent在同一環(huán)境中，不斷與環(huán)境交互，根據(jù)環(huán)境的反饋進(jìn)一步優(yōu)化動作，完成整體的路徑規(guī)劃。對多個Agent進(jìn)行路徑規(guī)劃主要有三個目標(biāo)：一是對多個Agent進(jìn)行路線規(guī)劃時要考慮Agent間的路徑?jīng)_突問題，避免多個Agent相撞；二是多個Agent進(jìn)行路線選擇時要避開障礙物；三是多個Agent到達(dá)目標(biāo)點的路徑總和盡可能的短。

2 基于強(qiáng)化學(xué)習(xí)的多Agent路徑規(guī)劃

2.1 強(qiáng)化學(xué)習(xí)相關(guān)理論

強(qiáng)化學(xué)習(xí)是一種無監(jiān)督學(xué)習(xí)方法，Agent通過與動態(tài)環(huán)境的反復(fù)交互，學(xué)會選擇最優(yōu)或近最優(yōu)的行為以實現(xiàn)其長期目標(biāo)[14]。Sutton和Barto定義了強(qiáng)化學(xué)習(xí)方法的四個關(guān)鍵要素：策略、獎賞函數(shù)、價值函數(shù)、環(huán)境模型[15]。強(qiáng)化學(xué)習(xí)的基本模型主要包括環(huán)境和智能體兩部分，如圖3所示。

圖3 強(qiáng)化學(xué)習(xí)基本模型

在圖3中，Agent根據(jù)當(dāng)前所處的環(huán)境狀態(tài)，執(zhí)行一個動作與環(huán)境交互，從環(huán)境中得到一個獎勵，同時到達(dá)新的狀態(tài)，進(jìn)行學(xué)習(xí)更新策略，接著再執(zhí)行一個動作作用于環(huán)境，不斷重復(fù)此過程，優(yōu)化策略完成任務(wù)。

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

S是一個有限狀態(tài)集；

A是一個有限行為集；

P是集合中基于行為的狀態(tài)轉(zhuǎn)移概率矩陣：

R是基于狀態(tài)和行為的獎勵函數(shù)：

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

2.2 多Agent路徑規(guī)劃

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

圖4 多Agent路徑規(guī)劃學(xué)習(xí)框架

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

2.3 多Agent路徑規(guī)劃學(xué)習(xí)算法實現(xiàn)

2.3.1聯(lián)合狀態(tài)設(shè)定準(zhǔn)則

2.3.2聯(lián)合動作

2.3.3獎勵函數(shù)

獎勵函數(shù)定義了Agent的學(xué)習(xí)目標(biāo)，并確定了Agent基于環(huán)境的感知狀態(tài)即時行動的價值。由于Agent試圖最大限度地獲得總報酬，因此獎勵函數(shù)本質(zhì)上是用來指導(dǎo)Agent實現(xiàn)其目標(biāo)的。獎勵函數(shù)的設(shè)置會決定強(qiáng)化學(xué)習(xí)算法的收斂速度和程度。常用的獎勵函數(shù)設(shè)置方法有：稀疏獎勵、形式化獎勵、獎勵系數(shù)變化獎勵等。本文采用的是稀疏獎勵的形式定義獎勵函數(shù)，設(shè)置情況如下式所示：

式中：a,b,c>0。

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

2.3.4價值更新函數(shù)

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

更新的過程：當(dāng)多個Agent在環(huán)境狀態(tài)St下，按照既定的動作選擇策略，選擇一個聯(lián)合動作At，執(zhí)行完動作后Agent到達(dá)一個新的環(huán)境狀態(tài)St+1，這時我們開始更新矩陣Q中的Q(S,A)值。Agent在狀態(tài)St+1時選擇Q矩陣對應(yīng)Q值最大的Q(St+1,At+1)，然后把Q(St+1,At+1)乘上一個衰減值γ并加上到達(dá)St+1時所獲取的獎勵R作為現(xiàn)實中Q(S,A)的值,然后減去之前的Q(S,A)，接著乘以一個學(xué)習(xí)效率α累加上最初的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動作選擇策略

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

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

2.3.6多Agent路徑規(guī)劃算法步驟

在多Agent的路徑規(guī)劃中，多個Agent根據(jù)當(dāng)前所處的環(huán)境狀態(tài)，不斷地與環(huán)境進(jìn)行交互，在學(xué)習(xí)過程中對學(xué)習(xí)結(jié)果進(jìn)行更新修正，用于指導(dǎo)Agent的動作選擇，最終通過不斷的學(xué)習(xí)，找到一組可以最大化獎勵的動作序列，完成多Agent路徑規(guī)劃任務(wù)。該方法的偽代碼如算法1所示。

算法1多Agent路徑規(guī)劃算法

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

該算法的具體學(xué)習(xí)過程的形式化描述如下：

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

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

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

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

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

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

(7)T：=T+1，判斷T>Tmax：若成立，則學(xué)習(xí)結(jié)束；否則轉(zhuǎn)(3)。

3 實驗仿真與分析

3.1 實驗設(shè)置

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

圖5 實驗環(huán)境

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

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

文獻(xiàn)[16]和本文方法采用同一的學(xué)習(xí)更新函數(shù)的參數(shù)設(shè)置，如表1所示。

表1 更新函數(shù)的參數(shù)設(shè)置

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

3.2 實驗結(jié)果與分析

為了驗證本文方法的有效性，針對上述同一任務(wù)目標(biāo)，進(jìn)行兩組實驗，將本文方法與文獻(xiàn)[16]方法進(jìn)行對比，兩組實驗均訓(xùn)練4 000次。

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

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

類似地，第2行第4列的Agent2運動軌跡如圖7(a)所示，Agent2在第4個步長時與靜態(tài)障礙物發(fā)生碰撞，Agent2的動作序列為{L→U→R→R}，經(jīng)過4 000次學(xué)習(xí)，得到的最終路徑規(guī)劃結(jié)果如圖7(b)所示，Agent2到達(dá)目標(biāo)點的總步長為6。

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

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

圖8 最終路徑規(guī)劃結(jié)果

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

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

圖9 回合訓(xùn)練結(jié)果

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

圖10 總探索步數(shù)

4 結(jié) 語

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