Multi-Agent Path Finding
- Also called: MAPF, multi-agent pathfinding, multi-robot path planning
- Category: Learning & autonomy › Multi-robot
- Tags: multi-robot, path-planning, warehouse-automation, coordination, graph-search
The problem of computing collision-free paths for many agents moving at once on a shared graph, such as warehouse robots on a grid, so that every agent reaches its goal without conflicts.
Definition
Multi-Agent Path Finding (MAPF) is the problem of planning paths for a group of agents that share an environment, so that each agent gets from its start to its goal without two agents occupying the same place at the same time or swapping places along the same edge. The environment is usually modeled as a graph, often a grid, and time is divided into discrete steps in which each agent either moves to a neighboring vertex or waits.
MAPF solutions are usually judged by sum of costs, the total time all agents take to reach their goals, or by makespan, the time until the last agent arrives. Finding an optimal solution under these objectives is NP-hard in general, so the field has developed algorithms that trade optimality for speed. Optimal methods include Conflict-Based Search (CBS), which plans each agent independently and then resolves collisions by adding constraints in a search tree. Suboptimal methods, such as prioritized planning, where agents plan one at a time and treat earlier agents as moving obstacles, scale to much larger teams.
Lifelong MAPF is a variant in which agents receive new goals as soon as they reach old ones, which matches how warehouse and sortation robots actually work. Planning then runs continuously, often over a limited time window, and throughput becomes the main measure.
Real robots also break the textbook assumptions: they have size, acceleration limits and execution delays, so MAPF plans are usually executed with an extra coordination layer that keeps robots safe when some fall behind schedule. Learning-based methods, including imitation learning from search-based planners, are an active research direction for scaling to very large fleets.
Why it matters
Warehouses, factories and sorting centers run growing fleets of mobile robots on shared floors, and their throughput depends on how well those robots are coordinated. MAPF provides the algorithms that keep the robots moving without collisions or deadlocks as fleets grow.
Key applications
- Warehouse and fulfillment-center robot fleets
- Parcel sortation systems with many mobile robots
- Coordinating automated guided vehicles in factories
- Multi-drone and airport ground traffic coordination
- Character movement in video games and crowd simulation
In practice
A team running a warehouse fleet typically models the floor as a grid or roadmap graph, with each cell sized to fit one robot. A central planner receives goals from the order system and computes coordinated paths, often with a prioritized or windowed search that replans every few seconds rather than solving the whole problem optimally. Paths are converted into timed waypoints and sent to the robots, and an execution layer, such as an action dependency graph, makes sure a robot does not enter a cell until the robot ahead has cleared it. Engineers measure throughput, waiting time and deadlock frequency in simulation at full fleet size before changing the floor layout or the algorithm on the real system.
Common misconceptions
- Each robot can plan its own shortest path independently — independent paths collide, so robots must be coordinated in time as well as space
- Optimal MAPF scales to any fleet size — optimal solving is NP-hard, so large fleets rely on suboptimal or windowed methods
- A MAPF plan can be executed exactly as computed — real robots run early or late, so execution needs its own safety and coordination layer
Who should know this
- Warehouse automation and fleet management engineers
- Multi-robot planning researchers
- AMR and AGV system integrators
- Operations researchers working on logistics
Related technologies
- Conflict-Based Search
- Prioritized Planning
- A* Search
- Fleet Management Systems
- Imitation Learning
Related terms
Related projects
- Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
- ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
- OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
- Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
- IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
- Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots