Task Assignment Algorithms In Spatial Crowdsourcing

The ubiquity of mobile devices and the sharp decreases in the cost of ultra-broadband wireless network flourish the market of spatial crowdsourcing,which has been proposed as a new framework to assign location-aware tasks(e.g.food delivery)to workers.Workers have to physically travel to task-specified locations to perform these spatial tasks.In this paper,we study the task assignment problem that concerns the optimal strategy of assigning each task to the proper worker such that the total number of completed tasks can be maximized.So far,most existing task assignment solutions only apply to specific scenarios,which adopt approximation algorithms to maximize the total number of assigned tasks.However,impractical constraints limit the generalization of these algorithms and greedy-based approximate solutions usually result in local optimization.In contrast to existing works,our proposed solutions focus on the exact algorithm to achieve global optimization,details of which can be listed as follows.(1)We focus on the problem of task assignment in spatial crowdsourcing.Some existing solutions are introduced and both the strengths and weaknesses are analyzed.(2)We identify and study in depth a new task assignment problem in the context of spatial crowdsourcing by taking workers' available working time into consideration.In this mode,working time varies for each worker and the working areas are only subject to workers' deadline,which eliminates impractical constraints and make the solution more general.(3)We propose a novel solution based on tree decomposition techniques,which separates workers into groups according to the task dependency and utilize heuristic-based search algorithm to find the global optimal result from the reconstructed dependency trees.We also propose three optimization strategies to improve the performance.(4)We conduct extensive experiments to study the impact of the key parameters and compare the effectiveness of our proposed solution to the current state-of-the-art solution.