A Two-stage Reinforcement Learning-based Approach for Multi-entity Task Allocation

• URL: http://arxiv.org/abs/2407.00496v1
• Date: Sat, 29 Jun 2024 17:13:44 GMT
• Title: A Two-stage Reinforcement Learning-based Approach for Multi-entity Task Allocation
• Authors: Aicheng Gong, Kai Yang, Jiafei Lyu, Xiu Li,
• Abstract summary: 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.
• Score: 27.480892280342417
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Task allocation is a key combinatorial optimization problem, crucial for modern applications such as multi-robot cooperation and resource scheduling. Decision makers must allocate entities to tasks reasonably across different scenarios. However, traditional methods assume static attributes and numbers of tasks and entities, often relying on dynamic programming and heuristic algorithms for solutions. In reality, task allocation resembles Markov decision processes, with dynamically changing task and entity attributes. Thus, algorithms must dynamically allocate tasks based on their states. To address this issue, we propose a two-stage task allocation algorithm based on similarity, utilizing reinforcement learning to learn allocation strategies. The proposed pre-assign strategy allows entities to preselect appropriate tasks, effectively avoiding local optima and thereby better finding the optimal allocation. We also introduce an attention mechanism and a hyperparameter network structure to adapt to the changing number and attributes of entities and tasks, enabling our network structure to generalize to new tasks. Experimental results across multiple environments demonstrate that our algorithm effectively addresses the challenges of dynamic task allocation in practical applications. Compared to heuristic algorithms like genetic algorithms, our reinforcement learning approach better solves dynamic allocation problems and achieves zero-shot generalization to new tasks with good performance. The code is available at https://github.com/yk7333/TaskAllocation.

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)
• Heterogeneous Graph Reinforcement Learning for Dependency-aware Multi-task Allocation in Spatial Crowdsourcing [33.915222518617085]
  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.
  arXiv  Detail & Related papers  (2024-10-20T17:00:45Z)
• Learning Dual-arm Object Rearrangement for Cartesian Robots [28.329845378085054]
  This work focuses on the dual-arm object rearrangement problem abstracted from a realistic industrial scenario of Cartesian robots. The goal of this problem is to transfer all the objects from sources to targets with the minimum total completion time. We develop an effective object-to-arm task assignment strategy for minimizing the cumulative task execution time and maximizing the dual-arm cooperation efficiency.
  arXiv  Detail & Related papers  (2024-02-21T09:13:08Z)
• Multi-Objective Optimization for Sparse Deep Multi-Task Learning [0.0]
  We present a Multi-Objective Optimization algorithm using a modified Weighted Chebyshev scalarization for training Deep Neural Networks (DNNs) Our work aims to address the (economical and also ecological) sustainability issue of DNN models, with particular focus on Deep Multi-Task models.
  arXiv  Detail & Related papers  (2023-08-23T16:42:27Z)
• Fast Inference and Transfer of Compositional Task Structures for Few-shot Task Generalization [101.72755769194677]
  We formulate it as a few-shot reinforcement learning problem where a task is characterized by a subtask graph. Our multi-task subtask graph inferencer (MTSGI) first infers the common high-level task structure in terms of the subtask graph from the training tasks. Our experiment results on 2D grid-world and complex web navigation domains show that the proposed method can learn and leverage the common underlying structure of the tasks for faster adaptation to the unseen tasks.
  arXiv  Detail & Related papers  (2022-05-25T10:44:25Z)
• Elastic Architecture Search for Diverse Tasks with Different Resources [87.23061200971912]
  We study a new challenging problem of efficient deployment for diverse tasks with different resources, where the resource constraint and task of interest corresponding to a group of classes are dynamically specified at testing time. Previous NAS approaches seek to design architectures for all classes simultaneously, which may not be optimal for some individual tasks. We present a novel and general framework, called Elastic Architecture Search (EAS), permitting instant specializations at runtime for diverse tasks with various resource constraints.
  arXiv  Detail & Related papers  (2021-08-03T00:54:27Z)
• Exploring Relational Context for Multi-Task Dense Prediction [76.86090370115]
  We consider a multi-task environment for dense prediction tasks, represented by a common backbone and independent task-specific heads. We explore various attention-based contexts, such as global and local, in the multi-task setting. We propose an Adaptive Task-Relational Context module, which samples the pool of all available contexts for each task pair.
  arXiv  Detail & Related papers  (2021-04-28T16:45:56Z)
• Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling [8.14784681248878]
  In this paper, we propose a reinforcement learning approach to solve a realistic scheduling problem. We apply it to an algorithm commonly executed in the high performance computing community, the Cholesky factorization. Our algorithm uses graph neural networks in combination with an actor-critic algorithm (A2C) to build an adaptive representation of the problem on the fly.
  arXiv  Detail & Related papers  (2020-11-09T10:57:21Z)
• Multi-task Supervised Learning via Cross-learning [102.64082402388192]
  We consider a problem known as multi-task learning, consisting of fitting a set of regression functions intended for solving different tasks. In our novel formulation, we couple the parameters of these functions, so that they learn in their task specific domains while staying close to each other. This facilitates cross-fertilization in which data collected across different domains help improving the learning performance at each other task.
  arXiv  Detail & Related papers  (2020-10-24T21:35:57Z)
• Learning Adaptive Exploration Strategies in Dynamic Environments Through Informed Policy Regularization [100.72335252255989]
  We study the problem of learning exploration-exploitation strategies that effectively adapt to dynamic environments. We propose a novel algorithm that regularizes the training of an RNN-based policy using informed policies trained to maximize the reward in each task.
  arXiv  Detail & Related papers  (2020-05-06T16:14:48Z)
• Multi-Task Reinforcement Learning with Soft Modularization [25.724764855681137]
  Multi-task learning is a very challenging problem in reinforcement learning. We introduce an explicit modularization technique on policy representation to alleviate this optimization issue. We show our method improves both sample efficiency and performance over strong baselines by a large margin.
  arXiv  Detail & Related papers  (2020-03-30T17:47:04Z)

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.