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

📄 arXiv: 2410.15449v1 📥 PDF

作者: Yong Zhao, Zhengqiu Zhu, Chen Gao, En Wang, Jincai Huang, Fei-Yue Wang

分类: cs.AI

发布日期: 2024-10-20

💡 一句话要点

提出基于异构图强化学习的HGRL-TA框架，解决空间众包中依赖感知的多任务分配问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 空间众包 任务分配 异构图 强化学习 图神经网络 多任务优化

📋 核心要点

  1. 现有空间众包任务分配方法难以处理子任务间的依赖关系和异构技能需求，导致任务分配效率低下。
  2. 提出HGRL-TA框架，利用异构图表示任务和工作者关系，并通过强化学习进行任务分配决策。
  3. 实验结果表明，HGRL-TA在解决DMA问题上优于现有元启发式方法，平均利润提升21.78%。

📝 摘要（中文）

空间众包(SC)在学术界和工业界日益受到关注，SC平台上的任务变得越来越复杂，需要具备不同技能的工作者之间的协作。最近的研究通过将复杂任务分解为具有依赖关系的子任务，并将它们分配给合适的工作者来解决复杂任务。然而，子任务之间的依赖关系及其异构的技能需求，以及在多任务分配模式下有效利用工作者有限工作时间的需求，给实现最佳任务分配方案带来了挑战。因此，本文正式研究了依赖感知多任务分配(DMA)问题，并提出了一个精心设计的框架来解决它，称为基于异构图强化学习的任务分配(HGRL-TA)。为了解决表示和嵌入多样化问题实例以确保鲁棒泛化的问题，我们提出了一种多关系图模型和一个基于复合路径的异构图注意力网络(CHANet)，用于有效地表示和捕获任务和工作者之间复杂的联系，以及提供问题状态的嵌入。任务分配决策由策略网络顺序确定，该策略网络使用近端策略优化算法与CHANet同时训练。大量的实验结果表明，所提出的HGRL-TA在解决DMA问题上的有效性和通用性，与使用元启发式方法相比，平均利润提高了21.78%。

🔬 方法详解

问题定义：论文旨在解决空间众包中依赖感知多任务分配(DMA)问题。现有方法通常忽略子任务之间的依赖关系以及工作者技能的异构性，导致任务分配方案并非最优，无法充分利用工作者的工作时间，从而影响整体利润。

核心思路：论文的核心思路是将任务和工作者之间的复杂关系建模为异构图，并利用强化学习来学习最优的任务分配策略。通过异构图，可以有效地表示任务之间的依赖关系以及工作者与任务之间的匹配程度。强化学习则用于在考虑长期回报的情况下，做出序列化的任务分配决策。

技术框架：HGRL-TA框架主要包含以下几个模块：1) 多关系图模型：用于表示任务和工作者之间的复杂关系，包括任务之间的依赖关系、工作者与任务之间的技能匹配关系等。2) 基于复合路径的异构图注意力网络(CHANet)：用于学习任务和工作者的嵌入表示，CHANet能够捕获异构图中不同类型节点和边之间的复杂关系。3) 策略网络：用于根据当前状态（任务和工作者的嵌入表示）做出任务分配决策。4) 强化学习训练：使用近端策略优化(PPO)算法同时训练CHANet和策略网络，以最大化长期利润。

关键创新：论文的关键创新在于：1) 提出了多关系图模型来表示空间众包场景中的复杂关系，能够同时建模任务依赖和技能匹配。2) 设计了基于复合路径的异构图注意力网络(CHANet)，能够有效地学习异构图中节点和边的嵌入表示。3) 将异构图表示学习与强化学习相结合，实现端到端的任务分配优化。

关键设计：在多关系图模型中，节点表示任务和工作者，边表示任务之间的依赖关系（例如，任务A必须在任务B之前完成）以及工作者与任务之间的技能匹配程度。CHANet通过聚合来自不同类型邻居节点的信息来更新节点嵌入，聚合权重由注意力机制学习。策略网络采用Actor-Critic结构，Actor网络输出任务分配概率，Critic网络评估当前状态的价值。PPO算法用于优化Actor和Critic网络，目标是最大化累积奖励（利润）。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，HGRL-TA在解决依赖感知多任务分配问题上表现出色，与传统的元启发式方法相比，平均利润提高了21.78%。这表明HGRL-TA能够更有效地利用工作者的工作时间，并做出更优的任务分配决策。此外，实验还验证了HGRL-TA的泛化能力，能够在不同的空间众包场景中取得良好的性能。

🎯 应用场景

该研究成果可应用于各种空间众包平台，例如外卖配送、快递服务、共享出行等。通过优化任务分配，可以提高平台效率、降低运营成本、提升用户体验，并为工作者带来更高的收入。未来，该方法还可以扩展到更复杂的任务分配场景，例如智能制造、智慧城市等。

📄 摘要（原文）

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.