arXiv:2410.15449cs.AI2024-10被引 3

用图强化学习解决空间众包中多任务依赖分配问题,提升收益21.78%。

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

  • 构建异构图注意力网络,捕捉任务与工人间复杂依赖关系
  • 通过强化学习策略网络实现逐次最优分配,平均利润高出传统方法21.78%
  • 适用于需协同技能、有依赖关系的复杂空间众包任务分配

空间众包(SC)在学术界和工业界日益流行,任务日趋复杂,需具备不同技能的工人协作完成。现有研究将复杂任务分解为有依赖关系的子任务并分配给合适工人,但子任务间的依赖关系、异构技能需求以及工人有限工作时间的高效利用,给多任务分配带来挑战。本文正式研究依赖感知多任务分配(DMA)问题,提出基于异构图强化学习的任务分配框架HGRL-TA。为有效表示和嵌入多样化问题实例以保证鲁棒泛化能力,设计多关系图模型与基于复合路径的异构图注意力网络(CHANet),精准捕捉任务与工人间的复杂关系并生成问题状态嵌入。任务分配决策由策略网络逐次确定,与CHANet联合使用近端策略优化算法进行训练。大量实验表明,所提HGRL-TA在解决DMA问题上具有显著有效性与通用性,平均收益比元启发式方法高21.78%。

原文摘要 · Abstract (English)

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.

空间众包多任务分配图神经网络强化学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。