群智协同任务分配研究综述

doi:10.3778/j.issn.1002-8331.2105-0396

摘要/Abstract

摘要：

任务分配是群智协同计算和众包中的核心问题之一，即通过设计合理的任务分配策略，在满足任务约束条件下，将群智任务分配给合适的工作者，以提高群智任务的完成效率和结果质量。分析了目前任务分配方法存在的问题，总结并提出了一个通用的任务分配框架，并分别从工作者模型、任务模型、任务分配算法三个方面对国内外相关研究工作进行了分析、归纳和总结。提出了群智协同任务分配研究中的关键问题与今后的研究趋势。

关键词: 群智协同计算, 任务分配, 任务模型, 工作者模型

Abstract:

Task allocation is one of the core issues in crowd-based cooperative computing and crowdsourcing, that is, by designing a reasonable task allocation strategy, the tasks are assigned to the appropriate workers under the task constraints, so as to improve the result quality and completion efficiency of tasks. The problems of the current task allocation method are analyzed first, and then, a general task allocation framework is proposed and the relevant research work at home and abroad is analyzed in three aspects：worker model, task model, and task allocation algorithm. Finally, the key issues and future research trends in the research of task allocation for crowd-based cooperative computing are put forward.

Key words: crowd-based cooperative computing, task assignment, task model, worker model

陈宝童，王丽清，蒋晓敏，姚寒冰. 群智协同任务分配研究综述[J]. 计算机工程与应用, 2021, 57(20): 1-12.

CHEN Baotong, WANG Liqing, JIANG Xiaomin, YAO Hanbing. Survey of Task Assignment for Crowd-Based Cooperative Computing[J]. Computer Engineering and Applications, 2021, 57(20): 1-12.

参考文献

[1] 孙海龙，卢暾，李建国，等.群智协同计算：研究进展与发展趋势[C]//中国计算机学会文集，2017.
SUN H L，LU T，LI J G，et al.Crowd-based cooperative computing：research progress and development trend[C]//CCF Proceedings，2017.
[2] LI W，WU W J，WANG H M，et al.Crowd intelligence in AI 2.0 era[J].Frontiers of Information Technology & Electronic Engineering，2017，18（1）：15-43.
[3] 王青，谭良.基于用户主题精确感知大数据群体计算任务分配算法[J].计算机应用，2016，36（10）：2777-2783.
WANG Q，TAN L.Optimization algorithm for accurately theme-aware task assignment in crowd computing on big data[J].Journal of Computer Applications，2016，36（10）：2777-2783.
[4] ABHINAV K，BHATIA G K，DUBEY A，et al.TasRec：a framework for task recommendation in crowdsourcing[C]//Proceedings of the 15th International Conference on Global Software Engineering.New York：ACM，2020：86-95.
[5] CHILTON L B，HORTON J J，MILLER R C.Task search in a human computation market[C]//Proceedings of the ACM SIGKDD Workshop on Human Computation，Washington DC，July，2010.New York：ACM，2010：1-9.
[6] LYKOURENTZOU I，KHAN V J，PAPANGELIS K，et al.Macrotask crowdsourcing：an integrated definition[M]//Macrotask crowdsourcing.Cham：Springer，2019：1-13.
[7] LIU Y，LEHDONVIRTA V，KLEPPE M，et al.A crowdsourcing based mobile image translation and knowledge sharing service[C]//Proceedings of the 9th International Conference on Mobile and Ubiquitous Multimedia，Limassol Cyprus，December，2010.New York：ACM，2010：1-9.
[8] 原博洋，王丽清.基于工作者多属性特征模型的任务分配方法[J].计算机工程与设计，2020，41（5）：1398-1403.
YUAN B Y，WANG L Q.Task assignment method based on worker multi-attribute characteristic model[J].Computer Engineering and Design，2020，41（5）：1398-1403.
[9] 郑志蕴，江国林，张行进，等.基于滑动任务窗口的众包质量评估算法[J].小型微型计算机系统，2017，38（9）：2125-2129.
ZHENG Z Y，JIANG G L，ZHANG X J，et al.Crowdsourcing quality evaluation algorithm based on sliding task window[J].Journal of Chinese Computer System，2017，38（9）：2125-2129.
[10] LIU X，LU M，OOI B C，et al.CDAS：a crowdsourcing data analytics system[J].arXiv：1207.0143，2012.
[11] YAN Y，ROSALES R，FUNG G，et al.Active learning from crowds[C]//Proceedings of the 28th International Conference on Machine Learning，Bellevue，Washington，USA，June 28-July 2，2011.New York：ACM，2011：1161-1168.
[12] 李勇军，郭基凤，缑西梅.软件“众包”任务分配方法[J].计算机系统应用，2015（2）：1-6.
LI Y J，GUO J F，GOU X M.Software task allocation method in crowdsourcing[J].Computer Systems & Applications，2015（2）：1-6.
[13] GONCALVES J，FELDMAN M，HU S，et al.Task routing and assignment in crowdsourcing based on cognitive abilities[C]//Proceedings of the 26th International Conference on World Wide Web Companion，Perth，Australia，April 3-7，2017.Republic and Canton of Geneva：ACM，2017：1023-1031.
[14] HETTIACHCHI D，VAN B N，KOSTAKOS V，et al.CrowdCog：a cognitive skill based system for heterogeneous task assignment and recommendation in crowdsourcing[J].Proceedings of the ACM on Human-Computer Interaction，2020，4：1-22.
[15] SORDEN S D.The cognitive theory of multimedia learning[M]//Handbook of educational theories.New York：Cambridge University Press，2012.
[16] 仲秋雁，张媛，李晨，等.考虑用户兴趣和能力的众包任务推荐方法[J].系统工程理论与实践，2017，37（12）：3270-3280.
ZHONG Q Y，ZHANG Y，LI C，et al.Task recommendation method based on workers’ interest and competency for crowdsourcing[J].System Engineering Theory and Practice，2017，37（12）：3270-3280.
[17] SCARR S，WEBER B L R.The reliability of reviews for the American Psychologist[J].American Psychologist，1978，33（10）：935.
[18] ZHANG Y，VAN DER SCHAAR M.Reputation-based incentive protocols in crowdsourcing applications[C]//2012 Proceedings IEEE INFOCOM，Orlando，Florida，USA，March 25-30，2012.Piscataway，NJ：IEEE，2012：2140-2148.
[19] LI Q，CAO H，WANG S，et al.A reputation-based multi-user task selection incentive mechanism for crowdsensing[J].IEEE Access，2020，8：74887-74900.
[20] JAGAB S，SUBRAMANIAN L，VENKATARAMAN A.Reputation-based workerfiltering in crowdsourcing[C]//Advances in Neural Information Processing Systems，2014：2492-2500.
[21] GUO B，CHEN C，ZHANG D，et al.Mobile crowd sensing and computing：when participatory sensing meets participatory social media[J].IEEE Communications Magazine，2016，54（2）：131-137.
[22] CHERIAN J，LUO J，GUO H，et al.Parkgauge：gauging the occupancy of parking garages with crowdsensed parking characteristics[C]//17th IEEE International Conference on Mobile Data Management（MDM），Porto，Portugal，June 13-16，2016.Piscataway，NJ：IEEE，2016：92-101.
[23] RZADKOWSKI G，GLAZEWSKA I，SAWINSKA K.The Gompertz function and its applications in management[J].Foundations of Management，2015，7（1）：185.
[24] HUANG K L，KANHERE S S，HU W.Are you contrib-uting trustworthy data? The case for areputation system in participatory sensing[C]//Proceedings of the 13th ACM International Conference on Modeling，Analysis，and Simulation of Wireless and Mobile Systems，Bodrum Turkey，October，2010.New York：ACM，2010：14-22.
[25] 肖嵩，袁景凌，盛德明，等.一种基于多信息融合的兴趣点推荐模型[J/OL].小型微型计算机系统（2019-12-11）[2021-01-13].http：//kns.cnki.net/kcms/detail/21.1106.TP.
202001231.1625.015.html.
XIAO S，YUAN J L，SHENG D M，et al.A point of interest recommendation model based on multi-information fusion[J/OL].Journal of Chinese Computer Systems（2019-12-16）[2021-01-13].http：//kns.cnki.net/kcms/detail.21.1106.TP.202001231.1625.01html.
[26] 刘业政，吴锋，孙见山，等.基于群偏好与用户偏好协同演化的群推荐方法[J].系统工程理论与实践，2021，41（3）：537-553.
LIU Y Z，WU F，SUN J S，et al.Group recommendation method based on co-evolution of group preference and user preference[J].Systems Engineering-Theory & Practice，2021，41（3）：537-553.
[27] 武建新，张志鸿.融合用户评分与显隐兴趣相似度的协同过滤推荐算法[J].计算机科学，2021，48（5）：147-154.
WU J X，ZHANG Z H.Collaborative filtering recommendation algorithm based on user rating and similarity of explicit and implicit interest[J].Computer Science，2021，48（5）：147-154.
[28] AMBATI V，VOGEL S，CARBONELL J G.Towards task recommendationin micro-task markets[J].Human Computation，2011，11：1-4.
[29] ZHONG Q，ZHANG Y，LI C，et al.Task recommendation method based on workers’ interest and competency for crowdsourcing[J].System Engineering Theory and Practice，2017，37（12）：3270-3280.
[30] RAKESH V，LEE W C，REDDY C K.Probabilistic group recommendation model for crowdfunding domains[C]//Proceedings of the Ninth ACM International Conference on Web Search and Data Mining，San Francisco，California，USA，February，2016.New York：ACM，2016：257-266.
[31] XU F，JI Z，WANG B.Dual role model for question recommendation in community question answering[C]//Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval，Portland Oregon，USA，August，2012.New York：ACM，2012：771-780.
[32] GUOZ，TANG C，NIU W，et al.Fine-grained recommendation mechanism to curb astroturfing in crowdsourcing systems[J].IEEE Access，2017，5：15529-15541.
[33] ZHANGW，WANG J.A collective Bayesian Poisson factorization model for cold-start local event recom mendation[C]//Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Sydney，NSW，Australia.New York：ACM，2012：1455-1464.
[34] ZHOU G，LAI S，LIU K，et al.Topic-sensitive probabilistic model for expert finding in question answer communities[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management，Maui，Hawaii USA.New York：ACM，2012：1662-1666.
[35] 严俊，库少平，喻楚.基于活跃度的众包工作者信誉模型[J].计算机应用，2017，37（7）：2039-2043.
YAN J，KU S P，YU C.Reputation model of crowdsourcing workers based on active degree[J].Journal of Computer Applications，2017，37（7）：2039-2043.
[36] YU D，ZHOU Z，WANG Y.Crowdsourcing software task assignment method for collaborative development[J].IEEE Access，2019，7：35743-35754.
[37] 施智敏.面向不同任务特征的多目标众包任务推荐方法[D].徐州：中国矿业大学，2019.
SHI Z M.Multi-objective task recommendation method based on different task characteristics for crowdsourcing[D].Xuzhou：China University of Mining and Technology，2019.
[38] 周侨，方明.基于多Agent的众包任务分配算法的研究[J].智能计算机与应用，2019，9（1）：104-107.
ZHOU Q，FANG M.Research on crowdsourcing task allocation algorithm based on multi-Agent[J].Intelligent Computer and Applications，2019，9（1）：104-107.
[39] 王从文，王璨，徐春明，等.基于工人信誉度和距离的任务分配算法[J].价值工程，2020，39（16）：201-203.
WANG C W，WANG C，XU C M，et al.Task assign-ment algorithm based on worker credibility and dis-tance[J].Value Engineering，2020，39（16）：201-203.
[40] CHEN Y Y，LV P，GUO D K，et al.A survey on task and participant matching in mobile crowd sensing[J].Journal of Computer Science and Technology，2018，33（4）：768-791.
[41] AHMED A，YASUMOTO K，YAMAUCHI Y，et al.Dis-tance and time based node selection for probabilistic coverage in people-centric sensing[C]//2011 8th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks，Salt Lake City，UT，USA，June 27-30，2011.Piscataway，NJ：IEEE，2011：134-142.
[42] HACHEM S，PATHAK A，ISSARNY V.Probabilistic regi-
stration for large-scale mobile participatory sensing[C]//IEEE International Conference on Pervasive Computing and Communications，San Diego，CA，USA.Piscataway，NJ：IEEE，2013：132-140.
[43] LI L，WANG C，SONG S，et al.A task assignment strategy for crowdsourcing-based web accessibility evaluation system[C]//Proceedings of the 14th Web for All Conference on the Future of Accessible Work，Perth，Western Australia.New York：ACM，2012：1-4.
[44] KAMREL M M，GIL-SOLLA A，RAMOS-CARBER M.Tasks recommendation in crowdsourcing based on workers’ implicit profiles and performance history[C]//Proceedings of the 2020 9th International Conference on Software and Information Engineering，Cairo，Egypt，November，2020.New York：ACM，2020：51-55.
[45] JURCA R，FALTINGS B.Towards incentive-compatible reputation management[C]//Workshop on Deception，Fraud and Trust in Agent Societies，Bologna，Italy，July 15，2002. Berlin，Heidelberg：Springer，2002：138-147.
[46] DIFALLAH D E，DEMARTINI G，CUDRE-MAUROUX P.Pick-a-crowd：tell me what you like，and I’ll tell you what to do[C]//Proceedings of the 22nd International Conference on World Wide Web，Rio de Janeiro，Brazil.New York：ACM，2012：367-374.
[47] MONTANDONJ E，SILVA L L，VALENTE M T.Identifying experts in software libraries and frameworks among github users[C]//2019 IEEE/ACM 16th International Conference on Mining Software Repositories，Montreal，QC，Canada，May 25-31，2019.Piscataway，NJ：IEEE，2019：276-287.
[48] WU G，CHEN Z，LIU J，et al.Task assignment for social-oriented crowdsourcing[J].Frontiers of Computer Science，2021，15（2）：1-11.
[49] RAHMAN H，ROY S B，THIRUMURUGANATHAN S，et al.Optimized group formation for solving collaborative tasks[J].The VLDB Journal，2019，28（1）：1-23.
[50] YU D，WANG Y，ZHOU Z.Software crowdsourcing task allocation algorithm based on dynamic utility[J].IEEE Access，2019，7：33094-33106.
[51] YUEN M C，KING I，LEUNG K S.Task recommendation in crowdsourcing systems[C]//Proceedings of the First International Workshop on Crowdsourcing and Data Mining，Beijing，China，August，2012.New York：ACM，2012：22-26.
[52] MAO K，YANG Y，WANG Q，et al.Developer recommendation for crowdsourced software development tasks[C]//2015 IEEE Symposium on Service-Oriented System Engineering，San Francisco，CA，March 28-April 3，2015.Washington，DC：IEEE，2015：347-356.
[53] SHAO W，WANG X，JIAO W.A developer recommendation framework in software crowdsourcing develop-ment[C]//National Software Application Conference，Kunming，China，November 3-5.Singapore：Springer，2016：151-164.
[54] LI Y M，HSIEH C Y，LIN L F，et al.A social mechanism for task-oriented crowdsourcing recommendations[J].Decision Support Systems，2021，141：32-47.
[55] PENG Z，GUI X，AN J，et al.TDSRC：a task-distributing system of crowdsourcing based on social relation cognition[J].Mobile Information Systems，2019，2019：7413460.
[56] YUEN M C，KING I，LEUNG K S.An online-updating algorithm on probabilistic matrix factorization with active learning for task recommendation in crowdsourcing systems[J].Big Data Analytics，2016，1（1）：1-29.
[57] 毛鹏，章鸣雷，胡传杉.基于遗传非负矩阵分解的任务自动分配研究[J].上海管理科学，2017（5）：98-103.
MAO P，ZHANG M L，HU C S.Research on automatic assignment of task based on the genetic NMF[J].Shanghai Management Science，2017（5）：98-103.
[58] YUEN M C，KING I，LEUNG K S.Taskrec：probabilistic matrix factorization in task recommendation in crowdsouring sytems[C]//International Conference on Neural Information Processing，Doha，Qatar，Nov 12-15，2012.Berlin，Heidelberg：Springer，2012：516-525.
[59] YUEN M C，KING I，LEUNG K S.Taskrec：a task recommendation framework in crowdsourcing systems[J].Neural Processing Letters，2015，41（2）：223-238.
[60] SAFRAN M，CHE D.Efficient learning-based recommendation algorithms for top-N tasks and top-N workers in large-scale crowdsourcing systems[J].ACM Transactions on Information Systems（TOIS），2018，37（1）：1-46.
[61] YUEN M C，KING I，LEUNG K S.Temporal context-aware task recommendation in crowdsourcing systems[J].Knowledge-Based Systems，2021，219：106770.
[62] YUEN M C，KING I，LEUNG K S.An online-updating approach on task recommendation in crowdsourcing systems[C]//International Conference on Neural Information Processing，Kyoto，Japan，October 16-21，2016.Switzerland：Springer，2016：91-101.
[63] GAO L，GAN Y，SUN M，et al.The user-knowledge crowdsourcing task allocation integrated decision model and genetic matrix factorization algorithm[J].Expert Systems With Applications，2021，165：113798.
[64] ISLAM L，ALVI S T，RAHMAN M，et al.A blockchain-based crowdsourced task assessment framework using smart contract[J].International Journal of Advanced Computer Science and Applications，2021，12（1）：590-600.
[65] ZHANG J，CUI W，MA J，et al.Blockchain-based secure and fair crowdsourcing scheme[J].International Journal of Distributed Sensor Networks，2019，15（7）：1-15.
[66] XIONG J，LIU H，JIN B，et al.A lightweight privacy protection scheme based on user preference in mobile crowdsensing[J].Transactions on Emerging Telecommunications Technologies，2020，32（5）：39-54.
[67] PENG F，TANG S，ZHAO B，et al.A privacy-preserving data aggregation of mobile crowdsensing based on local differential privacy[C]//Proceedings of the ACM Turing Celebration Conference-China，Chengdu，China，May 17-19，2019.New York：ACM，2019：1-5.
[68] PENG T，LIU Q，MENG D，et al.Collaborative trajectory privacy preserving scheme in location-based services[J].Information Sciences，2017，387：165-179.
[69] ZENGM，CHENG Z，HUANG X，et al.Spatial crowdsourcing quality control model based on K-anonymity location privacy protection and ELM spammer detection[J].Mobile Information Systems，2019.
[70] XU X，YANG Z，XIAN Y.Atm：attribute-based privacy-preserving task assignment and incentive mechanism for crowdsensing[J].IEEE Access，2021，9：60923-60933.
[71] CELIS L E，REDDY S P，SINGH I P，et al.Assignment techniques for crowdsourcing sensitive tasks[C]//Proceedings of the 19th ACM Conference on Computer-Supported Cooperative Work & Social Computing，San Francisco，California，USA，February 27-March 2，2016.New York：ACM，2016：836-847.
[72] LI T.Solving mysteries with crowds：supporting crowdsourced sensemaking with a modularized pipeline and context slices[D].Virginia Tech，2020.
[73] MARCUS A，KARGER D，MADDEN S，et al.Counting with the crowd[J].Proceedings of the VLDB Endowment，2012，6（2）：109-120.
[74] CHEN P，SUN H，FANG Y，et al.Conan：a framework for detecting and handling collusion in crowdsourcing[J].Information Sciences，2020，515：44-63.
[75] HAO J，HUANG C，CHEN G，et al.Privacy-preserving interest-ability based task allocation in crowdsourcing[C]//2019 IEEE International Conference on Communications（ICC），Shanghai，China，May 20-24，2019.Washington，DC：IEEE，2019：1-6.
[76] YIN H，XIONG Y，DENG T，et al.A privacy-preserving and identity-based personalized recommendation scheme for encrypted tasks in crowdsourcing[J].IEEE Access，2019，7：138857-138871.
[77] XU J，CUI B，SHI R，et al.Outsourced privacy-aware task allocation with flexible expressions in crowdsourcing[J].Future Generation Computer Systems，2020，112：383-393.
[78] XU J，LIN Z，WU J.Privacy-preserving task-matching and multiple-submissions detection in crowdsourcing[J].Sensors，2021，21（9）：3036.
[79] ZHANG J，ZHANG Q，JI S.A fog-assisted privacy-preserving task allocation in crowdsourcing[J].IEEE Internet of Things Journal，2020，7（9）：8331-8342.
[80] LIU K，CHEN W，ZHANG Z.Blockchain-empowered decentralized framework for secure and efficient software crowdsourcing[C]//2020 IEEE World Congress on Services（SERVICES），Beijing，China，Oct 18-23，2020.Washington，DC：IEEE，2019：128-133.
[81] WU Y，TANG S，ZHAO B，et al.BPTM：blockchain-based privacy-preserving task matching in crowdsourcing[J].IEEE Access，2019，7：45605-45617.
[82] ZHANG C，GUO Y，DU H，et al.Pfcrowd：privacy-preserving and federated crowdsourcing framework by using blockchain[C]//2020 IEEE/ACM 28th International Symposium on Quality of Service（IWQoS），Hangzhou，China，June 15-17，2020.Washington，DC：IEEE，2020：1-10.
[83] GONG D，PENG C，YAO X，et al.A model of new workers’ accurate acceptance of tasks using capable sensing[J].Swarm and Evolutionary Computation，2020，59：100732.
[84] SHI Z，GONG D，YAO X，et al.New task oriented rec-ommendation method based on hungarian algorithm in crowdsourcing platform[C]//2020 IEEE World Congress on Services（SERVICES），Beijing，China，Oct 18-23，2020.Washington，DC：IEEE，2019：134-144.
[85] TU J，CHENG P，CHEN L.Quality-assured synchronized task assignment in crowdsourcing[J].IEEE Transactions on Knowledge and Data Engineering，2019，33（3）：1156-1168.
[86] LI Q，CAI L.Online task scheduling with workers variabilities in crowdsourcing[J].IEEE Access，2021，9：78025-78034.
[87] WANG G，ALI F，YANG J，et al.Multicriteria-based crowd selection using ant colony optimization[J].Complexity，2021：6622231.
[88] YUEN M C，KING I，LEUNG K S.Task matching in crowdsourcing[C]//International Conference on Internet of Things and 4th International Conference on Cyber，Physical and Social Computing，Dalian，China，Oct 19-22，2011.Washington，DC：IEEE，2011：409-412.
[89] GADIRAJU U，DEMARTINI G，KAWASE R，et al.Crowd anatomy beyond the good and bad：behavioral traces for crowd worker modeling and pre-selection[J].Computer Supported Cooperative Work（CSCW），2019，28（5）：815-841.
[90] SCHNITZER S，NEITZEL S，RENSING C.From task classification towards similarity measures for recommendation in crowdsourcing systems[J].arXiv：1707.06562，2017.
[91] JOHN I，BHATNAGAR S.Efficient budget allocation and task assignment in crowdsourcing[C]//Proceedings of the ACM India Joint International Conference on Data Science and Management of Data，Kolkata，India，January 3-5，2019.New York：ACM，2019：318-321.
[92] DAI W，WANG Y，MA J，et al.BTR：a feature-based Bayesian task recommendation scheme for crowdsourcing system[J].IEEE Transactions on Computational Social Systems，2020，7（3）：780-789.
[93] SHAN C，MAMOULIS N，CHENG R，et al.An end-to-end deep RL framework for task arrangement in crowdsourcing platforms[C]//2020 IEEE 36th International Conference on Data Engineering（ICDE），Dallas，TX，USA，April 20-24，2020.Washington，DC：IEEE，2020：49-60.
[94] PAN Q，DONG H，WANG Y，et al.Recommendation of crowdsourcing tasks based on word2vec semantic tags[J].Wireless Communications and Mobile Computing，2019，2019：2121850.
[95] ZHOU C，THAM C K，MOTANI M.Online auction for scheduling concurrent delay tolerant tasks in crowdsourcing systems[J].Computer Networks，2020，169：107045.
[96] XIAO M，MA K，LIU A，et al.Sra：secure reverse auction for task assignment in spatial crowdsourcing[J].IEEE Transactions on Knowledge and Data Engineering，2019，32（4）：782-796.
[97] XIA H，MCKERNAN B.Privacy in crowdsourcing：a review of the threats and challenges[J].Computer Supported Cooperative Work（CSCW），2020，29（3）：263-301.