Towards City-scale Mobile Crowdsourcing: Task Recommendations under Trajectory Uncertainties

• Main Authors: CHEN CEN, CHENG, Shih-Fen, LAU, Hoong Chuin, MISRA, Archan
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2015
• Subjects: Deterministic modeling; Industry practices; Integer linear program; sLagrangian relaxation techniques; Location based; Mobile crowdsourcing; Stochastic task; Transportation network; Computer Sciences; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/2815; https://ink.library.smu.edu.sg/context/sis_research/article/3815/viewcontent/IJCAI2015_City_scaleCrowdsourcing.pdf
• Institution: Singapore Management University

In this work, we investigate the problem of large-scale mobile crowdsourcing, where workers are financially motivated to perform location-based tasks physically. Unlike current industry practice that relies on workers to manually pick tasks to perform, we automatically make task recommendation based on workers’ historical trajectories and desired time budgets. The challenge of predicting workers’ trajectories is that it is faced with uncertainties, as a worker does not take same routes every day. In this work, we depart from deterministic modeling and study the stochastic task recommendation problem where each worker is associated with several predicted routine routes with probabilities. We formulate this problem as a stochastic integer linear program whose goal is to maximize the expected total utility achieved by all workers. We further exploit the separable structures of the formulation and apply the Lagrangian relaxation technique to scale up computation. Experiments have been performed over the instances generated using the real Singapore transportation network. The results show that we can find significantly better solutions than the deterministic formulation.