Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding
- URL: http://arxiv.org/abs/2305.03632v1
- Date: Fri, 5 May 2023 15:43:20 GMT
- Title: Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding
- Authors: Keisuke Okumura
- Abstract summary: We extend the recently-developed LaCAM algorithm for multi-agent pathfinding (MAPF)
LaCAM is a sub-optimal search-based algorithm that uses lazy successor generation to dramatically reduce the planning effort.
We propose its anytime version, called LaCAM*, which eventually converges to optima.
- Score: 5.025654873456756
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This study extends the recently-developed LaCAM algorithm for multi-agent
pathfinding (MAPF). LaCAM is a sub-optimal search-based algorithm that uses
lazy successor generation to dramatically reduce the planning effort. We
present two enhancements. First, we propose its anytime version, called LaCAM*,
which eventually converges to optima, provided that solution costs are
accumulated transition costs. Second, we improve the successor generation to
quickly obtain initial solutions. Exhaustive experiments demonstrate their
utility. For instance, LaCAM* sub-optimally solved 99% of the instances
retrieved from the MAPF benchmark, where the number of agents varied up to a
thousand, within ten seconds on a standard desktop PC, while ensuring eventual
convergence to optima; developing a new horizon of MAPF algorithms.
Related papers
- Decoding-Time Language Model Alignment with Multiple Objectives [88.64776769490732]
Existing methods primarily focus on optimizing LMs for a single reward function, limiting their adaptability to varied objectives.
Here, we propose $textbfmulti-objective decoding (MOD)$, a decoding-time algorithm that outputs the next token from a linear combination of predictions.
We show why existing approaches can be sub-optimal even in natural settings and obtain optimality guarantees for our method.
arXiv Detail & Related papers (2024-06-27T02:46:30Z) - 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) - Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large
Neighborhood Search [30.364955687049292]
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.
arXiv Detail & Related papers (2023-12-28T01:24:42Z) - 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) - Engineering LaCAM$^\ast$: Towards Real-Time, Large-Scale, and
Near-Optimal Multi-Agent Pathfinding [12.02023514105999]
This paper addresses the challenges of real-time, large-scale, and near-optimal multi-agent pathfinding (MAPF) through enhancements to the recently proposed LaCAM* algorithm.
LaCAM* is a scalable search-based algorithm that guarantees the eventual finding of optimal solutions for cumulative transition costs.
arXiv Detail & Related papers (2023-08-08T14:36:58Z) - 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) - Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
We present the first efficient scalable and general framework that can directly search on the tasks of interest.
Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree.
We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
arXiv Detail & Related papers (2022-09-27T17:51:31Z) - Collaborative Intelligent Reflecting Surface Networks with Multi-Agent
Reinforcement Learning [63.83425382922157]
Intelligent reflecting surface (IRS) is envisioned to be widely applied in future wireless networks.
In this paper, we investigate a multi-user communication system assisted by cooperative IRS devices with the capability of energy harvesting.
arXiv Detail & Related papers (2022-03-26T20:37:14Z) - Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and
Personalized Federated Learning [56.17603785248675]
Model-agnostic meta-learning (MAML) has become a popular research area.
Existing MAML algorithms rely on the episode' idea by sampling a few tasks and data points to update the meta-model at each iteration.
This paper proposes memory-based algorithms for MAML that converge with vanishing error.
arXiv Detail & Related papers (2021-06-09T08:47:58Z) - Pushing the Envelope: From Discrete to Continuous Movements in
Multi-Agent Path Finding via Lazy Encodings [15.99072005190786]
We introduce a novel solving approach for obtaining makespan optimal solutions called SMT-CBS$mathcalR$ based on em satisfiability modulo theories (SMT)
The new algorithm combines collision resolution known from conflict-based search (CBS) with previous generation of incomplete SAT encodings on top of a novel scheme for selecting decision variables in a potentially uncountable search space.
arXiv Detail & Related papers (2020-04-25T13:21:32Z)
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.