ul Hassan, Umair and Curry, Edward
(2016)
Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning.
Expert Systems with Applications, 58.
pp. 36-56.
ISSN 09574174
Abstract
Spatial crowdsourcing has emerged as a new paradigm for solving problems in the physical world with the help of human workers. A major challenge in spatial crowdsourcing is to assign reliable workers to nearby tasks. The goal of such task assignment process is to maximize the task completion in the face of uncertainty. This process is further complicated when tasks arrivals are dynamic and worker reliability is unknown. Recent research proposals have tried to address the challenge of dynamic task assignment. Yet the majority of the proposals do not consider the dynamism of tasks and workers. They also make the unrealistic assumptions of known deterministic or probabilistic workers’ reliabilities. In this paper, we propose a novel approach for dynamic task assignment in spatial crowdsourcing. The proposed approach combines bi-objective optimization with combinatorial multi-armed bandits. We formulate an online optimization problem to maximize task reliability and minimize travel costs in spatial crowdsourcing. We propose the distance-reliability ratio (DRR) algorithm based on a combinatorial fractional programming approach. The DRR algorithm reduces travel costs by 80% while maximizing reliability when compared to existing algorithms. We extend the DRR algorithm for the scenario when worker reliabilities are unknown. We propose a novel algorithm (DRR-UCB) that uses an interval estimation heuristic to approximate worker reliabilities. Experimental results demonstrate that the DRR-UCB achieves high reliability in the face of uncertainty. The proposed approach is particularly suited for real-life dynamic spatial crowdsourcing scenarios. This approach is generalizable to the similar problems in other areas in expert systems. First, it encompasses online assignment problems when the objective function is a ratio of two linear functions. Second, it considers situations when intelligent and repeated assignment decisions are needed under uncertainty.
| Item Type: |
Article
|
| Keywords: |
Spatial crowdsourcing;
Task assignment;
Combinatorial fractional programming;
Multi-armed bandit; |
| Academic Unit: |
Faculty of Social Sciences > School of Business |
| Item ID: |
16003 |
| Identification Number: |
https://doi.org/10.1016/j.eswa.2016.03.022 |
| Depositing User: |
Souleiman Hasan
|
| Date Deposited: |
24 May 2022 15:46 |
| Journal or Publication Title: |
Expert Systems with Applications |
| Publisher: |
Elsevier |
| Refereed: |
Yes |
| URI: |
|
| Use Licence: |
This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available
here |
Repository Staff Only(login required)
 |
Item control page |
Downloads per month over past year
Origin of downloads
Altmetric
Altmetric