趙鵬程, 高 尚, 于洪梅

(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長春 130012)

眾包(crowdsourcing)是一種利用人群智慧完成任務(wù)的計(jì)算范式. 隨著移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展和移動(dòng)設(shè)備的普及, 空間眾包(space crowdsourcing, SC)[1]成為一種新興的眾包類別. 在SC系統(tǒng)中, 首先請(qǐng)求者將時(shí)空任務(wù)提交到平臺(tái)； 然后在差旅預(yù)算、 任務(wù)期限和技能要求等約束條件下進(jìn)行任務(wù)分配或選擇； 最后工人在截止日期前趕往指定地點(diǎn)完成任務(wù)并獲得報(bào)酬. 目前, 任務(wù)分配作為空間眾包中最基本的挑戰(zhàn), 得到廣泛關(guān)注. 現(xiàn)有的工作存在以下不足： 1) 大多數(shù)只考慮工人或請(qǐng)求者單方面的利益, 若只考慮工人利益, 則會(huì)導(dǎo)致偏遠(yuǎn)地區(qū)的任務(wù)難以完成； 若只考慮請(qǐng)求者利益, 則任務(wù)分配可能會(huì)對(duì)某些工人不公平; 2) 通常只考慮強(qiáng)制工人合作或禁止工人合作的單一場(chǎng)景, 前者忽略了工人的情感和偏好, 而后者不利于工人和請(qǐng)求者利益的最大化； 3) 精確算法由于復(fù)雜度過高而難以在實(shí)際中應(yīng)用, 而貪婪算法僅注重眼前利益, 只能得到次優(yōu)解.

研究表明, 多智能體系統(tǒng)(multi-agent system, MAS)與眾包系統(tǒng)的關(guān)鍵要素和過程聯(lián)系緊密[2], 多主體技術(shù)可用來提高眾包系統(tǒng)的自適應(yīng)性和自組織性, 并解決任務(wù)分配、 任務(wù)分解、 激勵(lì)機(jī)制設(shè)計(jì)等眾包中的典型挑戰(zhàn). 此外, 深度強(qiáng)化學(xué)習(xí)(deep reinforcement learning, DRL)以Markov決策過程為理論框架, 考慮了動(dòng)態(tài)環(huán)境下的即時(shí)回報(bào)和未來回報(bào), 根據(jù)與復(fù)雜環(huán)境交互的經(jīng)驗(yàn), 直接擬合參數(shù)化模型學(xué)習(xí)最優(yōu)策略, 在許多復(fù)雜的實(shí)際問題中都取得了成功. 近年來, 研究者們開始將注意力機(jī)制[3-5]引入DRL模型中, 通過有針對(duì)性地利用輸入信息, 提升了模型的性能[6-7].

基于上述研究, 本文通過定義允許但非強(qiáng)制合作的空間眾包(allow but not force cooperation spatial crowdsourcing, ABNFC-SC)場(chǎng)景, 利用基于A2C(advantage actor-critic)方法的多智能體深度強(qiáng)化學(xué)習(xí)(multi-agent deep reinforcement learning, MADRL)模型解決其中的任務(wù)分配問題. 優(yōu)化目標(biāo)是同時(shí)最大化任務(wù)完成率和工人收益率, 且本文設(shè)計(jì)了同時(shí)考慮請(qǐng)求者利益和工人利益的全局獎(jiǎng)勵(lì)函數(shù). 為提升模型的性能, 引入注意力機(jī)制以指導(dǎo)智能體間的協(xié)作. 實(shí)驗(yàn)結(jié)果證明了本文方法的有效性、 魯棒性和優(yōu)越性.

1 預(yù)備知識(shí)

1.1 多智能體深度強(qiáng)化學(xué)習(xí)與A2C算法

多智能體強(qiáng)化學(xué)習(xí)是強(qiáng)化學(xué)習(xí)的思想和算法在多智能體系統(tǒng)中的應(yīng)用[8-9], 其中各智能體在與環(huán)境互動(dòng)和彼此交流中不斷地學(xué)習(xí)和改進(jìn)自身策略, 所有智能體協(xié)同工作以實(shí)現(xiàn)特定的目標(biāo)[10]. 為解決更大規(guī)模和更高復(fù)雜度的問題, 研究者們將深度學(xué)習(xí)方法[11-12]與傳統(tǒng)的多智能體強(qiáng)化學(xué)習(xí)算法相結(jié)合, 提出了多智能體深度強(qiáng)化學(xué)習(xí).

演員-評(píng)論家(actor-critic, AC)算法是經(jīng)典的強(qiáng)化學(xué)習(xí)方法, 該方法訓(xùn)練一個(gè)充當(dāng)Actor角色的策略網(wǎng)絡(luò)以產(chǎn)生最優(yōu)化策略, 同時(shí)訓(xùn)練一個(gè)充當(dāng)Critic的價(jià)值網(wǎng)絡(luò)對(duì)Actor的動(dòng)作進(jìn)行打分, 并指導(dǎo)Actor的策略更新. 通過引入優(yōu)勢(shì)函數(shù), 可得AC方法擴(kuò)展為A2C方法[13], 實(shí)現(xiàn)了性能的進(jìn)一步提升.

1.2 注意力機(jī)制

注意力機(jī)制的原理是通過訓(xùn)練參數(shù)化模型從輸入信息中提取出與任務(wù)目標(biāo)高度相關(guān)的信息, 排除干擾, 從而提高任務(wù)處理的效率和準(zhǔn)確性. 本文采用經(jīng)典Query-Key-Value模式的注意力機(jī)制[14], 其形式化描述為

(1)

其中Q,K,V為特征向量,dk為Q(或K)的維度.

2 場(chǎng)景定義

本文所用的一些符號(hào)及其意義列于表1.

表1 符號(hào)及描述

2.1 任務(wù)和工人

在每個(gè)時(shí)間步, 任意任務(wù)tj(j∈[1,M])都可定義為一個(gè)七元組tj=〈l,a,d,b,r,f,Ψ〉, 其中:tj.l表示任務(wù)所在位置;tj.a表示任務(wù)被提交到平臺(tái)的時(shí)刻;tj.d表示任務(wù)的截止時(shí)間;tj.b表示任務(wù)預(yù)算;tj.r表示任務(wù)半徑, 即平臺(tái)只為tj分配位于以tj.l為圓心、 以tj.r為半徑范圍內(nèi)的工人;tj.f表示任務(wù)是否允許被多個(gè)工人合作完成,tj.f=1表示允許,tj.f=0表示禁止; 向量tj.Ψ=(ψ1,ψ2,…,ψNΨ)標(biāo)記了任務(wù)的技能要求, 其中NΨ為所有任務(wù)要求技能的總數(shù), 并且對(duì)?k∈[1,NΨ],tj.Ψ.ψk=1表示tj要求對(duì)應(yīng)技能,tj.Ψ.ψk=0表示tj不要求對(duì)應(yīng)技能.

在每個(gè)時(shí)間步, 任意工人wi(i∈[1,N])都可以定義為一個(gè)六元組wi=〈l,v,ξ,f,μ,Ψ〉, 其中:wi.l表示工人的當(dāng)前位置;wi.v表示工人的移動(dòng)速度;wi.ξ表示工人在前往任務(wù)地點(diǎn)行程中單位距離的開銷;wi.f表示工人是否愿意與他人合作,wi.f=1表示愿意,wi.f=0表示不愿意;wi.μ表示失敗概率, 即wi有wi.μ的概率使任務(wù)失敗(由于設(shè)備故障、 主觀放棄等原因)； 與任務(wù)中的對(duì)應(yīng)定義類似, 向量wi.Ψ=(ψ1,ψ2,…,ψNΨ)標(biāo)記了wi擁有的技能.

2.2 技能覆蓋向量

為清楚表達(dá)工人wi對(duì)任務(wù)tj技能要求的滿足程度, 同時(shí)為方便描述, 下面給出技能覆蓋向量(skill cover vector)的概念, 其為一個(gè)NΨ維向量, 定義為

(2)

其中對(duì)?k∈[1,NΨ], 有

(3)

進(jìn)一步, 為Up,j和Uq,j(0

(4)

2.3 約束條件

下面給出wi成為tj的潛在工人的約束條件.潛在工人的含義：wi是tj的潛在分配對(duì)象, 但平臺(tái)最終不一定會(huì)將tj分配給wi.約束條件如下.

1) 空間約束:wi必須位于tj的選擇半徑內(nèi), 即

dist(wi.l,tj.l)≤tj.r,

(5)

其中不等號(hào)左邊表示wi和tj之間的直線距離.

2) 時(shí)間約束:wi必須在tj的截止時(shí)間前到達(dá)任務(wù)地點(diǎn), 即

route(wi.l,tj.l)/wi.v≤(tj.d-tj.a),

(6)

其中不等號(hào)左邊表示從wi.l到tj.l的路線長度.

3) 預(yù)算約束:wi的行程代價(jià)不得超過任務(wù)預(yù)算, 即

Ci,j=wi.ξ·route(wi.l,tj.l)≤tj.b.

(7)

4) 技能約束: 在tj有技能要求的前提下, 如果tj禁止合作或wi不愿合作, 則wi必須具備tj要求的全部技能； 否則,wi只需具備至少一項(xiàng)tj要求的技能即可, 即

(8)

其中ones表示求向量中1的個(gè)數(shù)的函數(shù).

基于上述條件, 定義參數(shù)Fi,j, 規(guī)定若wi和tj滿足上述條件, 則Fi,j=1, 表示wi是tj的潛在工人; 反之,Fi,j=0, 表示wi不是tj的潛在工人.

下面給出由潛在工人組成的工人小組G可獲得tj的必要條件.

1) 整體預(yù)算約束: 小組成員的行程代價(jià)之和不得超過任務(wù)預(yù)算, 即

(9)

2) 整體技能須滿足tj的技能要求, 即令

UG=U1,j⊕U2,j⊕…⊕U|G|,j,

(10)

則

ones(UG)=ones(tj.Ψ).

(11)

特別地, 當(dāng)|G|=1時(shí), 上述條件即為單個(gè)潛在工人可獲得tj的必要條件.

2.4 解決方案

本文將每個(gè)工人建模為一個(gè)智能體, 但MADRL模型中智能體的個(gè)數(shù)和網(wǎng)絡(luò)結(jié)構(gòu)都是固定的, 因此MADRL只支持在固定個(gè)數(shù)的工人和任務(wù)之間進(jìn)行匹配(設(shè)任務(wù)和工人的個(gè)數(shù)分別為M,N), 而現(xiàn)實(shí)中M個(gè)任務(wù)不一定恰好對(duì)應(yīng)N個(gè)潛在工人.本文采用如下方法解決該問題： 在每輪匹配中, 首先利用下列每輪匹配中任務(wù)和工人選擇算法確定實(shí)際參與匹配的工人集合W和任務(wù)集合T; 其次, 若|W|

算法1每輪匹配中任務(wù)和工人選擇算法.

輸入：M,N, 任務(wù)隊(duì)列Qt, 可用工人集合SW, 計(jì)數(shù)器k；

輸出： 參與本輪匹配的任務(wù)集合T和工人集合W；

1) 初始化：T=?,W=?,k=0

2) while TRUE

3)t←Qt.top( )

4)G←GetPotentialWorkers(t,SW)//由約束條件, 從SW中找出t的所有潛在工人, 構(gòu)成集合G

5) ifk+1≤M, |W∪G|≤Nthen

6)k←k+1,W←W∪G,T←T∪{t},Qt.pop( ),SW←SW-G

7) else

8) break

9) end if

10) end while.

圖1 ABNFC-SC工作流程Fig.1 Workflow of ABNFC-SC

本文解決方案的思路如圖1所示， 首先在訓(xùn)練階段的每個(gè)時(shí)間步, 根據(jù)算法1, 由訓(xùn)練數(shù)據(jù)生成M個(gè)任務(wù)和N個(gè)工人/智能體(其中可能包含虛擬的任務(wù)或工人), 并由每個(gè)智能體根據(jù)自身的策略選擇要執(zhí)行的任務(wù). 工人選擇好任務(wù)后, 進(jìn)入任務(wù)反選工人過程, 即對(duì)每個(gè)任務(wù), 根據(jù)約束條件, 通過窮舉搜索, 在選擇了該任務(wù)的工人中選出能以最小代價(jià)完成該任務(wù)的工人或工人小組(如果存在這樣的工人或工人小組). 然后程序模擬工人執(zhí)行任務(wù)的過程, 并根據(jù)執(zhí)行結(jié)果計(jì)算各智能體的立即回報(bào). 最后, 根據(jù)立即回報(bào)更新MADRL模型參數(shù)并開始下一輪匹配. 重復(fù)以上過程直到訓(xùn)練結(jié)束. 注意, 盡管窮舉搜索的復(fù)雜度較高, 但在本文研究的問題中, 選擇同一任務(wù)的工人一般不超過5個(gè), 因此窮舉搜索是完全可行的.

在實(shí)際應(yīng)用階段, 任務(wù)被提交到平臺(tái)后先進(jìn)入任務(wù)隊(duì)列等待, 當(dāng)平臺(tái)上等待的任務(wù)數(shù)量和對(duì)應(yīng)的潛在工人數(shù)量達(dá)到匹配條件(即算法1中循環(huán)的退出條件)時(shí), 平臺(tái)即進(jìn)行一次任務(wù)分配. 首先, 由訓(xùn)練好的MADRL模型在后臺(tái)模擬工人選擇任務(wù)； 然后, 運(yùn)用窮舉搜索, 平臺(tái)反選工人并形成最終的任務(wù)分配方案發(fā)布； 最后, 獲得任務(wù)的工人前往任務(wù)地點(diǎn)執(zhí)行任務(wù)并取得報(bào)酬.

3 模型設(shè)計(jì)

3.1 模型概述

圖2 MA-A2C-AM架構(gòu)Fig.2 Architecture of MA-A2C-AM

本文提出具有注意力機(jī)制的多智能體優(yōu)勢(shì)演員-評(píng)論家(multi-agent advantage actor critic with attention mechanism)模型, 簡稱MA-A2C-AM, 其架構(gòu)如圖2所示. 為解決可擴(kuò)展性問題, 本文采用去中心化結(jié)構(gòu); 為解決環(huán)境非穩(wěn)定問題, 本文利用注意力機(jī)制計(jì)算其他智能體對(duì)智能體i的影響ci, 并將ci和局部觀測(cè)oi一起輸入價(jià)值網(wǎng)絡(luò)Vωi, 使得Critic能根據(jù)局部觀測(cè)和來自其他智能體的有效信息更準(zhǔn)確地評(píng)估當(dāng)前狀態(tài). 進(jìn)一步, 本文同時(shí)將ci引入策略網(wǎng)絡(luò)πθi, 使智能體學(xué)會(huì)彼此合作, 根據(jù)其他智能體的狀態(tài)自適應(yīng)地調(diào)整自身策略, 最終實(shí)現(xiàn)整體利益的最大化.圖2中, i表示除智能體i外其他智能體的集合.

3.2 輸入輸出和獎(jiǎng)勵(lì)函數(shù)

首先定義智能體i的局部觀測(cè)oi為

oi={wi.f,Ii,1,Ii,2,…,Ii,M},

(12)

其中對(duì)?j∈[1,M], 向量Ii,j表示與tj相關(guān)的信息, 表示為

Ii,j=(tj.f,tj.b,Fi,j,Ci,j,Ui,j),

(13)

式中Ci,j為從wi.l到tj.l的行程代價(jià).對(duì)智能體i, 其策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)的輸入均為其局部觀測(cè)oi和其他智能體信息對(duì)它的影響, 即由注意力機(jī)制計(jì)算出的上下文向量ci.

策略網(wǎng)絡(luò)的輸出是一個(gè)概率分布, 輸出節(jié)點(diǎn)有(M+1)個(gè), 其中前M個(gè)節(jié)點(diǎn)的輸出值依次表示選擇任務(wù)t1到任務(wù)tM的概率, 第(M+1)個(gè)節(jié)點(diǎn)的輸出表示不選擇任何任務(wù)的概率.價(jià)值網(wǎng)絡(luò)只有一個(gè)輸出節(jié)點(diǎn), 其輸出是一個(gè)實(shí)數(shù), 表示對(duì)智能體i當(dāng)前狀態(tài)的打分, 即對(duì)智能體i在當(dāng)前狀態(tài)下的折扣累計(jì)回報(bào)估計(jì).

在ABNFC-SC中, 工人之間本質(zhì)上是相互協(xié)作的關(guān)系, 需要相互協(xié)作以完成共同的目標(biāo)----最大化任務(wù)的完成率和工人的整體收益. 因此, 本文將獎(jiǎng)勵(lì)函數(shù)設(shè)置為任務(wù)完成率和工人收益率的加權(quán)和, 且所有智能體共享此獎(jiǎng)勵(lì), 即對(duì)任意?i∈[1,N], 智能體i在時(shí)間步τ的即時(shí)獎(jiǎng)勵(lì)為

(14)

其中α∈[0,1]為權(quán)重參數(shù),Tτ和Mτ分別為第τ個(gè)時(shí)間步發(fā)布和完成的實(shí)際任務(wù)總數(shù),Vτ為第τ個(gè)時(shí)間步發(fā)布的實(shí)際任務(wù)總價(jià)值(即預(yù)算之和),Pτ為第τ個(gè)時(shí)間步工人的總收益(即工人完成的任務(wù)總價(jià)值減去工人總的行程代價(jià)).這些量都可以在訓(xùn)練過程中根據(jù)工人執(zhí)行任務(wù)情況及任務(wù)和工人的屬性計(jì)算.

3.3 工作流程

在時(shí)間步τ, 對(duì)任意智能體i, 首先用全連接層FC1_i對(duì)局部觀測(cè)oi進(jìn)行embedding操作, 得到ei.其次, 利用注意力機(jī)制由ei和ek(k∈i)計(jì)算出上下文向量ci, 然后將ei和ci輸入第二個(gè)全連接層FC2_i_A和FC2_i_C, 再分別經(jīng)過softmax層和linear層得到最終的策略和對(duì)當(dāng)前狀態(tài)的打分.最后, 根據(jù)策略產(chǎn)生動(dòng)作aτ,i, 以所有智能體的聯(lián)合動(dòng)作Aτ=aτ,1×aτ,2×…×aτ,N與環(huán)境互動(dòng), 從而得到即時(shí)獎(jiǎng)勵(lì)rτ,i和新的觀測(cè)oτ,i+1, 并進(jìn)入下一輪迭代.期間, 智能體會(huì)收集軌跡數(shù)據(jù)并適時(shí)更新網(wǎng)絡(luò)參數(shù).

本文將策略網(wǎng)絡(luò)的損失函數(shù)定義為

(15)

其中:τb和τe分別表示minibatch中的第一個(gè)和最后一個(gè)時(shí)間步;Aτ,i為優(yōu)勢(shì)函數(shù),

(16)

γ∈(0,1]為折扣因子.式(15)同時(shí)包含了策略梯度損失和策略熵?fù)p失.策略梯度損失的作用是根據(jù)優(yōu)勢(shì)函數(shù)的正負(fù)增大或減小在未來采取相應(yīng)動(dòng)作的概率, 而引入策略熵?fù)p失的目的是鼓勵(lì)智能體在訓(xùn)練初期多探索不同動(dòng)作, 避免模型短期內(nèi)貪婪地收斂到局部最優(yōu).超參數(shù)β通常是一個(gè)很小的正數(shù), 用于確定熵項(xiàng)的相對(duì)重要性.

為提高價(jià)值網(wǎng)絡(luò)對(duì)當(dāng)前狀態(tài)下預(yù)期回報(bào)的評(píng)估準(zhǔn)確性, 本文將折扣累計(jì)回報(bào)和價(jià)值網(wǎng)絡(luò)輸出之間的均方誤差作為價(jià)值網(wǎng)絡(luò)的損失函數(shù), 即

(17)

3.4 模型訓(xùn)練

算法2MA-A2C-AM訓(xùn)練過程.

輸入： 每個(gè)智能體的價(jià)值網(wǎng)絡(luò)和策略網(wǎng)絡(luò);

輸出： 網(wǎng)絡(luò)參數(shù){θi}i∈[1,N],{ωi}i∈[1,N];

超參數(shù)：α,β,γ,|B|,T,ηθ,ηω//T表示訓(xùn)練的總步數(shù);

2) repeat

3) 對(duì)?i∈[1,N]： 智能體i根據(jù)πθi(·|oτ,i,oτ,i)執(zhí)行動(dòng)作aτ,i

4) 用聯(lián)合動(dòng)作Aτ=aτ,1×aτ,2×…×aτ,N與環(huán)境互動(dòng), 模擬工人執(zhí)行任務(wù)

5) 對(duì)?i∈[1,N]： 智能體i得到獎(jiǎng)勵(lì)rτ,i和新的局部觀測(cè)oτ+1,i

6) 對(duì)?i∈[1,N]：Bi←Bi∪{(τ,oτ,i,aτ,i,rτ,i,oτ+1,i,oτ+1,i)}

7)h←h+1,τ←τ+1,k←k+1

8) ifk=|B| or訓(xùn)練數(shù)據(jù)耗盡

9) 對(duì)?i∈[1,N]： 對(duì)?τ∈Bi, 計(jì)算Rτ,i；θi←θi-ηθθiL(θi)；ωi←ωi-ηωωiL(ωi)；Bi←?

10)k←0

11) end if

12) if 訓(xùn)練數(shù)據(jù)耗盡

13)τ←0,k←0, {Bi←?,o0,i}i∈[1,N]

14) end if

15) untilh≥T.

算法2給出了模型的訓(xùn)練過程. 在時(shí)間步τ, 首先對(duì)?i∈[1,N], 智能體i根據(jù)局部觀測(cè)和策略網(wǎng)絡(luò)選擇動(dòng)作ai.然后程序模擬聯(lián)合動(dòng)作與環(huán)境的交互并計(jì)算即時(shí)獎(jiǎng)勵(lì)rτ,i, 同時(shí)每個(gè)智能體收集自身訓(xùn)練軌跡.當(dāng)樣本的數(shù)量達(dá)到minibatch規(guī)?；蛴?xùn)練數(shù)據(jù)耗盡時(shí), 每個(gè)智能體根據(jù)樣本和價(jià)值網(wǎng)絡(luò)計(jì)算折扣累計(jì)回報(bào)Rτ,i, 并通過小批量梯度更新策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)的參數(shù). 如果訓(xùn)練數(shù)據(jù)耗盡但未達(dá)到總訓(xùn)練步數(shù), 則使用原訓(xùn)練數(shù)據(jù)開始新一輪訓(xùn)練. 迭代以上訓(xùn)練過程, 直到達(dá)到總訓(xùn)練步數(shù).

4 實(shí)驗(yàn)分析

4.1 對(duì)比方法和評(píng)價(jià)指標(biāo)

本文將MA-A2C-AM與MADDPG[15],A2C[13],OG[16](online greedy)等3種方法進(jìn)行性能比較. 其中: MADDPG是經(jīng)典的多智能體深度強(qiáng)化學(xué)習(xí)方法, 采用集中訓(xùn)練分散執(zhí)行架構(gòu), Actor僅依據(jù)局部觀測(cè)做出決策, 而集中式Critic根據(jù)所有智能體的觀測(cè)為Actor打分, 在本文實(shí)驗(yàn)中, MADDPG的工作方式與MA-A2C-AM完全相同, 區(qū)別僅在于兩者采用不同的強(qiáng)化學(xué)習(xí)模型產(chǎn)生策略； A2C是經(jīng)典的單智能體強(qiáng)化學(xué)習(xí)方法, 同樣采用Actor-Critic架構(gòu), 并利用優(yōu)勢(shì)函數(shù)降低估計(jì)的方差, 本文中A2C采用在線分配方法, 為每個(gè)新到達(dá)的任務(wù)選擇合適的工人； A2C無法支持工人合作, 因?yàn)樵诤献鲌?chǎng)景下單智能體強(qiáng)化學(xué)習(xí)的動(dòng)作空間隨潛在工人數(shù)量呈指數(shù)增長； OG是一種在線貪婪算法, 其迭代地嘗試將能以較低的成本覆蓋更多技能的工人分配給當(dāng)前任務(wù), 直到完成任務(wù). 所有基于強(qiáng)化學(xué)習(xí)的方法均使用式(14)作為回報(bào)函數(shù).

本文使用任務(wù)完成率(task completion rate, TCR)和工人收益率(worker profitability rate, WPR)兩項(xiàng)指標(biāo)評(píng)價(jià)各算法的性能, 分別表示為

(18)

(19)

4.2 實(shí)驗(yàn)數(shù)據(jù)和基本設(shè)置

表2 實(shí)驗(yàn)場(chǎng)景設(shè)置

本文將2013-01-01—2018-12-31的數(shù)據(jù), 共1 778 108條, 用于訓(xùn)練, 剩余700 466條數(shù)據(jù)用于測(cè)試. Actor和Critic被同時(shí)訓(xùn)練, 以形成最佳任務(wù)分配策略, 但在測(cè)試時(shí)只需使用Actor產(chǎn)生動(dòng)作, Critic被棄用.

MA-A2C-AM,MADDPG和A2C均采用Leaky ReLU為激活函數(shù), Adam為梯度優(yōu)化器, 神經(jīng)網(wǎng)絡(luò)的權(quán)重和偏置均由機(jī)器學(xué)習(xí)庫PyTorch默認(rèn)初始化. 超參數(shù)β和γ統(tǒng)一設(shè)置為β=0.01,γ=0.98, 所有模型均訓(xùn)練100萬時(shí)間步. 對(duì)MA-A2C-AM, FC1_i及注意力模塊中的全連接層節(jié)點(diǎn)個(gè)數(shù)為24, FC2_i_A和FC2_i_C節(jié)點(diǎn)個(gè)數(shù)為64. 對(duì)MADDPG, Actor隱藏層設(shè)置為{32,16}, Critic隱藏層設(shè)置為{128,64,32}. 為增加早期探索,ε-greedy被用作行為策略, 且在訓(xùn)練的前3/4段,ε從0.8指數(shù)衰減到0.01.對(duì)于A2C, 其價(jià)值網(wǎng)絡(luò)和策略網(wǎng)絡(luò)隱藏層均為{64,32}, 并且任務(wù)的潛在工人上限設(shè)為5, 即在每輪匹配中, 若當(dāng)前任務(wù)的潛在工人不足5位, 則以虛擬工人補(bǔ)充； 若超過5位(實(shí)驗(yàn)中該情況極少發(fā)生), 則選最先找到的5位. 其余超參數(shù)及訓(xùn)練時(shí)長列于表3, 其中訓(xùn)練時(shí)長取多次相同實(shí)驗(yàn)的平均值. 表3中, lr_a和lr_c分別表示Actor和Critic的學(xué)習(xí)率. 實(shí)驗(yàn)的軟硬件設(shè)置為: 系統(tǒng)采用Ubuntu 16.04 LTS, 編程語言采用Python 3.7.4+PyTorch 1.0.0, CPU為Intel Xeon E5-2620×1, GPU為Tesla P40×1.

表3 超參數(shù)和訓(xùn)練時(shí)長

4.3 結(jié)果與分析

本文采用控制變量法進(jìn)行實(shí)驗(yàn), 可變參數(shù)為工人總數(shù)、 任務(wù)半徑、 任務(wù)預(yù)算, 其取值見表2. 其中U(2.1,25),3.0,2 000表示默認(rèn)值. 在每組實(shí)驗(yàn)中, 只改變其中一個(gè)參數(shù), 同時(shí)保持其他參數(shù)為默認(rèn)值. 在進(jìn)行對(duì)比實(shí)驗(yàn)前, 需確定不同實(shí)驗(yàn)條件下M,N,α的最佳取值.

4.3.1 確定最佳M,N值

由于訓(xùn)練強(qiáng)化學(xué)習(xí)模型會(huì)耗費(fèi)大量時(shí)間, 所以通過枚舉(M,N)并進(jìn)行大量實(shí)驗(yàn)確定所有實(shí)驗(yàn)條件下的最佳(M,N)不切實(shí)際, 因此本文結(jié)合有限的實(shí)驗(yàn)推斷不同條件下(M,N)的合理取值.步驟如下：

1) 在表2所列的默認(rèn)實(shí)驗(yàn)條件下, 取α=0.5, 對(duì)某特定M, 依次取M個(gè)連續(xù)的任務(wù)并根據(jù)算法1計(jì)算對(duì)應(yīng)的潛在工人數(shù)量, 記為NM, 可得一系列NM.對(duì)這些NM求平均值并對(duì)結(jié)果取整, 將最終的結(jié)果記為N, 即得到了一個(gè)(M,N)對(duì), 改變M, 最終得到一系列的(M,N)對(duì), 即{(1,3),(2,7),(3,10),(4,13),(5,17),(6,20),(7,24)}.

3) 對(duì)于其他實(shí)驗(yàn)設(shè)置, 首先按步驟1)中的方法找出對(duì)應(yīng)的(M,N)對(duì), 然后選出N值位于步驟2)中最優(yōu)區(qū)間中的(M,N)對(duì), 如果有多個(gè)(M,N)對(duì)符合條件, 則將N值最小的(M,N)對(duì)作為最終結(jié)果.表4列出了不同可變參數(shù)下最終選定的(M,N)對(duì).

4.3.2 確定最佳α值

為找到最合適的比例系數(shù)α, 本文考察了MA-A2C-AM針對(duì)不同α的表現(xiàn).令α在0～1間以0.1為步長變化, 其余參數(shù)采用默認(rèn)值, 觀察MA-A2C-AM在TCR和WPR兩個(gè)指標(biāo)上的變化, 結(jié)果如圖4所示.由圖4可見, 當(dāng)α>0.6時(shí), TCR的增加變得緩慢, 同時(shí)WPR開始下降, 所以實(shí)現(xiàn)整體最大化的α值在0.6附近.進(jìn)一步的實(shí)驗(yàn)證明,α對(duì)不同條件不敏感且MA-A2C-AM上的結(jié)論同樣適用于MADDPG.因此, 在后續(xù)實(shí)驗(yàn)中統(tǒng)一設(shè)置α=0.6.

表4 不同實(shí)驗(yàn)條件下的(M,N)對(duì)

圖3 (M,N)對(duì)對(duì)實(shí)驗(yàn)結(jié)果的影響Fig.3 Effect of (M,N) pairs on experimental results

圖4 α對(duì)實(shí)驗(yàn)結(jié)果的影響Fig.4 Effect of α on experimental results

4.3.3 結(jié)果對(duì)比

確定了最佳的(M,N)和α后, 下面將MA-A2C-AM與其他3種任務(wù)分配方法進(jìn)行性能對(duì)比. 工人總數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響如圖5所示.

圖5 工人總數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響Fig.5 Effect of total number of workers on experimental results

由圖5可見, 隨著可用工人數(shù)量的增加, 所有方法都可以更好地實(shí)現(xiàn)分配. OG雖然允許工人合作, 但其只貪婪地優(yōu)化當(dāng)前任務(wù)的分配, 形成了局部最優(yōu)解, 因而表現(xiàn)最差. 由于A2C無法支持工人間的合作, 因此難以實(shí)現(xiàn)較高的任務(wù)完成率, 在TCR上僅略優(yōu)于OG. A2C在WPR上相對(duì)于OG有較明顯的優(yōu)勢(shì), 表明A2C學(xué)習(xí)到了有利于長期目標(biāo)的策略. MADDPG和MA-A2C-AM優(yōu)于另外兩種方法, 表明合作機(jī)制加上合理的分配策略, 能提高任務(wù)分配的效果, 也顯示出多智能體強(qiáng)化學(xué)習(xí)在解決空間眾包任務(wù)分配問題上的優(yōu)勢(shì). 去中心化的MA-A2C-AM比集中式訓(xùn)練的MADDPG有更好的可擴(kuò)展性, 可以在較多的任務(wù)和工人間進(jìn)行匹配, 并且MA-A2C-AM中的注意力機(jī)制促進(jìn)了智能體間的協(xié)作. 因此, MA-A2C-AM實(shí)現(xiàn)了優(yōu)于MADDPG的分配策略.

圖6 任務(wù)半徑對(duì)實(shí)驗(yàn)結(jié)果的影響Fig.6 Effect of task radius on experimental results

任務(wù)半徑對(duì)實(shí)驗(yàn)結(jié)果的影響如圖6所示. 由圖6可見, 圖6中各方法的排名相對(duì)于圖5沒有變化. 隨著任務(wù)半徑的增大, 可用工人逐漸增多, 原來無法得到工人的任務(wù)可以被較遠(yuǎn)地方的工人執(zhí)行, 因此TCR和WPR隨之提高. 但距離越遠(yuǎn)的工人行程代價(jià)越高, 其收益也越低, WPR的增速隨任務(wù)半徑的增大而逐漸放緩. 特別地, 對(duì)于MADDPG和MA-A2C-AM, 盡管兩者憑借較好的策略使更多的任務(wù)被工人合作完成, 但由于合作小組總的行程代價(jià)與小組規(guī)模成正比, 因此, 當(dāng)任務(wù)半徑大于3.0 km時(shí), 盡管兩者的TCR還略有增加, 但WPR卻幾乎不再增加.

任務(wù)預(yù)算對(duì)實(shí)驗(yàn)結(jié)果的影響如圖7所示. 為簡單, 在圖7中, 任務(wù)預(yù)算區(qū)間用區(qū)間的左側(cè)表示. 由圖7可見, 不同方法的排名仍然沒有變化. 過低的預(yù)算通常不足以抵消工人的行程代價(jià), 而當(dāng)預(yù)算超過任務(wù)半徑內(nèi)最昂貴的工人行程代價(jià)時(shí), 即使再增加預(yù)算, 可用工人也不會(huì)再增加. 由圖7(A)可見, 當(dāng)預(yù)算區(qū)間在[0.4,0.9]時(shí), 所有方法均較差, 而當(dāng)預(yù)算大于1.7時(shí), 所有方法的TCR幾乎都不再增加. 而預(yù)算的增加直接導(dǎo)致了工人收益的增加, 因此圖7(B)中WPR能持續(xù)增長.

圖7 任務(wù)預(yù)算對(duì)實(shí)驗(yàn)結(jié)果的影響Fig.7 Effect of task budget on experimental results

4.4 復(fù)雜度分析

綜上所述, 針對(duì)目前空間眾包場(chǎng)景單一、 分配方法難以兼顧請(qǐng)求者和工人雙方利益的問題, 本文提出了一種基于多智能體深度強(qiáng)化學(xué)習(xí)的空間眾包任務(wù)分配算法. 首先形式化定義了允許但不強(qiáng)制工人合作的空間眾包場(chǎng)景, 然后設(shè)計(jì)了基于多智能體深度強(qiáng)化學(xué)習(xí)模型的分配算法. 為指導(dǎo)智能體間的有效合作, 引入了注意力機(jī)制； 為平衡請(qǐng)求者和工人雙方利益, 設(shè)計(jì)了同時(shí)考慮雙方利益的獎(jiǎng)勵(lì)函數(shù). 對(duì)比實(shí)驗(yàn)結(jié)果表明, 本文方法均實(shí)現(xiàn)了最優(yōu)的任務(wù)完成率和工人收益率, 證明了本文方法的可擴(kuò)展性、 有效性和魯棒性.