移动众包环境下基于友谊度的任务规划

梁媛; 吕卫锋; 吴文峻; 许可

doi:10.1631/FITEE.1601860

Your Location：

Home >

Browse articles >

移动众包环境下基于友谊度的任务规划

人工智能2.0专辑 | Updated：2022-05-19

- 移动众包环境下基于友谊度的任务规划
- Friendship-aware task planning in mobile crowdsourcing
- 信息与电子工程前沿（英文） 2017年18卷第1期页码：107-121
- Affiliations：
  
  State Key Laboratory of Software Development Environment, School of Computer Science, Beihang University, Beijing 100191, China
- Author bio：
  
  E-mail:liangyuan120@nlsde.buaa.edu.cn
  E-mail:lwf@nlsde.buaa.edu.cn
  E-mail:wwj@nlsde.buaa.edu.cn
  E-mail:kex@nlsde.buaa.edu.cn
- Funds：
  
  Project supported by the National High-Tech R & D Program (863) of China (No. 2014AA015203)
- DOI：10.1631/FITEE.1601860
  中图分类号： TP3
- 收稿：2016-12-23，
  
  录用：2017-1-9，
  
  纸质出版：2017-01
- Accepted：
Scan QR Code
梁媛, 吕卫锋, 吴文峻, 等. 移动众包环境下基于友谊度的任务规划[J]. 信息与电子工程前沿（英文）, 2017,18(1):107-121.

Yuan LIANG, Wei-feng LV, Wen-jun WU, et al. Friendship-aware task planning in mobile crowdsourcing[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 107-121.
梁媛, 吕卫锋, 吴文峻, 等. 移动众包环境下基于友谊度的任务规划[J]. 信息与电子工程前沿（英文）, 2017,18(1):107-121. DOI： 10.1631/FITEE.1601860.

Yuan LIANG, Wei-feng LV, Wen-jun WU, et al. Friendship-aware task planning in mobile crowdsourcing[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 107-121. DOI： 10.1631/FITEE.1601860.

摘要

最近，众包平台已吸引了大量的注册用户在线下执行特定的任务。然而，大部分现有方法仅考虑了工人和任务信息都已提前获知的情况（静态离线情景），而较少考虑到工人动态抵达的情况（动态在线情景）。因此，当工人动态抵达时，如何给工人安排适合的任务以获得其最大的满意度成为了一个具有挑战性的问题。为解决这一问题，本文提出了一种有用并且普遍的人工-任务模型，该模型不仅考虑在静态离线时给工人安排任务的情况，还同时考虑了在工人动态抵达时如何给工人安排合适的任务。在本文中，为解决静态离线情景下的任务分配问题，我们首先提出一个有效的贪心算法。由于贪心算法极易陷入局部最优，我们又加入了模拟退火法来提高贪心算法的性能。另外，为解决动态在线情景下的分配问题，我们提出了一种贪心算法。最后，在真实数据集和具有不同分布人造数据集上进行了大量实验，实验结果验证了算法的效果与性能。

Abstract

Recently

crowdsourcing platforms have attracted a number of citizens to perform a variety of locationspecific tasks. However

most existing approaches consider the arrangement of a set of tasks for a set of crowd workers

while few consider crowd workers arriving in a dynamic manner. Therefore

how to arrange suitable location-specific tasks to a set of crowd workers such that the crowd workers obtain maximum satisfaction when arriving sequentially represents a challenge. To address the limitation of existing approaches

we first identify a more general and useful model that considers not only the arrangement of a set of tasks to a set of crowd workers

but also all the dynamic arrivals of all crowd workers. Then

we present an effective crowd-task model which is applied to offline and online settings

respectively. To solve the problem in an offline setting

we first observe the characteristics of task planning (CTP) and devise a CTP algorithm to solve the problem. We also propose an effective greedy method and integrated simulated annealing (ISA) techniques to improve the algorithm performance. To solve the problem in an online setting

we develop a greedy algorithm for task planning. Finally

we verify the effectiveness and efficiency of the proposed solutions through extensive experiments using real and synthetic datasets.

关键词

Keywords

references

N Armenatzoglou , , , H Pham , , , V Ntranos , , , 等 . . Real-time multi-criteria social graph partitioning: a game theoretic approach . . 2015 . . Proc. ACM SIGMOD Int. Conf. on Management of Data . . 1617 - - 1628 . . DOI: 10.1145/2723372.2749450 http://doi.org/10.1145/2723372.2749450 . .

RE Burkard , , , M Dell'Amico , , , S Martello . . Assignment Problems , , 2009 . . : Philadelphia : Society for Industrial and Applied Mathematics , , . .

CC Cao , , , J She , , , Y Tong , , , 等 . . Whom to ask? Jury selection for decision making tasks on micro-blog services . . Proc. VLDB Endow. , , 2012 . . 5 ( ( 11 ): ): 1495 - - 1506 . . DOI: 10.14778/2350229.2350264 http://doi.org/10.14778/2350229.2350264 . .

CC Cao , , , Y Tong , , , L Chen , , , 等 . . WiseMarket: a new paradigm for managing wisdom of online social users . . 2013 . . Proc. ACM SIGGKDD Int. Conf. on Knowledge Discovery and Data Mining . . 455 - - 463 . . DOI: 10.1145/2487575.2487642 http://doi.org/10.1145/2487575.2487642 . .

Y Cheng , , , Y Yuan , , , L Chen , , , 等 . . DistR: a distributed method for the reachability query over large uncertain graphs . . IEEE Trans. Parall. Distr. Syst. , , 2016 . . 27 ( ( 11 ): ): 3172 - - 3185 . . DOI: 10.1109/TPDS.2016.2535444 http://doi.org/10.1109/TPDS.2016.2535444 . .

D Gao , , , Y Tong , , , J She , , , 等 . . Top- k team recommendation in spatial crowdsourcing . . 2016 . . Proc. Int. Conf. on Web-Age Information Management . . 191 - - 204 . . DOI: 10.1007/978-3-319-39937-9_15 http://doi.org/10.1007/978-3-319-39937-9_15 . .

RM Karp , , , UV Vazirani , , , VV Vazirani . . An optimal algorithm for on-line bipartite matching . . 1990 . . Proc. 22nd Annual ACM Symp. on Theory of Computing . . 352 - - 358 . . DOI: 10.1145/100216.100262 http://doi.org/10.1145/100216.100262 . .

L Kazemi , , , C Shahabi . . GeoCrowd: enabling query answering with spatial crowdsourcing . . 2012 . . Proc. 20th Int. Conf. on Advances in Geographic Information Systems . . 189 - - 198 . . DOI: 10.1145/2424321.2424346 http://doi.org/10.1145/2424321.2424346 . .

S Kirkpatrick , , , JCD Gelatt , , , MP Vecchi . . Optimization by simulated annealing . . Science , , 1987 . . 220 ( ( 4598 ): ): 671 - - 680 . . DOI: 10.1126/science.220.4598.671 http://doi.org/10.1126/science.220.4598.671 . .

K Li , , , W Lu , , , S Bhagat , , , 等 . . On social event organization . . 2014 . . Proc. 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining . . 1206 - - 1215 . . DOI: 10.1145/2623330.2623724 http://doi.org/10.1145/2623330.2623724 . .

X Liu , , , Q He , , , Y Tian , , , 等 . . Event-based social networks: linking the online and offline social worlds . . 2012 . . Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining . . 1032 - - 1040 . . DOI: 10.1145/2339530.2339693 http://doi.org/10.1145/2339530.2339693 . .

A Mehta . . Online matching and ad allocation . . Found. Trends Theor. Comput. Sci. , , 2012 . . 8 ( ( 4 ): ): 265 - - 368 . . DOI: 10.1561/0400000057 http://doi.org/10.1561/0400000057 . .

R Meng , , , Y Tong , , , L Chen , , , 等 . . CrowdTC: crowdsourced taxonomy construction . . 2015 . . Proc. IEEE Int. Conf. on Data Mining . . 913 - - 918 . . DOI: 10.1109/ICDM.2015.77 http://doi.org/10.1109/ICDM.2015.77 . .

M Musthag , , , D Ganesan . . Labor dynamics in a mobile micro-task market . . 2013 . . Proc. SIGCHI Conf. on Human Factors in Computing Systems . . 641 - - 650 . . DOI: 10.1145/2470654.2470745 http://doi.org/10.1145/2470654.2470745 . .

YH Pan . . Heading toward artificial intelligence 2.0 . . Engineering , , 2016 . . 2 ( ( 4 ): ): 409 - - 413 . . DOI: 10.1016/J.ENG.2016.04.018 http://doi.org/10.1016/J.ENG.2016.04.018 . .

J She , , , Y Tong , , , L Chen . . Utility-aware social event-participant planning . . 2015a . . Proc. ACM SIGMOD Int. Conf. on Management of Data . . 1629 - - 1643 . . DOI: 10.1145/2723372.2749446 http://doi.org/10.1145/2723372.2749446 . .

J She , , , Y Tong , , , L Chen , , , 等 . . Conflict-aware event-participant arrangement . . 2015b . . Proc. 31st IEEE Int. Conf. on Data Engineering . . 735 - - 746 . . DOI: 10.1109/ICDE.2015.7113329 http://doi.org/10.1109/ICDE.2015.7113329 . .

J She , , , Y Tong , , , L Chen , , , 等 . . Conflict-aware event-participant arrangement and its variant for online setting . . IEEE Trans. Knowl. Data Eng. , , 2016 . . 28 ( ( 9 ): ): 2281 - - 2295 . . DOI: 10.1109/TKDE.2016.2565468 http://doi.org/10.1109/TKDE.2016.2565468 . .

Y Sun , , , CC Chen . . A novel social event recommendation method based on social and collaborative friendships . . 2013 . . Int. Conf. on Social Informatics . . 109 - - 118 . . DOI: 10.1007/978-3-319-03260-3_10 http://doi.org/10.1007/978-3-319-03260-3_10 . .

HF Ting , , , XZ Xiang . . Near optimal algorithms for online maximum edge-weighted b-matching and twosided vertex-weighted b-matching . . Theor. Comput. Sci. , , 2015 . . 607 ( ( 2 ): ): 247 - - 256 . . DOI: 10.1016/j.tcs.2015.05.032 http://doi.org/10.1016/j.tcs.2015.05.032 . .

Y Tong , , , L Chen , , , Y Cheng , , , 等 . . Mining frequent itemsets over uncertain databases . . Proc. VLDB Endow. , , 2012a . . 5 ( ( 11 ): ): 1650 - - 1661 . . DOI: 10.14778/2350229.2350277 http://doi.org/10.14778/2350229.2350277 . .

Y Tong , , , L Chen , , , B Ding . . Discovering thresholdbased frequent closed itemsets over probabilistic data . . 2012b . . Proc. IEEE 28th Int. Conf. on Data Engineering . . 270 - - 281 . . DOI: 10.1109/ICDE.2012.51 http://doi.org/10.1109/ICDE.2012.51 . .

Y Tong , , , L Chen , , , PS Yu . . UFIMT: an uncertain frequent itemset mining toolbox . . 2012c . . Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining . . 1508 - - 1511 . . DOI: 10.1145/2339530.2339767 http://doi.org/10.1145/2339530.2339767 . .

Y Tong , , , CC Cao , , , L Chen . . TCS: efficient topic discovery over crowd-oriented service data . . 2014a . . Proc. 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining . . 861 - - 870 . . DOI: 10.1145/2623330.2623647 http://doi.org/10.1145/2623330.2623647 . .

Y Tong , , , CC Cao , , , CJ Zhang , , , 等 . . CrowdCleaner: data cleaning for multi-version data on the web via crowdsourcing . . 2014b . . Proc. IEEE 30th Int. Conf. on Data Engineering . . 1182 - - 1185 . . DOI: 10.1109/ICDE.2014.6816736 http://doi.org/10.1109/ICDE.2014.6816736 . .

Y Tong , , , L Chen , , , J She . . Mining frequent itemsets in correlated uncertain databases . . J. Comput. Sci. Technol. , , 2015a . . 30 ( ( 4 ): ): 696 - - 712 . . DOI: 10.1007/s11390-015-1555-9 http://doi.org/10.1007/s11390-015-1555-9 . .

Y Tong , , , J She , , , L Chen . . Towards better understanding of App functions . . J. Comput. Sci. Technol. , , 2015b . . 30 ( ( 5 ): ): 1130 - - 1140 . . DOI: 10.1007/s11390-015-1588-0 http://doi.org/10.1007/s11390-015-1588-0 . .

Y Tong , , , J She , , , B Ding , , , 等 . . Online minimum matching in real-time spatial data: experiments and analysis . . Proc. VLDB Endow. , , 2016a . . 9 ( ( 12 ): ): 1053 - - 1064 . . DOI: 10.14778/2994509.2994523 http://doi.org/10.14778/2994509.2994523 . .

Y Tong , , , J She , , , B Ding , , , 等 . . Online mobile micro-task allocation in spatial crowdsourcing . . 2016b . . Proc. 32nd IEEE Int. Conf. on Data Engineering . . 49 - - 60 . . DOI: 10.1109/ICDE.2016.7498228 http://doi.org/10.1109/ICDE.2016.7498228 . .

Y Tong , , , J She , , , R Meng . . Bottleneck-aware arrangement over event-based social networks: the maxmin approach . . World Wide Web J. , , 2016c . . 19 ( ( 6 ): ): 1151 - - 1177 . . DOI: 10.1007/s11280-015-0377-6 http://doi.org/10.1007/s11280-015-0377-6 . .

Y Tong , , , X Zhang , , , L Chen . . Tracking frequent items over distributed probabilistic data . . World Wide Web J. , , 2016d . . 19 ( ( 4 ): ): 579 - - 604 . . DOI: 10.1007/s11280-015-0341-5 http://doi.org/10.1007/s11280-015-0341-5 . .

DB West . . Introduction to Graph Theory , , 2001 . . : Pearson : . .

D Yang , , , C Shen , , , W Lee , , , 等 . . On socio-spatial group query for location-based social networks . . 2012 . . Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining . . 949 - - 957 . . DOI: 10.1145/2339530.2339679 http://doi.org/10.1145/2339530.2339679 . .

CJ Zhang , , , L Chen , , , Y Tong . . MaC: a probabilistic framework for query answering with machine-crowd collaboration . . 2014a . . Proc. 23rd ACM Int. Conf. on Information and Knowledge Management . . 11 - - 20 . . DOI: 10.1145/2661829.2661880 http://doi.org/10.1145/2661829.2661880 . .

CJ Zhang , , , Y Tong , , , L Chen . . Where to: crowdaided path selection . . Proc. VLDB Endow. , , 2014b . . 7 ( ( 14 ): ): 2005 - - 2016 . . DOI: 10.14778/2733085.2733105 http://doi.org/10.14778/2733085.2733105 . .

CJ Zhang , , , L Chen , , , Y Tong , , , 等 . . Cleaning uncertain data with a noisy crowd . . 2015 . . Proc. 31st IEEE Int. Conf. on Data Engineering . . 6 - - 17 . . DOI: 10.1109/ICDE.2015.7113268 http://doi.org/10.1109/ICDE.2015.7113268 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Focused crawling strategies based on ontologies and simulated annealing methods for rainstorm disaster domain knowledge

KeJia: towards an autonomous service robot with tolerance of unexpected environmental changes

Task planning in robotics: an empirical comparison of PDDL- and ASP-based systems