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

2022/11/24 by Keisuke Okumura, Okumura, Keisuke · 19 citations
Computer Science · #Robotic Path Planning Algorithms #Data Management and Algorithms #Software Testing and Debugging Techniques

paper · pdf · doi:10.48550/arxiv.2211.13432

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.

Cited by

• CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs
• db-LaCAM: Fast and Scalable Multi-Robot Kinodynamic Motion Planning with Discontinuity-Bounded Search and Lightweight MAPF
• An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms
• FICO: Finite-Horizon Closed-Loop Factorization for Unified Multi-Agent Path Finding
• Local Guidance for Configuration-Based Multi-Agent Pathfinding
• Graph Attention-Guided Search for Dense Multi-Agent Pathfinding
• Towards Information-Optimized Multi-Agent Path Finding: A Hybrid Framework with Reduced Inter-Agent Information Sharing
• Destination-to-Chutes Task Mapping Optimization for Multi-Robot Coordination in Robotic Sorting Systems
• Sequence Pathfinder for Multi-Agent Pickup and Delivery in the Warehouse
• Multi-Agent Path Finding via Offline RL and LLM Collaboration
• Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Unassigned Agents
• ESCoT: An Enhanced Step-based Coordinate Trajectory Planning Method for Multiple Car-like Robots
• PANAMA: A Network-Aware MARL Framework for Multi-Agent Path Finding in Digital Twin Ecosystems
• Congestion Mitigation Path Planning for Large-Scale Multi-Agent Navigation in Dense Environments
• Budget Allocation Policies for Real-Time Multi-Agent Path Finding
• LF: Online Multi-Robot Path Planning Meets Optimal Trajectory Control
• Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning
• A Scalable Post-Processing Pipeline for Large-Scale Free-Space Multi-Agent Path Planning with PiBT
• Enhancing Lifelong Multi-Agent Path-finding by Using Artificial Potential Fields

Related

• Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding
• Engineering LaCAM^∗: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding
• Graph Attention-Guided Search for Dense Multi-Agent Pathfinding
• An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms
• LNS2+RL: Combining Multi-Agent Reinforcement Learning with Large Neighborhood Search in Multi-Agent Path Finding