Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search

• URL: http://arxiv.org/abs/2312.16767v2
• Date: Mon, 1 Jan 2024 13:43:52 GMT
• Title: Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search
• Authors: Thomy Phan, Taoan Huang, Bistra Dilkina, Sven Koenig
• Abstract summary: State-of-the-art anytime MAPF is based on Large Neighborhood Search (LNS) We propose Bandit-based Adaptive LArge Neighborhood search Combined with Exploration (BALANCE) We empirically demonstrate cost improvements of at least 50% compared to state-of-the-art anytime MAPF in large-scale scenarios.
• Score: 30.364955687049292
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Anytime multi-agent path finding (MAPF) is a promising approach to scalable path optimization in large-scale multi-agent systems. State-of-the-art anytime MAPF is based on Large Neighborhood Search (LNS), where a fast initial solution is iteratively optimized by destroying and repairing a fixed number of parts, i.e., the neighborhood, of the solution, using randomized destroy heuristics and prioritized planning. Despite their recent success in various MAPF instances, current LNS-based approaches lack exploration and flexibility due to greedy optimization with a fixed neighborhood size which can lead to low quality solutions in general. So far, these limitations have been addressed with extensive prior effort in tuning or offline machine learning beyond actual planning. In this paper, we focus on online learning in LNS and propose Bandit-based Adaptive LArge Neighborhood search Combined with Exploration (BALANCE). BALANCE uses a bi-level multi-armed bandit scheme to adapt the selection of destroy heuristics and neighborhood sizes on the fly during search. We evaluate BALANCE on multiple maps from the MAPF benchmark set and empirically demonstrate cost improvements of at least 50% compared to state-of-the-art anytime MAPF in large-scale scenarios. We find that Thompson Sampling performs particularly well compared to alternative multi-armed bandit algorithms.

Related papers

• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  Multi-agent pathfinding is a challenging computational problem that typically requires to find collision-free paths for multiple agents in a shared environment. We have created a foundation model for the MAPF problems called MAPF-GPT. Using imitation learning, we have trained a policy on a set of sub-optimal expert trajectories that can generate actions in conditions of partial observability. We show that MAPF-GPT notably outperforms the current best-performing learnable-MAPF solvers on a diverse range of problem instances.
  arXiv  Detail & Related papers  (2024-08-29T12:55:10Z)
• Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic [16.4408116214332]
  We propose Adaptive Delay-based Destroy-and-Repair with Enhanced Success-based Self-Learning (ADDRESS) as a single-destroy-heuristic variant of MAPF-LNS. We demonstrate cost improvements by at least 50% in large-scale scenarios with up to a thousand agents, compared with the original MAPF-LNS.
  arXiv  Detail & Related papers  (2024-08-06T05:15:35Z)
• Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding [9.831879504969224]
  Multi-agent path finding (MAPF) is the problem of finding paths for multiple agents such that they do not collide. Finding optimal solutions to MAPF is NP-Hard, yet modern optimal solvers can scale to hundreds of agents and even thousands in some cases. We show how this encoding can be effectively joined with existing encodings, resulting in a novel AS method we call MAPF Algorithm selection via Graph embedding.
  arXiv  Detail & Related papers  (2024-06-16T07:41:58Z)
• Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
  We present the first optimal any-angle multi-agent pathfinding algorithm. Our planner is based on the Continuous Conflict-based Search (CCBS) algorithm and an optimal any-angle variant of the Safe Interval Path Planning (TO-AA-SIPP) We adapt two techniques from classical MAPF to the any-angle setting, namely Disjoint Splitting and Multi-Constraints.
  arXiv  Detail & Related papers  (2024-04-25T07:41:47Z)
• Multimodal Learned Sparse Retrieval with Probabilistic Expansion Control [66.78146440275093]
  Learned retrieval (LSR) is a family of neural methods that encode queries and documents into sparse lexical vectors. We explore the application of LSR to the multi-modal domain, with a focus on text-image retrieval. Current approaches like LexLIP and STAIR require complex multi-step training on massive datasets. Our proposed approach efficiently transforms dense vectors from a frozen dense model into sparse lexical vectors.
  arXiv  Detail & Related papers  (2024-02-27T14:21:56Z)
• 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)
• 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)
• LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
  We propose a novel complete algorithm for multi-agent pathfinding (MAPF) called lazy constraints addition search for MAPF (LaCAM) LaCAM uses a two-level search to find solutions quickly, even with hundreds of agents or more. Our experiments reveal that LaCAM is comparable to or outperforms state-of-the-art sub-optimal MAPF algorithms in a variety of scenarios.
  arXiv  Detail & Related papers  (2022-11-24T06:27:18Z)
• Learning Space Partitions for Path Planning [54.475949279050596]
  PlaLaM outperforms existing path planning methods in 2D navigation tasks, especially in the presence of difficult-to-escape local optima. These gains transfer to highly multimodal real-world tasks, where we outperform strong baselines in compiler phase ordering by up to 245% and in molecular design by up to 0.4 on properties on a 0-1 scale.
  arXiv  Detail & Related papers  (2021-06-19T18:06:11Z)
• The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games [67.47961797770249]
  Multi-Agent PPO (MAPPO) is a multi-agent PPO variant which adopts a centralized value function. We show that MAPPO achieves performance comparable to the state-of-the-art in three popular multi-agent testbeds.
  arXiv  Detail & Related papers  (2021-03-02T18:59:56Z)

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.