Cost-Efficient Worker Trajectory Planning Optimization in Spatial Crowdsourcing Platforms

摘要

With the progress of mobile devices and the successful usage of the wisdom of crowds, spatial crowdsourcing has attracted much attention from the research community. This paper addresses the efficient worker recruitment problem under the task coverage constraint. The efficiency of worker recruitment is measured by the total quality collected by a set of workers and the corresponding cost, e.g., proportional to the overall trajectory length of workers. Specifically, we consider two different scenarios, 1-D line topology and general 2-D topology, in which workers may have either homogeneous or heterogeneous crowdsourcing quality (e.g., the quality of videos or photos for an object at a particular location). In the 1-D scenario, we propose two dynamic programming approaches to find the optimal solution in both homogeneous and heterogeneous cases. In the general 2-D scenario, the proposed problem turns out to be NP-hard even in the homogeneous case. We first prove that the simple nearest assignment has an approximation ratio of 1/(2n), where n is the number of the workers. Therefore, the nearest assignment cannot be scalable. We further propose a novel assignment approach based on the minimum spanning tree. The proposed approach is proved to be close to the optimal solution in the homogeneous case and 1/ρ in the heterogeneous case, where ρ is the maximum quality ratio between two workers. The effectiveness of the proposed algorithm is verified using a real mobility trace: Uber pick-up trace in the New York City.