事件驅(qū)動(dòng)的強(qiáng)化學(xué)習(xí)多智能體編隊(duì)控制

徐鵬，謝廣明,2,3，文家燕,2，高遠(yuǎn)

（1. 廣西科技大學(xué) 電氣與信息工程學(xué)院，廣西 柳州 545006; 2. 北京大學(xué) 工學(xué)院，北京 100871; 3. 北京大學(xué) 海洋研究院，北京 100871）

強(qiáng)化學(xué)習(xí)是受動(dòng)物能有效適應(yīng)環(huán)境的啟發(fā)發(fā)展而來的一種算法?；舅枷胧且栽囧e(cuò)的機(jī)制與環(huán)境進(jìn)行交互，在沒有導(dǎo)師信號(hào)的情況下，使獎(jiǎng)勵(lì)累積最大化，來尋求最優(yōu)的策略[1-3]。目前強(qiáng)化學(xué)習(xí)的行業(yè)應(yīng)用頗廣泛，比如無人駕駛、人形機(jī)器人、智能交通和多智能體協(xié)同等。其中多智能體編隊(duì)的強(qiáng)化學(xué)習(xí)研究是一個(gè)重要的方向[4-5]。文獻(xiàn)[4]設(shè)計(jì)多動(dòng)作回放的馬爾可夫模型，在此框架下，多智能體 Q 學(xué)習(xí)可收斂到最優(yōu)的聯(lián)合行動(dòng)策略。文獻(xiàn)[5]提出一種評(píng)估 Q 值法，多智能體通過交流 Q 值函數(shù)和折扣獎(jiǎng)勵(lì)方差來學(xué)習(xí)世界，較快完成了編隊(duì)任務(wù)。然后，智能體在這些學(xué)習(xí)過程中，需要連續(xù)地與環(huán)境進(jìn)行交互，會(huì)導(dǎo)致大量的通信和計(jì)算資源消耗。因此在有限資源情況下，保證多智能體系統(tǒng)的編隊(duì)性能，考慮如何降低資源消耗是必要的，這也是促使開展本項(xiàng)研究的直接原因。

事件驅(qū)動(dòng)機(jī)制已經(jīng)被證明可以有效地減小大規(guī)模網(wǎng)絡(luò)的通信量[6-7]。綜合已有研究成果，事件驅(qū)動(dòng)條件設(shè)計(jì)主要分為兩類：狀態(tài)相關(guān)[8]和狀態(tài)無關(guān)[9]。其主要做法都是通過檢測智能體采樣前后狀態(tài)的偏差值大小，判斷是否滿足事件驅(qū)動(dòng)條件，來決定間歇性的更新控制輸入，減小控制器與多智能體系統(tǒng)的通信頻率和計(jì)算量[10-12]。文獻(xiàn)[10]較早在狀態(tài)反饋控制器中引入事件驅(qū)動(dòng)控制機(jī)制。文獻(xiàn)[11]考慮多智能體間同步采樣異步觸發(fā)機(jī)制解決多智能體環(huán)形編隊(duì)問題，其中智能體可獨(dú)立地選擇觸發(fā)條件參數(shù)。但是當(dāng)前強(qiáng)化學(xué)習(xí)與事件驅(qū)動(dòng)的結(jié)合相對(duì)較少[13-14]。文獻(xiàn)[13]設(shè)計(jì)事件驅(qū)動(dòng)控制器并應(yīng)用于非線性連續(xù)系統(tǒng)的強(qiáng)化學(xué)習(xí)中，解決了自適應(yīng)動(dòng)態(tài)規(guī)劃問題。文獻(xiàn)[14]提出根據(jù)智能體觀測信息的變化率設(shè)計(jì)觸發(fā)函數(shù)，減少學(xué)習(xí)過程中的計(jì)算資源消耗。

綜合以上分析，本文區(qū)別于傳統(tǒng)的多智能體強(qiáng)化學(xué)習(xí)算法，在資源有限的情況下，考慮將事件驅(qū)動(dòng)和強(qiáng)化學(xué)習(xí)相結(jié)合，側(cè)重于事件驅(qū)動(dòng)在強(qiáng)化學(xué)習(xí)過程中動(dòng)作決策頻率方面的研究。

1 問題描述

1.1 基于強(qiáng)化學(xué)習(xí)的編隊(duì)問題

Z＞0表示正整數(shù)集合。多智能體編隊(duì)問題描述如圖1所示，假設(shè)有 N(N≥2) 個(gè)智能體從初始位置出發(fā)，初始位置為隨機(jī)分布的坐標(biāo)點(diǎn)，抵達(dá)各自的期望位置，每個(gè)智能體對(duì)應(yīng)的期望位置點(diǎn)不同，且期望位置點(diǎn)的數(shù)量等于多智能體個(gè)體的數(shù)量。為便于分析，令多智能體在二維網(wǎng)格中運(yùn)動(dòng)，定義網(wǎng)格的大小為 (xt,i,yt,i)，在二維網(wǎng)格中坐標(biāo) ( xt,i,yt,i) 表示智能體 i 的狀態(tài) st,i∈Z＞20，并朝著對(duì)應(yīng)的期望點(diǎn) Gi(i=1,2,···,N) 運(yùn)動(dòng)，每個(gè)智能體對(duì)應(yīng)的期望位置點(diǎn)會(huì)按照貪婪法則預(yù)先給定。智能體 i 運(yùn)動(dòng)過程中，動(dòng)作集合Ai(s)={上，下，左，右，保持}，因此下一刻狀態(tài)值可能為 (xt,i,yt,i-1)，(xt,i,yt,i+1)，( xt,i-1,yt,i)，( xt,i+1,yt,i) 和 ( xt,i,yt,i)。

綜上所述，基于強(qiáng)化學(xué)習(xí)的多智能體編隊(duì)問題可描述為：智能體與環(huán)境進(jìn)行交互，學(xué)習(xí)動(dòng)作決策策略，最小化群體的動(dòng)作總量 K1，使多智能體抵達(dá)各自的期望位置點(diǎn)，且在運(yùn)動(dòng)過程中不發(fā)生碰撞。在學(xué)習(xí)最優(yōu)動(dòng)作策略過程中，當(dāng)所有智能體都抵達(dá)目標(biāo)位置時(shí)，群體會(huì)得到一個(gè) r+的獎(jiǎng)勵(lì)，否則會(huì)得到 r-的懲罰。每個(gè)智能體都可以與鄰居智能體交互，來獲取其他智能體的獎(jiǎng)勵(lì)信號(hào)。

圖 1 編隊(duì)問題Fig. 1 Formation problem

1.2 分散式馬爾可夫模型

博弈論中智能體的每一個(gè)決策都會(huì)導(dǎo)致狀態(tài)的轉(zhuǎn)移，此時(shí)的決策序列稱為一個(gè)隨機(jī)策略。具有馬爾可夫(Markov)特性的隨機(jī)策略稱為Markov策略(MG)。MG是研究具有離散時(shí)間特性的多智能體系統(tǒng)的重要理論框架。

考慮一個(gè)分散式馬爾可夫模型(decentralized Markov decision processes，DEC-MDPs)，DECMDPs是一個(gè)五元組，其中：I為有限智能體集合；S為狀態(tài)集合；Ai(s)為第 i 個(gè)智能體在狀態(tài) s∈S 下可選動(dòng)作集合，則多智能體在狀態(tài) s 下的聯(lián)合行動(dòng)表示為 A(s)=A1(s)×A2(s)×···×AN(s) ；P為動(dòng)作轉(zhuǎn)移概率；ri表示智能體 i 獎(jiǎng)賞值。在DEC-MDPs中，每個(gè)智能體不依賴全局信息，只保持自身和編隊(duì)期望點(diǎn)的相對(duì)關(guān)系，且每個(gè)智能體只需獲取自身的局部觀測信息，在通信無障礙情況下，這些局部信息的并集為一個(gè)完整的全局信息。多智能體的混合策略組合π=(π1(s),π2(s),···,πN(s)) 構(gòu)成整個(gè)系統(tǒng)的一個(gè)混合策略，策略 π 可看成是狀態(tài)空間 s 到動(dòng)作空間Ai(s) 的映射。求解DEC-MDPs的目的是尋求一個(gè)最優(yōu)策略 π，來最大化系統(tǒng)的回報(bào)值。

1.3 Q 學(xué)習(xí)

Q 學(xué)習(xí)是最早的在線強(qiáng)化學(xué)習(xí)算法，同時(shí)也是強(qiáng)化學(xué)習(xí)最重要的算法之一。Watkins在博士論文中[15]提出了 Q 學(xué)習(xí)算法，如圖2所示，通過與環(huán)境的交互，學(xué)習(xí)環(huán)境狀態(tài)到行為的映射關(guān)系，使智能體從環(huán)境中獲得最大累積獎(jiǎng)賞值，通常 用值函數(shù)來評(píng)價(jià)策略 π 的優(yōu)劣。

圖 2 Q學(xué)習(xí)流程圖Fig. 2 Flow chart of Q-learning

圖2采用的是折扣累積獎(jiǎng)賞，策略 π 的狀態(tài)值函數(shù)為

式中，γ 為折扣因子， s0為初始狀態(tài)。另一種形式的值函數(shù)是狀態(tài)動(dòng)作值函數(shù)：

此時(shí)最優(yōu)策略可以根據(jù)式(1)得到：

那么可借助時(shí)間差分誤差來更新 Q 函數(shù)，智能體將觀測到的數(shù)據(jù)代入 Q 函數(shù)中進(jìn)行迭代學(xué)習(xí)，得到精確的解：

式中，t 為當(dāng)前時(shí)刻； αt為當(dāng)前的學(xué)習(xí)率；a′為狀態(tài)s+1 時(shí)執(zhí)行的動(dòng)作。

Q 學(xué)習(xí)最大的特點(diǎn)是智能體可以通過試錯(cuò)的方式尋求最優(yōu)的策略，因此所有的狀態(tài)動(dòng)作都需要被無限次地遍歷，同時(shí)這也會(huì)造成大量的通信和計(jì)算資源消耗。

2 算法設(shè)計(jì)

為解決經(jīng)典強(qiáng)化學(xué)習(xí)過程中存在通信和計(jì)算資源消耗大問題，本節(jié)在經(jīng)典強(qiáng)化學(xué)習(xí)中引入事件驅(qū)動(dòng)控制機(jī)制。

2.1 事件驅(qū)動(dòng)條件設(shè)計(jì)

在DEC-MDPs中，每個(gè)智能體可獨(dú)立地觀測局部狀態(tài)信息，同時(shí)廣播給附近的其他智能體。觀測結(jié)束后，其根據(jù)上一時(shí)刻觀測與當(dāng)前觀測的狀態(tài)偏差值大小，決定是否要執(zhí)行更新動(dòng)作。這里采用狀態(tài)值 Qt,i(st,i,at,i) 作為智能體 i 在 t 時(shí)刻的當(dāng)前觀測值， Qt,i(st,i,at,i) 可通過查詢Q-Table獲得，則智能體 i 從 t -1 時(shí)刻到 t 時(shí)刻的偏差值可寫成：

式中，t ＞0； ei(t) 為 觀測量的狀態(tài)偏差值；Qt-1,i(st-1,i,at-1,i)為 t -1 時(shí)刻狀態(tài)觀測值。

在基于事件驅(qū)動(dòng)的強(qiáng)化學(xué)習(xí)編隊(duì)問題中，如果智能體 i 在期望位置點(diǎn)上，會(huì)獲得較大的獎(jiǎng)賞值。換句話說，當(dāng)智能體 i 迅速到達(dá)期望位置時(shí)，獲得累積折扣獎(jiǎng)賞值較大。因此，根據(jù)智能體的累積折扣獎(jiǎng)賞值進(jìn)行設(shè)計(jì)狀態(tài)閾值函數(shù)是合理的。但是，狀態(tài)閾值函數(shù)如果僅通過累積折扣獎(jiǎng)賞值去評(píng)估，智能體 i 往往會(huì)獲得自私的策略，不利于學(xué)到群體最優(yōu)的策略。因此，考慮在智能體i 的狀態(tài)閾值函數(shù)中引入當(dāng)前獎(jiǎng)勵(lì)的偏差 δt,i。假設(shè)智能體能觀測到周圍的一圈10個(gè)格子，如果智能體 j 存在于智能體 i 的觀測范圍內(nèi)，稱智能體 j為智能體 i 的鄰居，則 t 時(shí)刻智能體 i 獎(jiǎng)勵(lì)的偏差δt,i可寫成：

式中，Nt,i為智能體 i 在 t 時(shí)刻鄰居集合，|Nt,i|為智能體 i 鄰居個(gè)數(shù)。當(dāng)智能體 i

的狀態(tài)偏差大于狀態(tài)閾值函數(shù)時(shí)，更新智能體 i 的動(dòng)作并對(duì)自身動(dòng)作決策進(jìn)行廣播。同一時(shí)刻里，不一定所有的智能體都會(huì)被驅(qū)動(dòng)，未被驅(qū)動(dòng)的智能體僅接受信息，有利于減少多智能體系統(tǒng)通信和計(jì)算資源的消耗，則事件驅(qū)動(dòng)條件設(shè)計(jì)為式(2)：

式中 0 ＜σi＜1。

2.2 基于事件驅(qū)動(dòng)的 Q 學(xué)習(xí)

如圖3所示，智能體執(zhí)行過程為：當(dāng)智能體感知自己附近有障礙物時(shí)，即優(yōu)先避碰，避碰結(jié)束后重新進(jìn)行編隊(duì)。在通信無障礙的情況下，考慮基于事件驅(qū)動(dòng)的DEC-MDPs，由六元組

圖 3 基于事件驅(qū)動(dòng)的強(qiáng)化學(xué)習(xí)框架Fig. 3 The frame of reinforcement learning with eventtriggered

圖2經(jīng)典的 Q 學(xué)習(xí)是使用一個(gè)合理的策略產(chǎn)生動(dòng)作，根據(jù)動(dòng)作與環(huán)境交互，可得到下一刻的狀態(tài)以及獎(jiǎng)賞值，不斷地優(yōu)化獎(jiǎng)賞值來得到最優(yōu)的 Q 函數(shù)。基于事件驅(qū)動(dòng)的 Q 學(xué)習(xí)不同于經(jīng)典的 Q 學(xué)習(xí)算法，智能體首先判斷事件條件是否觸發(fā)，來決定是否基于當(dāng)前的狀態(tài)值，更新動(dòng)作與環(huán)境進(jìn)行交互。多智能體從各自的初始位置點(diǎn)出發(fā)，當(dāng)每個(gè)智能體都抵達(dá)期望位置點(diǎn)時(shí)，稱為一輪Episode學(xué)習(xí)終止。則對(duì)于事件驅(qū)動(dòng)的強(qiáng)化學(xué)習(xí)多智能體編隊(duì)算法可描述為

1)初始化Q矩陣；

2)初始化多智能體的當(dāng)前狀態(tài) s0；

3)智能體 i 以行為策略( ε - 貪心策略)選擇動(dòng)作 at,i；

4)智能體 i 與環(huán)境交互，獲取下一個(gè)狀態(tài) s′

t和即時(shí)的獎(jiǎng)賞值 rt,i；

5)智能體 i 更新當(dāng)前狀態(tài) st,i和 at,i的 Qt,i(st,i,at,i)值：

式中， 0＜α＜1 為學(xué)習(xí)率， 0＜γ＜1 為折扣因子；

6)如果每個(gè)智能體都抵達(dá)各自期望位置，則終止一輪Episode；

7)判斷是否滿足事件觸發(fā)條件，如果滿足返回步驟3)，不滿足返回步驟4)。

2.3 資源消耗對(duì)比

Q 學(xué)習(xí)中計(jì)算資源消耗，主要體現(xiàn)在遍歷所有的策略來尋求最優(yōu)解。每次學(xué)習(xí)過程中，智能體都要基于當(dāng)前的狀態(tài)遍歷 Q(s,a) 值表，查找一個(gè)最優(yōu)的策略。 Q(s,a) 值表的實(shí)現(xiàn)采用Lookup表格，其中 s∈S 和 a ∈Ai(s)， 表的大小為 S ×A 的乘積的元素個(gè)數(shù)。下面舉例說明 Q(s,a) 表大小，假設(shè)存在 N 個(gè)智能體，每個(gè)智能體有 M 個(gè)動(dòng)作，環(huán)境中共存在 n2狀態(tài)，那么 Q (s,a) 值表的大小為MN×n2N，在 ρ 步中，智能體共需遍歷 MN×n2N×ρ次 Q(s,a) 值表，做 Mρ 次動(dòng)作決策，這需要占用極大的通信和計(jì)算資源。假設(shè)智能體在在 ρ 步中，有 λ 次不被驅(qū)動(dòng)，則通信次數(shù)減少為 M(ρ-λ) 次，遍歷次數(shù)減少為 MN×n2N×(ρ-λ) 次。雖然基于事件驅(qū)動(dòng)的強(qiáng)化學(xué)習(xí)壓縮了整個(gè)學(xué)習(xí)的解空間，但在計(jì)算和通信資源限制下，基于事件驅(qū)動(dòng)的強(qiáng)化學(xué)習(xí)通過減少智能體的動(dòng)作決策，能在短時(shí)間內(nèi)找到一個(gè)動(dòng)作總量為 K2的可行的編隊(duì)策略，通過不斷更新迭代，最終尋求到最小化群體的動(dòng)作總量。

3 數(shù)值仿真分析

為了定量比較經(jīng)典 Q 學(xué)習(xí)和事件驅(qū)動(dòng) Q 學(xué)習(xí)動(dòng)作決策頻率的大小，假設(shè)智能體隨機(jī)初始化在大小為 20×20 的格子世界中，如圖4所示，存在3個(gè)智能體，每個(gè)智能體動(dòng)作集合為 Ai(s)，可觀測到格子的可能為“障礙物”“目標(biāo)點(diǎn)”“普通格子”，獎(jiǎng)賞 ri可寫成式(3)：

式中，當(dāng)智能體 i 未抵達(dá)目標(biāo)點(diǎn)時(shí) ω 為-1，否則為0；智能體 i 抵達(dá)期望點(diǎn)時(shí) β 為-1，否則為0；當(dāng)智能體 i 移動(dòng)到邊界或者撞上 L 型的障礙物時(shí)，智能體保持不動(dòng)，此時(shí) χ 為-1，否則為0；當(dāng)智能體 i 與智能 j 在同一時(shí)刻向同一格子移動(dòng)時(shí)，兩個(gè) 智能體保持不動(dòng)，此時(shí) ζ 為-1，否則為0。

圖 4 多智能體編隊(duì)Fig. 4 Formation of multi-agents systems

表1比較了事件驅(qū)動(dòng) Q 學(xué)習(xí)和經(jīng)典 Q 學(xué)習(xí)的動(dòng)作決策次數(shù)，為方便表達(dá)做如下定義：κ1為經(jīng)典 Q 學(xué)習(xí)決策次數(shù)， κ2為事件驅(qū)動(dòng) Q 學(xué)習(xí)決策次數(shù)，則減少?zèng)Q策率 η 可由如式(4)計(jì)算：

表 1 事件驅(qū)動(dòng)與經(jīng)典 Q 學(xué)習(xí)動(dòng)作決策次數(shù)對(duì)比Table 1 A comparison of action times between event-triggered Q and classical Q case

在同一組 σi=0.05 參數(shù)下，隨著Episode的增加，事件驅(qū)動(dòng) Q 學(xué)習(xí)減少的決策次數(shù)從407 024次增加到671 639次，但減少?zèng)Q策率 η 卻從67.79%下降到44.77%，可得減少?zèng)Q策次數(shù)的增長率逐漸下降。因此隨著算法的漸近收斂，減少的決策次數(shù)會(huì)趨近于一個(gè)飽和值。在同樣Episode下，可得不同 σi值的事件驅(qū)動(dòng)條件都能減少學(xué)習(xí)過程中的動(dòng)作決策頻率。

如圖5所示，基于事件驅(qū)動(dòng) Q 學(xué)習(xí)和經(jīng)典 Q學(xué)習(xí)經(jīng)過200輪Episode訓(xùn)練，可得 K1≈K2，說明兩種算法都成功完成編隊(duì)任務(wù)，且完成編隊(duì)任務(wù)的動(dòng)作次數(shù)趨近一致。相比經(jīng)典 Q 學(xué)習(xí)，基于事件驅(qū)動(dòng) Q 學(xué)習(xí)曲線梯度下降快，說明該算法能較快地找到一個(gè)成功策略，完成編隊(duì)任務(wù)。隨著減少的決策次數(shù)趨近穩(wěn)定，解空間被釋放，通過不斷迭代更新，尋求到最優(yōu)解。

圖 5 基于事件驅(qū)動(dòng) Q 學(xué)習(xí)與經(jīng)典 Q 學(xué)習(xí)動(dòng)作次數(shù)演變Fig. 5 Variation of the number of actions of event- triggered Q and classical Q

圖6對(duì)比了在不同參數(shù)下的事件驅(qū)動(dòng)條件編隊(duì)動(dòng)作次數(shù)的演變情況。結(jié)合表1，在一個(gè)Episode中，雖然 σi參數(shù)變小會(huì)降低編隊(duì)系統(tǒng)的決策率，但同時(shí)也會(huì)增加編隊(duì)的動(dòng)作決策次數(shù)，在基于事件驅(qū)動(dòng)的學(xué)習(xí)過程中，當(dāng) K2(1-η)＜K1事件驅(qū) 動(dòng)函數(shù)被視為有效。

圖 6 基于事件驅(qū)動(dòng) Q 學(xué)習(xí)不同 σi 下的動(dòng)作次數(shù)變化Fig. 6 Variation of the number of actions of eventtriggered

4 結(jié)束語

本文主要研究基于事件驅(qū)動(dòng)的強(qiáng)化學(xué)習(xí)多智能體編隊(duì)問題，側(cè)重于學(xué)習(xí)過程中動(dòng)作決策層面的研究。智能體在與環(huán)境交互中，根據(jù)觀測狀態(tài)值的變化與設(shè)計(jì)的事件驅(qū)動(dòng)條件比較，決定是否執(zhí)行動(dòng)作更新。研究結(jié)果表明，在相同時(shí)間內(nèi)，保證系統(tǒng)可允許編隊(duì)性能的前提下，事件驅(qū)動(dòng)機(jī)制可以降低智能體的動(dòng)作決策頻率和減少通信和計(jì)算資源消耗。因此，引入事件驅(qū)動(dòng)機(jī)制有助于強(qiáng)化學(xué)習(xí)在實(shí)際有限資源環(huán)境中的工程應(yīng)用。未來的工作會(huì)基于現(xiàn)有研究，將事件驅(qū)動(dòng)機(jī)制優(yōu)勢與更多種類的強(qiáng)化學(xué)習(xí)算法相結(jié)合，開展相關(guān)的理論和應(yīng)用研究。