Dynamic neighbourhood optimisation for task allocation using multi-agent

• URL: http://arxiv.org/abs/2102.08307v1
• Date: Tue, 16 Feb 2021 17:49:14 GMT
• Title: Dynamic neighbourhood optimisation for task allocation using multi-agent
• Authors: Niall Creech, Natalia Criado Pacheco, Simon Miles
• Abstract summary: In large-scale systems there are challenges when centralised techniques are used for task allocation. This paper presents four algorithms to solve these problems. It provides 5x better performance recovery over no-knowledge retention approaches when system connectivity is impacted.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In large-scale systems there are fundamental challenges when centralised techniques are used for task allocation. The number of interactions is limited by resource constraints such as on computation, storage, and network communication. We can increase scalability by implementing the system as a distributed task-allocation system, sharing tasks across many agents. However, this also increases the resource cost of communications and synchronisation, and is difficult to scale. In this paper we present four algorithms to solve these problems. The combination of these algorithms enable each agent to improve their task allocation strategy through reinforcement learning, while changing how much they explore the system in response to how optimal they believe their current strategy is, given their past experience. We focus on distributed agent systems where the agents' behaviours are constrained by resource usage limits, limiting agents to local rather than system-wide knowledge. We evaluate these algorithms in a simulated environment where agents are given a task composed of multiple subtasks that must be allocated to other agents with differing capabilities, to then carry out those tasks. We also simulate real-life system effects such as networking instability. Our solution is shown to solve the task allocation problem to 6.7% of the theoretical optimal within the system configurations considered. It provides 5x better performance recovery over no-knowledge retention approaches when system connectivity is impacted, and is tested against systems up to 100 agents with less than a 9% impact on the algorithms' performance.

Related papers

• 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)
• Agent-Oriented Planning in Multi-Agent Systems [54.429028104022066]
  We propose a novel framework for agent-oriented planning in multi-agent systems, leveraging a fast task decomposition and allocation process. We integrate a feedback loop into the proposed framework to further enhance the effectiveness and robustness of such a problem-solving process.
  arXiv  Detail & Related papers  (2024-10-03T04:07:51Z)
• 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)
• Decentralized Learning Strategies for Estimation Error Minimization with Graph Neural Networks [94.2860766709971]
  We address the challenge of sampling and remote estimation for autoregressive Markovian processes in a wireless network with statistically-identical agents. Our goal is to minimize time-average estimation error and/or age of information with decentralized scalable sampling and transmission policies.
  arXiv  Detail & Related papers  (2024-04-04T06:24:11Z)
• Adaptive Resource Allocation for Virtualized Base Stations in O-RAN with Online Learning [60.17407932691429]
  Open Radio Access Network systems, with their base stations (vBSs), offer operators the benefits of increased flexibility, reduced costs, vendor diversity, and interoperability. We propose an online learning algorithm that balances the effective throughput and vBS energy consumption, even under unforeseeable and "challenging'' environments. We prove the proposed solutions achieve sub-linear regret, providing zero average optimality gap even in challenging environments.
  arXiv  Detail & Related papers  (2023-09-04T17:30:21Z)
• Multi-Agent Reinforcement Learning for Long-Term Network Resource Allocation through Auction: a V2X Application [7.326507804995567]
  We formulate offloading of computational tasks from a dynamic group of mobile agents (e.g., cars) as decentralized decision making among autonomous agents. We design an interaction mechanism that incentivizes such agents to align private and system goals by balancing between competition and cooperation. We propose a novel multi-agent online learning algorithm that learns with partial, delayed and noisy state information.
  arXiv  Detail & Related papers  (2022-07-29T10:29: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)
• Computation Resource Allocation Solution in Recommender Systems [19.456109814747048]
  We propose a computation resource allocation solution (CRAS) that maximizes the business goal with limited computation resources and response time. The effectiveness of our method is verified by extensive experiments based on the real dataset from Taobao.com.
  arXiv  Detail & Related papers  (2021-03-03T08:41:43Z)
• Resource allocation in dynamic multiagent systems [0.0]
  The MG-RAO algorithm is developed to solve resource allocation problems in multi-agent systems. It shows a 23 - 28% improvement over fixed resource allocation in the simulated environments. Results also show that, in a volatile system, using the MG-RAO algorithm configured so that child agents model resource allocation for all agents as a whole has 46.5% of the performance of when it is set to model multiple groups of agents.
  arXiv  Detail & Related papers  (2021-02-16T17:56:23Z)
• A Machine Learning Approach for Task and Resource Allocation in Mobile Edge Computing Based Networks [108.57859531628264]
  A joint task, spectrum, and transmit power allocation problem is investigated for a wireless network. The proposed algorithm can reduce the number of iterations needed for convergence and the maximal delay among all users by up to 18% and 11.1% compared to the standard Q-learning algorithm.
  arXiv  Detail & Related papers  (2020-07-20T13:46:42Z)
• 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)

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.