基于預測算法的在線空間眾包任務分配策略

邢 虎,陳 榮,唐文君

(大連海事大學 信息科學與技術學院,遼寧 大連 116026)

0 概述

隨著移動互聯網技術的發展及移動設備計算與感知能力的提高,空間眾包(Spatial Crowdsourcing,SC)技術應運而生,其能夠利用互聯網上的零散勞動力來執行具有空間特性的現實任務。空間眾包概念由KAZEMI和SHAHABI于2012年[1]提出,并在近幾年得到迅速發展,被廣泛應用于土地利用[2-3]、防災減災[4-5]、資源勘查[6]和環境保護[7]等領域,給人們日常工作和生活帶來了巨大變化,同時為人類社會和經濟的發展起到了推動作用。

任務分配問題是空間眾包的核心問題,主要包括批處理模式[1,8-10]和即時模式[11-12]兩種任務分配模式。批處理模式會在較短的時間片內將任務分配給合適的工人。即時模式會在工人一開始加入時就立即分配合適的任務。兩種模式在處理動態任務分配時各有優劣,即時模式能迅速地將任務分配給工人,但其分配效果難以保證。批處理模式的分配時間較長,但是分配效果通常優于即時模式,并且能選擇合適的時間片。文獻[13]通過實驗驗證了批處理模式在任務分配上的有效性。因此,本文將工人和任務屬性添加到空間眾包任務分配模型中,并在批處理模式下,提出基于預測算法的在線任務分配策略(MNTP)。

1 相關工作

1.1 空間眾包

文獻[14]將眾包根據不同標準劃分為不同類別,便于對不同眾包問題展開研究。根據空間任務的發布模式,將空間眾包分為服務器端指派任務(Server Assigned Task,SAT)模式[15-16]和工人選擇任務(Worker Selected Task,WST)模式[11,17]。現有任務多數為SAT模式,因為SC服務器可通過將任務分配給工人來實現對工人的控制。而在WST模式下,工人根據自己的興趣選擇任務,而較少受到SC服務器的影響,很難通過任務分配實現目標優化。因此,本文基于SAT模式提高任務分配的數量和質量。

根據系統對工人任務信息的了解情況,將空間眾包分為離線和在線兩種情況。在離線情況下,由于系統對工人和任務信息非常了解,因此可以最大化全局目標函數,如最大化分配任務數[1],但是離線空間眾包在多數現實場景下為無效,而在線情況下系統以流方式接收輸入并進行立即處理[18],此時眾包工人和任務均為動態變化[19-20],工人任務信息對于服務器而言為未知,雖然該情況提升了研究難度,但其代表了多數SC的實際情況,因此本文的研究重點為在線情況下的動態任務分配。

1.2 空間眾包任務分配

空間眾包任務分配常被建模為動態任務分配問題進行求解,目前已有許多學者提出各種算法來解決該問題。文獻[18]提出貪婪策略,對在線二分匹配問題展開研究。貪婪策略的基本思想是將新到來的工人(任務)分配給當前最接近的未分配任務(工人)。文獻[1]提出批處理模式解決動態任務分配問題,其將連續時間分為多個時間片(即批次),并嘗試在每個時間片中實現任務分配最大化,因此在每一個時間片中可以將任務分配問題轉化為最大流問題,繼而采用經典的Ford-Fulkerson算法求解該問題以及位置熵和工人移動距離等實際問題。文獻[11]在此基礎上提出最大分數任務分配(Maximum Score Assignment,MSA)問題,將每個時間片中的任務分配轉化為二分圖最大權匹配問題,采用經典的匈牙利算法求解二分圖匹配問題。為應對多名工人完成一個任務的情況,文獻[16]提出一種RDB-Sam采樣算法來解決空間眾包的可靠性及多樣性問題,并設計分治法提高任務分配效率,即將整個問題實例劃分為多個子問題實例,先求解子問題實例再進行結果合并,從而在求解效率和有效性之間取得權衡,但是若子問題之間沖突過于頻繁,則會大幅增加運行時間。

2 空間眾包模型及問題定義

本文采取批處理模式解決動態任務分配問題,將整個時間段分成若干個時間間隔較短的時間片,假設在每個時間片內的工人和任務均為靜態。

定義1(時間片) 給定集合Φ={s1,s2,…},Φ表示整個時間段,si表示將Φ進行等分后的時間片,每個時間片內存在不同的工人和任務集合,在時間片內工人和任務信息均為已知。

2.1 空間眾包任務

空間眾包任務是整個空間眾包活動的起點,假設T為SC中的任務集合,ti∈T為集合T中的眾包空間任務,使用ti=六元組對空間眾包任務進行形式化定義,其中:ls表示任務開始位置;le表示結束位置;Tt表示空間任務提交時間;δ表示任務失效時間;σ表示完成任務所需時間;ty表示任務類型,不同類型的任務需要具有不同能力的工人完成。工人只有在失效時間Tt+δ前到達開始位置ls才能正常執行任務,并且只有耗費時間σ達到le才能完成任務。

2.2 空間眾包工人

空間眾包工人是整個空間活動的重要參與者,假設W表示SC中工人的集合,wi∈W為集合W的一名工人,使用wi=六元組對空間眾包工人進行形式化定義,其中:Id表示工人標識;la=表示工人當前位置;Tw表示工人開始接受任務的時間;τ表示工人連續工作時間;sk={ty1,ty2,…}表示工人的技能,代表其擅長的任務類型,服務器會優先為工人安排其擅長或者傾向于的任務,以提高工人的積極性和任務完成質量;r表示工人工作半徑,工人會接受其工作半徑內的任務。在該模型下工人存在工作時長,需要在規定時長內才可以接受任務,而任務要工人花費時間并且任務的完成伴隨空間位置的移動。因此,在該模型下存在很多約束,增加了問題研究的難度。

2.3 最大分數任務分配問題

任務存在不同類型,而工人能完成不同類型的任務,當工人完成任務的類型符合自身技能時,通常任務完成的質量及積極性都會得到提升。為對該情況進行描述,本文定義分數概念對上述情況進行衡量。

定義2(任務分配) 假設WT表示總任務分配集合,WTi表示時間片si上的所有任務分配策略,那么每個分配策略wtp∈WTi由wtp=二元組進行表示,其中,wj∈W,tk∈T。每個任務分配策略代表服務器在滿足工人任務雙方約束條件的情況下將任務分配給工人執行,一旦分配就不更改。

定義3(分數) 假設gm表示分數,m表示第m個任務分配,用于衡量分配質量。不同的任務分配會產生不同的分數,若工人技能正好包含任務類型,則會得到較高的分數,稱為專業分配,否則會得到較低的分數,稱為普通分配,分數的高低由wj和tk的匹配情況決定。

圖1描述了某個時間片內的工人和任務集合,工人和任務分布在整個地理空間上,其中不同顏色表示不同類型。如果工人和任務的顏色相同,代表其類型一致,則會得到一個較高的分值。假定顏色相同的專業分配分數為3,顏色不同的普通分配分數為1。工人只能接受在其工作半徑范圍內的任務,即以每個工人為圓心的圓形范圍。假設工人滿足其他約束,w1能夠分配的任務為t1、t2、t3、t6,其中:t2、t3是專業分配,得到的分配分數為3;t1、t6是普通分配,得到的分配分數為1。本文的目標是通過任務分配策略使得分配分數之和最大化。

圖1 某個時間片內的工人和任務集合

3 基于預測算法的任務分配策略

本文策略的任務分配模型如圖2所示,工人和任務將相關信息發送給服務器,服務器通過策略進行任務分配,將最合適的任務分配給工人,通過任務分配實現目標優化。

圖2 任務分配模型

3.1 最大分數的任務集合尋找

由于在每個時間片內工人和任務均為靜態,因此將任務分配轉化為靜態任務分配問題,而解決該問題的最佳方法是將最大分數任務分配問題轉化為二分圖最大權匹配問題。

在圖論中,二分圖為一類特殊的圖,二分圖的頂點可以分成兩個互斥的獨立集合U和V,圖中所有邊的兩個頂點分別連接U和V中的一個點。設工人和任務兩個互不相交的集合分別為W和T,給定一個圖G=(V,E),將工人和任務映射為G的頂點,保證W∪T=V,同時工人和任務之間的關系映射為G的邊,ei,j∈E,邊的起點對應工人wi∈W,邊的終點對應tj∈T,工人、任務及其匹配關系可以用G進行表示,因此將尋找滿足最大分數之和的任務分配集合問題轉化為二分圖最大權匹配問題。

將圖1中的工人、任務及其分配關系對應到二分圖上,例如w1在其工作半徑中存在4個任務,工人能完成4個任務中的1個任務,由于w1、t2、t3是相同的顏色,會得到較高的分數3,因此w1、t2、t3的邊的權重為3,t1、t6是普通匹配,權重為1,同理可得另外兩位工人和任務的分配關系,如圖3(a)所示。

目前,解決二分圖最大權匹配問題的經典算法為匈牙利算法。在對工人和任務采用匈牙利算法后得到的最大分數匹配結果如圖3(b)所示,其中實線代表最終分配結果、、,得到最大分數為7。該分配策略既能保證在一個時間片內任務分配得到最大分數,又能通過匈牙利算法求解二分圖最大權匹配問題,從而解決最大分數任務分配問題。

通過觀察圖3(b)的匹配結果,發現經過二分圖最大權匹配算法得到的結果不止一個,例如可以代替,此時得到的最大分數仍是7,同理可更改其他分配集合,均滿足最大分數的要求,因此可得到多個二分圖匹配結果,為進一步優化提供了可能。

圖3 二分圖及其最大分數匹配結果

3.2 最大分數的任務集合優化

通過上述分析可以得出,若存在多個滿足最大分數條件的任務分配,則可以重新定義不同的權重,采用約束求解方法對上述解進行進一步優化,定義如下指示變量:

其中:xj,k是一個指示變量,表示任務tk是否被分配給工人wj,若是,則為1,否則為0;WTi代表時間片si二分圖中的所有任務分配集合。令fmax為匈牙利算法求得的最大權之和,并將其作為約束加入到整數規劃中,在最大權的基礎上最小化成本,其目標和約束具體如下:

其中,cj,k為重新定義的權重,其對上文得到的任務分配的解做進一步優化。

4 任務分配算法設計

本文首先采用預測算法對任務進行初步分配,然后在保證每個時間片內任務分配分數最大化的同時,盡可能地將更適合工人的任務進行優先分配,保證工人在完成任務后能夠迅速分配到新任務,防止工人資源的浪費,同時能提高任務分配質量。任務分配算法的偽代碼具體如下:

算法1任務分配算法

輸入開始時間片Ts、結束時間片Te、時間片si、工人集合Wi、空間任務集合Ti、工人工作半徑r

輸出任務分配集合WTi

1.Wp=φ;//初始化工人池中的工人集合

Tp=φ;//初始化任務池中的任務集合

2.for si←Tsto Tedo

Wa=φ;//初始化初步符合分配條件的工人集合

Ta=φ;//初始化初步符合分配條件的任務集合

3.for wj∈Wpdo

4.if wj.Tw=sithen Wi←wj;end if

5.end for

6.for tk∈Tpdo

7.if tk.Tt=sithen Ti←tk;end if

8.end for

9.for wj∈Wido

Tj=φ;//初始化工人wj的候選空間任務集合

10.for tk∈Tido

11.if distance≤r && wj.τ≥tk.σ then

Tj←tk,Ta←tk;end if

12.if Tj≠φ Wa←wj;end if

13.end for

14.end for

15.將Wa和Ta通過匈牙利算法求出WTh和最大分數Gi;

17.Return WTi

18.end for

19.Update(Wp);

Update(Tp)

任務分配算法的輸入為工人和任務集合,輸出為任務分配集合,算法第1行～第14行將可繼續分配的工人和任務根據約束篩選出能夠進行分配的工人和任務集合。第15行是應用匈牙利算法進行工人和任務的分配,得到初步解及該時間片的最大化分數。第16行～第18行是通過約束求解過程既能得到最大分數,又能使工人完成任務后出現在任務分布較多的區域。第19行是更新工人池和任務池中的信息,該步驟是實現動態更新的關鍵,因為工人和任務在每個時間片內不斷變化,需要不斷更新工人和任務信息,并將過期失效的工人和任務從工人池和任務池中刪除,而能繼續出現的工人和任務更新對應的時間片和位置,從而使該模型更符合實際空間眾包。由于工人在未匹配的情況下并不表示靜止,通常會在某個固定范圍內自由移動,因此在工人和任務動態變化的情況下,能更好地驗證本文任務分配算法的有效性。

5 實驗結果與分析

本文實驗采用滴滴快車在西安和成都兩個城市2019年11月某一天的司機軌跡數據,提取司機和訂單數據分別作為工人和任務數據集,共4組數據集進行實驗,其中數據集1和數據集2為西安市內2019年11月某一天的工人和任務數據集,數據集3和數據集4為成都市內2019年11月某一天的工人和任務數據集。實驗分為預測實驗和分配實驗兩部分。

5.1 預測實驗

在預測實驗中,本文使用常見的Decision Table、K-Star、Multilayer Perceptron、Zero-R、Bagging、Vote、Polynomial等預測算法進行對比實驗,評價標準具體如下:

1)錯誤率(Error Rate,ER)

2)均方根對數誤差(Root Mean Squared Logarithmic Error,RMSLE)

其中,RRMSLE表示在整個時間段內,不同網格中每個時間片的預測值對數和實際值對數的均方根,用于衡量預測準確性,該值越小代表預測效果越好。

5.1.1 不同預測算法對預測結果的影響實驗

該實驗給出了相同參數和數據集下不同預測算法的ER和RMSLE值,如表1所示,其中最優結果加粗顯示。通過比較發現:在相同參數下,Zero-R和Vote兩種算法的預測結果最差,可能是因為兩種算法的模型簡單,作為基本算法進行對比,而其他預測算法的結果比較接近,其中Polynomial算法的預測結果為最優,說明當前數據集能夠擬合成一條較合理的曲線使得預測結果較準確,因此在下文實驗中會繼續驗證不同預測算法在不同數據集和網格劃分數量下的性能表現,進而確定每個數據集的最優預測算法。

表1 7種預測算法的錯誤率和均方根對數誤差對比

5.1.2 不同數據集對預測結果的影響實驗

該實驗給出了不同數據集和相同參數下不同預測算法的ER和RMSLE值,如圖4和圖5所示。實驗結果表明,數據集1和數據集2在預測效果上要差于數據集3和數據集4,因為成都數據集在任務數量上要多于西安數據集,且在每個網格中的任務數量較多,所以在預測時產生的誤差及其帶來的影響會更小,同時發現無論數據集如何變化,Polynomial算法效果均為最優。

圖4 不同數據集下7種算法的錯誤率對比

圖5 不同數據集下7種算法的均方根對數誤差對比

5.1.3 不同網格劃分數量對預測結果的影響實驗

該實驗在相同數據集下驗證不同網格劃分數量對預測結果的影響,得到的結果如圖6和圖7所示,分別描述了算法在不同網格劃分數量下ER和RMSLE的變化情況,其中網格劃分數量為6代表將當前的區域劃分成為6×6個網格,然后預測不同網格在不同時間片內的任務數量,可以看出不同算法的預測結果隨著網格劃分數量的增多而逐漸變差,這是因為隨著網格劃分數量的增多,在網格內的任務數量越來越少,那么對異常值就會越來越敏感,較小的誤差也會產生較大的影響。通過上述實驗發現,在不同數據集和網格劃分數量的情況下,Polynomial算法的預測效果均為最優,因此本文采用Polynomial算法進行任務分配預測。

圖6 不同網格劃分數量下7種算法的錯誤率比較

圖7 不同網格劃分數量下7種算法的均方根對數誤差對比

5.2 分配實驗

在分配實驗中采用文獻[11]提出的BASIC、CDP和LLEP策略以及本文基于預測算法的在線任務分配策略(MNTP)進行對比,評價標準具體如下:

1)總分數,表示整個時間段內任務分配的分數之和,在實驗中專業分配為3分,普通分配為1分,分數越大代表分配效果越好。

2)總分配數量,表示整個時間段內總任務分配的數量,其值越大代表任務分配越多,分配效果越好。

3)總專業分配數量,表示整個時間段內的總專業分配任務數量,其值越大代表專業分配越多,分配效果越好。

4)平均工人移動距離,表示工人到達分配任務起點的平均歐式距離,距離越短,代表工人需要移動的范圍越小,對于工人而言能夠降低成本,平均工人移動距離越小,代表分配效果越好。

5.2.1 不同任務分配策略對分配結果的影響實驗

該實驗給出了相同參數和數據集下BASIC、CDP、LLEP和MNTP策略在不同評價標準下的任務分配性能比較情況,如表2所示,其中最優結果加粗顯示。可以看出,MNTP策略在總分數、總分配數量和總專業分配數量上相對于其他策略約分別能提高11%、10%和11%,該實驗結果驗證了上文理論分析的正確性以及MNTP策略的有效性。

表2 4種任務分配策略的性能比較

5.2.2 不同工人工作半徑對分配結果的影響實驗

該實驗給出了不同工人工作半徑下BASIC、LLEP、CDP和MNTP策略的總分數,如圖8～圖11所示。可以看出,隨著工人工作半徑的增大,4種策略在4個評價標準上的數值均產生了不同程度的增加,由于隨著工人工作半徑的增大,每個工人能夠分配的任務數量也在增加,那么任務能夠被分配出去的概率也隨之增大,因此總分數、總分配數量和總專業分配數量均呈上升趨勢,同時因為工人半徑增大,分配的任務也隨之變得更遠,所以平均工人移動距離也有所增加。不同策略之間的情況也不盡相同,MNTP策略和其他策略的差距在不斷縮小,這是由于隨著工人工作半徑的增加,工人能夠分配的任務越來越多,在任務數量過多時,工人能以較大概率分配到執行任務,這就會導致MNTP策略的作用越來越小,因此4種策略的分配效果趨向于一致,但是MNTP策略始終能取得最優的任務分配效果,從而驗證其在不同工人工作半徑下的有效性。

圖8 工人工作半徑對不同策略總分數的影響

圖9 工人工作半徑對不同策略總分配數量的影響

圖10 工人工作半徑對不同策略總專業分配數量的影響

圖11 工人工作半徑對不同策略平均工人移動距離的影響

5.2.3 不同數據集對分配結果的影響實驗

該實驗給出了不同數據集下不同策略的任務分配結果,如表3～表6所示,其中最優結果加粗顯示。可以看出,在不同數據集上MNTP策略的分配效果均為最優,在數據集1和數據集2上總分數、總分配數量和總專業分配數量最多分別能提高3%、4%和7%,在數據集3和數據集4中總分數、總分配數量和總專業分配數量最多分別能提高11%、10%和11%。不同數據集的提升效果不同的主要原因為工人和任務的數量比例和分布不同,西安數據集的工人任務少,在相同的網格劃分數量下預測效果要比成都數據集差很多,并且西安數據集的任務分配比成都數據集更為均衡,同時工人和任務的平均距離相對較遠,任務被分配的概率本身就要小于成都數據集,因此在此情況下利用MNTP策略的任務分配提升效果相對會差一些,但其任務分配性能仍為最優。

表3 不同數據集下4種策略的總分數對比

表4 不同數據集下4種策略的總分配數量對比

表5 不同數據集下4種策略的總專業分配數量對比

表6 不同數據集下4種策略的平均工人移動距離對比

6 結束語

本文通過定義分數概念衡量任務類型和工人技能的匹配度,對專業分配賦予較高的分數,并利用最大分數任務分配問題保證任務分配的專業性。在此基礎上,對空間眾包實例中的工人和任務屬性進行分析,構建空間眾包任務分配模型,針對最大分數任務分配問題設計基于預測算法的任務分配策略,將區域劃分為網格并對每個網格在不同時刻的任務數量進行預測,保證工人在完成任務后盡可能處于任務密集區域,從而提高整個時間段內任務分配的總分數。實驗結果驗證了本文策略的有效性。后續將引入深度學習技術提升Polynomial算法的預測準確性,進一步提高任務分配的數量與質量。