Research On Task Allocation Methods For Crowdsourcing Systems

With the rapid development of Web2.0 technology,Internet thinking has been deeply integrated into every aspect of people’s thinking,study and life.As a new working mode,crowdsourcing is a distributed problem solving mechanism open to the Internet public,which could perfectly reflect the advantages of group wisdom.It has been successfully applied in many fields and has become a new hotspot in computer research.Task assignment is the core research problem in crowdsourcing system,and also the most important part in the process of crowdsourcing.This thesis takes traditional crowdsourcing,spatial crowdsourcing,and spatio-temporal crowdsourcing as the application background and research object.According to the problems of insufficient task matching quantity,low matching quality,low algorithm efficiency,and susceptibility to local optima,based on optimization theory,bipartite graph matching,recommendation system,path planning and other theories and methods,this thesis conducts in-depth analysis and research on offline task allocation and online task allocation in different types of crowdsourcing.The main research contents and innovations of this thesis are as follows:(1)In the traditional crowdsourcing task and worker assignment,a crowdsourcing task assignment algorithm based on Word2vec semantic similarity is proposed to solve the problem of insufficient task matching.Using the Word2vec method to train each word vector,the semantic label similarity matrix library is established by calculating the similarity between word vectors.Through the description text of the crowd task and the crowd worker,the semantic label matrix of the crowd task and the crowd worker is established,respectively.In addition,the correlation degree between the crowd worker and the crowd task is obtained based on the label similarity matrix,so as to realize the personalized recommendation of the crowd task.The accuracy of the matching between the crowd task and the crowd worker is improved through the threshold setting.The cold start problem is solved because the matching process does not require much consideration of historical information.By comparing and analyzing the simulation data and the data of Tianpeng network,the task allocation method based on Word2vec could match more crowd tasks and crowd workers,and make the task assignment with higher accuracy.(2)In the off-line task assignment of spatial crowdsourcing,aiming at the problems of mismatch between service quality and reward and low total utility of platform,a task assignment algorithm based on Agent negotiation and optimization is proposed to maximize total utility and average matching quality.The service quality of crowd workers is calculated by the generalized Pareto distribution.The mismatch between service quality and reward is quantified as the matching quality,and the positive correlation between the matching quality and the total effect is proved.The matching quality and the total utility of distribution are improved by Agent bilateral negotiation.Experiments are conducted on simulation data and gMission real data set.Through comparative analysis,the spatial crowdsourcing task assignment algorithm based on Agent negotiation has obvious advantages in terms of matching quality and total utility.(3)In the spatial crowdsourcing online task assignment,aiming at the problem of real-time performance and minimizing movement distance in online task allocation,a two-stage matching algorithm(Greedy and Hungarian,GH)based on time window is proposed.In the first stage,the matching process is divided into several continuous time Windows.A dynamic time window setting method based on BP neural network is proposed,and the crowd work place and the crowd workers in the same time window are matched.In the second stage,the crowd work place matched with the crowd workers in the previous stage is matched with the crowd tasks.Because of the relatively high time complexity of the Hungarian algorithm,the Adaptive Threshold(GH-AT)algorithm is further proposed and added with an adaptive threshold mechanism,so as to improve the overall operating efficiency and optimization effect of the algorithm.Through comparative analysis of experiments,the GH-AT algorithm has good advantages in reducing average moving distance cost and improving operation efficiency.(4)In spatio-temporal crowdsourcing online task assignment,aiming at the problem of multi-task path planning of single-order workers with time and space constraints,an adaptive tabu search task assignment method based on path planning is proposed.According to the relationship among tasks,worker density and time,the time window is set dynamically.The duration of online tasks is predicted by using LSTM,which is based on time-short memory cycle neural network.According to the estimated waiting time of each spatio-temporal crowd task,the crowd tasks in the region are matched.To avoid falling into local optima,the tabu search algorithm is used to realize the shortest path planning,which could ensure the task is completed in the shortest time,and reduce the overall moving cost of the task.Through comparative analysis of experiments,the method proposed in this thesis has outstanding performances on the multi-task online assignment,the total utility of the platform,the task matching efficiency,and the mobile cost.