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

• URL: http://arxiv.org/abs/2410.15449v1
• Date: Sun, 20 Oct 2024 17:00:45 GMT
• Title: Heterogeneous Graph Reinforcement Learning for Dependency-aware Multi-task Allocation in Spatial Crowdsourcing
• Authors: Yong Zhao, Zhengqiu Zhu, Chen Gao, En Wang, Jincai Huang, Fei-Yue Wang,
• Abstract summary: This paper formally investigates the problem of Dependency-aware Multi-task Allocation (DMA) It presents a well-designed framework to solve it, known as Heterogeneous Graph Reinforcement Learning-based Task Allocation (HGRL-TA) 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.
• Score: 33.915222518617085
• License:
• Abstract: 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.

Related papers

• Task-Aware Harmony Multi-Task Decision Transformer for Offline Reinforcement Learning [70.96345405979179]
  The purpose of offline multi-task reinforcement learning (MTRL) is to develop a unified policy applicable to diverse tasks without the need for online environmental interaction. variations in task content and complexity pose significant challenges in policy formulation. We introduce the Harmony Multi-Task Decision Transformer (HarmoDT), a novel solution designed to identify an optimal harmony subspace of parameters for each task.
  arXiv  Detail & Related papers  (2024-11-02T05:49:14Z)
• A Two-stage Reinforcement Learning-based Approach for Multi-entity Task Allocation [27.480892280342417]
  Decision makers must allocate entities to tasks reasonably across different scenarios. Traditional methods assume static attributes and numbers of tasks and entities, often relying on dynamic programming and algorithms for solutions. We propose a two-stage task allocation algorithm based on similarity, utilizing reinforcement learning to learn allocation strategies.
  arXiv  Detail & Related papers  (2024-06-29T17:13:44Z)
• Provable Benefits of Multi-task RL under Non-Markovian Decision Making Processes [56.714690083118406]
  In multi-task reinforcement learning (RL) under Markov decision processes (MDPs), the presence of shared latent structures has been shown to yield significant benefits to the sample efficiency compared to single-task RL. We investigate whether such a benefit can extend to more general sequential decision making problems, such as partially observable MDPs (POMDPs) and more general predictive state representations (PSRs) We propose a provably efficient algorithm UMT-PSR for finding near-optimal policies for all PSRs, and demonstrate that the advantage of multi-task learning manifests if the joint model class of PSR
  arXiv  Detail & Related papers  (2023-10-20T14:50:28Z)
• RHFedMTL: Resource-Aware Hierarchical Federated Multi-Task Learning [11.329273673732217]
  Federated learning is an effective way to enable AI over massive distributed nodes with security. It is challenging to ensure the privacy while maintain a coupled multi-task learning across multiple base stations (BSs) and terminals. In this paper, inspired by the natural cloud-BS-terminal hierarchy of cellular works, we provide a viable resource-aware hierarchical federated MTL (RHFedMTL) solution.
  arXiv  Detail & Related papers  (2023-06-01T13:49:55Z)
• Learning Reward Machines in Cooperative Multi-Agent Tasks [75.79805204646428]
  This paper presents a novel approach to Multi-Agent Reinforcement Learning (MARL) It combines cooperative task decomposition with the learning of reward machines (RMs) encoding the structure of the sub-tasks. The proposed method helps deal with the non-Markovian nature of the rewards in partially observable environments.
  arXiv  Detail & Related papers  (2023-03-24T15:12:28Z)
• Learning Complex Teamwork Tasks Using a Given Sub-task Decomposition [11.998708550268978]
  We propose an approach which uses an expert-provided decomposition of a task into simpler multi-agent sub-tasks. In each sub-task, a subset of the entire team is trained to acquire sub-task-specific policies. The sub-teams are then merged and transferred to the target task, where their policies are collectively fine-tuned to solve the more complex target task.
  arXiv  Detail & Related papers  (2023-02-09T21:24:56Z)
• Residual Q-Networks for Value Function Factorizing in Multi-Agent Reinforcement Learning [0.0]
  We propose a novel concept of Residual Q-Networks (RQNs) for Multi-Agent Reinforcement Learning (MARL) The RQN learns to transform the individual Q-value trajectories in a way that preserves the Individual-Global-Max criteria (IGM) The proposed method converges faster, with increased stability and shows robust performance in a wider family of environments.
  arXiv  Detail & Related papers  (2022-05-30T16:56:06Z)
• Semantic-Aware Collaborative Deep Reinforcement Learning Over Wireless Cellular Networks [82.02891936174221]
  Collaborative deep reinforcement learning (CDRL) algorithms in which multiple agents can coordinate over a wireless network is a promising approach. In this paper, a novel semantic-aware CDRL method is proposed to enable a group of untrained agents with semantically-linked DRL tasks to collaborate efficiently across a resource-constrained wireless cellular network.
  arXiv  Detail & Related papers  (2021-11-23T18:24:47Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)
• Gradient Surgery for Multi-Task Learning [119.675492088251]
  Multi-task learning has emerged as a promising approach for sharing structure across multiple tasks. The reasons why multi-task learning is so challenging compared to single-task learning are not fully understood. We propose a form of gradient surgery that projects a task's gradient onto the normal plane of the gradient of any other task that has a conflicting gradient.
  arXiv  Detail & Related papers  (2020-01-19T06:33:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.