Multi-Agent Path Finding with Continuous Time Using SAT Modulo Linear Real Arithmetic

0585930 - ÚI 2025 RIV PT eng C - Konferenční příspěvek (zahraniční konf.)
Kolárik, Tomáš - Ratschan, Stefan - Surynek, P.
Multi-Agent Path Finding with Continuous Time Using SAT Modulo Linear Real Arithmetic.
Proceedings of the 16th International Conference on Agents and Artificial Intelligence (Volume 1). Setubal: SCitePress, 2024 - (Rocha, A.; Steels, L.; an den Herik, J.), s. 47-58. ISBN 978-989-758-680-4. ISSN 2184-433X.
[ICAART 2024: International Conference on Agents and Artificial Intelligence /16./. Rome (IT), 24.02.2024-26.02.2024]
Grant CEP: GA ČR(CZ) GA21-09458S
Institucionální podpora: RVO:67985807
Klíčová slova: Multi-Agent Path Finding * Satisfiability Modulo Theories
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://doi.org/10.5220/0012379700003636

This paper introduces a new approach to solving a continuous-time version of the multi-agent path finding problem. The algorithm translates the problem into an extension of the classical Boolean satisfiability problem, satisfiability modulo theories (SMT), that can be solved by off-the-shelf solvers. This enables the exploitation of conflict generalization techniques that such solvers can handle. Computational experiments show that the new approach scales better with respect to the available computation time than state-of-the art approaches and is usually able to avoid their exponential behavior on a class of benchmark problems modeling a typical bottleneck situation.
Trvalý link: https://hdl.handle.net/11104/0353563