mapf.info
webmaster: Sven Koenig
Learn all about Multi-Agent Path Finding (MAPF)
Welcome!
New MAPF competition in 2023: The League of Robot Runners will return in 2024
(click here for more information)
MAPF Team wins the NeurIPS Flatland Competition in 2020
(click here for more information)
Multi-Agent Path Finding (MAPF) is the problem of computing collision-free paths for a team of agents from their current locations to given destinations. Application examples include autonomous aircraft towing vehicles, automated warehouse systems, office robots, and game characters in video games. Practical systems must find high-quality collision-free paths for such agents quickly.
Consider, for example, automated warehouses. Path planning for robots in such warehouses is tricky since most warehouse space is used for storage, resulting in narrow corridors where robots cannot pass each other. Warehouse robots operate all day long but a simplified one-shot version of the path-planning problem is the simplest form of a MAPF problem, which can be described as follows: On math paper, some cells are blocked. The blocked cells and the current cells of n robots are known. A different unblocked cell is assigned to each of the n robots as its goal cell. The problem is to move the robots from their current cells to their goal cells in discrete time steps and let them wait there. The optimization objective is to minimize the makespan, that is, the number of time steps until all robots are at their goal cells. During each time step, each robot can wait in its current cell or move from its current cell to an unblocked neighboring cell in one of the four main compass directions. Robots are not allowed to collide. Two robots collide if and only if, during the same time step, they both move to the same cell or both move to the current cell of the other robot. There are also versions of the MAPF problem with different optimization objectives than makespan (such as the sum of the time steps of each robot until it is at its goal cell) or slightly different collision or movement rules. For example, solving the eight-puzzle (the toy with eight square tiles in a three by three frame) is a version of the MAPF problem where the tiles are the robots.
Click here for a longer introduction to MAPF.
To stay informed on MAPF-related papers or events, please join the MAPF mailing list on Google groups. (If you do not have access to them, you can send an email to Sven Koenig instead.)
You can also download a bibtex file for all publications listed on this website and then use this file with LaTex to generate the bibliographies for your publications. See "Publications" on the menu to the left and read the top paragraph there.