LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding

• URL: http://arxiv.org/abs/2211.13432v1
• Date: Thu, 24 Nov 2022 06:27:18 GMT
• Title: LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding
• Authors: Keisuke Okumura
• Abstract summary: 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.
• Score: 5.025654873456756
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a novel complete algorithm for multi-agent pathfinding (MAPF) called lazy constraints addition search for MAPF (LaCAM). MAPF is a problem of finding collision-free paths for multiple agents on graphs and is the foundation of multi-robot coordination. LaCAM uses a two-level search to find solutions quickly, even with hundreds of agents or more. At the low-level, it searches constraints about agents' locations. At the high-level, it searches a sequence of all agents' locations, following the constraints specified by the low-level. Our exhaustive experiments reveal that LaCAM is comparable to or outperforms state-of-the-art sub-optimal MAPF algorithms in a variety of scenarios, regarding success rate, planning time, and solution quality of sum-of-costs.

Related papers

• 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)
• 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)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding [5.025654873456756]
  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.
  arXiv  Detail & Related papers  (2023-05-05T15:43:20Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  We propose Multi-agent Deep Covering Option Discovery, which constructs the multi-agent options through minimizing the expected cover time of the multiple agents' joint state space. Also, we propose a novel framework to adopt the multi-agent options in the MARL process. We show that the proposed algorithm can effectively capture the agent interactions with the attention mechanism, successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
  arXiv  Detail & Related papers  (2022-10-07T00:40:59Z)
• Conflict-Based Search for Explainable Multi-Agent Path Finding [7.734726150561088]
  In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. MAPF problem asks for a set of non-colliding paths that admits a short-enough explanation. Traditional MAPF algorithms are not equipped to directly handle explainable-MAPF. We adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to handle explainable MAPF.
  arXiv  Detail & Related papers  (2022-02-20T23:13:14Z)
• MRDet: A Multi-Head Network for Accurate Oriented Object Detection in Aerial Images [51.227489316673484]
  We propose an arbitrary-oriented region proposal network (AO-RPN) to generate oriented proposals transformed from horizontal anchors. To obtain accurate bounding boxes, we decouple the detection task into multiple subtasks and propose a multi-head network. Each head is specially designed to learn the features optimal for the corresponding task, which allows our network to detect objects accurately.
  arXiv  Detail & Related papers  (2020-12-24T06:36:48Z)
• Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering [15.99072005190786]
  We introduce multi-goal multi agent path finding (MAPF$MG$) which generalizes the standard discrete multi-agent path finding (MAPF) problem. We suggest two novel algorithms using different paradigms to address MAPF$MG$: a search-based search algorithm called Hamiltonian-CBS (HCBS) and a compilation-based algorithm built using the SMT paradigm, called SMT-Hamiltonian-CBS (SMT-HCBS)
  arXiv  Detail & Related papers  (2020-09-10T22:27:18Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

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.