Conflict-Based Search

Ask about this topic

Overview

Conflict-Based Search (CBS) coordinates agents by detecting a collision, branching on constraints that prevent it, and replanning affected agents individually; under standard assumptions, this can find optimal paths. Variants such as continuous-time CBS, SIPP-based planners, and anytime or bounded-gap search extend the method to asynchronous actions, non-unit costs, and limited computation. CBS is used on standard multi-agent pathfinding benchmark maps and in settings such as warehouse fleets, elevators, and multi-robot manipulation, while conflict-directed reasoning also appears in verified search. A central challenge is retaining strong guarantees as richer dynamics and online disturbances increase the cost of conflict detection and replanning.

Latest papers

CardsList

17 papers1 paper in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

  1. cuArms: GPU-Accelerated Conflict-Based Planning for Multi-Arm Manipulation

    Oct 26, 2026Philip Huang, Fabio Ramos, Jiaoyang Li +2Multi-Robot Motion PlanningMulti-Task Robotic Manipulation

    NVIDIA · Carnegie Mellon · University of Sydney

  2. CORE: Conflict-Oriented Reasoning Elimination for Verifiable Language-Model Search

    Sep 30, 2026Siyu Song, Rui Xu, Jia Lin +2Efficient Language Model ReasoningLLM Reasoning

    School of Computer Science and Technology, School of Computer Science and Engineering · School of Information Science and Engineering, Sun Yat-sen University · College of Computer Science, College of Computer Science

  3. A traffic management system for large and heterogeneous vehicles in narrow industrial environments

    Sep 9, 2026Alessandro Bonetti, Silvia Proia, Simone Guidetti +1Robot NavigationRobust MAPF

    Department of Sciences and Methods for Engineering (DISMI), University of Modena and Reggio Emilia, Italy · Gruppo TecnoFerrari S.p.a. con socio unico, Italy

  4. Multi-Group Pipe Routing under Permanent Geometric Occupancy: Problem, Benchmark, and Classical Baselines

    Aug 27, 2026Deng QuanMulti-Agent Path FindingConflict-Based Search

  5. AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding

    Aug 8, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianRobust MAPFConflict-Based Search

    Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden.

  6. Embodying Multi-Hand Manipulation Policies by Searching the Assignment and Null Spaces

    Jul 24, 2026Yorai Shaoul, Jiaoyang Li, Maxim LikhachevMulti-Robot Motion PlanningConstrained Motion Planning

    The Robotics Institute, Carnegie Mellon University

  7. Model-Based Diffusion Optimal Control for Multi-Robot Motion Planning

    Jul 14, 2026Zhilin He, Yorai Shaoul, Jiaoyang LiMulti-Robot Motion PlanningConstrained Motion Planning

    Carnegie Mellon University, Pittsburgh, PA, USA

  8. Conflict-Based Lazy Search for Fast Multi-Manipulator Planning

    Jul 5, 2026Dongliang Zheng, Zhipeng Wang, Siqi Wang +4Multi-Robot Motion PlanningConflict-Based Search

    Shanghai Research Institute for Intelligent Autonomous Systems, Shanghai Institute of Intelligent Science and Technology, the State Key Laboratory of Autonomous Intelligent Unmanned Systems, and Frontiers Science Center for Intelligent Autonomous Systems of Ministry of Education, Tongji University, Shanghai 201203, China · Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China · School of Aerospace Engineering and Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA

  9. Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search

    Jun 30, 2026Willem van Osselaer, Jiarui Li, Meshal Alharbi +1Branch and BoundTree Search

    Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA, USA

  10. Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding

    May 15, 2026Ning Zhou, Nikolai W. F. Bode, Edmund R. HuntMulti-Agent System OptimizationMulti-Robot Coordination

    University of Bristol

  11. Multi-Agent Pathfinding with Non-Unit Integer Edge Costs via Enhanced Conflict-Based Search and Graph Discretization

    Apr 7, 2026Hongkai Fan, Qinjing Xie, Bo Ouyang +4Safe Interval Path PlanningMulti-Agent Path Finding

    College of Electrical and Information Engineering at Hunan University · China Mobile Group Hunan Company Limited, Changsha 410082, China

  12. Certificate-Driven Closed-Loop Multi-Agent Path Finding with Inheritable Factorization

    Apr 1, 2026Jiarui Li, Runyu Zhang, Gioele ZardiniMulti-Agent Path FindingConflict-Based Search

    The authors are with the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA, USA

  13. Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions

    Mar 19, 2026Xuemian Wu, Shizhe Zhao, Zhongqiang RenMulti-Agent Path FindingConflict-Based Search

    Shanghai Jiao Tong University, Shanghai, China

  14. Multi-Robot Coordination for Planning under Context Uncertainty

    Mar 14, 2026Pulkit Rustagi, Kyle Hollins Wray, Sandhya SaisubramanianMulti-Robot Motion PlanningMulti-Robot Coordination

    Collaborative Robotics and Intelligent Systems (CoRIS) Institute, Oregon State University, Corvallis, OR 97331, USA · Khoury College of Computer Sciences, Northeastern University, Boston, MA 02115, USA

  15. Multi-Robot Trajectory Planning via Constrained Bayesian Optimization and Local Cost Map Learning with STL-Based Conflict Resolution

    Mar 6, 2026Sourav Raxit, Abdullah Al Redwan Newaz, Jose Fuentes +3STL Motion PlanningMulti-Robot Motion Planning

    Department of Computer Science, University of New Orleans, New Orleans, LA 70148, USA · Knight Foundation School of Computing and Information Sciences, Florida International University, Miami, FL 33199, USA · Providence College, Department of Mathematics & Computer Science, Providence, RI 02918, USA

  16. Conflict-Based Search for Multi-Agent Path Finding with Elevators

    Feb 24, 2026Haitong He, Xuemian Wu, Shizhe Zhao +1Conflict-Based SearchMulti-Agent Path Finding

    Global College, Shanghai Jiao Tong University, China.

  17. Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding

    Feb 12, 2026Jiarui Li, Federico Pecora, Runyu Zhang +1Conflict-Based SearchMulti-Agent Path Finding

    Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA, USA · independent contributor