Conflict-based search for optimal multi-agent pathfinding

2014/12/01 by Guni Sharon, Roni Stern, Ariel Felner +2 · 1,192 citations
Computer Science · Mathematics · #AI-based Problem Solving and Planning #Algorithm #Artificial intelligence #Combinatorics #Computer science #Generalization #Graph #Mathematical optimization #Mathematics #Multi-Agent Systems and Negotiation #Node (physics) #Pathfinding #Robotic Path Planning Algorithms #Search algorithm #Search tree #Set (abstract data type) #Shortest path problem #Task (project management) #Theoretical computer science #Tree (set theory)

paper · doi:10.1016/j.artint.2014.11.006

published in Artificial Intelligence 219, 40-66 (Elsevier BV)

openalex publication_date 2014/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Citations

• The increasing cost tree search for optimal multi-agent pathfinding

Cited by

• Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding
• CBS-Budget (CBSB): A complete and bounded suboptimal search for multi-agent path finding
• Embodying Multi-Hand Manipulation Policies by Searching the Assignment and Null Spaces
• Remote ID Spoofing-Aware Trajectory Planning for Small Unmanned Aerial Systems
• Socially Consistent Multi-Robot Navigation Using Decoupled Planning and Trajectory Coordination
• Stigmergic Graph Memory: An Environment-Aware Approach for Many-to-Many Multi-Agent Pickup and Delivery
• Efficient Compilation for Shuttling Trapped-Ion Machines via the Position Graph Architectural Abstraction
• Conflict-Based Search for Connected Multi-Agent Path Finding
• Formation Control with Lane Preference for Connected and Automated Vehicles in Multi-lane Scenarios
• CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs
• Multi-Robot Motion Planning from Vision and Language using Heat-Inspired Diffusion
• CAHC:A General Conflict-Aware Heuristic Caching Framework for Multi-Agent Path Finding
• db-LaCAM: Fast and Scalable Multi-Robot Kinodynamic Motion Planning with Discontinuity-Bounded Search and Lightweight MAPF
• From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding
• Deadlock-Free Hybrid RL-MAPF Framework for Zero-Shot Multi-Robot Navigation
• Subdimensional Expansion Using Attention-Based Learning For Multi-Agent Path Finding
• Asynchronous Distributed Multi-Robot Motion Planning Under Imperfect Communication
• An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms
• PushingBots: Collaborative Pushing via Neural Accelerated Combinatorial Hybrid Optimization
• FICO: Finite-Horizon Closed-Loop Factorization for Unified Multi-Agent Path Finding
• Collaborative Multi-Robot Non-Prehensile Manipulation via Flow-Matching Co-Generation
• Multi-objective Conflict-based Search Using Safe-interval Path Planning
• Design for One, Deploy for Many: Navigating Tree Mazes with Multiple Agents
• A Multi-Robot Path Planning Method Based on Multi-Scale Perception and Experience Enhancement
• Automatic Algorithm Selection In Multi-agent Pathfinding
• Integer-Programming-Based Narrow-Passage Multi-Robot Path Planning with Effective Heuristics
• EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
• Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search
• Two algorithms for the package-exchange robot-routing problem
• Polynomial-time Configuration Generator for Connected Unlabeled Multi-Agent Pathfinding
• MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments
• DiRAC - Distributed Robot Awareness and Consensus
• DeepMNavigate: Deep Reinforced Multi-Robot Navigation Unifying Local & Global Collision Avoidance
• Near-Optimal Multi-Robot Motion Planning with Finite Sampling
• Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
• Decentralized Multi-Robot Relative Navigation in Unknown, Structurally Constrained Environments under Limited Communication
• R3R: Decentralized Multi-Agent Collision Avoidance with Infinite-Horizon Safety
• Collaborative Task Assignment, Sequencing and Multi-agent Path-finding
• Conflict-Based Search as a Protocol: A Multi-Agent Motion Planning Protocol for Heterogeneous Agents, Solvers, and Independent Tasks
• Conflict-Based Search and Prioritized Planning for Multi-Agent Path Finding Among Movable Obstacles
• Multi-Agent Path Finding via Offline RL and LLM Collaboration
• Neural Algorithmic Reasoners informed Large Language Model for Multi-Agent Path Finding
• Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search
• Recent Advancements in Microscopy Image Enhancement using Deep Learning: A Survey
• Multi-Robot Path Planning in Complex Environments via Graph Embedding
• Repulsive Trajectory Modification and Conflict Resolution for Efficient Multi-Manipulator Motion Planning
• Relay-Based Coordination for Energy-Efficient Multi-Robot Pickup and Delivery
• A Holistic Architecture for Monitoring and Optimization of Robust Multi-Agent Path Finding Plan Execution
• Diffusion-Guided Multi-Arm Motion Planning
• Risk-Bounded Multi-Agent Visual Navigation via Iterative Risk Allocation
• MAPF-HD: Multi-Agent Path Finding in High-Density Environments
• Efficient Multi-Agent Coordination via Dynamic Joint-State Graph Construction
• SAFE--MA--RRT: Multi-Agent Motion Planning with Data-Driven Safety Certificates
• Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Unassigned Agents
• Optimal Multi-agent Path Finding in Continuous Time
• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning
• Robust Trajectory Planning for Spatial-Temporal Multi-Drone Coordination in Large Scenes
• Multi-Robot Navigation in Social Mini-Games: Definitions, Taxonomy, and Algorithms
• Coordinated Complexity-Aware 4D Trajectory Planning
• MAPF-World: Action World Model for Multi-Agent Path Finding
• Flow-Based Task Assignment for Large-Scale Online Multi-Agent Pickup and Delivery
• Benchmarking Shortcutting Techniques for Multi-Robot-Arm Motion Planning
• Optimal Planning for Multi-Robot Simultaneous Area and Line Coverage Using Hierarchical Cyclic Merging Regulation
• When Agents Break Down in Multiagent Path Finding
• A Group Consensus-Driven Auction Algorithm for Cooperative Task Allocation Among Heterogeneous Multi-Agents
• Multi-Agent Path Finding Among Dynamic Uncontrollable Agents with Statistical Safety Guarantees
• Homotopy-aware Multi-agent Navigation via Distributed Model Predictive Control
• Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search
• Cooperative Pathfinding based on memory-efficient Multi-agent RRT*
• Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution
• Spatial and Temporal Splitting Heuristics for Multi-Robot Motion Planning
• Average Case Constant Factor Time and Distance Optimal Multi-Robot Path Planning in Well-Connected Environments
• Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics
• Path Finding for the Coalition of Co-operative Agents Acting in the Environment with Destructible Obstacles
• Solution Space Path Planning: A Real-Time Human-Centered Path Planning Algorithm for En-Route Air Traffic Control
• Ella: Embodied Social Agents with Lifelong Memory
• Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning
• A MILP-Based Solution to Multi-Agent Motion Planning and Collision Avoidance in Constrained Environments
• A Scalable Post-Processing Pipeline for Large-Scale Free-Space Multi-Agent Path Planning with PiBT
• Structural Integrality in Task Assignment and Path Finding via Total Unimodularity of Petri Net Models
• Distributed multi-robot collision avoidance via deep reinforcement learning for navigation in complex scenarios
• Multi Agent Path Finding with Awareness for Spatially Extended Agents
• Enhancing Lifelong Multi-Agent Path-finding by Using Artificial Potential Fields
• Optimizing Cooperative path-finding: A Scalable Multi-Agent RRT* with Dynamic Potential Fields
• Multi-agent navigation based on deep reinforcement learning and traditional pathfinding algorithm
• Multi-Agent Path Finding For Large Agents Is Intractable
• Internal State Estimation in Groups via Active Information Gathering
• Streaming Multi-agent Pathfinding
• PRISM: Complete Online Decentralized Multi-Agent Pathfinding with Rapid Information Sharing using Motion Constraints
• Multi-Agent Path Finding via Finite-Horizon Hierarchical Factorization
• Constant-Memory Strategies in Stochastic Games: Best Responses and Equilibria
• JaxRobotarium: Training and Deploying Multi-Robot Policies in 10 Minutes
• High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods
• Coordinating Large-Scale Robot Networks with Motion and Communication Uncertainties for Logistics Applications
• Experimental Validation of Multi-lane Formation Control for Connected and Automated Vehicles in Multiple Scenarios
• Decentralised Approach for Multi Agent Path Finding
• A Job-Assignment Heuristic for Lifelong Multi-Agent Path Finding Problem with Multiple Delivery Locations
• On dynamic multi-agent pathfinding methods: review, simulations and modifications
• A Time-dependent Risk-aware distributed Multi-Agent Path Finder based on A*
• Position Paper: From Multi-Agent Pathfinding to Pipe Routing
• PRIMAL3: Pathfinding via Reinforcement and Imitation Multi-Agent Learning - Leveraging LaCAM3
• Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions
• Neural ATTF: A Scalable Solution to Lifelong Multi-Agent Path Planning
• Coordinated Multi-Robot Disassembly for Makespan Optimization of Large-Scale Assemblies
• P-ARC: Exploiting Subproblem Independence for Parallel Multi-Robot Motion Planning
• Multi-Robot Motions in Milliseconds: Vector-Accelerated Primitives for Sampling-Based Planning
• Real-Time LaCAM for Real-Time MAPF
• Congestion-aware Evacuation Routing using Augmented Reality Devices
• Algorithms for Smooth, Safe and Quick Routing on Sensor-Equipped Grid Networks. [europepmc]
• Coordinated Multi-Robotic Vehicles Navigation and Control in Shop Floor Automation. [europepmc]
• Agree to Disagree: Subjective Fairness in Privacy-Restricted Decentralised Conflict Resolution. [europepmc]
• Model predictive path integral for decentralized multi-agent collision avoidance. [europepmc]
• Heterogeneous foraging swarms can be better. [europepmc]
• Conflict-based strategy combined integrated optimal conflict avoidance algorithm. [europepmc]
• Real time task planning for order picking in intelligent logistics warehousing. [europepmc]
• Automated and collision-free navigation of multiple micro-objects in obstacle-dense microenvironments using optoelectronic tweezers. [europepmc]
• Dynamic Path Planning for Unmanned Autonomous Vehicles Based on CAS-UNet and Graph Neural Networks. [europepmc]
• Multi-Robot Path Planning for High-Density Parking Environments Considering Efficiency and Fairness. [europepmc]
• A Multi-Policy Rapidly-Exploring Random Tree Based Mobile Robot Controller for Safe Path Planning in Human-Shared Environments. [europepmc]
• Multi-AGV path planning method for the textile industry based on improved ant colony optimization algorithm and R-tree line-segment bilayer conflict detection. [europepmc]
• MURM-A*: An Improved A* Within Comprehensive Path-Planning Scheme for Cellular-Connected Multi-UAVs Based on Radio Map and Complex Network. [europepmc]