基于共享注意力的多智能體強(qiáng)化學(xué)習(xí)訂單派送

黃曉輝，楊凱銘，凌嘉壕

（華東交通大學(xué) 信息工程學(xué)院，南昌 330013）

0 引言

近年來，隨著互聯(lián)網(wǎng)高速發(fā)展，人們的出行方式有了很大改變?！熬W(wǎng)約車”走入了人們的生活，隨時隨地約車、方便快捷且舒適等特點(diǎn)使“網(wǎng)約車”迅速成為人們出行的熱門之選。隨著需求的不斷增長，網(wǎng)約車平臺也面臨著一項(xiàng)難題，即如何高效地將訂單派送給合適的司機(jī)。高效的訂單派送能極大地優(yōu)化交通資源分配，同時提高司機(jī)及平臺收入，并提高用戶體驗(yàn)及出行效率，對交通擁堵的情況也略有改善［1-3］。現(xiàn)今，強(qiáng)化學(xué)習(xí)方法受到了廣泛的關(guān)注，主要被用于解決序列決策問題，并且在解決極其復(fù)雜的決策問題方面取得了巨大的成功［4-7］。例如Mnih 等［8］提出了一種新的智能決策方法，稱為深度Q 網(wǎng)絡(luò)（Deep-Q-Network，DQN），它可以儲存訓(xùn)練中的經(jīng)驗(yàn)，直接從歷史經(jīng)驗(yàn)中學(xué)習(xí)成功的策略。Rashid等［9］提出了一種新穎的基于價值的強(qiáng)化學(xué)習(xí)方法，可以端到端進(jìn)行集中的訓(xùn)練，以分散的方式執(zhí)行策略，稱為混合Q 值網(wǎng)絡(luò)（Q-learning MIXing network，QMIX）。QMIX 設(shè)計(jì)了一個神經(jīng)網(wǎng)絡(luò)來整合每個智能體的局部值函數(shù)得到聯(lián)合動作值函數(shù)，確保整體最優(yōu)解和個體最優(yōu)解的一致?；诖?，De Lima 等［10］提出將QMIX 用于訂單派送，取得了不錯的效果；但是，該算法忽視了車輛與車輛之間的關(guān)聯(lián)，單純地認(rèn)為車輛與車輛是完全獨(dú)立的個體，從而導(dǎo)致車輛基于貪婪的原則選擇訂單，可能錯失整體的更優(yōu)解。本文提出一種基于共享注意力的多智能體強(qiáng)化學(xué)習(xí)（Shared Attention Reinforcement Learning，SARL）算法，在不改變先到先服務(wù)的原則下，融入共享注意力模塊，讓車輛與車輛互相關(guān)注、合作，以獲得整體更優(yōu)解。

本文的主要工作如下：將訂單匹配問題建模為以最快送達(dá)時間為目標(biāo)的馬爾可夫決策過程，并基于此提出了SARL算法；設(shè)計(jì)了一個共享注意力模塊，將注意力機(jī)制與多智能體強(qiáng)化學(xué)習(xí)相結(jié)合用于訂單派送；最后在不同規(guī)模的數(shù)據(jù)集上驗(yàn)證了本文算法的優(yōu)越性以及泛化能力。

1 相關(guān)工作

目前基于強(qiáng)化學(xué)習(xí)的訂單派送算法主要分為兩類：基于價值網(wǎng)絡(luò)的單智能體強(qiáng)化學(xué)習(xí)算法和基于多智能體的強(qiáng)化學(xué)習(xí)算法。

1.1 基于價值網(wǎng)絡(luò)的單智能體強(qiáng)化學(xué)習(xí)算法

該方法主要將整體訂單信息輸入控制中樞，然后由控制中樞經(jīng)過學(xué)習(xí)和訓(xùn)練后分配給合適的車輛完成訂單。如圖1 所示，智能體讀取環(huán)境狀態(tài)信息，通過價值網(wǎng)絡(luò)對狀態(tài)和可行動作進(jìn)行評估，選擇其中一種動作執(zhí)行；動作改變環(huán)境，環(huán)境給出新的狀態(tài)和執(zhí)行該動作的獎勵，以此循環(huán)。這種方法的特點(diǎn)就是集中訓(xùn)練、統(tǒng)一分配，控制中樞會根據(jù)價值網(wǎng)絡(luò)進(jìn)行學(xué)習(xí)，評估每一個動作將帶來的影響價值，然后根據(jù)價值選擇合適的動作。

圖1 深度強(qiáng)化學(xué)習(xí)流程Fig.1 Flow of deep reinforcement learning

Pan 等［11］開發(fā)了一種新的深度強(qiáng)化學(xué)習(xí)算法，稱為層次強(qiáng)化定價（Hierarchical Reinforcement Pricing，HRP）。HRP 解決了由于高維空間和時間依賴而產(chǎn)生的復(fù)雜性問題，減少了輸入空間和訓(xùn)練損失。與現(xiàn)有算法相比，HRP 算法提高了收斂性，取得了更好的性能。Tang 等［12］提出了小腦價值網(wǎng)絡(luò)（Cerebellar Value NETwork，CVNET）模型，該模型將地圖分層平鋪，然后通過小腦嵌入組合在一起，幫助網(wǎng)絡(luò)學(xué)習(xí)比經(jīng)緯度更抽象的概念比如街道、小區(qū)、城市等；其次針對不同區(qū)域比如市中心或者郊區(qū)網(wǎng)絡(luò)能自適應(yīng)學(xué)習(xí)并結(jié)合不同地圖精度來獲得更準(zhǔn)確的狀態(tài)表達(dá)。Wang 等［13］提出了基于行動搜索的深度Q 網(wǎng)絡(luò)學(xué)習(xí)方法，為了提高模型的適應(yīng)性和效率，還提出了一種相關(guān)特征漸進(jìn)遷移的方法，并證明了先從源城市學(xué)習(xí)到分配策略，然后再將它遷移到目標(biāo)城市或者同一個城市的不同時間的方法，比沒有遷移的學(xué)習(xí)效果更好。van Hasselt 等［14］提出了一種新的時差學(xué)習(xí)算法——多Q 學(xué)習(xí)（Multi Q-Learning，MQL）。MQL 算法試圖通過使用多動作值函數(shù)近似來提高值估計(jì)的穩(wěn)定性。Chilukuri 等［15］提出了時間約束網(wǎng)絡(luò)中聯(lián)合路由和調(diào)度的深度強(qiáng)化學(xué)習(xí)（deep REinforcement learning method for joint routing and sCheduling in time-ConstrainEd network，RECCE）算法，用于集中控制時間受限網(wǎng)絡(luò)中的聯(lián)合路由與調(diào)度，不同于其他啟發(fā)式算法在每個時間間隙中考慮相同的調(diào)度標(biāo)準(zhǔn)（如松弛性、相對截止日期），RECCE 利用深度強(qiáng)化學(xué)習(xí)應(yīng)用不同的標(biāo)準(zhǔn)在每個時隙中轉(zhuǎn)發(fā)數(shù)據(jù)包，結(jié)果表明RECCE 效果顯著。

1.2 基于多智能體的強(qiáng)化學(xué)習(xí)算法

多智能體強(qiáng)化學(xué)習(xí)主要是讓每一個智能體做自己的決策，一般執(zhí)行三種任務(wù)，完全合作任務(wù)（訂單派送一般被認(rèn)為是完全合作任務(wù)）、完全對抗任務(wù)和混合任務(wù)。每個智能體會根據(jù)相應(yīng)值網(wǎng)絡(luò)學(xué)習(xí)出一個價值，再通過特定網(wǎng)絡(luò)將價值組合得到聯(lián)合動作-狀態(tài)的總獎勵值。Rashid 等［9］提出的QMIX 網(wǎng)絡(luò)將聯(lián)合作用值估計(jì)為每個智能體值的復(fù)雜非線性組合，這些值只以局部觀察為條件，在結(jié)構(gòu)上強(qiáng)制每個智能體的聯(lián)合動作值是單調(diào)的，這使非策略學(xué)習(xí)中的聯(lián)合動作值更易最大化，并保證了集中式和分散式策略之間的一致性。針對QMIX 的局限性，Son 等［16］提出了分解變換協(xié)作多智能體強(qiáng)化學(xué)習(xí)（Q-learning to factorize with TRANsformation for cooperative multi-agent reinforcement learning，QTRAN）。QTRAN 擺脫了結(jié)構(gòu)約束，采用了一種新的方法將原來的聯(lián)合作用值函數(shù)轉(zhuǎn)換為易于分解的聯(lián)合作用值函數(shù)，并且具有相同的最優(yōu)作用。QTRAN 保證了比QMIX 更通用的因子分解，因此比以前的方法覆蓋了更廣泛的多智能體強(qiáng)化學(xué)習(xí)任務(wù)類別。Cui 等［17］提出了一種基于協(xié)調(diào)度的合作多智能體強(qiáng)化學(xué) 習(xí)方法（Cooperative Multi-Agent Reinforcement Learning method based on Coordination Degree，CMARL-CD），并對其在更一般情況下的動態(tài)特性進(jìn)行了分析，結(jié)果表明CMARL-CD 在不需要估計(jì)全局價值函數(shù)的情況下實(shí)現(xiàn)了智能體之間的協(xié)調(diào)。每個智能體估計(jì)自身行動的協(xié)調(diào)度，這代表了成為最優(yōu)行動的潛力。Liu 等［18］提出了COPA，一個教練-選手框架，假設(shè)教練對環(huán)境有全局觀，并通過分配個人策略來協(xié)調(diào)只有部分觀點(diǎn)的球員。具體來說，采用教練和球員的注意力機(jī)制；提出一個變分目標(biāo)來規(guī)范學(xué)習(xí)；設(shè)計(jì)一種自適應(yīng)的溝通方式，讓教練決定何時與選手溝通。Luo 等［19］提出了一種新的基于動作級聯(lián)的策略優(yōu)化方法，將電動汽車重新定位的動作分解為兩個后續(xù)的、有條件依賴的子動作，并使用兩個連通網(wǎng)絡(luò)來求解制定的多智能強(qiáng)化學(xué)習(xí)任務(wù)。Zhou 等［20］提出了一種基于多智能體強(qiáng)化學(xué)習(xí)的分散執(zhí)行訂單調(diào)度方法，以解決大規(guī)模訂單調(diào)度問題。與以前的協(xié)作多智能體強(qiáng)化學(xué)習(xí)算法不同，所有智能體在聯(lián)合策略評估的指導(dǎo)下獨(dú)立工作，因?yàn)橹悄荏w之間不需要通信或顯式合作。

2 問題及符號定義

本文是一個在線學(xué)習(xí)問題，首先將問題建模為馬爾可夫決策過程G=(N，S，A，R，P，γ)，其中N、S、A、R、P、γ分別為智能體的數(shù)量、狀態(tài)集、動作空間、獎勵函數(shù)、轉(zhuǎn)移概率函數(shù)、折扣因子。它們的定義如下：

智能體數(shù)量N：將每輛空閑車輛視為一個智能體，每個智能體有自己獨(dú)立的決策，它的目標(biāo)是將發(fā)送訂單的乘客送到目的地；智能體之間彼此獨(dú)立，只負(fù)責(zé)自己的決策。

狀態(tài)轉(zhuǎn)移概率函數(shù)P(st+1|st，at)：S×A→[0，1]，它表示當(dāng)前狀態(tài)采取聯(lián)合行動時轉(zhuǎn)移到下一個狀態(tài)時的概率。

在強(qiáng)化學(xué)習(xí)過程中，需要度量每一個動作以及車輛聯(lián)合動作的價值：

聯(lián)合總價值Qtot：表示總體價值，即所有智能體執(zhí)行動作后產(chǎn)生的共同價值，它的大小表示整體行為的好壞。

3 基于共享注意力的多智能體強(qiáng)化學(xué)習(xí)算法

SARL 算法的整體框架主要分為兩層：第一層為計(jì)算個體價值的智能體網(wǎng)絡(luò)；第二層為計(jì)算聯(lián)合價值的共享注意力模塊。

3.1 計(jì)算Qi的智能體網(wǎng)絡(luò)

SARL 的框架如圖2 所示：第一層網(wǎng)絡(luò)采用DQN 估計(jì)個體價值，采用DQN 的優(yōu)勢是可以更準(zhǔn)確地估算個體價值。如果乘客或者車輛不在地圖上，所有坐標(biāo)信息都會被設(shè)置為0，每位乘客都會與一輛汽車配對，作為整體行動的一部分。網(wǎng)絡(luò)將為每個乘客匹配車輛并估算個體價值，并輸出具有最大個體價值的動作。整體損失函數(shù)為：

圖2 SARL的整體框架Fig.2 Overall framework of SARL

G為Huber 損失函數(shù)，定義如下：

Huber 損失函數(shù)的優(yōu)勢在于當(dāng)對動作價值的估計(jì)有噪聲時，例如出現(xiàn)經(jīng)驗(yàn)回訪池中沒有的狀態(tài)-動作對，它對噪聲是魯棒的，在這種情況下可以防止梯度爆炸。Huber 損失結(jié)合了平均絕對誤差和均方誤差的優(yōu)點(diǎn)，對異常點(diǎn)更加魯棒。

3.2 共享注意力模塊

共享注意力模塊是對多頭注意力機(jī)制的改進(jìn)，框架如圖3 所示。Qtot的計(jì)算公式如下：

圖3 共享注意力模塊Fig.3 Shared attention module

接下來，對N個智能體的聯(lián)合價值Qh求和，得到：

其中：H是多頭注意力的頭數(shù)，也就是說，共享注意力模塊首先利用單頭注意力計(jì)算出聯(lián)合價值Qh，再將這個過次重復(fù)H次，將結(jié)果加在一起得到聯(lián)合總價值Qtot。C（s）是訓(xùn)練中的固有噪聲，可以通過輸入全局狀態(tài)St的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)獲得。

在第一層DQN，對每個智能體輸入同樣的全局狀態(tài)St而不是智能體個體的觀察值，這樣做的目的是每個智能體在學(xué)習(xí)狀態(tài)時都可以考慮到其他智能體位置從而做出選擇，以便多智能體之間的合作。

在第二層共享注意力模塊，把共享特征向量（除第i個智能體以外的所有智能體的狀態(tài)信息）作為輸入而不是個體的觀測值，這樣可以讓網(wǎng)絡(luò)通過Softmax 學(xué)習(xí)車輛之間的動作、位置的相似性，讓智能體選擇動作時更關(guān)注其他智能體的選擇和位置，達(dá)到選擇更優(yōu)聯(lián)合價值的目的。

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

4.1 實(shí)驗(yàn)設(shè)置與評價指標(biāo)

為了對本文算法進(jìn)行評估和對比，采用了文獻(xiàn)［3］中的一個模擬環(huán)境。本文使用地圖為網(wǎng)格地圖，如圖4 所示，每條邊代表一條街道，每個交叉點(diǎn)表示路口，每個交叉點(diǎn)表示附近范圍的集合即車輛只在交叉點(diǎn)處接送乘客。每條道路上都有汽車通行所需時間成本，成本代表了不同交通條件在內(nèi)的因素，根據(jù)現(xiàn)實(shí)路況模擬生成。

圖4 網(wǎng)格地圖Fig.4 Grid map

實(shí)驗(yàn)分為3 個部分：1）在100×100 的地圖上進(jìn)行了6 組車輛與乘客數(shù)量不同的訓(xùn)練及實(shí)驗(yàn)；2）為了驗(yàn)證本算法在不同大小城市的泛化能力，將100×100 的地圖上訓(xùn)練的模型，在10×10 及500×500 的網(wǎng)格大小上進(jìn)行實(shí)驗(yàn)；3）評估了數(shù)量不同的車輛和乘客的性能，也就是說，車輛和乘客的數(shù)量是根據(jù)地圖大小在一個范圍內(nèi)隨機(jī)分配的。

為了保持結(jié)果的客觀性，所有實(shí)驗(yàn)及對比實(shí)驗(yàn)使用同一批參數(shù)，訓(xùn)練次數(shù)相同。

評價指標(biāo)為實(shí)驗(yàn)1 000 次以上每輪實(shí)驗(yàn)平均花費(fèi)時長以及提升率：時長代表這一次實(shí)驗(yàn)該網(wǎng)格地圖中所有乘客都被車輛送達(dá)目的地所花費(fèi)的時間；提升率表示SARL 算法時間效率對比其他算法最優(yōu)時間效率所提升的百分比，即（次優(yōu)算法消耗的時間-SARL 算法消耗的時間）/次優(yōu)算法消耗的時間。

4.2 對比算法

本實(shí)驗(yàn)對比算法如下：

Random［10］：完全隨機(jī)匹配車輛給乘客，不作任何調(diào)度。

Greedy［10］：非基于學(xué)習(xí)的貪婪算法，遵循先到先服務(wù)策略，因?yàn)樘崆耙笥密嚨某丝蜁@得更高的優(yōu)先級，每位乘客都會按距離貪婪地匹配一輛車。

IDQN（Individual Deep-Q-Network）［10］：為了有效地為乘客匹配車輛，為每輛車（即智能體）執(zhí)行一次DQN 算法，根據(jù)價值來選擇合適的動作以獲得最大獎勵。

QMIX［9］：該算法采用一個混合網(wǎng)絡(luò)對單智能體局部值函數(shù)進(jìn)行合并，并在訓(xùn)練學(xué)習(xí)過程中加入全局狀態(tài)信息輔助來提高算法性能。

4.3 不同地圖尺寸的實(shí)驗(yàn)

首先在100×100 網(wǎng)格地圖上共選擇6 組車乘組合（P、C表示在固定人車網(wǎng)格地圖中每回合初始的乘客數(shù)量和車輛數(shù)量）進(jìn)行實(shí)驗(yàn)，訓(xùn)練模型；為了驗(yàn)證模型的泛化能力，在10×10 以及500×500 網(wǎng)格上進(jìn)行同樣的6 組實(shí)驗(yàn)。表1 為平均每次實(shí)驗(yàn)所花時長對比，其中：加粗表示最優(yōu)結(jié)果，下劃線表示次優(yōu)結(jié)果?？梢钥闯鯯ARL 算法平均每次實(shí)驗(yàn)所花時長始終最短，在所有車乘組合中都超越了幾種對比算法。

表1 在不同尺寸地圖上的實(shí)驗(yàn)對比Tab.1 Experimental comparison on different size maps

在100×100 網(wǎng)格上，對比其他算法最優(yōu)時間，在車乘組合為（20，25）時，SARL 提升率達(dá)到最大，為18.03%；在10×10 網(wǎng)格上，在車乘組合（20，25）時，SARL 提升率達(dá)到最大，為18.42%；在500×500 網(wǎng)格上，在車乘組合（9，4）時，SARL提升率達(dá)到最大，為10.08%。這說明SARL 可以在一種地圖大小上訓(xùn)練，然后在另一種地圖大小（無論是更大或是更?。┥线M(jìn)行測試，并且表現(xiàn)良好，說明相比QMIX 等算法，SARL能更好地推廣到不同大小地圖，驗(yàn)證了其泛化能力。

4.4 車輛和乘客組合可變情況下實(shí)驗(yàn)結(jié)果

本節(jié)實(shí)驗(yàn)中，車輛與乘客在一個區(qū)間里隨意變化，這比固定車輛與乘客組合更現(xiàn)實(shí)，也更難，因?yàn)槟Ｐ捅仨氝m應(yīng)更多變的環(huán)境因素。在10×10 的網(wǎng)格地圖上，車輛與乘客在數(shù)量1 至10 隨機(jī)變化，即Pmax=10，Cmax=10；在500×500 的網(wǎng)格地圖上，車輛與乘客在1 至20 隨機(jī)變化，即Pmax=20，Cmax=20。結(jié)果如表2 所示，可以看出在10×10 網(wǎng)格上，SARL 算法相比QMIX 算法的提升率達(dá)到了6.28%；在500×500 網(wǎng)格上，SARL算法相比QMIX 算法的提升率達(dá)到了1.24%。這說明即使面對車輛和乘客組合可變的復(fù)雜情況，SARL 算法在實(shí)驗(yàn)中依然優(yōu)于對比算法，在更復(fù)雜更現(xiàn)實(shí)的情況下依然性能穩(wěn)定。

表2 車輛和乘客組合可變時的效率對比Tab.2 Comparison of efficiency with variable vehicle and passenger combinations

5 結(jié)語

多智能體強(qiáng)化學(xué)習(xí)近年來作為人工智能領(lǐng)域的一種熱門算法，被廣泛應(yīng)用于車輛調(diào)度、訂單派送等問題，并取得了不錯的進(jìn)展?；诖耍疚奶岢隽薙ARL——一種新的多智能體強(qiáng)化學(xué)習(xí)框架用于訂單派送，并添加了一個共享注意力模塊以此達(dá)到車輛彼此關(guān)注、合作的目的。結(jié)果表明SARL在時間效率性能上超越了所有對比算法，而且值得注意的是，SARL 在多車合作的實(shí)驗(yàn)場景下表現(xiàn)也很優(yōu)異。

在接下來的研究，一方面準(zhǔn)備優(yōu)化實(shí)驗(yàn)的模擬器，用真實(shí)數(shù)據(jù)來訓(xùn)練模擬器；另一方面，考慮在框架中加入知識遷移，以達(dá)到更好的泛化的目的。