The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
Conflict-based search for optimal multi-agent pathfinding
Open accessAbstract
In the multi agent path finding problem (MAPF) paths should be found for several agents, each with a different start and goal position such that agents do not collide. Previous optimal solvers applied global A*-based searches. We present a new search algorithm called Conflict Based Search (CBS). CBS is a two-level algorithm. At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. In many cases this reformulation enables CBS to examine fewer states than A* while still maintaining optimality. We analyze CBS and show its benefits and drawbacks. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
A performance comparison of multi-hop wireless ad hoc network routing protocols
Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y.-C., & Jetcheva, J. (1998) · Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking · doi:10.1145/288235.288256 · Cited by 4,673
Depth-first iterative-deepening
Korf, R. E. (1985) · Artificial Intelligence · doi:10.1016/0004-3702(85)90084-0 · Cited by 1,562
A Multiagent Approach to Autonomous Intersection Management
Dresner, K., & Stone, P. (2008) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2502 · Cited by 1,304
Robotics: Science and Systems (RSS)
Trinkle, J., & Matsuoka, Y. (2010) · AI Magazine · doi:10.1609/aimag.v31i1.2237 · Cited by 1,081
Generalized best-first search strategies and the optimality of A*
Dechter, R., & Pearl, J. (1985) · Journal of the ACM · doi:10.1145/3828.3830 · Cited by 1,071
Bonet, B., & Geffner, H. (2001) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00108-4 · Cited by 959
Erdmann, M., & Lozano-Pérez, T. (1987) · Algorithmica · doi:10.1007/bf01840371 · Cited by 736
Silver, D. (2005) · Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · doi:10.1609/aiide.v1i1.18726 · Cited by 688
Benchmarks for Grid-Based Pathfinding
Sturtevant, N. R. (2012) · IEEE Transactions on Computational Intelligence and AI in Games · doi:10.1109/tciaig.2012.2197681 · Cited by 549
Self-citation2022 International Conference on Robotics and Automation (ICRA)
(2022) · doi:10.1109/icra46639.2022 · Cited by 463
Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs
Yu, J., & LaValle, S. (2013) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v27i1.8541 · Cited by 413
Optimal motion planning for multiple robots having independent goals
LaValle, S. M., & Hutchinson, S. A. (1998) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.736775 · Cited by 411
Finding Optimal Solutions to Cooperative Pathfinding Problems
Standley, T. (2010) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v24i1.7564 · Cited by 358
The increasing cost tree search for optimal multi-agent pathfinding
Sharon, G., Stern, R., Goldenberg, M., & Felner, A. (2013) · Artificial Intelligence · doi:10.1016/j.artint.2012.11.006 · Cited by 323
Self-citationBennewitz, M., Burgard, W., & Thrun, S. (2002) · Robotics and Autonomous Systems · doi:10.1016/s0921-8890(02)00256-7 · Cited by 251
Finding Optimal Solutions to Rubik's Cube Using Pattern Databases
Korf, R. E. (1997) · Cited by 245
Decentralized Cooperative Policy for Conflict Resolution in Multivehicle Systems
Pallottino, L., Scordio, V. G., Bicchi, A., & Frazzoli, E. (2007) · IEEE Transactions on Robotics · doi:10.1109/tro.2007.909810 · Cited by 234
M*: A complete multirobot path planning algorithm with performance bounds
Wagner, G., & Choset, H. (2011) · 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems · doi:10.1109/iros.2011.6095022 · Cited by 228
Additive Pattern Database Heuristics
Felner, A., Korf, R. E., & Hanan, S. (2004) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1480 · Cited by 206
Self-citationA General Formal Framework for Pathfinding Problems with Multiple Agents
Erdem, E., Kisa, D., Öztok, U., & Schüller, P. (2013) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v27i1.8592 · Cited by 202
Complete Algorithms for Cooperative Pathfinding Problems
Standley, T., & Korf, R. E. (2012) · Cited by 197
Planning optimal paths for multiple robots on graphs
Yu, J., & LaValle, S. M. (2013) · 2013 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2013.6631084 · Cited by 197
Push and swap: fast cooperative path-finding with completeness guarantees
Luna, R., & Bekris, K. E. (2011) · International Joint Conference on Artificial Intelligence · doi:10.5591/978-1-57735-516-8/ijcai11-059 · Cited by 192
Finding a shortest solution for the N x N extension of the 15- Puzzle is intractable
Ratner, D., & Warmuth, M. K. (1986) · National Conference on Artificial Intelligence · Cited by 181
Topological constraints in search-based robot path planning
Bhattacharya, S., Likhachev, M., & Kumar, V. (2012) · Autonomous Robots · doi:10.1007/s10514-012-9304-1 · Cited by 172
Multi-agent Path Planning and Network Flow
Yu, J., & LaValle, S. M. (2013) · Springer Tracts in Advanced Robotics · doi:10.1007/978-3-642-36279-8_10 · Cited by 164
MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees
Wang, K.-H. C., & Botea, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1401.3905 · Cited by 162
Time complexity of iterative-deepening-A∗
Korf, R. E., Reid, M., & Edelkamp, S. (2001) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00094-7 · Cited by 156
Goldenberg, M., Felner, A., Stern, R., Sharon, G., Sturtevant, N., Holte, R. C., & Schaeffer, J. (2014) · Journal of Artificial Intelligence Research · doi:10.1613/jair.4171 · Cited by 149
Self-citationThe 2022 International Conference on Computer-Aided Design (ICCAD)
Mitra, T. (2023) · IEEE Design and Test · doi:10.1109/mdat.2023.3238340 · Cited by 129
Single- and dual-arm motion planning with heuristic search
Cohen, B. J., Chitta, S., & Likhachev, M. A. (2013) · The International Journal of Robotics Research · doi:10.1177/0278364913507983 · Cited by 115
Towards Optimal Cooperative Path Planning in Hard Setups through Satisfiability Solving
Surynek, P. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32695-0_50 · Cited by 110
Finding Optimal Solutions to the Twenty-Four Puzzle
Korf, R. E., & Taylor, L. A. (1996) · Cited by 106
Conflict-Based Search For Optimal Multi-Agent Path Finding
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v26i1.8140 · Cited by 93
Self-citationODrM* optimal multirobot path planning in low dimensional search spaces
Ferner, C., Wagner, G., & Choset, H. (2013) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2013.6631119 · Cited by 93
Efficient and complete centralized multi-robot path planning
Luna, R., & Bekris, K. E. (2011) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2011.6048846 · Cited by 85
Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives
Sajid, Q., Luna, R., & Bekris, K. E. (2021) · Proceedings of the International Symposium on Combinatorial Search · doi:10.1609/socs.v3i1.18243 · Cited by 75
Improving Collaborative Pathfinding Using Map Abstraction
Sturtevant, N., & Buro, M. (2006) · Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · doi:10.1609/aiide.v2i1.18750 · Cited by 74
Self-citationInternational Conference on Robotics and Automation (ICRA)
Martínez-Carranza, J., & Calway, A. D. (2012) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · Cited by 73
Conflict-Oriented Windowed Hierarchical Cooperative A*
Bnaya, Z., & Felner, A. (2014) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2014.6907401 · Cited by 37
Self-citationDistributed Optimization with Pairwise Constraints and its Application to Multi-robot Path Planning
Bhattacharya, S., Kumar, V., & Likachev, M. (2010) · doi:10.15607/rss.2010.vi.023 · Cited by 19
Distributed navigation in an unknown physical environment
Gilboa, A., Meisels, A., & Felner, A. (2006) · Adaptive Agents and Multi-Agents Systems · doi:10.1145/1160633.1160735 · Cited by 16
Self-citation
Cited by
A review of cooperative multi-agent deep reinforcement learning
Oroojlooy, A., & Hajinezhad, D. (2023) · Applied Intelligence · doi:10.1007/s10489-022-04105-y · Cited by 482
PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning
Sartoretti, G., Kerr, J., Shi, Y., Wagner, G., Kumar, T. K. S., Koenig, S., & Choset, H. (2019) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2019.2903261 · Cited by 417
Fan, T., Long, P., Liu, W., & Pan, J. (2020) · The International Journal of Robotics Research · doi:10.1177/0278364920916531 · Cited by 332
Trajectory Planning for Quadrotor Swarms
Honig, W., Preiss, J. A., Kumar, T. K. S., Sukhatme, G. S., & Ayanian, N. (2018) · IEEE Transactions on Robotics · doi:10.1109/tro.2018.2853613 · Cited by 315
Graph Neural Networks for Decentralized Multi-Robot Path Planning
Li, Q., Gama, F., Ribeiro, A., & Prorok, A. (2020) · 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros45743.2020.9341668 · Cited by 271
Metadata
- Authors
- Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R.
- Venue
- Artificial Intelligence
- Publisher
- Elsevier BV
- Published
- 2015-02
- Volume
- 219
- Pages
- 40-66
- ISSN
- 0004-3702 (ISSN-L)
- OpenAlex
- W1989407213
- Cited by
- 1,242
- References
- 43
- FWCI
- 14.84
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.