黃曉輝，楊凱銘，凌嘉壕

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

0 引言

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

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

1 相關(guān)工作

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

1.1 基于價值網(wǎng)絡的單智能體強化學習算法

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

圖1 深度強化學習流程Fig.1 Flow of deep reinforcement learning

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

1.2 基于多智能體的強化學習算法

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

2 問題及符號定義

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

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

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

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

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

3 基于共享注意力的多智能體強化學習算法

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

3.1 計算Qi的智能體網(wǎng)絡

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

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

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

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

3.2 共享注意力模塊

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

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

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

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

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

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

4 實驗與結(jié)果分析

4.1 實驗設置與評價指標

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

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

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

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

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

4.2 對比算法

本實驗對比算法如下：

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

Greedy［10］：非基于學習的貪婪算法，遵循先到先服務策略，因為提前要求用車的乘客會獲得更高的優(yōu)先級，每位乘客都會按距離貪婪地匹配一輛車。

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

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

4.3 不同地圖尺寸的實驗

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

表1 在不同尺寸地圖上的實驗對比Tab.1 Experimental comparison on different size maps

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

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

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

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

5 結(jié)語

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

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