A new algorithm lets warehouse robots — or any large swarm — plan collision-free paths while accounting for more than one blocking agent at a time.
Researchers introduced Multi-Dependency PIBT (MD-PIBT), a framework that extends the widely used Priority Inheritance with Backtracking algorithm for multi-agent path finding. The older PIBT approach restricts its search to paths that conflict with at most one other agent at a time, which becomes a hard ceiling in dense environments. MD-PIBT reframes the problem by explicitly modeling dependencies between agents, allowing the planner to reason about chain-reaction conflicts across multiple robots simultaneously. In tests, it handled up to 10,000 agents under real-world movement constraints — including robots with speed and acceleration limits.
Most commercial robot deployments in dense spaces, like fulfillment warehouses, hit practical walls with existing MAPF solvers when congestion peaks. MD-PIBT's multi-step planning is particularly noted as effective for large agents, the category most prone to cascading blockages. The framework is also general enough to reproduce the behavior of prior algorithms, meaning teams can adopt it without abandoning existing infrastructure.
The code is open-source on GitHub, which is either a sign of genuine research confidence or a bid for industry adoption — probably both.