Multi-Agent Path Finding

Planning routes for a whole group of robots to their respective goals at the same time, guaranteeing none of them collide.

Multi-agent path finding studies the problem: given a map with multiple agents (robots, AGVs, etc.), each with its own start and goal, compute collision-free paths for all of them together. The classic setup discretizes the map into a grid or graph and time into steps, with each agent, each step, allowed to move to an adjacent cell or wait. There are two main kinds of conflict: two agents occupying the same cell at the same time (a vertex conflict), or two agents swapping positions between adjacent cells (an edge conflict). Common objectives are the sum of all agents' arrival times, or the time of the last arrival (makespan). Finding the optimal solution is NP-hard; common algorithms include conflict-based search (CBS, which plans each agent independently first, then adds constraints and replans whenever a conflict is found) and prioritized planning (planning agents in order, with later ones yielding to earlier ones). A 2019 survey by Stern et al. unified the definitions of various variants and gave grid-based benchmarks. It is the core problem behind warehouse robot fleet scheduling, and complements single-robot path planning and local avoidance methods such as ORCA.

ExampleIn an e-commerce warehouse, large numbers of transport robots carry shelves to picking stations (Amazon's Kiva system is a well-known example of this scenario); every time a new task arrives, the scheduling system has to replan conflict-free paths for these robots.

Also called

MAPF, Multi-Robot Path Planning

Related

Path Planning · Multi-robot Collaboration · A* Search · Fleet Management System (e.g. Open-RMF) · Velocity Obstacles · Autonomous Mobile Robot

Sources

Wikipedia: Multi-agent pathfinding
Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks (arXiv 1906.08291)