# Heterogeneous Graph Reinforcement Learning for Dependency-aware Multi-task Allocation in Spatial Crowdsourcing

arXiv: https://arxiv.org/abs/2410.15449 · HTML: https://mlsanity.com/paper/2410.15449/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 10 of its 54 references that are in the map.
- First posted on arXiv 20 Oct 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 10 of 10)

- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [A Survey on Heterogeneous Graph Embedding: Methods, Techniques, Applications and Sources](https://mlsanity.com/paper/2011.14867/) (2020)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Simple and Efficient Heterogeneous Graph Neural Network](https://mlsanity.com/paper/2207.02547/) (2022)
- [Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case](https://mlsanity.com/paper/1910.07421/) (2019)
- [Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time](https://mlsanity.com/paper/2006.03750/) (2020)
- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [Task Assignment on Multi-Skill Oriented Spatial Crowdsourcing](https://mlsanity.com/paper/1510.03149/) (2015)
- [TaskMe: Multi-Task Allocation in Mobile Crowd Sensing](https://mlsanity.com/paper/1608.02657/) (2016)
- [CrowdOS: A Ubiquitous Operating System for Crowdsourcing and Mobile Crowd Sensing](https://mlsanity.com/paper/1909.00805/) (2019)

## Built on by (most cited first, 1 of 1)

- [A Multi-Agent Reinforcement Learning Approach for Cooperative Air-Ground-Human Crowdsensing in Emergency Rescue](https://mlsanity.com/paper/2505.06997/) (2025)

## Abstract (arXiv)

Spatial Crowdsourcing (SC) is gaining traction in both academia and industry, with tasks on SC platforms becoming increasingly complex and requiring collaboration among workers with diverse skills. Recent research works address complex tasks by dividing them into subtasks with dependencies and assigning them to suitable workers. However, the dependencies among subtasks and their heterogeneous skill requirements, as well as the need for efficient utilization of workers' limited work time in the multi-task allocation mode, pose challenges in achieving an optimal task allocation scheme. Therefore, this paper formally investigates the problem of Dependency-aware Multi-task Allocation (DMA) and presents a well-designed framework to solve it, known as Heterogeneous Graph Reinforcement Learning-based Task Allocation (HGRL-TA). To address the challenges associated with representing and embedding diverse problem instances to ensure robust generalization, we propose a multi-relation graph model and a Compound-path-based Heterogeneous Graph Attention Network (CHANet) for effectively representing and capturing intricate relations among tasks and workers, as well as providing embedding of problem state. The task allocation decision is determined sequentially by a policy network, which undergoes simultaneous training with CHANet using the proximal policy optimization algorithm. Extensive experiment results demonstrate the effectiveness and generality of the proposed HGRL-TA in solving the DMA problem, leading to average profits that is 21.78% higher than those achieved using the metaheuristic methods.