黃曉輝，楊凱銘，凌嘉壕

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

0 引言

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

2 問(wèn)題及符號(hào)定義

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

智能體數(shù)量N：將每輛空閑車輛視為一個(gè)智能體，每個(gè)智能體有自己獨(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)合行動(dòng)時(shí)轉(zhuǎn)移到下一個(gè)狀態(tài)時(shí)的概率。

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

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

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

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

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

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

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

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

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

3.2 共享注意力模塊

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

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

接下來(lái)，對(duì)N個(gè)智能體的聯(lián)合價(jià)值Qh求和，得到：

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

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

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

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

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

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

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

實(shí)驗(yàn)分為3 個(gè)部分：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）評(píng)估了數(shù)量不同的車輛和乘客的性能，也就是說(shuō)，車輛和乘客的數(shù)量是根據(jù)地圖大小在一個(gè)范圍內(nèi)隨機(jī)分配的。

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

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

4.2 對(duì)比算法

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

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

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

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

QMIX［9］：該算法采用一個(gè)混合網(wǎng)絡(luò)對(duì)單智能體局部值函數(shù)進(jìn)行合并，并在訓(xùn)練學(xué)習(xí)過(guò)程中加入全局狀態(tài)信息輔助來(lá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)所花時(shí)長(zhǎng)對(duì)比，其中：加粗表示最優(yōu)結(jié)果，下劃線表示次優(yōu)結(jié)果?？梢钥闯鯯ARL 算法平均每次實(shí)驗(yàn)所花時(shí)長(zhǎng)始終最短，在所有車乘組合中都超越了幾種對(duì)比算法。

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

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

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

本節(jié)實(shí)驗(yàn)中，車輛與乘客在一個(gè)區(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%。這說(shuō)明即使面對(duì)車輛和乘客組合可變的復(fù)雜情況，SARL 算法在實(shí)驗(yàn)中依然優(yōu)于對(duì)比算法，在更復(fù)雜更現(xiàn)實(shí)的情況下依然性能穩(wěn)定。

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

5 結(jié)語(yǔ)

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

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