Optimizing Crowd-Aware Multi-Agent Path Finding through Local Broadcasting with Graph Neural Networks

• URL: http://arxiv.org/abs/2309.10275v2
• Date: Mon, 25 Mar 2024 20:28:22 GMT
• Title: Optimizing Crowd-Aware Multi-Agent Path Finding through Local Broadcasting with Graph Neural Networks
• Authors: Phu Pham, Aniket Bera,
• Abstract summary: Multi-Agent Path Finding (MAPF) in crowded environments presents a challenging problem in motion planning. We introduce CRAMP, a novel crowd-aware decentralized reinforcement learning approach to address this problem. CRAMP improves the solution quality up to 59% measured in makespan and collision count, and up to 35% improvement in success rate in comparison to previous methods.
• Score: 15.88107215224685
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-Agent Path Finding (MAPF) in crowded environments presents a challenging problem in motion planning, aiming to find collision-free paths for all agents in the system. MAPF finds a wide range of applications in various domains, including aerial swarms, autonomous warehouse robotics, and self-driving vehicles. Current approaches to MAPF generally fall into two main categories: centralized and decentralized planning. Centralized planning suffers from the curse of dimensionality when the number of agents or states increases and thus does not scale well in large and complex environments. On the other hand, decentralized planning enables agents to engage in real-time path planning within a partially observable environment, demonstrating implicit coordination. However, they suffer from slow convergence and performance degradation in dense environments. In this paper, we introduce CRAMP, a novel crowd-aware decentralized reinforcement learning approach to address this problem by enabling efficient local communication among agents via Graph Neural Networks (GNNs), facilitating situational awareness and decision-making capabilities in congested environments. We test CRAMP on simulated environments and demonstrate that our method outperforms the state-of-the-art decentralized methods for MAPF on various metrics. CRAMP improves the solution quality up to 59% measured in makespan and collision count, and up to 35% improvement in success rate in comparison to previous methods.

Related papers

• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning [46.354187895184154]
  Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph. In this work, we investigate the decentralized MAPF setting, when the central controller that posses all the information on the agents' locations and goals is absent. We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones.
  arXiv  Detail & Related papers  (2023-10-02T13:51:32Z)
• AI planning in the imagination: High-level planning on learned abstract search spaces [68.75684174531962]
  We propose a new method, called PiZero, that gives an agent the ability to plan in an abstract search space that the agent learns during training. We evaluate our method on multiple domains, including the traveling salesman problem, Sokoban, 2048, the facility location problem, and Pacman.
  arXiv  Detail & Related papers  (2023-08-16T22:47:16Z)
• Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via Environment Manipulation [12.401344261399613]
  Multi-agent pathfinding is concerned with planning collision-free paths for a team of agents from their start to goal locations in an environment cluttered with obstacles. We introduce a new extension of MAPF, which we call Terraforming MAPF (tMAPF), where some agents are responsible for moving obstacles to clear the way for other agents. We present extensions of two state-of-the-art algorithms, CBS and PBS, in order to tackle tMAPF, and demonstrate that they can consistently outperform the best solution possible under a static-obstacle setting.
  arXiv  Detail & Related papers  (2022-03-20T12:18:35Z)
• Learning Cooperation and Online Planning Through Simulation and Graph Convolutional Network [5.505634045241288]
  We introduce a simulation based online planning algorithm, that we call SiCLOP, for multi-agent cooperative environments. Specifically, SiCLOP tailors Monte Carlo Tree Search (MCTS) and uses Coordination Graph (CG) and Graph Neural Network (GCN) to learn cooperation. It also improves scalability through an effective pruning of action space.
  arXiv  Detail & Related papers  (2021-10-16T05:54:32Z)
• Locality Matters: A Scalable Value Decomposition Approach for Cooperative Multi-Agent Reinforcement Learning [52.7873574425376]
  Cooperative multi-agent reinforcement learning (MARL) faces significant scalability issues due to state and action spaces that are exponentially large in the number of agents. We propose a novel, value-based multi-agent algorithm called LOMAQ, which incorporates local rewards in the Training Decentralized Execution paradigm.
  arXiv  Detail & Related papers  (2021-09-22T10:08:15Z)
• Effects of Smart Traffic Signal Control on Air Quality [0.0]
  Multi-agent deep reinforcement learning (MARL) has been studied experimentally in traffic systems. A recently developed multi-agent variant of the well-established advantage actor-critic (A2C) algorithm, called MA2C, exploits the promising idea of some communication among the agents. In this view, the agents share their strategies with other neighbor agents, thereby stabilizing the learning process even when the agents grow in number and variety.
  arXiv  Detail & Related papers  (2021-07-06T02:48:42Z)
• Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
  Multi Agent Path Finding (MAPF) requires identification of conflict free paths for spatially-extended agents. These find application in real world problems like Convoy Movement Problem, Train Scheduling etc. Our proposed approach, Decentralised Multi Agent Path Finding (DeMAPF), handles MAPF as a sequence of pathplanning and allocation problems.
  arXiv  Detail & Related papers  (2021-06-03T18:07:26Z)
• Optimizing Mixed Autonomy Traffic Flow With Decentralized Autonomous Vehicles and Multi-Agent RL [63.52264764099532]
  We study the ability of autonomous vehicles to improve the throughput of a bottleneck using a fully decentralized control scheme in a mixed autonomy setting. We apply multi-agent reinforcement algorithms to this problem and demonstrate that significant improvements in bottleneck throughput, from 20% at a 5% penetration rate to 33% at a 40% penetration rate, can be achieved.
  arXiv  Detail & Related papers  (2020-10-30T22:06:05Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

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.