Planning over MAPF Agent Dependencies via Multi-Dependency PIBT

When a fulfillment center runs 4,000 robots, the hard problem is not navigation — it is coordination. Every robot needs a path, and every path is a potential collision with every other robot. That is the multi-agent path finding (MAPF) problem, and researchers from Carnegie Mellon University and the University of Melbourne think they have found a better way to solve it at scale.

A paper posted to arXiv on March 24, 2026 introduces MD-PIBT, or Multi-Dependency Priority Inheritance with Backtracking. It is a generalization of PIBT, the algorithm that has become the default coordination layer for warehouse robot fleets since Kei Okumura and colleagues published it in the Artificial Intelligence journal in 2022. The key difference: PIBT and its enhanced variant EPIBT both restrict their search to paths conflicting with at most one other agent. MD-PIBT lifts that restriction, reframing priority inheritance as a graph search over agent dependencies rather than a per-agent planning heuristic.

PIBT is constrained because it restricts its search to paths that conflict with at most one other agent. This limitation also applies to Enhanced PIBT. MD-PIBT generalizes both — specific parameterizations can reproduce each algorithm's behavior, which means existing implementations can adopt it without throwing out their current stack.

For a warehouse, the practical implication is significant. Imagine a pick station with a queue: robot A is waiting for robot B to clear the aisle, and robot B is waiting for robot C to finish unloading. That is a three-robot dependency chain. PIBT handles the A-B conflict, then the B-C conflict — two separate negotiations. MD-PIBT sees the whole chain as a single graph structure and can reprioritize across all three simultaneously. In a congested environment with hundreds or thousands of agents, those chains get long and tangled fast.

The researchers claim MD-PIBT scales to 10,000 homogeneous agents under kinodynamic constraints — movement limits that mirror real robot physics. The number is also the benchmark target in the Amazon-sponsored League of Robot Runners competition, which requires planning 10,000 agents in one second. Amazon itself operates more than 500,000 mobile robots across its fulfillment network, with individual facilities typically running 4,000 or more, according to the company's robotics blog. As of July 2025, Amazon said its DeepFleet coordination system — which assigns and routes robot tasks across a fleet — reduced robot travel time by 10 percent.

Jiaoyang Li, a researcher at the CMU Robotics Institute and winner of the 2023 League of Robot Runners competition, is a co-author of the new paper alongside Zixiang Jiang from the University of Melbourne, Yulun Zhang, and Rishi Veerapaneni. The paper does not claim DeepFleet uses MD-PIBT — it is an academic result, not a product announcement — but the benchmarks are tuned to exactly the problem Amazon's logistics division faces.

The paper's GitHub repository includes reference implementations. The algorithmic claims are verifiable: PIBT and EPIBT code is available from Okumura's project page, and the League of Robot Runners provides standardized scenarios. The research has not been peer-reviewed — it is a preprint — so the scalability numbers should be treated as unverified until the community has had time to reproduce them. That said, the paper's argument is grounded in established theory: dependency-graph search as a generalization of priority inheritance is a clean conceptual move, not a brute-force hack.

What is worth watching next is how quickly this gets absorbed into existing MAPF frameworks. The algorithm is a parameterization, not an architecture — teams running PIBT-based planners can likely adopt MD-PIBT by swapping in a different priority function without rebuilding their pipelines. If the scalability claims hold under independent testing, that is the kind of quiet infrastructure improvement that ripples through warehouse automation quietly and then suddenly becomes load-bearing for anyone running large robot fleets.

The coordination problem does not get easier as you scale. A system that works at 500 agents and one that works at 10,000 are not the same problem with different numbers. MD-PIBT is a genuine conceptual advance on the smaller problem — whether it holds at the scale Amazon needs is the open question.