webmaster: Sven Koenig

Learn all about Multi-Agent Path Finding (MAPF)


J. Chudy, N. Popov and P. Surynek. Emulating Centralized Control in Multi-Agent Pathfinding Using Decentralized Swarm of Reflex-Based Robots. In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2020.

Abstract: Multi-agent pathfinding (MAPF) represents a core problem in robotics. In its abstract form, the task is to navigate agents in an undirected graph to individual goal vertices so that conflicts between agents do not occur. Many algorithms for finding feasible or optimal solutions have been devised. We focus on the execution of MAPF solutions with a swarm of simple physical robots. Such execution is important for understanding how abstract plans can be transferred into reality and vital for educational demonstrations. We show how to use a swarm of reflex-based Ozobot Evo robots for MAPF execution. We emulate centralized control of the robots using their reflex-based behavior by putting them on a screen’s surface, where control curves are drawn in real-time during the execution. We identify critical challenges and ways to address them to execute plans successfully with the swarm. The MAPF execution was evaluated experimentally on various benchmarks.

Download the paper in pdf.

(last updated in 2022)