webmaster: Sven Koenig

Learn all about Multi-Agent Path Finding (MAPF)


O. Salzman and R. Stern. Research Challenges and Opportunities in Multi-Agent Path Finding and Multi-Agent Pickup and Delivery Problems. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1711-1715, 2020.

Abstract: Recent years have shown a large increase in applications and research of problems that include moving a fleet of physical robots. One particular application that is currently a multi-billion industry led by tech giants such as Amazon robotics and Alibaba is warehouse robots. In this application, a large number of robots operate autonomously in the warehouse picking up, carrying, and putting down the inventory pods. In this paper, we outline several key research challenges and opportunities that manifest in this warehouse application. The first challenge, known as the Multi-Agent Path Finding (MAPF) problem, is the problem of finding a non-colliding path for each agent. While this problem has been well-studied in recent years, we outline several open questions, including understanding the actual hardness of the problem, learning the warehouse to improve online computations, and distributing the problem. The second challenge is known as the Multi-Agent Package and Delivery (MAPD) problem, which is the problem of moving packages in the warehouse. This problem has received some attention, but with limited theoretical understanding or exploitation of the incoming stream of requests. Finally, we highlight a third, often overlooked challenge, which is the challenge of designing the warehouse in a way that will allow efficient solutions of the two above challenges.

Download the paper in pdf.

(last updated in 2022)