周維慶，王 飛，崔 丹，李 琛

（1.青島大學(xué) 自動化學(xué)院，青島 266071；2.山東省工業(yè)控制重點實驗室，青島 266071；3.山東濰坊煙草有限公司，濰坊 262400；4.大連海事大學(xué) 船舶電氣工程學(xué)院，大連 116026）

隨著科學(xué)技術(shù)的發(fā)展，越來越多的自主移動機器人被投入到現(xiàn)實生活中，如物料搬運機器人[1]，自主清掃機器人[2]，救援機器人[3]等，路徑規(guī)劃任務(wù)也相應(yīng)受到人們的廣泛關(guān)注。路徑規(guī)劃考慮的是使智能體在可以自主避障的前提下找到一條通往目的地的最合適的路徑[4]，常見的應(yīng)用于路徑規(guī)劃的方法有：LPA* 算法[5]、D* 算法[6]、D*Lite 算法[7-8]、Dijkstra 算法[9]、A* 算法[10-12]等。但是上述大部分算法搜索最優(yōu)策略效率較低，隨著狀態(tài)空間、動作空間的增加，算法時間復(fù)雜度和收斂速度呈指數(shù)增長。近些年，基于神經(jīng)網(wǎng)絡(luò)的深度多智能體強化學(xué)習(xí)算法（deep multi-agent reinforcement learning，DMARL）憑借著其強大的計算能力以及泛化能力，在缺少先驗知識的情況下，通過與環(huán)境交互，依然能夠快速地收斂到最優(yōu)策略，這種優(yōu)勢十分適合去優(yōu)化移動機器人路徑規(guī)劃問題。

基于值函數(shù)分解框架下的深度強化學(xué)習(xí)算法是針對多智能體信用分配問題而提出的一類方法，被廣泛應(yīng)用于合作型離散動作環(huán)境中。但是和普通的強化學(xué)習(xí)一樣，算法通過選擇Q 值最大的動作對以獲取最優(yōu)策略。由于訓(xùn)練過程中Q 值函數(shù)未收斂時，對狀態(tài)-動作對的估值并不準(zhǔn)確，因此可能會選取到一些次優(yōu)動作導(dǎo)致算法收斂速度變慢，并占據(jù)更多的計算資源。

為了緩解上述問題，減少算法在決策時的盲目性，本文提出了基于表格記憶下的值函數(shù)分解算法QMIX_TM，其主要的思想是在QMIX 算法的基礎(chǔ)上引入記憶表格Qm，將動作選擇的方式由只根據(jù)Q 值和隨機策略選擇動作這2 種方法變?yōu)楦鶕?jù)記憶表格Qm、Q 值和隨機策略選擇動作這3 種方法。算法訓(xùn)練的前中期主要通過協(xié)調(diào)表格Qm和隨機2 種方法選擇動作，加快算法的收斂速度，并將Qm記錄的數(shù)據(jù)存放到經(jīng)驗池用來訓(xùn)練神經(jīng)網(wǎng)絡(luò)，隨著訓(xùn)練次數(shù)的增加，逐漸減少使用隨機策略的概率，最終僅使用表格Qm和Q 值網(wǎng)絡(luò)2 種方法選擇動作。將QMIX_TM 算法與VDN 算法和QMIX 算法進行比較，在清掃機器人合作清理污漬仿真平臺上驗證了算法的有效性。

由于每個智能體獲取的都是局部觀測，但是最終獲得的全局回報是所有智能體共享的，這就會引發(fā)信用分配問題，從而不利于策略的訓(xùn)練。為了解決這類問題，COMA[13]基于策略梯度，利用反事實基線來推斷每個智能體對總回報的貢獻有多大，以此來優(yōu)化策略。但是當(dāng)聯(lián)合動作空間非常大時，尋找最優(yōu)聯(lián)合動作是非常困難的，因此基于價值函數(shù)分解的一類方法應(yīng)運而生，VDN[14]通過簡單求和的方式把全局Q 值函數(shù)分解為多個q 值函數(shù)，QMIX[15]在保證聯(lián)合動作值函數(shù)與每個智能體動作值函數(shù)之間是單調(diào)的前提下對全局Q 值函數(shù)進行非線性分解，QTRAN[16]直接去學(xué)習(xí)真實全局Q 值函數(shù)，使用該全局Q 值函數(shù)去更新各個智能體的q 值函數(shù)。QPD[17]采用了積分梯度的方法分解全局Q 值，通過局部Q 值更新每個智能體的策略。

相比于以上介紹的算法，QMIX_TM 算法在值函數(shù)分解的思想上，為了解決算法在訓(xùn)練過程中收斂速度慢和數(shù)據(jù)利用率低的問題。QMIX_TM 算法在選擇動作時增加了表格記憶這一方法，緩解了算法盲目探索的問題，加快了算法的收斂速度，并且將表格中記錄的高質(zhì)量數(shù)據(jù)集存入回放經(jīng)驗池中供算法訓(xùn)練，提高了高價值數(shù)據(jù)的利用率。

1 算法介紹

1.1 基于價值函數(shù)分解的深度強化學(xué)習(xí)算法

將聯(lián)合動作價值函數(shù)Qtot（τ，u）分解為多個狀態(tài)-動作價值函數(shù)Qi（τi，ui），每個智能體對應(yīng)一個Qi（τi，ui），這種方法稱為值函數(shù)分解，不同的分解方式對算法的性能有較大影響，本文為了滿足去中心化思想，保證Qtot（τ，u）和Qi（τi，ui）的單調(diào)性，即：

采用QMIX算法的思想，只需保證argmaxQtot（τ，u）滿足式（2）：

式中：τ 表示智能體的聯(lián)合動作觀察歷史；u 表示聯(lián)合動作；τi表示智能體i 的動作觀察歷史；ui表示智能體i 執(zhí)行的動作；n 表示智能體個數(shù)。

為了滿足式（2）中描述的個體最優(yōu)則整體最優(yōu)的條件，Qtot（τ，u）按照圖1 中的方式進行分解。

圖1 值函數(shù)網(wǎng)絡(luò)分解示意圖Fig.1 Schematic diagram of value function network decomposition

定義QMIX_TM 算法的損失函數(shù)，如式（3）所示：

式中：r 為立即回報；s 為全局狀態(tài)；θ 為Q 值網(wǎng)絡(luò)的參數(shù)；θ′為目標(biāo)網(wǎng)絡(luò)的參數(shù)；b 為從回放經(jīng)驗池中選取數(shù)據(jù)量的大小。

1.2 表格記憶

為了提高數(shù)據(jù)利用率，提高算法的收斂速度，本文在訓(xùn)練階段，引入了表格Qm來記錄高價值的狀態(tài)-動作對，引導(dǎo)算法快速收斂到最優(yōu)策略，限制表格Qm的大小為v，防止表格元組過多導(dǎo)致查找困難，當(dāng)超過v 時，則表格Qm會將出現(xiàn)頻率最少的狀態(tài)-動作對刪除并引入新的數(shù)據(jù)到表格中，表格的更新流程如圖2 所示。

圖2 表格記憶更新流程Fig.2 Tabular memory update flow chart

由圖2 可以看出，表格將累積回報作為更新的重要依據(jù)，主要思想是若在相同狀態(tài)下執(zhí)行不同的聯(lián)合動作獲得了更高的累積回報，那么就將此狀態(tài)-動作對視為更有價值的數(shù)據(jù)在表格中更新，并存放于回放經(jīng)驗池中供策略網(wǎng)絡(luò)進行訓(xùn)練。注意：在算法實現(xiàn)中，只有當(dāng)前episode 的累積回報大于以往的episode 的累積回報時，才會根據(jù)圖2 去更新表格Qm。QMIX_TM 算法的訓(xùn)練階段聯(lián)合動作選擇方式如式（5）所示：

式中：ξ∈（0，1），代表0 到1 之間的隨機數(shù)；δ＝0.2+（（0.8-0.0）/train_episode·episode），train_episode 表示策略訓(xùn)練的總輪數(shù)，episode 代表當(dāng)前策略已經(jīng)訓(xùn)練的輪數(shù)。

QMIX_TM 算法的偽代碼如表1 所示。

表1 QMIX_TM 算法Tab.1 QMIX_TM algorithm

2 實驗仿真

2.1 清掃機器人合作清理污漬任務(wù)

圖3 為清掃機器人合作清理污漬任務(wù)，環(huán)境為8×8 的方形迷宮，2 個白色清掃機器人初始位置一致，位于方形迷宮左上角，在環(huán)境初始階段，通道中布滿了污漬，清掃機器人探索過的區(qū)域，代表該區(qū)域的污漬已被清理完畢，帶底紋區(qū)域代表環(huán)境中設(shè)置的障礙物，清掃機器人合作清理污漬任務(wù)目標(biāo)是協(xié)調(diào)2 個智能體躲避障礙物并以最短時間將通道的污漬全部清理掉。狀態(tài)變量包括2 個智能體的位置和通道的污漬是否被清理，智能體i 的動作空間為ai∈｛0，1，2，3｝，分別代表｛上，下，左，右｝這4 個動作。

圖3 清掃機器人合作清理污漬任務(wù)Fig.3 Cleaning robot cooperative transportation task

清理污漬任務(wù)的獎勵函數(shù)定義如下：智能體每執(zhí)行1 個動作后會獲得-0.1 的立即回報，每碰撞到障礙物會獲得-0.2 的立即回報，每清理掉一塊污漬后會獲得+1 的立即回報。

經(jīng)實驗證明，若完全使用隨機策略去探索清掃機器人合作清理污漬任務(wù)，每輪實驗至少需要900個步長才能將污漬全部清理干凈。為了增加挑戰(zhàn)性，設(shè)置每輪訓(xùn)練最大步長為400。

2.2 清掃機器人合作清理污漬任務(wù)實驗數(shù)據(jù)分析

表2 為實驗中各個參數(shù)的設(shè)定數(shù)值，為了防止偶然性，在清掃機器人合作清理污漬任務(wù)上一共進行了50 次實驗，每一次包括L 個episode 用于訓(xùn)練，1000 個episode 用于評價，在評價階段探索率設(shè)定為0，清掃機器人動作選取規(guī)則是：當(dāng)表格中包含當(dāng)前狀態(tài)時，使用表格記錄的對應(yīng)動作，否則使用神經(jīng)網(wǎng)絡(luò)來選取動作。實驗數(shù)據(jù)均取自這50 次實驗的均值。為了驗證算法的魯棒性，將2 個清掃機器人的初始位置修改為地圖的右下角，如圖4 所示，并進行了50 次實驗，在實驗結(jié)果中用QMIX_TM（change）表示。

表2 實驗數(shù)據(jù)Tab.2 Experimental data

圖4 清掃機器人合作清理污漬任務(wù)Fig.4 Cleaning robot cooperative stain cleaning task

圖5 為基于QMIX_TM 算法學(xué)習(xí)到的清掃機器人合作清理污漬任務(wù)最優(yōu)路徑示意圖，圖6 為算法收斂曲線圖，表3～表5 分別表示清掃機器人合作清理污漬任務(wù)成功率、清掃機器人合作清理污漬任務(wù)的平均累積回報和清掃機器人合作清理污漬任務(wù)的平均時間。

表3 清掃機器人合作清理污漬任務(wù)成功率Tab.3 Success rate for cleaning robot cooperation to clean stain task

表4 清掃機器人合作清理污漬任務(wù)的平均累積回報Tab.4 Average cumulative reward for cleaning robot cooperation to clean stain task

表5 清掃機器人合作清理污漬任務(wù)的平均時間Tab.5 Average times for cleaning robot cooperation to clean stain task

圖5 基于QMIX_TM 算法學(xué)習(xí)到的清掃機器人合作清理污漬任務(wù)最優(yōu)路徑Fig.5 Based on the QMIX_TM algorithm learned the optimal path of the cleaning robot cooperative cleaning task of cleaning stains

圖6 算法收斂曲線圖Fig.6 Algorithm convergence graph

2.3 實驗結(jié)果分析

由實驗結(jié)果可以看出，在清掃機器人合作清理污漬任務(wù)中，經(jīng)QMIX_TM 訓(xùn)練后的清掃機器人可以探索出最優(yōu)路徑，以最短時間成功將環(huán)境中的污漬清理干凈，而經(jīng)QMIX 訓(xùn)練后的清掃機器人清理污漬所花費的時間較長，并且在400 個步長內(nèi)不能完全將任務(wù)中的污漬清理干凈。這是因為相比較QMIX 算法，QMIX_TM 引入表格Qm，專門記錄高價值的狀態(tài)-動作對，引導(dǎo)算法快速選擇出最優(yōu)動作，并且將這些高價值的狀態(tài)-動作對存放到經(jīng)驗回放池中供算法訓(xùn)練，可以提高數(shù)據(jù)利用率。因此在相同的訓(xùn)練輪數(shù)下，QMIX_TM 算法與不使用表格記憶方法的QMIX 算法相比，具有更快的收斂速度，可以獲得更令人滿意的效果。

3 結(jié)語

本文基于值函數(shù)分解算法QMIX_TM 對清掃機器人路徑規(guī)劃問題進行了研究，引入表格Qm來記錄高價值狀態(tài)-動作對，以此引導(dǎo)算法快速選擇可以使算法獲得最高累積回報的動作，加速算法的收斂速度，并且將這些數(shù)據(jù)存放到經(jīng)驗回放池中以訓(xùn)練神經(jīng)網(wǎng)絡(luò)，提高數(shù)據(jù)利用率。最后QMIX_TM 通過與QMIX、VDN 算法在清掃機器人合作清理污漬仿真平臺上對比，驗證了QMIX_TM 算法可以有效地解決清掃機器人合作清理污漬任務(wù)。但是針對更加高維的狀態(tài)集或者動作集，使用表格去記錄顯然不是一個明智之舉，未來，將會考慮使用其他方式來替代表格存儲數(shù)據(jù)，將算法應(yīng)用到更為復(fù)雜的實驗環(huán)境中。