Collaborative Task Allocation With Reinforcement Learning and Heterogeneous Graph Attention

Abstract

Task allocation is a core problem of mobile crowdsensing (MCS) applications. Depending on sensing task requirements and worker capabilities, tasks are allocated to selected workers that can meet various constraints and complete the tasks efficiently. Typically, an MCS platform serves as a mediator and assists the allocation, which is similar to the Uber system that matches passengers and drivers. As an incentive, the MCS platform typically aims to maximize its profit while respecting the limitations of both sides. Although task allocation has been studied widely in the literature, we focus on a less addressed aspect, which is to balance achievable profits and collaboration efficiency among a group of workers allocated to fulfill a task. In particular, we take into account the impact of workers’ collaboration efficiency on the achieved performance. As our collaborative task allocation problem is proved to be NP-hard, we formulate the problem based on a temporal heterogeneous graph and apply an expressive neural network model to represent graph-based problem instances. Thus, we can use a deep reinforcement learning (DRL) approach to train a solution model, which is expected to be generalizable to diverse instances. To reduce the network dimensionality and capture essential features, we decompose the heterogeneous graph into smaller and simpler subgraphs and use graph attention networks (GATs) [Veličković et al. (2018)] to transform subgraphs into embedding vectors. We conduct extensive experiments to train and test the solution model with different DRL approaches. The results show that the proposed approach offers competitive advantages over the reference heuristic and attention-based methods.