Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2018

Abstract

Spatial crowdsourcing emerges as a new computing paradigm with the development of mobile Internet and the ubiquity of mobile devices. The core of many real-world spatial crowdsourcing applications is to assign suitable tasks to proper workers in real time. Many works only assign a set of tasks to each worker without making the plan how to perform the assigned tasks. Others either make task plans only for a single worker or are unable to operate in real time. In this paper, we propose a new problem called the Multi-Worker-Aware Task Planning (MWATP) problem in the online scenario, in which we not only assign tasks to workers but also make plans for them, such that the total utility (revenue) is maximized. We prove that the offline version of MWATP problem is NP-hard, and no online algorithm has a constant competitive ratio on the MWATP problem. Two heuristic algorithms, called Delay-Planning and Fast-Planning, are proposed to solve the problem. Extensive experiments on synthetic and real datasets verify the effectiveness and efficiency of the two proposed algorithms.

Keywords

Spatial crowdsourcing, Task assignment, Task planning

Discipline

Software Engineering

Research Areas

Software and Cyber-Physical Systems

Publication

Proceedings of the 23rd Database Systems for Advanced Applications, DASFAA 2018, Gold Coast, 2018 May 21-24

First Page

301

Last Page

317

Identifier

10.1007/978-3-319-91458-9_18

Publisher

Springer Link

City or Country

Gold Coast, Australia

Additional URL

https://doi.org/10.1007/978-3-319-91458-9_18

Share

COinS