Improving Learnt Local MAPF Policies with Heuristic Search

• URL: http://arxiv.org/abs/2403.20300v1
• Date: Fri, 29 Mar 2024 17:16:20 GMT
• Title: Improving Learnt Local MAPF Policies with Heuristic Search
• Authors: Rishi Veerapaneni, Qian Wang, Kevin Ren, Arthur Jakobsson, Jiaoyang Li, Maxim Likhachev,
• Abstract summary: Multi-agent path finding (MAPF) is the problem of finding collision-free paths for a team of agents to reach their goal locations. Current machine learning approaches to MAPF have proposed methods that have started to scratch the surface of this potential. We show several model-agnostic ways to use search with learnt policies that significantly improve the policies' success rates and scalability.
• Score: 24.06091123268885
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-agent path finding (MAPF) is the problem of finding collision-free paths for a team of agents to reach their goal locations. State-of-the-art classical MAPF solvers typically employ heuristic search to find solutions for hundreds of agents but are typically centralized and can struggle to scale when run with short timeouts. Machine learning (ML) approaches that learn policies for each agent are appealing as these could enable decentralized systems and scale well while maintaining good solution quality. Current ML approaches to MAPF have proposed methods that have started to scratch the surface of this potential. However, state-of-the-art ML approaches produce "local" policies that only plan for a single timestep and have poor success rates and scalability. Our main idea is that we can improve a ML local policy by using heuristic search methods on the output probability distribution to resolve deadlocks and enable full horizon planning. We show several model-agnostic ways to use heuristic search with learnt policies that significantly improve the policies' success rates and scalability. To our best knowledge, we demonstrate the first time ML-based MAPF approaches have scaled to high congestion scenarios (e.g. 20% agent density).

Related papers

• RAILGUN: A Unified Convolutional Policy for Multi-Agent Path Finding Across Different Environments and Tasks [17.17370365888357]
  Multi-Agent Path Finding (MAPF) is crucial for applications ranging from aerial swarms to warehouse automation. We have developed the first centralized learning-based policy for MAPF problem called RAILGUN. By leveraging a CNN-based architecture, RAILGUN can generalize across different maps and handle any number of agents.
  arXiv  Detail & Related papers  (2025-03-04T20:35:20Z)
• Ensembling Prioritized Hybrid Policies for Multi-agent Pathfinding [18.06081009550052]
  Multi-Agent Reinforcement Learning (MARL) based Multi-Agent Path Finding (MAPF) has recently gained attention due to its efficiency and scalability. Several MARL-MAPF methods choose to use communication to enrich the information one agent can perceive. We propose a new method, Ensembling Prioritized Hybrid Policies (EPH)
  arXiv  Detail & Related papers  (2024-03-12T11:47:12Z)
• 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)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  Multi-Agent Pathfinding problem involves finding a set of conflict-free paths for a group of agents confined to a graph. In this study, we focus on the decentralized MAPF setting, where the agents may observe the other agents only locally. We propose a decentralized multi-agent Monte Carlo Tree Search (MCTS) method for MAPF tasks.
  arXiv  Detail & Related papers  (2023-12-26T06:57:22Z)
• 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)
• Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
  Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents. We propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations.
  arXiv  Detail & Related papers  (2023-08-22T07:17:39Z)
• Provably Learning Nash Policies in Constrained Markov Potential Games [90.87573337770293]
  Multi-agent reinforcement learning (MARL) addresses sequential decision-making problems with multiple agents. Constrained Markov Games (CMGs) are a natural formalism for safe MARL problems, though generally intractable.
  arXiv  Detail & Related papers  (2023-06-13T13:08:31Z)
• Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning [139.53668999720605]
  We present a multi-agent PPO algorithm in which the local policy of each agent is updated similarly to vanilla PPO. We prove that with standard regularity conditions on the Markov game and problem-dependent quantities, our algorithm converges to the globally optimal policy at a sublinear rate.
  arXiv  Detail & Related papers  (2023-05-08T16:20:03Z)
• Distributed Heuristic Multi-Agent Path Finding with Communication [7.854890646114447]
  Multi-Agent Path Finding (MAPF) is essential to large-scale robotic systems. Recent methods have applied reinforcement learning (RL) to learn decentralized polices in partially observable environments. This paper combines communication with deep Q-learning to provide a novel learning based method for MAPF.
  arXiv  Detail & Related papers  (2021-06-21T18:50:58Z)
• POMP: Pomcp-based Online Motion Planning for active visual search in indoor environments [89.43830036483901]
  We focus on the problem of learning an optimal policy for Active Visual Search (AVS) of objects in known indoor environments with an online setup. Our POMP method uses as input the current pose of an agent and a RGB-D frame. We validate our method on the publicly available AVD benchmark, achieving an average success rate of 0.76 with an average path length of 17.1.
  arXiv  Detail & Related papers  (2020-09-17T08:23:50Z)

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.