Home > CSC-OpenAccess Library > Manuscript Information
EXPLORE PUBLICATIONS BY COUNTRIES |
 |
 |
EUROPE |
|
MIDDLE EAST |
|
ASIA |
|
AFRICA |
| ............................. | |
|
United States of America |
|
United Kingdom |
|
Canada |
|
Australia |
|
Italy |
|
France |
|
Brazil |
|
Germany |
|
Malaysia |
|
Turkey |
|
China |
|
Taiwan |
|
Japan |
|
Saudi Arabia |
|
Jordan |
|
Egypt |
|
United Arab Emirates |
|
India |
|
Nigeria |
A Conceptual Agile Conflict-Based Search Framework for Scalable Multi-Agent Pathfinding in Dense Environments
Shafakhatullah Khan Mohammed, Pallavi Singhal
Pages - 1 - 8 | Revised - 15-10-2025 | Published - 31-10-2025
MORE INFORMATION
KEYWORDS
Conflict-Based Search, Heuristic Search, Multi-Agent Pathfinding, Bounded Suboptimality, Collision Avoidance.
ABSTRACT
This paper presents theoretically proved Agile CBS algorithm, an extension of the traditional
Conflict-Based Search which is customized to support bounded-suboptimal solutions for Multi-
Agent Pathfinding problems. The method uses flexible assignment of intermediate targets and
adaptive resolution of constraints, focusing to improve scalability, especially in environments with
high agent density. Unlike conventional CBS, which resolves conflicts reactively, Agile CBS
decomposes long-term objectives into incremental sub-goals, enabling progressive planning
while maintaining bounded suboptimality guarantees. The algorithm utilizes a constraint tree for
high-level search and A* for low-level path computation, thereby reducing planning overhead in
scenarios where optimal solvers encounter computational challenges. While theoretical in nature,
this framework provides a foundation for developing scalable classical AI-based MAPF solvers.
| Barer, M., Sharon, G., Stern, R. & Felner, A. (2021) 'Suboptimal variants of the Conflict-Based search algorithm for the Multi-Agent pathfinding problem', In Proceedings of the International Symposium on Combinatorial Search (SoCS), 5(1), pp. 19-27. | |
| Bing Ai, Jiuchuan Jiang, Shoushui Yu, and Yichuan Jiang. (2021) 'Multi-Agent Path Finding with heterogeneous edges and roundtrips', Knowledge-Based Systems, 234(5), 107554. | |
| Chan, S., Stern, R., Felner, A. & Koenig, S. (2023) 'Greedy Priority-Based search for suboptimal Multi-Agent path finding', In Proceedings of the International Symposium on Combinatorial Search (SoCS), 16(1), pp. 11-19. | |
| De Wilde, B., Ter Mors, A.W. & Witteveen, C. (2013) 'Push and rotate: cooperative multi-agent path planning', In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 87-94. | |
| Dechter, R. & Pearl, J. (1985) 'Generalized best-first search strategies and the optimality of A*', Journal of the ACM, 32(3), pp. 505-536. | |
| Hart, P., Nilsson, N. & Raphael, B. (1968) 'A formal basis for the heuristic determination of minimum cost paths', IEEE Transactions on Systems Science and Cybernetics, 4(2), pp. 100-107. | |
| Huang, T., Li, J., Koenig, S. & Dilkina, B. (2022) 'Anytime Multi-Agent path finding via Machine Learning-Guided large neighborhood search', In Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), pp. 9368-9376. | |
| Li, J., Ruml, W. & Koenig, S. (2021) 'EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding', In Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), pp. 12353-12362. | |
| Okumura, K. (2023) 'LACAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding', In Proceedings of the AAAI Conference on Artificial Intelligence, 37(10), pp. 11655-11662. | |
| Ryan, M.R. (2008) 'Exploiting subgraph structure in Multi-Robot Path Planning', Journal of Artificial Intelligence Research, 31, pp. 497-542. | |
| Sharon, G., Stern, R., Felner, A. & Sturtevant, N.R. (2014) 'Conflict-based search for optimal multi-agent pathfinding', Artificial Intelligence, 219, pp. 40-66. | |
| Sharon, G., Stern, R., Goldenberg, M. & Felner, A. (2012) 'The increasing cost tree search for optimal multi-agent pathfinding', Artificial Intelligence, 195, pp. 470-495. | |
| Silver, D. (2021) 'Cooperative pathfinding', In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 1(1), pp. 117-122. | |
| Stern, R., Felner, A., Van Den Berg, J., Puzis, R., Shah, R. & Goldberg, K. (2014) 'Potential-based bounded-cost search and Anytime Non-Parametric A⁎', Artificial Intelligence, 214, pp. 1-25. | |
| Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T., Li, J., Atzmon, D., Cohen, L., Kumar, T.K., Bartk, R. & Boyarski, E. (2021) 'Multi-Agent Pathfinding: Definitions, variants, and benchmarks', Proceedings of the International Symposium on Combinatorial Search (SoCS), 10(1), pp. 151-158. | |
| Sturtevant, N.R. (2012) 'Benchmarks for Grid-Based Pathfinding', IEEE Transactions on Computational Intelligence and AI in Games, 4(2), pp. 144-148. | |
| Tang, H., Berto, F., Ma, Z., Hua, C., Ahn, K. & Park, J. (2024) 'HiMAP: Learning Heuristics-Informed Policies for Large-Scale Multi-Agent Pathfinding', In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 2498-2500. | |
| Van Den Berg, J., Guy, S.J., Lin, M. & Manocha, D. (2011) 'Reciprocal N-Body collision avoidance', Springer Tracts in Advanced Robotics, pp. 3-19. | |
| Wagner, G. & Choset, H. (2011) 'M*: A complete multirobot path planning algorithm with performance bounds', In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3260-3267. | |
| Yu, J. & LaValle, S. (2013) 'Structure and intractability of optimal Multi-Robot Path planning on graphs', In Proceedings of the AAAI Conference on Artificial Intelligence, 27(1), pp. 1443-1449. | |
| Zhang, Y., Chen, Z., Harabor, D., Bodic, P.L. & Stuckey, P.J. (2024) 'Planning and Execution in Multi-Agent Path Finding: Models and Algorithms', In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 34, pp. 707-715. | |
Mr. Shafakhatullah Khan Mohammed
Department of Computer Science Engineering, Maulana Azad University, Jodhpur, Rajasthan, 342802 - India
shafakhat91@gmail.com
Dr. Pallavi Singhal
Department of Computer Science Engineering, Maulana Azad University, Jodhpur, Rajasthan, 342802 - India
|
|
|
|
| View all special issues >> | |
|
|
