11/11/2021: Multi-Agent Path Finding: A New Boolean Encoding, Roberto Asín, University of Concepcion

Speaker/presenter: Roberto Asín

i) Presentation description:

Multi-agent pathfinding (MAPF) is an NP-hard problem. As such, dense maps may be very hard to solve optimally. In such scenarios, compilation-based approaches, via Boolean satisfiability (SAT) and answer set programming (ASP), have been shown to outperform heuristic-search-based approaches, such as conflict-based search (CBS). In this session, a new Boolean encoding for MAPF has been explained. This encoding was implemented in ASP and MaxSAT, and was published in The International Symposium on Combinatorial Search of 2021. A feature that distinguishes that encoding from previous ones is that swap and follow conflicts are encoded using binary clauses, which can be exploited by conflict-driven clause learning (CDCL) solvers due to the strengthened propagation. In such encoding, the number of clauses used to encode swap and follow conflicts do not depend on the number of agents, allowing the method to scale better. For MaxSAT, the authors study different ways in which to combine the MSU3 and LSU algorithms for maximum performance.

The experimental evaluation, over square grids, ranging from 20×20 to 50×50, and warehouse maps, was done varying the percentage of occupied cells and considering very dense maps. The performance of the new encoding, in comparison with solvers of the state-of-the-art, including the search-based algorithm CBS, the ASP-based solver ASP-MAPF, and the branch-and-cut-and-price hybrid solver, BCP shows a significant improvement over the state of the art, especially on very high puzzle-like maps. Nevertheless, the compilation-based methods are penalized by the need of waiting possibly-large grounding phases over different calls to the underlying CDCL solver, which renders them less competitive in terms of the total amount of time required to deliver an optimal solution on low to medium occupied maps.

References:

[1] Roberto Ası́n Achá, Rodrigo López, Sebastián Hagedorn, and Jorge A Baier. A new boolean encoding for mapf and its performance with asp and maxsat solvers. In Proceedings of the International Symposium on Combinatorial Search, volume 12, pages 11–19, 2021.

[2] Rodrigo N. Gómez, Carlos Hernández, and Jorge A. Baier. A compact answer set programming encoding of multi-agent pathfinding. IEEE Access, 9:26886–26901, 2021.

[3] Edward Lam, Pierre Le Bodic, Daniel Damir Harabor, and Peter J. Stuckey. Branch-and-cut-and-price for multi-agent pathfinding. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 1289–1296, 2019.

[4] Jiaoyang Li, Ariel Felner, Eli Boyarski, Hang Ma, and Sven Koenig. Improved heuristics for multi-agent path finding with conflict-based search. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 442–449, 2019.

[5] Pavel Surynek, Ariel Felner, Roni Stern, and Eli Boyarski. Efficient SAT approach to multi-agent path finding under the sum of costs objective. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI), pages 810–818. IOS Press, 2016