Distributed Online Rollout for Multivehicle Routing in Unmapped Environments

• URL: http://arxiv.org/abs/2305.15596v3
• Date: Sat, 24 Feb 2024 01:57:58 GMT
• Title: Distributed Online Rollout for Multivehicle Routing in Unmapped Environments
• Authors: Jamison W. Weber, Dhanush R. Giriyan, Devendra R. Parkar, Dimitri P. Bertsekas, Andr\'ea W. Richa
• Abstract summary: We present a fully distributed, online, and scalable reinforcement learning algorithm for the well-known multivehicle routing problem. Agents self-organize into local clusters and independently apply a multiagent rollout scheme locally to each cluster. Our algorithm achieves approximately a factor of two cost improvement over the base policy for a range of radii bounded from below and above by two and three times the critical sensing radius, respectively.
• Score: 0.8437187555622164
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work we consider a generalization of the well-known multivehicle routing problem: given a network, a set of agents occupying a subset of its nodes, and a set of tasks, we seek a minimum cost sequence of movements subject to the constraint that each task is visited by some agent at least once. The classical version of this problem assumes a central computational server that observes the entire state of the system perfectly and directs individual agents according to a centralized control scheme. In contrast, we assume that there is no centralized server and that each agent is an individual processor with no a priori knowledge of the underlying network (including task and agent locations). Moreover, our agents possess strictly local communication and sensing capabilities (restricted to a fixed radius around their respective locations), aligning more closely with several real-world multiagent applications. These restrictions introduce many challenges that are overcome through local information sharing and direct coordination between agents. We present a fully distributed, online, and scalable reinforcement learning algorithm for this problem whereby agents self-organize into local clusters and independently apply a multiagent rollout scheme locally to each cluster. We demonstrate empirically via extensive simulations that there exists a critical sensing radius beyond which the distributed rollout algorithm begins to improve over a greedy base policy. This critical sensing radius grows proportionally to the $\log^*$ function of the size of the network, and is, therefore, a small constant for any relevant network. Our decentralized reinforcement learning algorithm achieves approximately a factor of two cost improvement over the base policy for a range of radii bounded from below and above by two and three times the critical sensing radius, respectively.

Related papers

• Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Design [3.5527561584422465]
  We present AlterNAting COordination and Network-Design Algorithm (Anaconda) Anaconda is a scalable algorithm that also enjoys near-optimality guarantees. We demonstrate in simulated scenarios of area monitoring and compare it with a state-of-the-art algorithm.
  arXiv  Detail & Related papers  (2024-09-02T18:11:33Z)
• Networked Communication for Mean-Field Games with Function Approximation and Empirical Mean-Field Estimation [59.01527054553122]
  Decentralised agents can learn equilibria in Mean-Field Games from a single, non-episodic run of the empirical system. We introduce function approximation to the existing setting, drawing on the Munchausen Online Mirror Descent method. We additionally provide new algorithms that allow agents to estimate the global empirical distribution based on a local neighbourhood.
  arXiv  Detail & Related papers  (2024-08-21T13:32:46Z)
• DePAint: A Decentralized Safe Multi-Agent Reinforcement Learning Algorithm considering Peak and Average Constraints [1.1549572298362787]
  We propose a momentum-based decentralized gradient policy method, DePAint, to solve the problem. This is the first privacy-preserving fully decentralized multi-agent reinforcement learning algorithm that considers both peak and average constraints.
  arXiv  Detail & Related papers  (2023-10-22T16:36:03Z)
• Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
  Solving the multi-vehicle routing problem as a team Markov game with partially observable costs. Our multi-agent reinforcement learning approach, the so-called multi-agent Neural Rewriter, builds on the single-agent Neural Rewriter to solve the problem by iteratively rewriting solutions.
  arXiv  Detail & Related papers  (2022-06-13T09:17:40Z)
• AoI-Aware Resource Allocation for Platoon-Based C-V2X Networks via Multi-Agent Multi-Task Reinforcement Learning [22.890835786710316]
  This paper investigates the problem of age of information (AoI) aware radio resource management for a platooning system. Multiple autonomous platoons exploit the cellular wireless vehicle-to-everything (C-V2X) communication technology to disseminate the cooperative awareness messages (CAMs) to their followers. We exploit a distributed resource allocation framework based on multi-agent reinforcement learning (MARL), where each platoon leader (PL) acts as an agent and interacts with the environment to learn its optimal policy.
  arXiv  Detail & Related papers  (2021-05-10T08:39:56Z)
• Competing Adaptive Networks [56.56653763124104]
  We develop an algorithm for decentralized competition among teams of adaptive agents. We present an application in the decentralized training of generative adversarial neural networks.
  arXiv  Detail & Related papers  (2021-03-29T14:42:15Z)
• Learning Connectivity for Data Distribution in Robot Teams [96.39864514115136]
  We propose a task-agnostic, decentralized, low-latency method for data distribution in ad-hoc networks using Graph Neural Networks (GNN) Our approach enables multi-agent algorithms based on global state information to function by ensuring it is available at each robot. We train the distributed GNN communication policies via reinforcement learning using the average Age of Information as the reward function and show that it improves training stability compared to task-specific reward functions.
  arXiv  Detail & Related papers  (2021-03-08T21:48:55Z)
• Decentralized Control with Graph Neural Networks [147.84766857793247]
  We propose a novel framework using graph neural networks (GNNs) to learn decentralized controllers. GNNs are well-suited for the task since they are naturally distributed architectures and exhibit good scalability and transferability properties. The problems of flocking and multi-agent path planning are explored to illustrate the potential of GNNs in learning decentralized controllers.
  arXiv  Detail & Related papers  (2020-12-29T18:59:14Z)
• Multi-Agent Decentralized Belief Propagation on Graphs [0.0]
  We consider the problem of interactive partially observable Markov decision processes (I-POMDPs) We propose a decentralized belief propagation algorithm for the problem. Our work appears to be the first study of decentralized belief propagation algorithm for networked multi-agent I-POMDPs.
  arXiv  Detail & Related papers  (2020-11-06T18:16:26Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  Decentralized multi-agent reinforcement learning algorithms are sometimes unpractical in complicated applications. We propose a flexible fully decentralized actor-critic MARL framework, which can handle large-scale general cooperative multi-agent setting. Our framework can achieve scalability and stability for large-scale environment and reduce information transmission.
  arXiv  Detail & Related papers  (2020-04-17T14:56:29Z)

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.