Symmetry Breaking Constraints for Multi-Agent Pathfinding

Описание: Presented at the 2019 Amazon Research Awards Robotics Symposium.

In this talk we describe recent progress in the area of optimal Multi-Agent Path Finding. We identify a type of conflict between agents called pairwise path symmetry: situations where pairs of agents have many individually optimal paths but which are all pairwise incompatible with one another. We show that these problems are everywhere in optimal MAPF and that, left untreated, they cause a combinatorial explosion in the size of the search space. We then introduce new constraint-based reasoning techniques to efficiently detect and resolve these symmetries, and we report large performance and success-rate improvements in the context of Conflict-based Search.

References:

Li, J., Harabor, D., Stuckey, P.J., Ma, H. and Koenig, S., 2019, July. Symmetry-breaking constraints for grid-based multi-agent path finding. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 6087-6095).
(PDF: https://ojs.aaai.org/index.php/AAAI/a...)

Li, J., Gange, G., Harabor, D., Stuckey, P.J., Ma, H. and Koenig, S., 2020, June. 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).
(PDF: https://ojs.aaai.org/index.php/ICAPS/...)

Sharon, G., Stern, R., Felner, A. and Sturtevant, N.R., 2015. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219, pp.40-66.
(PDF: https://webdocs.cs.ualberta.ca/~natha...)