A Multi-armed Bandit Approach to Online Spatial Task Assignment

Spatial crowd sourcing 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 assignments 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.