Online Task Allocation Strategy for Spatial Crowdsourcing Based on Prediction Algorithm

doi:10.19678/j.issn.1000-3428.0057768

Abstract

Abstract: Based on the diversity of Spatial Crowdsourcing(SC) tasks,this paper constructs a task allocation model for SC,and proposes an online task allocation strategy based on the prediction algorithm.In the batch processing mode,the problem of Maximum Score Assignment(MSA) is transformed into the problem of searching for the maximum weighted bipartite graph matching.The Hungarian algorithm is used to solve the problem to obtain the maximum score of each time interval,and the prediction algorithm is used to ensure workers that have completed the task are in the task-intensive regions as far as possible,so the possibility of workers finding no suitable task to execute is reduced,and the optimal online task allocation of the model is implemented.Experimental results on the real dataset provided by Didi show that compared with the BASIC,LLEP and CDP strategies,the proposed strategy can improve the total number of task assignment in the whole time interval by up to 10%,and has a higher task allocation efficiency and quality.

Key words: Spatial Crowdsourcing(SC), task allocation, prediction algorithm, Hungarian algorithm, constraint solving

摘要： 根据空间众包任务类型的多样化特点，构建空间众包任务分配模型并提出基于预测算法的在线任务分配策略。在批处理模式下，将最大分数任务分配问题转化为寻找二分图最大权匹配问题，通过匈牙利算法对其进行求解得到每个时间片的最大分数，并利用预测算法使得工人在完成该任务后尽可能处于任务密集区域，避免出现工人没有合适任务可执行的情况发生，实现模型的最优在线任务分配。在滴滴快车数据集上的实验结果表明，与BASIC、LLEP和CDP策略相比，该策略在整个时间段内的总任务分配数量最多能提高10%，具有更高的任务分配效率与质量。

关键词: 空间众包, 任务分配, 预测算法, 匈牙利算法, 约束求解

CLC Number:

TP311

XING Hu, CHEN Rong, TANG Wenjun. Online Task Allocation Strategy for Spatial Crowdsourcing Based on Prediction Algorithm[J]. Computer Engineering, 2020, 46(9): 27-34,43.

邢虎, 陈荣, 唐文君. 基于预测算法的在线空间众包任务分配策略[J]. 计算机工程, 2020, 46(9): 27-34,43.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0057768

http://www.ecice06.com/EN/Y2020/V46/I9/27

Figures/Tables 17

References

[1] KAZEMI L,SHAHABI C.GeoCrowd:enabling query answering with spatial crowdsourcing[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems.New York,USA:ACM Press,2012:189-198.
[2] FRITZ S,MCCALLUM I,SCHILL C,et al.Geo-Wiki.Org:the use of crowdsourcing to improve global land cover[J].Remote Sensing,2009,1(3):345-354.
[3] XING Hanfa,MENG Yuan,HOU Dongyang,et al.Employing crowdsourced geographic information to classify land cover with spatial clustering and topic model[J].Remote Sensing,2017,9(6):602-608.
[4] TWIGG J,CHRISTIE N,HAWORTH J,et al.Improved methods for fire risk assessment in low-income and informal settlements[J].International Journal of Environmental Research and Public Health,2017,14(2):139-158.
[5] LUE E,WILSON J P,CURTIS A.Conducting disaster damage assessments with spatial video,experts,and citizens[J].Applied Geography,2014,52:46-54.
[6] PETTINARI M L,OTTMAR R D,PRICHARD S J,et al.Development and mapping of fuel characteristics and associated fire potentials for South America[J].International Journal of Wildland Fire,2014,23(5):643-654.
[7] BOULOS M N K,RESCH B,CROWLEY D N,et al.Crowdsourcing,citizen sensing and sensor Web technologies for public and environmental health surveillance and crisis management:trends,OGC standards and application examples[J].International Journal of Health Geographics,2011,10(1):67-78.
[8] TO H,SHAHABI C,KAZEMI L.A server-assigned spatial crowdsourcing framework[J].ACM Transactions on Spatial Algorithms and Systems,2015,1(1):1-28.
[9] CHENG Peng,LIAN Xiang,CHEN Lei,et al.Task assignment on multi-skill oriented spatial crowdsourcing[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(8):2201-2215.
[10] HU Huiqi,BAO Zhifeng,LI Guoliang,et al.Crowdsourced POI labelling:location-aware result inference and task assignment[C]//Proceedings of the 32nd International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2016:61-72.
[11] DENG D X,SHAHABI C,DEMIRYUREK U.Maximizing the number of worker's self-selected tasks in spatial crowdsourcing[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York,USA:ACM Press,2013:324-333.
[12] LI Y,YIU M L,XU W J.Oriented online route recommendation for spatial crowdsourcing task workers[C]//Proceedings of International Symposium on Spatial and Temporal Databases.Berlin,Germany:Springer,2015:137-156.
[13] LI Yiming,FANG Jingzhi,ZENG Yuxiang,et al.Two-sided online bipartite matching in spatial data:experiments and analysis[J].GeoInformatica,2020,24(1):175-198.
[14] GUMMIDI S R B,XIE X K,PEDERSEN T B.A survey of spatial crowdsourcing[J].ACM Transactions on Database Systems,2019,44(2):1-46.
[15] CHENG Peng,LIAN Xiang,CHEN Lei,et al.Prediction-based task assignment in spatial crowdsourcing[C]//Proceedings of the 33rd International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2017:997-1008.
[16] CHENG Peng,LIAN Xiang,CHEN Zhao,et al.Reliable diversity-based spatial crowdsourcing by moving workers[J].Proceedings of the VLDB Endowment,2015,8(10):1022-1033.
[17] DENG D X,SHAHABI C,DEMIRYUREK U,et al.Task selection in spatial crowdsourcing from worker's perspective[J].GeoInformatica,2016,20(3):529-568.
[18] KARP R M.On-line algorithms versus off-line algorithms:how much is it worth to know the future?[J].Mathematical Social Sciences,1993,25(3):307-315.
[19] ASGHARI M,SHAHABI C.An on-line truthful and individually rational pricing mechanism for ride-sharing[C]//Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York,USA:ACM Press,2017:1-10.
[20] TONG Yongxin,WANG Libin,ZHOU Zimu,et al.Flexible online task assignment in real-time spatial data[J].Proceedings of the VLDB Endowment,2017,10(11):1334-1345.

Please choose a citation manager

Content to export