李偉科，岳洪偉，王宏民，楊 勇，趙 敏，鄧輔秦,,?

(1. 五邑大學 智能制造學部, 廣東 江門 529020；2. 深圳市人工智能與機器人研究院, 廣東 深圳 518116；3. 深圳市杉川機器人有限公司, 廣東 深圳 518006；4．中電科普天科技股份有限公司研發(fā)中心，廣東 廣州 510310)

隨著計算機技術(shù)、控制理論和人工智能理論的不斷發(fā)展與成熟，模塊化自重構(gòu)機器人(MSRR)系統(tǒng)的研究近年來已經(jīng)成為一個熱點。MSRR系統(tǒng)有多個相同的物理模塊，可以自由地相對移動，相互連接或者斷開。這些模塊通過改變它們的相對位置和連接，重新排列成不同形態(tài)的機器人。MSRR通過避開不同的環(huán)境障礙物，以滿足不同的任務(wù)要求。因此，MSRR系統(tǒng)在通用性、魯棒性和低成本方面要優(yōu)于傳統(tǒng)的固定形態(tài)的機器人。這種系統(tǒng)特別適用于工作環(huán)境大、操作任務(wù)復雜的場合，如緊急搜索、救援、核電站維修等領(lǐng)域。在這些場景中，MSRR必須在短時間內(nèi)到達目標點，形成任務(wù)所需的隊形。因此，文中討論的問題是MSRR如何避開障礙物，在短時間內(nèi)到達指定的目標點(即路徑規(guī)劃)，以形成指定的隊形?；诓煌娜蝿?wù)需求，MSRR可以進一步形成任務(wù)所需的形態(tài)解決復雜未知的任務(wù)。MSRR在形成指定的隊形前，需要規(guī)劃前往指定目標點的最優(yōu)路徑。文獻[12]提出了一種基于網(wǎng)格的滑動立方體自重構(gòu)機器人，并提出了一種基于Cellular Automata的自重構(gòu)算法來控制機器人避開障礙物。文獻[13]受強化學習算法的啟發(fā)，提出一種用于滑動立方體的Million Module March的算法。然而，由于這些算法是在具有滑動立方體形狀的模塊化機器人中實現(xiàn)的，它們受到滑動立方體物理形狀的限制，只能避開立方體模塊大小的障礙物。

文獻[3]將MSRR從一種形態(tài)轉(zhuǎn)換為最終形態(tài)的動作序列定義為自重構(gòu)(SR)過程。在自重構(gòu)問題(SRP)中，研究者使用馬爾科夫決策過程(MDP)來規(guī)劃兩個模塊單元之間的路徑，使偏離目標位置的模塊單元能夠移動到其目標點。然而，基于MDP算法規(guī)劃的路徑很容易相交，導致機器人之間發(fā)生碰撞、鎖死和失去連接。

在強化學習中，智能體是通過與環(huán)境的不斷交互和獎勵信號的反饋學習策略的。文獻[13]受到強化學習的啟發(fā)，提出一種Million Module March的算法，使智能體避開障礙物，并形成指定隊形。文獻[17]將SRP建模為強化學習問題，成功地將Q-learning算法應(yīng)用在智能體中，并讓智能體學習如何自主在相鄰模塊之間形成指定的直線(Line)、連接模塊網(wǎng)格(Mass)和模塊形成的環(huán)路 (Ring)三種形狀。由于傳統(tǒng)的Q-learning算法在訓練的初始階段缺乏對周圍環(huán)境的先驗知識，智能體會隨機選擇動作，造成迭代次數(shù)的浪費和算法收斂速度的緩慢。為了緩解這些問題，文獻[19]提出基于知識共享的Q-learning策略來實現(xiàn)不同智能體之間的信息交互。文獻[20]進一步提出了一種基于環(huán)境知識共享的群體Q-learning算法(SQL-SIE)來加速算法的收斂。然而，上述算法在MSRR進行隊形轉(zhuǎn)換時需要進行二次訓練，以形成不同的隊形形狀。此外，上述算法在訓練智能體從起始點前往目標點時，并沒有合適的獎勵引導智能體向有利于前往目標點的方向移動，這會導致算法的迭代次數(shù)增大，算法難以收斂。為了解決以上問題，文中提出一個兩階段的強化學習算法來解決MSRR的編隊控制問題。在第一階段，利用基于群體和知識共享的Q-learning訓練所有機器人前往二維離散地圖的中心點，以獲得一個包含全局地圖信息的最優(yōu)共享Q表。在這個階段中，文中引入曼哈頓距離作為獎賞值，引導智能體更快向目標點的方向移動，以減小迭代次數(shù)，加快算法的收斂速度。在第二階段，機器人根據(jù)第一階段獲得的最優(yōu)共享Q表和當前所處的位置，找到前往指定目標點的最優(yōu)路徑。

文中算法的貢獻如下：

(1)該算法在第一階段是訓練四周的機器人前往地圖的中心點，所以獲得的最優(yōu)共享Q表包含的地圖信息比較全面，智能體可以根據(jù)這個最優(yōu)共享Q表和當前所處的位置，找到前往地圖任意一點最優(yōu)路徑。

(2)該算法在MSRR進行多次隊形轉(zhuǎn)換時，不需要多次訓練，節(jié)省大量的運行時間，算法的收斂速度快。

(3)該算法引入了曼哈頓距離作為獎賞值，引導智能體向有利于目標點的方向移動，以減小迭代次數(shù)，加快算法的收斂速度。

1 多智能體編隊的問題描述

文中考慮的MSRR系統(tǒng)如圖1所示，這是一種小型的球形機器人，內(nèi)部有兩個在塑料防水殼內(nèi)表面上滾動的電機，使機器人可以移動。

圖1 MSRR系統(tǒng)

文中在數(shù)學上將MSRR建模成智能體，因此將MSRR的編隊控制問題看作是多智能體編隊控制問題。這種問題主要分為兩種：第一種是每個智能體移動到各自指定的目標點以形成指定的隊形。第二種是每個智能體保持初始隊形向目標點移動。文中要解決的是第一種編隊控制問題。智能體需要到達指定的目標點，不能占據(jù)其他智能體的目標點。如果智能體的下一步動作會占據(jù)障礙物或者其他智能體的位置，它將保持當前位置不變。如果智能體到達指定的目標點，它將不再繼續(xù)移動。

編隊控制問題是指智能體從各自的起點出發(fā)，需要避開隨機產(chǎn)生的障礙物，在短時間內(nèi)到達最終目標點，并形成指定的隊形。智能體的起始點隨機設(shè)置在地圖的四周，而目標區(qū)域則是位于地圖的中間區(qū)域。

在文中，多智能體編隊控制問題是一個具有馬爾科夫性質(zhì)的連續(xù)決策問題，因此把它建模成一個強化學習問題。文中將二維離散網(wǎng)格左下角的點作為原點，記為(,)，每個智能體∈{,,…，}獲取當前坐標(,)作為當前狀態(tài)。當智能體在戶外時，通過GPS定位技術(shù)獲得其他智能體的相對位置。

在文中，將智能體在二維網(wǎng)格地圖里的動作空間集合設(shè)置為{,,,}，其中表示向上(,+1)，表示向下(,-1)，表示向左(-1,)，表示向右(+1,)。

2 改進的強化學習算法

2.1 基本強化學習算法

在強化學習算法中，智能體可以不斷地與周圍環(huán)境進行試錯交互，使長期累積獎勵最大化，并將環(huán)境的反饋作為輸入。在整個強化學習與周圍環(huán)境的持續(xù)交互過程中，智能體的正確行為受到獎勵，錯誤行為受到懲罰。強化學習的目的是獲得一個最優(yōu)策略，使智能體可以根據(jù)策略和當前環(huán)境選擇一個最優(yōu)的行動，使累積回報最大化。

累積回報表示為每一時刻回報的總和，表示為：

(1)

表示智能體的內(nèi)部狀態(tài)，表示通過執(zhí)行動作之后獲得的獎勵，∈(0,1]表示折扣因子。

Q-learning是一種經(jīng)典的基于表的強化學習算法。它將狀態(tài)和動作映射到一個動作值函數(shù)中去存儲值，然后根據(jù)值選擇動作以獲得最大獎勵。動作值為(,)，即在某一個時刻環(huán)境狀態(tài)∈下，智能體通過執(zhí)行動作∈能夠獲得的最大獎賞值。在Q-learning算法中，每個智能體通過下式來更新其值：

(,)=(1-)(,)+[+max(+1,)]

(2)

∈(0,1]表示學習率。

2.2 基于群體的強化學習算法

在強化學習中，智能體是通過試錯的方式學習策略的，因此獲得最優(yōu)策略需要花費大量的計算時間，特別是對于復雜的學習問題。遺傳算法、粒子群優(yōu)化算法、蟻群算法等基于群體的算法可以在廣闊的求解空間下快速找到多模態(tài)函數(shù)的全局最優(yōu)解。因此，文中致力于結(jié)合基于群體的算法和強化學習的算法，能夠快速獲得復雜學習問題的最優(yōu)解。

通常，強化學習目標是尋找最優(yōu)策略滿足下式：

=argmax()

(3)

(4)

為了設(shè)計更合理的獎懲機制以有效引導智能體到達各自指定的目標點，以形成不同的隊形，進而能夠形成不同的形態(tài)來解決不同復雜的任務(wù)。文中引入曼哈頓距離，將作為獎賞值，獎勵下一步動作能夠離指定目標點更近的智能體，如下式：

(5)

到達各自指定目標點的智能體將不再移動，并且會獲得100的獎賞值。

2.3 知識共享算法

Q-learning是一種無模型的強化學習算法，通過環(huán)境的反饋為智能體的狀態(tài)和行為構(gòu)造一個獎勵值。在獎懲機制的作用下，正確行為的Q值增大，錯誤行為的Q值減小，使智能體的行為趨于最優(yōu)。因此，每個智能體可以選擇從起點到目標點的最優(yōu)路徑。然而，傳統(tǒng)的Q-learning算法仍然存在以下缺點：

(1)存儲空間要求大；

(2)訓練時間太長；

(3)收斂到最優(yōu)解的速度很慢。

在本文的算法中，不同智能體之間可以交換它們獲得的周圍環(huán)境信息，即知識共享。為了緩解上述的問題，文獻[19]提出了基于知識共享的Q-learning策略來實現(xiàn)學習不同智能體之間進行信息交互。文獻[20]進一步提出了一種基于環(huán)境知識共享的群體Q-learning算法(SQL-SIE)來加速算法的收斂。然而，在智能體進行多次隊形轉(zhuǎn)換的場景中使用這種算法時，需要經(jīng)過多次訓練，才能讓智能體學到形成不同隊形的策略，這會耗費大量的運行時間。為了緩解這種問題，受群體強化學習算法和知識共享算法的啟發(fā)，本文提出一種兩階段強化學習算法。

2.4 兩階段強化學習算法

在現(xiàn)實世界中，人們傾向于將一個復雜的任務(wù)分解成幾個簡單的子任務(wù)，以不同的方式解決它們，然后將它們有機地組合在一起。在解決了這些簡單的子任務(wù)之后，更容易將獲得的知識構(gòu)件轉(zhuǎn)移到其他復雜的問題上。文獻[20]將仿真環(huán)境分解為基礎(chǔ)區(qū)域和目標區(qū)域，還將訓練過程分解為兩個階段，以此加快算法的收斂速度。受上述工作的啟發(fā)，本文將仿真環(huán)境分解為基礎(chǔ)區(qū)域和目標區(qū)域，將每個智能體看作一個獨立的個體，并行執(zhí)行訓練，同時將算法的訓練過程分解為如下兩個階段：

(1)利用基于群體和知識共享的Q-learning訓練所有智能體前往網(wǎng)格地圖的中心點，以獲得一個包含全局地圖信息的最優(yōu)共享Q表；

(2)智能體根據(jù)這個最優(yōu)共享Q表和當前所處的位置，通過避開障礙物，尋找前往指定目標點的最優(yōu)路徑，形成指定的隊形，進而能夠形成不同的形態(tài)來解決不同復雜的任務(wù)。

基于以上兩階段強化學習算法的訓練過程，智能體可以將獲取到的周圍環(huán)境信息進行融合，形成一個最優(yōu)共享Q表。通過這個最優(yōu)共享Q表，智能體能夠及時更新它們自身的學習策略，選擇更優(yōu)的下一步動作。因此，在一些復雜的學習環(huán)境中，智能體通過知識共享算法快速獲取周圍環(huán)境信息以獲得最優(yōu)策略。

3 仿真實驗與分析

本文將文獻[20]中的SQL-SIE算法作為一個基準算法，通過兩個數(shù)值實驗來驗證文中算法的性能。第一個實驗是使用文中算法和SQL-SIE算法分別訓練12、16和20個智能體自主尋找從起始點到指定目標點的無碰撞路徑，以形成矩形的隊形，并統(tǒng)計所有智能體總的探索步數(shù)。第二個實驗是使用文中算法和SQL-SIE算法分別訓練12、16和20個智能體從矩形隊形轉(zhuǎn)換為十字隊形，并統(tǒng)計整個程序的運行時間。

3.1 相關(guān)參數(shù)設(shè)置

在以下數(shù)值實驗中，仿真環(huán)境是一個二維離散網(wǎng)格地圖，地圖四周隨機出現(xiàn)的智能體的數(shù)量為，對應(yīng)著出現(xiàn)在目標區(qū)域的目標點數(shù)量為。文中所有的實驗都是在臺式機上完成的，配置為Intel i9-9900K CPU和內(nèi)存為16GB，以MATLAB2019b編寫代碼。

為了測試文中提出算法的性能，隨機設(shè)置占網(wǎng)格地圖面積20%的障礙物，仿真環(huán)境如圖2所示。藍色圓圈是智能體，粉色正方形是隨機生成且不占據(jù)智能體位置的障礙物，目標區(qū)域是黑色菱形圍成的區(qū)域。

圖2 二維離散網(wǎng)格仿真環(huán)境

實驗中所有算法用到的參數(shù)如表1所示。的初始值為1。每次迭代更新之后，的值則變?yōu)楫斍爸档?.5%，以加快貪心策略的實施。只有當所有的智能體都到達各自指定的目標點時，一次迭代更新才算成功完成。在每次迭代更新中，當智能體的探索步數(shù)超過2000，且不是所有的智能體都達到各自指定的目標點時，則當前迭代更新被認為是失敗的。文中所有數(shù)值實驗的迭代次數(shù)的上限是3500，將最后一個智能體到達目標點的探索步數(shù)作為衡量完成編隊控制任務(wù)的指標。學習率表示智能體對新知識的接受程度，折現(xiàn)因子表示未來獎勵的重要程度。

表1 相關(guān)參數(shù)

3.2 矩形隊形

在這個實驗中，多智能體編隊控制任務(wù)是按照預(yù)先設(shè)定的規(guī)則，自主尋找從起始點到指定目標點的一組無碰撞路徑，以形成矩形的隊形。為了使文中的算法研究更具意義和通用性，在網(wǎng)格地圖的目標區(qū)域內(nèi)也設(shè)置隨機障礙物，同時分別訓練12、16和20個智能體來完成編隊控制任務(wù)，并統(tǒng)計所有智能體總的探索步數(shù)。在本實驗中，文中算法的訓練過程如下所示：

(1)多智能體隨機地出現(xiàn)在二維網(wǎng)格地圖四周；

(2)使用兩階段強化學習算法訓練多智能體，通過避開障礙物，到達地圖的中心點，生成最優(yōu)共享Q表；

(3)基于這個最優(yōu)共享Q表，智能體從中心點出發(fā)，到達各自指定的目標點，以形成矩形隊形。

圖3～圖5是將50×50網(wǎng)格地圖獲得的數(shù)據(jù)，經(jīng)過平滑處理后的結(jié)果(連續(xù)50個數(shù)取均值)，文中算法的收斂速度比SQL-SIE算法快，智能體總的探索步數(shù)更少。

圖3 訓練12個智能體的編隊控制結(jié)果對比

圖4 訓練16個智能體的編隊控制結(jié)果對比

圖5 訓練20個智能體的編隊控制結(jié)果對比

在基于群體的強化學習和知識共享算法的作用下，本文算法融合所有智能體周圍的環(huán)境信息，將環(huán)境信息存儲為一個共享的Q表，并將共享的Q表傳遞給每個智能體。智能體得到這個共享Q表之后，及時更新自己的Q表?；诟潞蟮腝表，智能體根據(jù)當前所處的環(huán)境位置以獲得更好的下一步行動和更大的獎勵值，加快算法的收斂速度。此外，由于本文算法的第一階段是訓練分布在地圖四周的智能體移動到地圖的中心，因此智能體獲得比SQL-SIE算法更全面的地圖信息。通過上述過程，智能體得到最優(yōu)的共享Q表，得到從地圖上任意一點移動到另一點的最優(yōu)路徑。

當在50×50和100×100的網(wǎng)格地圖上使用文中算法分別訓練12、16和20個智能體時，所有智能體在3000迭代次數(shù)后都能獲得到達各自指定目標點的最優(yōu)路徑。然而，使用SQL-SIE算法訓練同樣的智能體在100×100的網(wǎng)格地圖中獲得前往指定目標點的最優(yōu)策略時，超過一半的智能體不能到達各自指定的目標點。根本原因是實驗環(huán)境是一個有限大小的二維離散網(wǎng)格圖，智能體必須避開路上的障礙物，而且在該算法的障礙物設(shè)定中，先到達各自指定目標點的智能體被其他未到達的智能體視為障礙物，其他智能體要避開這些障礙物。因此，一些智能體在前往其指定目標點的途中會受到上述兩種障礙物的阻礙而導致智能體無法繼續(xù)移動。而本文算法是先訓練智能體到達地圖的中心點，則不會出現(xiàn)以上的情形。此外，在SQL-SIE算法的獎勵設(shè)置中，只有當智能體碰到障礙物或到達目標區(qū)域時，智能體才能獲得獎勵。然而，從起始點到目標點，沒有適當?shù)莫剟钜龑е悄荏w向有利于到達目標點的方向移動，導致了出現(xiàn)稀疏獎勵的問題，容易出現(xiàn)在障礙物附近來回走動的現(xiàn)象，使得算法難以收斂到穩(wěn)定狀態(tài)。為了解決上述問題，本文算法將式(2)獎勵給下一步動作距離各自指定目標點更近的智能體。這個獎懲機制能夠引導智能體以最小的探索步數(shù)移動到各自指定的目標點，加快算法的收斂速度。

規(guī)定智能體在每個迭代次數(shù)中的最大探索步數(shù)為2000，如果智能體在當前迭代次數(shù)中花費超過2000探索步數(shù)都無法到達其指定的目標點，2000就作為該智能體到達目標點的最大探索步數(shù)。如表2所示，與SQL-SIE算法相比，在50×50的網(wǎng)格地圖中，本文算法訓練智能體到達指定目標點所需要的總的探索步數(shù)要少將近50%。

表2 50×50網(wǎng)格環(huán)境總的探索步數(shù)

在有限大小的二維網(wǎng)格環(huán)境和有限迭代次數(shù)的情況下，隨著智能體數(shù)量的增加，本文算法的優(yōu)勢更加突出。這是因為隨著智能體數(shù)量的增加，智能體通過知識共享可以更快、更全面地獲取全局信息。事實上，使用文中算法訓練智能體可以得到去往目標點的最優(yōu)路徑，而使用SQL-SIE算法訓練則不能得到最優(yōu)路徑。此外，如表3所示，在100×100的網(wǎng)格地圖中，當使用SQL-SIE算法訓練智能體時，由于存在稀疏獎勵的問題，超過一半的智能體不能到達指定的目標點。因此，當使用文中算法訓練智能體移動到各自的目標點時，得到總的探索步數(shù)將遠小于使用SQL-SIE算法得出總的探索步數(shù)，并且隨著智能體數(shù)量的增加，這個差距會變得更加顯著。

表3 100×100網(wǎng)格環(huán)境總的探索步數(shù)

3.3 隊形轉(zhuǎn)換

為了驗證本文算法在多智能體進行隊形轉(zhuǎn)換的性能要優(yōu)于SQL-SIE算法，文中設(shè)計這個實驗分別訓練12、16和20個智能體來完成隊形轉(zhuǎn)換的任務(wù)，并統(tǒng)計從矩形隊形轉(zhuǎn)換到十字隊形所需要的運行時間。本文算法的訓練過程如下：

(1)訓練網(wǎng)格地圖四周的智能體通過避開障礙物，到達網(wǎng)格地圖的中心點，并生成最優(yōu)共享Q表；

(2)智能體根據(jù)上述的最優(yōu)共享Q表，從中心點移動到各自指定的目標點，形成矩形隊形；

(3)繼續(xù)沿用上述的最優(yōu)共享Q表，智能體從矩形隊形上的目標點繼續(xù)移動到另一組指定的目標點，形成十字隊形。

同時，本實驗使用SQL-SIE算法來完成編隊轉(zhuǎn)換任務(wù)。該任務(wù)的訓練過程主要分為兩個階段：第一階段是訓練智能體從地圖的四邊移動到地圖的中心區(qū)域形成矩形隊形。第二階段是訓練智能體從矩形隊形轉(zhuǎn)換為十字隊形。統(tǒng)計上述兩種算法中所有智能體完成隊形轉(zhuǎn)換任務(wù)所需的運行時間。

如表4所示，在50×50的網(wǎng)格地圖中，使用文中算法完成隊形轉(zhuǎn)換任務(wù)的運行時間比使用SQL-SIE算法快將近5倍。因為文中算法的第一階段是訓練分布在地圖周圍的智能體，使其移動到地圖的中心，因此智能體可以獲得比SQL-SIE算法更全面的地圖信息，從而獲得最優(yōu)的Q表。此外，智能體經(jīng)過第一階段的訓練后，可以得到全地圖的環(huán)境信息融合而成的Q表，因此可以減少智能體的隨機試錯次數(shù)，從而加快算法的收斂速度。通過使用這個最優(yōu)Q表，智能體可以得到從地圖上任意一點移動到另一點的最優(yōu)路徑。智能體在轉(zhuǎn)換隊形時不需要再進行訓練，只需要根據(jù)Q表和當前所處的位置執(zhí)行下一步動作。因此，當智能體從矩形隊形轉(zhuǎn)換為十字隊形時，只需要根據(jù)Q表和當前所處的位置移動到十字隊形上各自指定的目標點，即可快速完成隊形轉(zhuǎn)換任務(wù)。

表4 50×50網(wǎng)格環(huán)境運行時間(s)

如表5所示，在100×100網(wǎng)格地圖中，使用SQL-SIE算法不能分別訓練12、16和20個智能體形成矩形隊形，更不能完成隊形轉(zhuǎn)換任務(wù)，因此本文將100×100網(wǎng)格地圖下使用SQL-SIE算法訓練智能體完成隊形轉(zhuǎn)換任務(wù)的運行時間表示為無窮大。

表5 100×100網(wǎng)格環(huán)境運行時間(s)

4 結(jié) 論

將模塊化機器人編隊控制建模成一個多智能體強化學習問題進行研究。本文研究每個智能體都學習一種最優(yōu)的策略，通過避開障礙物，在最短的時間內(nèi)移動到目標點和形成特定的隊形，以完成編隊控制任務(wù)。本文還研究將多智能體從矩形隊形轉(zhuǎn)換成十字隊形的編隊控制問題。在基于群體和知識共享的基礎(chǔ)上，提出了兩階段強化學習算法。在第一階段，使用基于群體的強化學習算法和知識共享的算法訓練智能體避開隨機產(chǎn)生的障礙物，尋找到達中心點的最優(yōu)路徑。由于這個階段是訓練地圖四周的智能體從起始點前往中心點，為了能夠減小稀疏獎勵的影響，設(shè)計適當?shù)莫剟钜龑е悄荏w向有利于到達中心點的方向移動，從而減少算法迭代次數(shù)，提高算法的收斂速度，文中引入了曼哈頓距離作為獎賞值。因此通過這個階段能夠獲得較為全面的地圖信息，即能得到地圖上任意一點移動到另一點的最優(yōu)路徑。在第二階段，利用第一階段獲得的最優(yōu)共享Q表，訓練智能體從中心點移動到各自指定的目標點，完成編隊任務(wù)。在這個階段中，當智能體進行多次隊形轉(zhuǎn)換時，不需要多次訓練，只需根據(jù)最優(yōu)共享Q表和所處位置，移動到各自指定目標點。實驗結(jié)果表明，該算法具有較好的性能。主要表現(xiàn)在算法收斂速度較快，智能體實現(xiàn)隊形轉(zhuǎn)換任務(wù)需要的時間較短，具有良好的實用性。