Time-Constrained Task Allocation and Worker Routing in Mobile Crowd-Sensing Using a Decomposition Technique and Deep Q-Learning

Abstract

Mobile crowd-sensing (MCS) is a data collection paradigm, which recruits mobile users with smart devices to perform sensing tasks on a city-wide scale. In MCS, a key challenge is task allocation, especially when MCS applications are time-sensitive, and the platform needs to consider task completion order (since a worker may perform multiple tasks and different task completion orders lead to different travel costs and response times, i.e., the times needed to arrive at the task venues), requirements of tasks (such as deadline and required sensor) and workers heterogeneity. In other words, the task allocation problem consists of multiple task completion order problems, which is challenging to solve due to the large solution space. Therefore, in this paper, we first formulate the considered problem into two related integer linear programming problems (i.e., assignment and task completion order problems) using a decomposition technique in order to reduce the problem size and enable the use of diverse searching strategies. Then, a deep Q-learning (DQN)-based algorithm, namely assignment DQN with a local search (A-DQN w/ LS), is proposed to determine the task–worker assignments, which iteratively employs an asymmetric traveling salesman (ATSP) heuristic to find the task completion orders of the workers. The local optimizer is applied at the end of the A-DQN algorithm to deal with the computation time and local optima. Simulation results show that the proposed method outperforms existing approaches under different sensing dynamics in terms of total cost.

Keywords

• Deep reinforcement learning
• mobile crowd-sensing
• task allocation
• tabu search