面向工作者能力評估的眾包任務分配方法的研究進展綜述

馬 華，陳躍鵬，唐文勝，婁小平，黃卓軒

（湖南師范大學信息科學與工程學院，長沙 410081）

0 引言

近年來，隨著互聯網技術和共享經濟模式的不斷成熟，以亞馬遜Mechanical Turk、CrowdFlower、豬八戒網、任務中國等為代表的眾包（Crowdsourcing）平臺發展迅速。為獲取創新創意思想、提高工作效率、降低成本等，眾多企業開始將其工作任務發布到眾包平臺，征集盡可能優秀的解決方案，并通過分布式協作提高任務的完成效率。例如，“豬八戒網”現有約300多萬個眾包任務，覆蓋近20個產業主類目，懸賞金額約53億元［1］；“任務中國”約有5.7萬個面向設計、網站、寫作以及多媒體開發等方面的眾包任務，懸賞金額約3 800萬元［1］；“中移在線”官網顯示，2019年完成各類任務達12.8億次，注冊會員有60多萬人，服務次數達1億多次。

作為一種通過互聯網群體智慧解決復雜問題的重要模式［2］，眾包現已吸引了學術界和產業界的廣泛重視。中國計算機學會在《中國計算機科學技術發展報告》［3］中將眾包視為群智協同計算領域的研究重點之一。近年來許多重要的國際會議發布了眾包的相關研究成果。例如，2018年Ma等［4］討論了眾包任務的定價機制、2017年Hung等［5］探討了眾包任務質量控制模型、2017年Li等［6］討論了眾包在數據庫中的應用、2016年Mavridis等［7］探討了知識密集型眾包任務的分配優化算法。目前，眾包在實時O2O（Online to Offline）應用、交通管理、災情監控、社交媒體、軟件服務、自然語言處理、信息檢索等領域均有較成功的應用［8-10］。

作者對近十年（截止于2019年12月）發表在中國知網（China National Knowledge Infrastructure，CNKI）和WOS（Web Of Science）上的論文進行了仔細梳理，選擇與計算機領域相關性較大的期刊（其中，中文文獻以核心期刊級別以上為主）和有代表性的書籍和會議論文，通過主題詞“眾包”（或“Crowdsourcing”）檢索，并在檢索文獻過程中采用倒查法、順查法和追溯法擴充文獻，以厘清國內外現有的與“眾包”（或“Crowdsourcing”）相關的主要研究的文獻量、研究熱點和整體研究趨勢等信息。梳理結果顯示，CNKI中有論文5 232篇，WOS中有3495篇。2010—2019年的眾包文獻發文量詳細情況如圖1所示。以CNKI為例，2016年發文量出現了第一個高峰期，達2014年的2倍；2017年后發文量趨于平穩，年均發文量約700篇。

圖1 2010—2019年的眾包文獻發文量Fig.1 Literatures published about crowdsourcing in 2010 to2019

使用Citespace軟件分析獲得了近10年來眾包研究的關鍵詞共現圖譜（如圖2所示）、高中心性關鍵詞統計表（如表1所示）和高中心性關鍵詞圖譜（如圖3所示）。

圖2 關鍵詞共現圖譜Fig.2 Keywords co-occurrence map

圖3 高中心性關鍵詞圖譜Fig.3 Map of keywordswith high centrality

表1 高中心性關鍵詞Tab.1 Keywords with high centrality

由高中心性關鍵詞的分布與連線特征可知，眾包的影響因素和激勵機制、眾包任務的分配、工作者的信譽評估、眾包任務的質量控制策略等是近10年來我國關于眾包的研究熱點。其中，眾包任務質量控制一直是研究難點，它涉及眾包平臺、雇主和工作者等三方合作，為獲得滿意的結果，需要篩選高質量的候選工作者和應用高效的任務分配方法，而任務和多樣性與工作者能力的動態性和不確定性特征，增加了眾包任務質量控制研究的難度［11］。首先，眾包過程的某些影響因素（例如平臺上工作者的工作環境、狀態以及態度等）難以量化。其次，任務分配方法的設計涉及行為學、心理學和統計學等多個領域知識［12］。此外，任務類型多樣，現有的分配算法模型難以統一處理，即單個算法模型缺乏普適性。

近年來，時空眾包、空間眾包等新型的眾包應用不斷出現。不同于傳統眾包，時空眾包有更強的實時性、空間性以及移動性等，因此不能用已有的離線算法來求解。童詠昕等［10］對時空眾包的數據庫管理、任務分配、質量控制等方面研究進行了綜述；張志強等［13］提出了階段式動態眾包質量控制策略，以此來保證眾包任務的高質量完成。

通過梳理現有文獻可知，工作者能力的準確、全面評估對于眾包任務分配優化方法具有重要意義［14］。不同的候選工作者對于不同的眾包任務具有不同的勝任能力，它直接影響了眾包任務的最終完成質量。對于眾包平臺而言，如何結合歷史數據和注冊信息等準確評估候選工作者的綜合能力，在考慮時空、成本等諸多因素基礎上，為多個相關的眾包任務分配合適的眾包工人集，以獲取整體的最優任務完成滿意度和眾包平臺的利益最大化，是一個NP難問題［14］。

針對現有研究面臨的困難及挑戰，本文在總結工作者能力評估研究的基礎上，從基于匹配、基于規劃和基于角色協同等3個方面對眾包任務分配方法的現有研究成果進行綜述，以期為后續的深入研究提供有價值的參考和啟發。

1 眾包的概念和分類

1.1 眾包概念

2006年，Jeff Howe在《聯線》雜志上第一次提出了“眾包”的概念，即一家企業將以往由工人完成的工作任務，現以自由自愿的方式外包給非特定的公眾網絡的做法［15］。隨著眾包應用的發展，眾包定義在形式上發生了變化，Estellés-Arolas等［16］總結了2006年到2011年的28篇文章的36個定義，比較全面地從不同方面描述了眾包，歸納提煉出眾包的基本六要素，包括雇主、眾包平臺、工作者、任務、獎勵機制以及解決方案。2016年Kietzmann等［17］將眾包的定義擴展為“通過互聯網，以公開呼叫的形式將任何組織職能外包給網絡上的工作者（包括人類和非人類參與者）”。

目前，眾包在技術、形式和社會職能上發生了很大變化，它們包括：1）眾包不僅是一個“未定義的人員網絡”，并且聚集了具有一定能力技能的人員；2）眾包不再是單單屬于組織外部的努力，現在更多地與企業內部的員工一起合作；3）眾包不再局限于人群，很多項目以人群和機器之間的合作來完成某項特殊任務；4）可通過應用程序編程接口訪問眾包。

眾包任務的完成需要雇主、眾包平臺和工作者三者之間的良好協作。典型的眾包模式如圖4［18］所示。

圖4 典型的眾包模式Fig.4 Classic crowdsourcingmodel

綜上，眾包的主要特征可被歸納為：采用公開呼叫的方式召集互聯網大眾［19］；眾包任務通常是機器難以單獨解決的問題［18］；大眾通過獨立或協作完成眾包任務；眾包是一種分布式的問題解決機制［20］。

1.2 眾包分類

依據眾包平臺的實際應用，本文從大眾參與的形式和眾包獎勵機制兩個層面對眾包平臺分類。根據大眾參與的形式可將眾包分為競爭式和協作式2種方式；根據獎勵機制不同可將眾包分為積分型、懸賞型、知識能力產品出售型等3種方式。每種類型的主要特征及案例參見表2所示。同時，從眾包任務的類型差異性角度分析，按任務的復雜性、難度和粒度等不同標準，可以將眾包任務劃分為簡單任務、復雜任務、微觀 任 務、宏 觀 任 務 等［11］。例 如Mechanical Turk、Google Answers、豬八戒網和任務中國等眾包平臺，承接的任務大部分為微觀任務、宏觀任務和簡單任務，比如對大量圖片歸類、Logo設計、名片設計及地理位置標注等常規懸賞型任務，工作者接單并完成后獲得相應的報酬。

表2 眾包平臺分類Tab.2 Classification of crowdsourcing platforms

對于需要協同開發或者需要很強的專業性知識的復雜任務，如軟件眾包，多依靠開源的平臺來完成任務，是比較快捷高效的方式［21-22］，比如GitHub、Coding等開源社區。另外，與眾包相似的兩個概念是眾籌（Crowdfunding）和眾創，其中，眾籌強調的是資金的募集，與眾包有本質上的區別。三者主要區別和對應的案例如表3所示。

表3 眾包、眾籌與眾創的區別Tab.3 Differencesbetween crowdsourcing，crowdfundingand crowdcreation

2 眾包任務特點及工作流程

2.1 眾包任務特點

隨著應用場景的復雜性和多樣性，許多眾包任務開始對完成的時間、地點以及工作者響應時間等有更明確的要求，即出現了從傳統的基于Web的應用模式轉向具有時空屬性的眾包應用模式。例如滴滴出行、餓了么、美團眾包、Uber以及Gigwalk等典型的O2O應用。

根據任務是否存在時空約束這一條件，可將眾包分為兩大類：傳統眾包和時空眾包。兩者不僅在眾包任務類型和參與者上有差異，而且在眾包平臺的服務模式上也有很大區別。時空眾包強調實時性和空間性等，是線上和線下的資源的密切配合。由于任務特點有本質上的不同，并影響到任務分配、質量評估以及平臺數據管理［10］等方面，時空眾包已不能用已有的離線算法來解決相關問題，需進行專門研究。兩類眾包在服務范圍和涵蓋的任務類型上的區別如表4所示，其中√表示支持該類型的任務，—表示該項未發現。

表4 傳統眾包和時空眾包的比較Tab.4 Comparison between traditional crowdsourcingand spatiotemporal crowdsourcing

按照復雜性、難度和粒度等不同標準，眾包任務可分為四種類型：1）簡單任務。傳統眾包和空間眾包中多以簡單任務為主，通常任務可單獨完成，比如，名片設計、口號標語創作、文章翻譯、交通堵塞監控、自然災害數據采集等的興起等。2）復雜任務。主要涉及一些專業性、創新性比較強、任務流程比較復雜繁瑣并耗時較長的任務類型，單獨無法完成的任務有時需要團隊間的協作才能更好地保證任務完成的質量。例如，劇本的撰寫、網站的開發、算法的設計以及卡通人物的設計等均屬于復雜任務。其中，軟件眾包因其任務特點及眾包應用在軟件開發上的優勢，目前已成為學術界和產業界關注的重點。3）微觀任務。任務的粒度較小，內容通常較具體和客觀，任務的難度不限。可以是不需要任何專業知識背景的圖片標注任務、特定數據采集服務、地理位置的標注以及其他類型簡單又具體的任務，也有操作繁瑣需要專業知識的復雜任務，比如獲取某區域的重金屬污染指標數據、某區域的居民生活水平調查數據以及某農村留守兒童的數量比例等。4）宏觀任務。任務的粒度相對較大，任務類型包含較多主觀因素，相對來說任務難度比較低，比如360問答、知乎以及微博社區等發布的任務。工作者完成此類任務，多數不以盈利為目的，通過賺取積分、獲取點贊以及瀏覽量等方式來獲取關注等。

2.2 眾包工作流程

眾包工作流程如圖5所示。雇主、工作者、待解決的任務、獎勵機制、眾包平臺以及解決方案是基本的六要素。其中，工作者、眾包平臺與雇主三者是眾包過程的核心。眾包平臺承載任務及其用戶，任務通過眾包平臺將工作者與雇主建立供需關系，完善的獎勵機制可使整個眾包流程成為一個可持續的生產過程，良好的問題反饋機制將最大限度地保證任務的完成質量。對于有時空約束的時空眾包任務，雇主和工作者都要提交自己當前的時空信息，通過眾包平臺對時空屬性信息預處理，推薦或者分配合適的工作者。另外，對時空特性無嚴格要求的傳統眾包任務，時空屬性可不作為一項重要的指標參與到眾包的工作流程當中，如圖5虛線框所示。

圖5 眾包工作流程Fig.5 Crowdsourcing workflow

目前，成熟的眾包平臺，如Mechanical Turk、CrowdFlower、豬八戒網、任務中國以及滴滴打車、美團眾包等，都有良好的線上交流、問題反饋以及評分機制，可為保障任務完成質量提供支持。但是，通過調研也發現，基于Web的傳統眾包平臺在任務推薦、任務檢索等方面仍有很大的提升空間。

3 工作者能力評估

眾包平臺存在虛擬性和時空不對稱性，工作者能力評估機制應支持篩除低質量工作者，避免虛假交易和欺詐行為。準確評估工作者的能力是進行完成質量保障下的任務分配的前提條件。

3.1 工作者能力的評估指標

為全面客觀評價工作者的綜合能力，可建立m層n個指標的指標集（一般m≤3，n≤9）。指標集的目標層是工作者能力綜合評估指標。指標集的決策層可包括四個方面的指標：1）基本指標。例如注冊時間、年齡與文化程度、熟悉的專業領域三個方面。不同年齡和受教育程度的工作者的經濟、生活、心理、道德水平和信用狀態都可能存在一定差別。2）活躍程度指標。例如工作者登錄并使用平臺的頻率、在線工作時長、實際參與任務比率、實際中標任務比率等。這些指標體現了一個工作者的活躍程度。3）任務完成質量指標。包括按時完成任務比率、超時任務比率、已完成任務的好評率和差評率及被投訴率等方面。其中，超時任務比率是工作者超時完成的任務數量占工作者投標的任務總數量。4）其他指標。指能更全面評估工作者能力的指標集，可根據實際情況擴充。

3.2 評價指標的權重計算

確定指標權重的方法可分為主觀賦權、客觀賦權及主客觀賦權三種類型。層次分析法（Analytic Hierarchy Process，AHP）、模糊層次分析法（Fuzzy AHP，FAHP）、德菲爾法（Delphi Technique）等屬于主觀賦權類型。主成分分析（Principal Component Analysis，PCA）法、相關系數法、熵值法和坎蒂雷賦權法等屬于客觀賦權類型。將主觀賦權法與客觀賦權法相結合，可使評價結果更加精確和客觀，但其數學推導比較繁瑣，應用和實際操作缺乏靈活性。常用的權重計算方法的對比如表5所示。

表5 權重計算方法的比較Tab.5 Comparison of weight calculation methods

使用單一方法往往會出現權重的偏倚，因此融合方法的研究日趨豐富。例如，德菲爾法和AHP與PCA法相結合、德菲爾法和FAHP與因子分析法相結合、德菲爾法和AHP與熵值法相結合、德菲爾法和FAHP與熵值法相結合等。相比單一方法，融合方法可使評估對象的權重設定更客觀。

3.3 工作者能力的評估模型

對工作者能力的評估模型可分為兩類：一是可識別但不規避低質量工作者的模型；二是可識別且可規避低質量工作者的模型。后者較為復雜，但可減少由低質量工作者在承接任務時帶來的損失。

3.3.1 可識別但不規避低質量工作者的評估模型

工作者平均信譽模型［23］在實際的眾包系統中使用比較廣泛，該模型是將工作者所有的歷史任務完成質量累加后取平均值作為該工作者的信譽值，并根據此信譽值優先選擇合適的工作者。但是，該模型忽視了近期任務的完成情況相對于早期任務更能反映工作者當前實際信譽值。嚴俊等［24］改進了平均信譽模型，從工作者活躍度和歷史信譽值的角度提出活躍因子和歷史因子的概念，用于衡量工作者的綜合能力值，以提高任務的完成質量和完成效率，但缺乏考慮任務復雜度和工作者選擇機制。

借鑒C2C信譽評價模型，如易趣網、淘寶網的信用評價體系，用戶的信用值的計算是將用戶得到的所有信用反饋評分進行累加，即信用累加模型。文獻［25-26］在此研究基礎上，引入了服務加權計分、交易金額、交易時間、失敗懲罰因子等因素，引入交易金額能夠有效地解決“較小交易獲取信任行大騙”的問題；增加的懲罰因子，能有效應對“小額信用累積”的問題等。改進后的信用評價體系雖不能直接規避欺詐或者低質量的工作者參與交易，但工作者的信用值不會因再次誠信交易而快速恢復，可間接保障任務的完成質量，但不足是，影響因子的合理取值需通過大量實際數據進行驗證。

在軟件協同開發方面，謝新強等［22］通過對開發者的靜態和動態、顯式和隱式特征，定性定量相結合的方式，給出了開發者能力模型的模糊綜合評價方法。但是，該方法未考慮工作者能力的動態更新。由此，余敦輝等［27］提出一種軟件眾包工人能力動態度量算法，將影響工作者開發能力的諸多因素考慮在內，包括工人的靜態技能屬性、已完成任務的類型、任務復雜度、任務質量、任務開發實效、任務技能覆蓋率以及時間因子等，并結合歷史任務的完成時間順序，實現工人能力的動態更新。

在開源軟件核心開發者的評估方面，工作者一般通過分享經驗、代碼調試、提交更新補丁程序等途徑作出貢獻，項目貢獻度通常被視為工作者開發地位的重要指標，來識別核心開發者和外圍開發者。此外，現有研究也提出，可從社交網絡挖掘項目的貢獻度信息。現有文獻多用統計計數的方法［28-29］，以統計量為指標并通過設立閾值來判別開發者的地位，但這些方法忽略了對項目文件自身特性的分析。另外，吳哲夫等［30］從開發者對可信技術文件的貢獻出發，以9個Apache項目為基礎，結合傳統的評價指標建立變量，訓練支持向量機模型，以提高核心開發者的識別精度，為開源社區人員的晉升提供有效的依據，但是，該文獻定義的評價體系較為單一，難以綜合分析開發者的貢獻度。

3.3.2 可識別且可規避低質量工作者的評估模型

眾包工人能力度量是進行任務合理分配的一個關鍵因素，同時也直接關系到任務的完成質量，識別并規避低質量的工作者是一項研究重點也是難點。文獻［31-33］在識別惡意工作者行為特征方面做了深入研究，指出惡意工作者很少參與抽象的任務或具有創新性要求的任務，可通過對工作者的精確評估來有效地降低惡意工作者以及低能力工作者的參與，通常采用以下4種評估方法策略：

1）基于黃金標準數據的策略。

該策略中，先由雇主設計一些具有標準答案的問題同任務一起發布，并使工作者做任務的同時回答這些問題，通過回答的結果對工作者進行評估，檢測工作者對任務的了解程度，直接評估工作者是否有能力承接此項任務。針對簡單客觀的有標準答案的問題，使用該策略識別工作者的能力是很好的辦法。然而，眾包平臺上的任務大多為復雜任務和一些主觀性強的宏觀任務，缺乏具體的標準答案［13，34-35］；并且，該策略未充分考慮工作者的歷史表現和歷史信譽。針對現有不足，Gao等［36］考慮了問題的價值、工作者歷史表現、當前測試結果、測試任務的規模、精度與成本的關系以及獲得錯誤答案的風險等，把工作者過去的歷史表現作為精度的先驗分布，通過黃金標準數據中工作者的表現作為后驗分布，這種方法能較為準確地估計工作者的綜合能力，保證輸出的答案質量，具有較高的可靠性。

2）基于熵的眾包質量評估策略。

最大期望（Expectation Maximization，EM）算法是比較經典的眾包質量評估算法，但它不能直觀表示工作者完成任務的情況［37］。Dawid等［38］提出的EM算法，能得出工作者的“誤差矩陣”，進而求得對應工作者的誤差率，誤差率可作為工作者的衡量標準。此外，Raykar等［39］提出了一種基于熵的眾包質量評估算法，此算法很直觀地以區間值的形式將工作者完成任務的情況展現出來，好的工作者得分接近1，差的工作者得分接近于0。

3）階段式動態眾包質量控制策略。

該策略涉及質量評估算法、替換規則、監測點設置等方面。現有文獻對隨意類型和統一類型［12-13］的欺詐工作者進行了模型化表述，張志強等［13］通過EM算法計算出工作者的誤差率作為能力評估的指標，選取可靠工作者，并通過隨機簡單選取可靠工作者原則進行工作者的替換。潘慶先等［12］基于廣義Pareto分布的權重設置算法設計出了眾包工人權重設置框架，可有效規避工作者統一型的欺騙性為，但針對不同任務框架缺乏一定的通用性。此外，替換規則以及監測點的加入是否合理等問題需要重視，它們將會影響整個任務的完成進度，同時有可能會陷入一種惡性的循環替換中。

4）基于投票的質量控制策略。

此控制策略采用簡單多數投票規則［40］，即多個工作者參與一個任務的情況下，基于投票規則，以多數工作者認可的方案作為任務的最終方案，這在一定程度上可規避低質量或者惡意工作者參與從而導致整體結果質量下降的問題。該方法已被Mechanical Turk、CrowdFlower等平臺采用。該策略的缺陷在于未考慮投票者之間的能力認知差異。針對現有不足，Hirth等［41］提出了一種控制組質量確保技術，將任務分配給多個工作者，選取工作者或指定專家對反饋的方案進行“投票”，選出最優結果，如果符合雇主的要求就采用此方案，不符合就重新發包。“控制組質量確保技術”與“基于投票一次性策略”都是提高眾包結果質量的有效手段，但是未考慮工作者能力的動態變化情況。Quinn等［42］提出了一種冗余質量確保技術，它將任務分發給不同的工作者，再將結果聚合成最優結果，聚合的過程包含了對低質量答案的篩選過程，但其缺點是增加了任務量以及聚合過程的開支。

綜上，本文對工作者能力評估模型及算法進行了綜合比較，如表6所示。

表6 工作者能力評估模型及算法比較Tab.6 Comparison of worker ability evaluation models and algorithms

通過識別惡意工作者或者低質量工作者，并不能從根源上徹底規避它們參與眾包任務，但可通過設置篩選機制和評估機制降低其出現概率。例如，在任務分配前對工作者能力進行評估［43］、擴大評估指標維度、提高評估精度等來降低其對任務完成質量帶來的影響。

4 眾包任務分配方法

眾包平臺根據任務和工作者各自的特性為眾包任務選擇合適工作者。實際的眾包應用中，因雇主不可能了解所有工作者的真實技能、可信度以及協作能力，通常眾包平臺隨機將任務分配給工作者。針對特定類型的任務，通過冗余、重復的分配方式來盡可能地保證眾包結果的質量，其結果往往是任務完成的時間成本、資金成本以及任務結果精度達不到預期目標。為提升任務的完成質量，合理有效的任務分配機制一直是眾包任務質量保證關注的研究重點。

4.1 任務分配前的準備工作

傳統的任務分配多在公司內部或者任務與工作者類型已知的情況下進行，而眾包模式下的分配方式多為在線或離線狀態下完成，且工作時間及工作者類型等方面也有很大差異。因此，傳統模式下的任務分配算法并不能直接應用于眾包應用。眾包模式下在任務分配前，除了需要確定工作者的綜合能力外，還需確定眾包任務與工作者的相關特征。

首選，確定任務的類型，即靜態離線任務或動態在線任務。眾包平臺可以提前獲取靜態離線任務和工作者的各項指標信息。而對于動態在線任務，任務和上線的工作者是隨機出現的，因此，任務分配方法有很大區別。即分配方法上是隨機分配還是基于Top-k擇優分配策略。

其次，確定任務所需工作者的數量。通過梳理文獻，二者對應關系有一對一、一對多、多對多（包含協同關系）等3種類型。目前的分配算法多為“一對一”的研究，這些算法的復雜度較低，但針對“多對多”的類型，因考慮的因素、指標、涉及人員較多等不確定因素，給研究人員提出了很大的挑戰，可視為NP難問題。

最后，確定任務的選擇權，包括工作者主動選擇任務、工作者被動承接任務以及工作者與任務之間的雙向選擇等3種選項。針對傳統眾包任務的完成過程，目前多為工作者主動承接任務并提交方案，由雇主對方案進行審核的方式。比如Mechanical Turk、任務中國等的圖片標記、地點標注等簡單任務。工作者被動選擇和雙向選擇多出現在特定的眾包任務中。例如，時空眾包類型的神州專車平臺主動給工作者分派任務，即被動承接任務；傳統眾包的一些競標項目，如軟件眾包、軟件測試、網站開發等是雙向選擇的過程。眾包模式與傳統模式下任務分配方法的比較如表7所示。

表7 任務分配方法的比較Tab.7 Comparison of task assignment methods

綜上，不同特征的自由組合即可產生不同類型的任務，且每種類型的任務涉及的分析方法有本質上的區別。因此，在很大程度上影響了眾包平臺的應用類型、服務策略、任務分配方法以及質量控制方式等方面。簡單來講，任務類型與相關算法之間有一一對應的匹配關系，即算法的特定適用性。

目前針對眾包任務分配的問題，有不同方面的研究成果，本文將現有成果歸納為三類，即基于匹配的任務分配模型、基于規劃的任務分配模型、基于角色協同的任務分配方法。

4.2 基于匹配的任務分配方法

為實現任務的合理分配，眾包平臺需分析雇主發布的任務類型，結合承接此類任務的歷史工作者的綜合指標，建立有效的雇主-工作者之間的匹配關系，基本思想是通過二分圖匹配模型［44］實現任務的分配。根據任務與工作者在時間、空間以及狀態等特征，可將任務匹配方式分為靜態離線任務匹配和動態在線任務匹配。前者相關算法常用在傳統任務類型的眾包平臺中，如Mechanical Turk、豬八戒網、任務中國等傳統平臺；而后者的相關算法多用在有空間屬性要求的眾包應用中，如滴滴打車、美團眾包、百度外賣等空間眾包平臺。

4.2.1 靜態/離線匹配模型

離線匹配問題是一個組合優化問題，要求待匹配對象的所有信息均已知，基于已有信息實現最優匹配。經典的匹配問題為離線二分匹配問題。離線場景下傳統眾包平臺的任務分配現在大多采用靜態的任務匹配方式。當多個工作者同時競標同一項任務時，先由平臺建立任務模型和工作者模型，由雇主針對工作者的特性及其信譽進行選擇性的任務分配。這種分配算法的缺點是存在雇主的主觀意識，未對工作者提交的任務質量、任務數量及是否超時等方面進行綜合評價，分配效率低且誤差較大。

針對這些問題，研究人員提出了原始近似算法［45］，每個工人執行各種任務類型的黃金實例，計算結果并估計技能等級，形成一套評價標準體系，分配任務時向雇主提供客觀綜合的參考標準。另外，針對基于用戶主題的精確感知的任務分配方面，文獻［46-47］利用邏輯回歸對用戶的各個屬性進行訓練得到相應的權重，并針對不同的任務，對工作者進行預測分類，設置閾值，得到候選工作者序列。從實施結果來講，能實現任務的大概率精準匹配，但對工作者的協作能力、任務完成進度及任務完成時效性等問題尚需進一步研究。

4.2.2 動態/在線匹配模型

在實時性要求較高的空間眾包應用中，比如滴滴打車、美團外賣、神州專車等動態在線眾包應用，任務分配多采用動態在線匹配的方法為雇主尋找工作者［48］。實際應用中的“動態”具體體現在兩方面：單一對象（即工作者或眾包任務）的動態隨機出現；工作者和眾包任務兩類對象的動態隨機出現。現有研究多聚焦在前者，而后者的研究文獻較少。

1）單一對象的動態出現問題研究。

針對現有離線分配方法在時空眾包任務分配中的不適用性等情況，Tong等［49］指出了靜態離線算法不適用于全局在線微任務分配問題，并針對該問題把加權二分匹配算法［48］進行擴展，提出了一種競爭比為1/4的兩階段全局在線分配算法。此算法適用于單一對象出現的情況。Boutsis等［50］提出實時約束條件下的任務分配算法，進行一對一匹配。該算法同樣抽象為賦權二分圖匹配過程，根據任務信息估計工作者能否按時完成，但模型求解較復雜。Ting等［51］研究了在線最大加權二分匹配問題，優化目標為最大化匹配邊的總權值。

2）兩類對象的動態出現問題研究。

為最大化平臺的收益和效率，兩類對象的動態隨機分配問題是研究重點。余敦輝等［52］提出一種基于動態效用的閾值選擇算法，通過計算任務成功率期望、任務實際完成時長和工人的單位時間效用，并動態設置閾值，通過效用的對比來獲取最優的匹配方案。Tong等［53］通過不同特征的真實數據集和合成數據集的4種典型在線算法的評價，對時空數據問題中的最小二部匹配進行全面研究并得出三種實驗結論。宋天舒等［54］針對3類對象的在線任務分配問題，設計一種隨機閾值算法，并給出了該算法在最差情況下的競爭比分析。

4.3 基于規劃的任務分配方法

基于規劃的任務分配方法的目標是解決多任務全局最優分配問題。類似于匹配模型，基于規劃的分配方法也可以分為靜態離線場景的規劃模型與動態在線場景的規劃模型。

4.3.1 靜態/離線規劃模型

此模型跟經典的旅行商問題［38］可歸為一類，即針對某一工作者與眾包任務集，眾包平臺如何為該工作者分配合理的任務執行順序和方案，以最優方式高質量地完成多個任務的問題。Ho等［55］提出的多重任務分配算法近年來運用較多，也可視為問題的最優規劃模型，用來解決常規多任務分配問題與組角色多任務分配問題。但是該算法沒有考慮惡意工作者參與的情況，并且有可能低技能的工作者會分配到復雜任務而導致任務無法按時交期的問題。另外，蔣麗等［56］改進蟻群算法，針對O2O外賣訂單路徑最優規劃進行分析，將下一步移動的潛在客戶數量作為影響路徑選擇的影響因素。

4.3.2 動態/在線規劃模型

在空間眾包應用中有一類動態規劃問題，即每當有新任務發布時，需要工作者考慮要不要將此項新任務加入到在執行的任務進程中去，通過手動添加方式，將新任務加入到現有的任務進程中去［57］，這種方式全靠工作者平時的規劃經驗，沒有一個可靠的全局規劃方案給予技術支持。

李洋等［58］提出了樹分解模型來解決工作者帶有最晚工作時間約束的任務分配問題，并設計了一種深度優先搜索算法，來獲取最優方案。文獻［59-60］將工作者任務分配問題規約為最大任務調度問題，以k最鄰算法來選擇候選工作者，利用動態規劃和分支界定的思想，設計規劃路線使得工作者完成更多的工作，提高任務分配的性能。

綜上，基于規劃的任務分配方法，不管是具有動態/在線還是靜態/離線屬性的眾包任務，選擇最合適的眾包工人，使得全局任務分配效用最大化、工人承接數量最大化等，是當前眾包環境下質量控制研究的關鍵問題。

4.4 基于角色協同的任務分配方法

針對復雜任務的分配問題，需要考慮任務和工作者的屬性，也要考慮工作者之間以及工作者與任務之間的約束。基于角色協同（Role-Based Collaboration，RBC）是一種研究角色及其之間復雜關系的方法。按照需求設定一組角色，通過滿足一定的約束條件，完成現實中復雜問題的任務指派，RBC現已獲得廣泛關注［61］。RBC問題的核心是群組角色分配（Group Role Assignment，GRA）［62］，GRA中角色的沖突、約束、請求等關系都會造成算法的復雜性劇增，因此復雜任務的GRA問題目前并沒有很好的解決方案，屬于NP難問題。

Zhu等［61］對基于角色協同技術做了深入的研究，提出了E-CARGO模型，并將此模型用于解決有約束的問題中。此模型在處理角色協同任務分配時，借助Q矩陣可較好地完成有約束的指派問題［63］；并且，針對現實中工作者之間以及工作者與任務之間的復雜約束，使用E-CARGO中的沖突矩陣可以很好地定義復雜約束。基于E-CARGO模型，眾包任務分配問題的形式化模型可表示為：∑∷=E，C，O，R，A，G，具體組成部分的含義是：E代表問題環境，即一個涉及多個眾包工人和多個眾包任務的分配方案；C表示與E相關的、表示抽象概念的類集合；O表示與C相關的具體對象的集合；R表示當前待分配的任務集合；A表示眾包工人候選者集合；G表示工作組，即在完成所有任務分配后所建立的眾包工人的工作團隊。

其中，R、A和G是E-CARGO模型中的核心元素，通過模型建立各個元素之間的約束關系表達式，來求得任務的最佳分配，實現眾包平臺、工作者以及雇主三方利益最大化。例如：目前眾包平臺上有2項任務r1，r2∈R，這2項任務分別需要1名和2名工作者，某一時刻平臺上有3名合格的眾包工作者a1，a2，a3∈A，假設a2和a3為單一沖突元素，即不可協作，因此只能將a2和a3分派到不同的任務組中完成任務，通過Q矩陣的約束以及工人能力的綜合度量，實現任務的最優分配。但隨著工作者和任務數的增加，計算復雜度也將會劇增。基于角色協同的工作者分配過程如圖6所示。

圖6 基于角色協同的任務分配Fig.6 Task assignment of RBC

此外，針對復雜任務、工作者的能力冷啟動以及動態特性等問題，周僑等［64］提出一種基于多agent的眾包任務分配算法，通過多個agent高效協作來保證任務的分配效率并彌補個體工作者能力的限制，可提高復雜任務的工作效率。

綜上，本節從基于匹配、基于規劃和基于角色協同三個方面綜述眾包任務分配方法的研究，它們的對比分析情況如表8所示。

表8 眾包任務分配方法對比Tab.8 Comparison of crowdsourcing task assignment methods

5 未來展望

隨著眾包應用的不斷擴展和成熟，很多新算法被提出來，它們為雇主、眾包平臺、工作者三者實現各自利益最大化提供保障。在確保雇主以最小成本獲得盡可能高質量的方案的同時，眾包平臺能夠擁有最優的運行機制、最大的平臺效益以及工作者在相同時間內獲得更多的收入等。其中，工作者能力評估及眾包任務分配是關鍵的研究問題，也是影響眾包質量的關鍵因素。為實現眾包平臺和用戶的利益最大化，一些問題仍需深入探討。

1）面向多類型的眾包任務綜合分配算法。

不管是傳統眾包還是時空眾包，眾包任務類型的多樣化決定了不同分配算法的明顯差異性。在實際應用中，除了空間眾包平臺有較成熟的任務分配機制外，傳統眾包平臺多靠工作者自選模式完成任務，較少由平臺自動指派任務給工作者。針對不同任務類型特點，當前已提出眾多的分配算法，但如何面向不同類型建立眾包任務綜合分配算法，以支持眾包平臺覆蓋多種類型任務的分配并確保平臺整體效益的最大化，是值得繼續關注的重要問題。

2）優秀工作者社交關系數據的深度挖掘。

眾包平臺中，優秀的工作者之間多有技術或者項目之間的互動，同時雇主可能與特定工作者保持長期合作關系，當雇主發布需要多個工作者參與的眾包任務時，眾包平臺通過深度挖掘優秀工作者的社交網絡，有針對性地篩選高質量的工作者，能更可靠地保障任務的完成質量和完成效率。現有研究工作尚未涉及工作者之間、工作者與雇主之間社交關系的深度挖掘，這是一個值得進一步探索的方向。

3）用戶隱私與敏感任務信息的安全保障。

在眾包應用中，由于用戶信息、任務細節信息均暴露在眾包平臺上，可能存在用戶的個人數據以及任務的敏感數據泄露的風險，導致雇主不愿將包含敏感信息的任務投放到眾包平臺上。現有一些涉及隱私與數據保護的方案雖能夠在一定程度上降低數據泄露的風險，但在實際應用中并不理想。

因此，平臺如何通過對用戶信息的有效加密和任務信息的去敏感化，以提供足夠的安全保障，對于推動眾包應用的發展具有至關重要的意義。

6 結語

本文主要闡述了眾包環境下面向工作者能力評估的眾包任務分配方法的研究進展，并對相關方法進行了歸納總結。首先介紹了眾包的概念和分類，且對眾包的工作流程及任務特點進行了詳細介紹。然后，從指標集建立、權重確定、評估模型這三個方面對工作者能力評估的整個過程做了詳細的分析，特別對現有眾包任務的基于匹配的、基于規劃的和基于角色協同的三類分配方法進行了詳細闡述。隨著眾包應用的不斷推廣，未來在面向復雜類型的眾包任務分配、工作者社交關系的深度挖掘以及眾包平臺的信息安全保障等方面，仍需要開展進一步的深入研究。