ESO-MAPF: Bridging Discrete Planning and Continuous Execution in Multi-Agent Pathfinding

Authors
Chudý, J.; Surynek, P.
Year
2021
Published
Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2021. p. 16014-16016. ISSN 2159-5399. ISBN 978-1-57735-866-4.
Type
Proceedings paper
Annotation
We present ESO-MAPF, a research and educational platform for experimenting with multi-agent path finding (MAPF). ESO-MAPF focuses on demonstrating the planning-acting chain in the MAPF domain. MAPF is the task of finding collision free paths for agents from their starting positions to given individual goals. The standard MAPF uses the abstraction where agents move in an undirected graph via traversing its edges in discrete steps. The discrete abstraction simplifies the planning phase however resulting discrete plans often need to be executed in the real continuous environment. ESO-MAPF shows how to bridge discrete planning and the acting phase in which the resulting plans are executed on physical robots. We simulate centralized plans on a group of OZOBOT Evo robots using their reflex functionalities and outputs on the surface of the screen that serves as the environment. Various problems arising along the planning-acting chain are illustrated to emphasize the educational point of view.

Multi-Agent Path Finding with Mutex Propagation

Authors
Zhang, H.; Li, J.; Surynek, P.; Koenig, S.; Kumar, S.
Year
2020
Published
Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling. Menlo Park: AAAI Press, 2020. p. 323-332. ISSN 2334-0835. ISBN 978-1-57735-824-4.
Type
Proceedings paper
Annotation
Mutex propagation is a form of efficient constraint propagation popularly used in AI planning to tightly approximate the reachable states from a given state. We utilize this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF, mutex propagation provides stronger constraints for conflict resolution in Conflict-Based Search (CBS), a popular optimal MAPF algorithm, and provides it with the ability to identify and reason with symmetries in MAPF.

Unifying Search-based and Compilation-based Approaches to Multi-agent Path Finding through Satisfiability Modulo Theories

Authors
Year
2019
Published
Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2019. p. 1916-1922. ISSN 1045-0823. ISBN 978-0-9992411-4-1.
Type
Proceedings paper
Annotation
We unify search-based and compilation-based approaches to multi-agent path finding (MAPF) through satisfiability modulo theories (SMT). The task in MAPF is to navigate agents in an undirected graph to given goal vertices so that they do not collide. We rephrase Conflict-Based Search (CBS),one of the state-of-the-art algorithms for optimal MAPF solving, in the terms of SMT. This ideac ombines SAT-based solving known from MDD-SAT, a SAT-based optimal MAPF solver, at the low-level with conflict elimination of CBS at the high-level. Where the standard CBS branches the search after a conflict, we refine the propositional model with a disjunctive constraint. Our novel algorithm called SMT-CBS hence does not branch at the high-level but incrementally extends the propositional model. We experimentally compare SMT-CBS with CBS, ICBS, and MDD-SAT.

The person responsible for the content of this page: doc. Ing. Štěpán Starosta, Ph.D.