by Umair Ul Hassan, Edward Curry
Abstract:
Spatial crowdsourcing uses workers for performing tasks that require travel to different locations in the physical world. This paper considers the online spatial task assignment problem. In this problem, spatial tasks arrive in an online manner and an appropriate worker must be assigned to each task. However, outcome of an assignment is stochastic since the worker can choose to accept or reject the task. Primary goal of the assignment algorithm is to maximize the number of successful as- signments over all tasks. This presents an exploration-exploitation challenge; the algorithm must learn the task acceptance behavior of workers while selecting the best worker based on the previous learning. We address this challenge by defining a framework for online spatial task assignment based on the multi-armed bandit formalization of the problem. Furthermore, we adapt a contextual bandit algorithm to assign a worker based on the spatial features of tasks and workers. The algorithm simultaneously adapts the worker assignment strategy based on the observed task acceptance behavior of workers. Finally, we present an evaluation methodology based on a real world dataset, and evaluate the performance of the proposed algorithm against the baseline algorithms. The results demonstrate that the proposed algorithm performs better in terms of the number of successful assignments.
Reference:
Umair Ul Hassan, Edward Curry, "A Multi-armed Bandit Approach to Online Spatial Task Assignment", In 2014 IEEE 11th Intl Conf on Ubiquitous Intelligence and Computing, IEEE, pp. 212-219, 2014. Best Paper Award
Bibtex Entry:
@inproceedings{Hassan2014a,
abstract = {Spatial crowdsourcing uses workers for performing tasks that require travel to different locations in the physical world. This paper considers the online spatial task assignment problem. In this problem, spatial tasks arrive in an online manner and an appropriate worker must be assigned to each task. However, outcome of an assignment is stochastic since the worker can choose to accept or reject the task. Primary goal of the assignment algorithm is to maximize the number of successful as- signments over all tasks. This presents an exploration-exploitation challenge; the algorithm must learn the task acceptance behavior of workers while selecting the best worker based on the previous learning. We address this challenge by defining a framework for online spatial task assignment based on the multi-armed bandit formalization of the problem. Furthermore, we adapt a contextual bandit algorithm to assign a worker based on the spatial features of tasks and workers. The algorithm simultaneously adapts the worker assignment strategy based on the observed task acceptance behavior of workers. Finally, we present an evaluation methodology based on a real world dataset, and evaluate the performance of the proposed algorithm against the baseline algorithms. The results demonstrate that the proposed algorithm performs better in terms of the number of successful assignments.},
annote = {Best Paper Award},
author = {Hassan, Umair Ul and Curry, Edward},
booktitle = {2014 IEEE 11th Intl Conf on Ubiquitous Intelligence and Computing},
doi = {10.1109/UIC-ATC-ScalCom.2014.68},
file = {:Users/ed/Library/Application Support/Mendeley Desktop/Downloaded/Hassan, Curry - 2014 - A Multi-armed Bandit Approach to Online Spatial Task Assignment.pdf:pdf},
isbn = {978-1-4799-7646-1},
keywords = {multi- armed bandit,spatial crowdsourcing,task assignment},
month = {dec},
pages = {212--219},
publisher = {IEEE},
title = {{A Multi-armed Bandit Approach to Online Spatial Task Assignment}},
url = {http://www.edwardcurry.org/publications/Hassan_UIC2014.pdf},
year = {2014}
}