Abstract
Conflict-Based Search (CBS) is a widely used algorithm for solving multi-agent pathfinding (MAPF) problems optimally. The core idea of CBS is to run hierarchical search, when, on the high level the tree of solutions candidates is explored, and on the low-level an individual planning for a specific agent (subject to certain constraints) is carried out. To trade-off optimality for running time different variants of bounded sub-optimal CBS were designed, which alter both high- and low-level search routines of CBS. Moreover, anytime variant of CBS does exist that applies Focal Search (FS) to the high-level of CBS – Anytime BCBS. However, no comprehensive analysis of how well this algorithm performs compared to the naive one, when we simply re-invoke CBS with the decreased sub-optimality bound, was present. This work aims at filling this gap. Moreover, we present and evaluate another anytime version of CBS that uses FS on both levels of CBS. Empirically, we show that its behavior is principally different from the one demonstrated by Anytime BCBS. Finally, we compare both algorithms head-to-head and show that using Focal Search on both levels of CBS can be beneficial in a wide range of setups.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Andreychuk, A., Yakovlev, K., Atzmon, D., Stern, R.: Multi-agent pathfinding with continuous time. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), pp. 39–45 (2019)
Barer, M., Sharon, G., Stern, R., Felner, A.: Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In: Seventh Annual Symposium on Combinatorial Search (2014)
Boyrasky, E., Felner, A., Sharon, G., Stern, R.: Don’t split, try to work it out: bypassing conflicts in multi-agent pathfinding. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 25, pp. 47–51 (2015)
Chan, S.H., Li, J., Gange, G., Harabor, D., Stuckey, P.J., Koenig, S.: ECBS with flex distribution for bounded-suboptimal multi-agent path finding. In: Proceedings of the International Symposium on Combinatorial Search, vol. 12, pp. 159–161 (2021)
Cohen, L., et al.: Anytime focal search with applications. In: IJCAI, pp. 1434–1441 (2018)
Felner, A., et al.: Adding heuristics to conflict-based search for multi-agent path finding. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 28, pp. 83–87 (2018)
Gange, G., Harabor, D., Stuckey, P.J.: Lazy CBS: implicit conflict-based search using lazy clause generation. In: The International Conference on Automated Planning and Scheduling (ICAPS), pp. 155–162 (2019)
Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Hu, S., Harabor, D.D., Gange, G., Stuckey, P.J., Sturtevant, N.R.: Multi-agent path finding with temporal jump point search. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 32, pp. 169–173 (2022)
Li, J., Chen, Z., Harabor, D., Stuckey, P., Koenig, S.: Anytime multi-agent path finding via large neighborhood search. In: International Joint Conference on Artificial Intelligence (IJCAI) (2021)
Li, J., Chen, Z., Harabor, D., Stuckey, P.J., Koenig, S.: MAPF-LNS2: fast repairing for multi-agent path finding via large neighborhood search. In: Proceedings of the AAAI Conference on Artificial Intelligence (2022)
Li, J., Felner, A., Boyarski, E., Ma, H., Koenig, S.: Improved heuristics for multi-agent path finding with conflict-based search. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-2019), pp. 442–449 (2019). https://doi.org/10.24963/ijcai.2019/63
Li, J., Gange, G., Harabor, D., Stuckey, P.J., Ma, H., Koenig, S.: New techniques for pairwise symmetry breaking in multi-agent path finding. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 30, pp. 193–201 (2020)
Li, J., Harabor, D., Stuckey, P.J., Felner, A., Ma, H., Koenig, S.: Disjoint splitting for multi-agent path finding with conflict-based search. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 29, pp. 279–283 (2019)
Li, J., Ruml, W., Koenig, S.: EECBS: a bounded-suboptimal search for multi-agent path finding. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) (2021)
Morris, R., et al.: Planning, scheduling and monitoring for airport surface operations. In: Planning for Hybrid Systems, Papers from the 2016 AAAI Workshop (2016)
Pearl, J., Kim, J.H.: Studies in semi-admissible heuristics. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-4(4), 392–399 (1982)
Phillips, M., Likhachev, M.: Sipp: safe interval path planning for dynamic environments. In: 2011 IEEE International Conference on Robotics and Automation, pp. 5628–5635. IEEE (2011)
Sharon, G., Stern, R., Felner, A., Sturtevant, N.R.: Conflict-based search for optimal multi-agent pathfinding. Artif. Intell. 219, 40–66 (2015)
Silver, D.: Cooperative pathfinding. In: The First Artificial Intelligence and Interactive Digital Entertainment Conference, pp. 117–122 (2005)
Stern, R., et al.: Multi-agent pathfinding: definitions, variants, and benchmarks. In: Twelfth Annual Symposium on Combinatorial Search (2019)
Veloso, M.M., Biswas, J., Coltin, B., Rosenthal, S.: CoBots: robust symbiotic autonomous mobile service robots. In: the International Joint Conference on Artificial Intelligence (IJCAI), pp. 4423–4429 (2015)
Wurman, P.R., D’Andrea, R., Mountz, M.: Coordinating hundreds of cooperative, autonomous vehicles in warehouses. In: the AAAI Conference on Artificial Intelligence (AAAI), pp. 1752–1760 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Ivanashev, I., Andreychuk, A., Yakovlev, K. (2022). Analysis of the Anytime MAPF Solvers Based on the Combination of Conflict-Based Search (CBS) and Focal Search (FS). In: Pichardo Lagunas, O., Martínez-Miranda, J., Martínez Seis, B. (eds) Advances in Computational Intelligence. MICAI 2022. Lecture Notes in Computer Science(), vol 13612. Springer, Cham. https://doi.org/10.1007/978-3-031-19493-1_29
Download citation
DOI: https://doi.org/10.1007/978-3-031-19493-1_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-19492-4
Online ISBN: 978-3-031-19493-1
eBook Packages: Computer ScienceComputer Science (R0)