The paper introduces Conflict Based Search (CBS), a novel algorithm for solving the multi-agent pathfinding (MAPF) problem optimally. Unlike previous approaches that treat each agent as a single 'joint agent' and apply single-agent search variants of the A* algorithm, CBS is a two-level algorithm that does not convert the problem into a single 'joint agent' model. At the high level, a search is performed on a Conflict Tree (CT), which represents conflicts between individual agents. Each node in the CT represents constraints on the motion of the agents. At the low level, fast single-agent searches are performed to satisfy these constraints. This two-level formulation allows CBS to examine fewer states than A* while maintaining optimality. The paper also presents Meta-Agent CBS (MA-CBS), a generalization of CBS that allows agents to be merged into small groups of joint agents. This mitigates some of the drawbacks of basic CBS and further improves performance. MA-CBS can be built on top of any optimal and complete MAPF solver to enhance its performance. Experimental results show that CBS and MA-CBS outperform previous approaches, achieving up to an order of magnitude speedup in various problems. The introduction provides a background on single-agent and multi-agent pathfinding, highlighting the NP-hard nature of the MAPF problem and the limitations of A*-based approaches. The paper then surveys existing MAPF research, classifying it into optimal and sub-optimal solvers, and introduces the conflict-based formalization and CBS algorithm. The authors discuss the advantages and drawbacks of CBS compared to A*-based approaches and present experimental results supporting their findings. Finally, the paper introduces MA-CBS and its variants, demonstrating its superior performance on various domains.The paper introduces Conflict Based Search (CBS), a novel algorithm for solving the multi-agent pathfinding (MAPF) problem optimally. Unlike previous approaches that treat each agent as a single 'joint agent' and apply single-agent search variants of the A* algorithm, CBS is a two-level algorithm that does not convert the problem into a single 'joint agent' model. At the high level, a search is performed on a Conflict Tree (CT), which represents conflicts between individual agents. Each node in the CT represents constraints on the motion of the agents. At the low level, fast single-agent searches are performed to satisfy these constraints. This two-level formulation allows CBS to examine fewer states than A* while maintaining optimality. The paper also presents Meta-Agent CBS (MA-CBS), a generalization of CBS that allows agents to be merged into small groups of joint agents. This mitigates some of the drawbacks of basic CBS and further improves performance. MA-CBS can be built on top of any optimal and complete MAPF solver to enhance its performance. Experimental results show that CBS and MA-CBS outperform previous approaches, achieving up to an order of magnitude speedup in various problems. The introduction provides a background on single-agent and multi-agent pathfinding, highlighting the NP-hard nature of the MAPF problem and the limitations of A*-based approaches. The paper then surveys existing MAPF research, classifying it into optimal and sub-optimal solvers, and introduces the conflict-based formalization and CBS algorithm. The authors discuss the advantages and drawbacks of CBS compared to A*-based approaches and present experimental results supporting their findings. Finally, the paper introduces MA-CBS and its variants, demonstrating its superior performance on various domains.