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

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

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

0 引 言

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

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

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

1 整體框架

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

圖1 整體框架圖

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

1.1 環(huán)境建模

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

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

1.2 任務(wù)分配

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

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

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

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

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

強(qiáng)化學(xué)習(xí)是一種無(wú)監(jiān)督學(xué)習(xí)方法，Agent通過與動(dòng)態(tài)環(huán)境的反復(fù)交互，學(xué)會(huì)選擇最優(yōu)或近最優(yōu)的行為以實(shí)現(xiàn)其長(zhǎng)期目標(biāo)[14]。Sutton和Barto定義了強(qiáng)化學(xué)習(xí)方法的四個(gè)關(guān)鍵要素：策略、獎(jiǎng)賞函數(shù)、價(jià)值函數(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í)行一個(gè)動(dòng)作與環(huán)境交互，從環(huán)境中得到一個(gè)獎(jiǎng)勵(lì)，同時(shí)到達(dá)新的狀態(tài)，進(jìn)行學(xué)習(xí)更新策略，接著再執(zhí)行一個(gè)動(dòng)作作用于環(huán)境，不斷重復(fù)此過程，優(yōu)化策略完成任務(wù)。

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

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

A是一個(gè)有限行為集；

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

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

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

2.2 多Agent路徑規(guī)劃

在多Agent的強(qiáng)化學(xué)習(xí)過程中，每個(gè)Agent獲得的獎(jiǎng)勵(lì)不僅僅取決于Agent自身的動(dòng)作，同時(shí)還依賴于其他Agent的動(dòng)作。因此本文將強(qiáng)化學(xué)習(xí)的MDP模型擴(kuò)展為多馬爾科夫決策過程(MDPs)?，F(xiàn)假設(shè)有n個(gè)智能體，每個(gè)Agent可以選擇的動(dòng)作m個(gè)(即ai,i=1,2,…,m)，每個(gè)Agent的狀態(tài)個(gè)數(shù)為k個(gè)(即sj,j=1,2,…,m)，則多個(gè)Agent采取的聯(lián)合動(dòng)作可以表示為Ai，多個(gè)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í)速度，本文中我們首先對(duì)多Agent所處的環(huán)境進(jìn)行了預(yù)處理操作，剔除了一些無(wú)關(guān)的環(huán)境狀態(tài)，同時(shí)將先驗(yàn)信息更新到知識(shí)庫(kù)，提高了多Agent的學(xué)習(xí)效率。在該模型中，多個(gè)Agent基于當(dāng)前所處的狀態(tài)St，每個(gè)Agent根據(jù)知識(shí)庫(kù)的歷史經(jīng)驗(yàn)，按照一定的策略規(guī)則采取動(dòng)作集中的一個(gè)動(dòng)作at，所有的Agent的動(dòng)作組合成一次聯(lián)合動(dòng)作At作用于環(huán)境。當(dāng)聯(lián)合動(dòng)作At執(zhí)行完畢后，環(huán)境將轉(zhuǎn)化為一個(gè)新的狀態(tài)St+1，并且得到一個(gè)新的獎(jiǎng)勵(lì)值Rt+1。然后進(jìn)行學(xué)習(xí)，更新歷史經(jīng)驗(yàn)，進(jìn)一步完善知識(shí)庫(kù)。接著根據(jù)Agen所處的新狀態(tài)St+1和Rt+1選擇新的聯(lián)合動(dòng)作At+1。多個(gè)Agent與環(huán)境進(jìn)行周期性交互，不斷重復(fù)“探索-學(xué)習(xí)-決策-利用”過程，從歷史動(dòng)作中進(jìn)行學(xué)習(xí)更新自己的知識(shí)庫(kù)，作為歷史經(jīng)驗(yàn)指導(dǎo)下次動(dòng)作選擇。

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

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

2.3.2聯(lián)合動(dòng)作

2.3.3獎(jiǎng)勵(lì)函數(shù)

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

式中：a,b,c>0。

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

2.3.4價(jià)值更新函數(shù)

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

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

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

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

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

在多Agent的路徑規(guī)劃中，多個(gè)Agent根據(jù)當(dāng)前所處的環(huán)境狀態(tài)，不斷地與環(huán)境進(jìn)行交互，在學(xué)習(xí)過程中對(duì)學(xué)習(xí)結(jié)果進(jìn)行更新修正，用于指導(dǎo)Agent的動(dòng)作選擇，最終通過不斷的學(xué)習(xí)，找到一組可以最大化獎(jiǎng)勵(lì)的動(dòng)作序列，完成多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)點(diǎn)的數(shù)量及初始位置，獎(jiǎng)勵(lì)函數(shù)設(shè)置，Q表初始化。

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

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

(4) 執(zhí)行At，返回獎(jiǎng)勵(lì)值R和下一個(gè)狀態(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 實(shí)驗(yàn)仿真與分析

3.1 實(shí)驗(yàn)設(shè)置

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

圖5 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

(a) 首次實(shí)驗(yàn)軌跡 (b) 最終運(yùn)動(dòng)軌跡圖6 Agent1實(shí)驗(yàn)結(jié)果圖

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

(a) 首次實(shí)驗(yàn)軌跡(b) 最終運(yùn)動(dòng)軌跡圖7 Agent2首次實(shí)驗(yàn)運(yùn)動(dòng)軌跡

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

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

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

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

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

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

圖10 總探索步數(shù)

4 結(jié) 語(yǔ)

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