⚡ electrical engineering

Predictive congestion externality aware online scheduling for multi-robot warehouses under execution uncertainty

This paper introduces PACE, an online scheduling policy for multi-robot warehouses that mitigates traffic congestion by integrating predicted task completion costs with estimated assignment-induced congestion externalities derived from stochastic rollouts, thereby optimizing fleet performance particularly under high-traffic conditions.

Original authors: Chen Li

Published 2026-09-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chen Li

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern warehouse, the floor is no longer just a storage space; it is a dynamic river of movement. Hundreds of small, autonomous robots zip across the grid, carrying shelves of goods from storage to packing stations. These machines are the backbone of rapid delivery, capable of moving thousands of items an hour. However, their efficiency relies on a delicate balance. When a robot is assigned a task, it does not just move in isolation; it enters a shared network of paths, intersections, and narrow aisles. If a robot takes a route that seems perfect for itself, it might block a critical junction, forcing dozens of other robots to wait. This creates a ripple effect where a single decision causes a system-wide slowdown. The challenge for engineers is not just to tell a robot where to go, but to predict how that choice will affect the entire fleet before the robot even starts moving.

A new study by Chen Li at the Wuhan Institute of Technology tackles this problem by looking at the hidden cost of a robot's journey. The research focuses on a concept called "congestion externality," which is simply the extra waiting time a robot forces on everyone else when it takes a specific path. In traditional scheduling, a computer usually picks the robot that can finish a job the fastest based on its own distance and speed. This new approach argues that the fastest robot for one job might be the worst choice for the warehouse as a whole if its path clogs up a busy intersection. To solve this, the researcher developed a method called Predictive Assignment with Congestion Externalities, or PACE. Instead of just looking at the immediate task, PACE simulates the future to see how assigning a task to one robot will change the flow for all the others.

The method works by running thousands of quick, parallel simulations in the computer's memory. For every possible robot-task pairing, the system creates two versions of the future: one where the robot takes the job, and one where it does not. Crucially, these simulations include random delays to mimic real-world unpredictability, such as a robot slowing down slightly or a sensor glitch. By comparing the total waiting time of the entire fleet in both scenarios, the system calculates the "marginal congestion externality." This number represents the specific amount of extra delay the assignment would cause to the rest of the fleet. If a robot is the closest to a task but its route would trap others in a bottleneck, the system recognizes that the cost to the warehouse is too high, even if the robot itself finishes quickly.

The results of the study show that this foresight is most valuable when the warehouse is busy. In simulations using various warehouse layouts, including narrow corridors and complex crossroads, the new method consistently outperformed standard scheduling rules. When traffic was light, the difference was small, but as the number of robots and tasks increased toward the system's limit, the advantage became clear. The PACE method achieved higher throughput, meaning more tasks were completed per hour, and significantly reduced the time tasks spent waiting in line. It also prevented the "tail" of the distribution from getting too long, ensuring that a few difficult tasks did not get stuck indefinitely while others moved smoothly. The study found that the system was particularly effective at avoiding the "tragedy of the commons," where individual robots acting in their own best interest collectively create a traffic jam.

A key finding of the research is that the improvement comes specifically from this assignment-level feedback, not just from better pathfinding or collision avoidance. The researchers tested this by removing the externality calculation and found that the performance gains disappeared, proving that the value lies in choosing the right robot for the job before the movement begins. The system also proved robust against uncertainty; even when the simulations included unexpected delays or bursty traffic patterns, the method continued to make better decisions than traditional approaches. The researchers noted that the method does not force robots to take unnecessarily long detours; rather, it only accepts a slightly longer path for one robot if that choice prevents a much larger delay for the entire fleet.

The study concludes that this approach is best viewed as a complement to existing planning systems. While other algorithms ensure robots do not crash into each other, PACE ensures they do not get in each other's way in the first place. The simulations suggest that for warehouse operators, this type of scheduling is most critical during peak hours or in facilities with tight bottlenecks. By treating the waiting time of the entire fleet as a cost to be managed, the system turns a chaotic flow of independent agents into a coordinated whole. The research demonstrates that in a crowded digital world, the smartest move is often not the one that looks fastest for the individual, but the one that keeps the entire network moving.

Technical Summary: Predictive Congestion Externality Aware Online Scheduling for Multi-Robot Warehouses

1. Problem Formulation

The paper addresses the challenge of online task assignment in dense, multi-robot warehouse environments where Automated Guided Vehicles (AGVs) and Autonomous Mobile Robots (AMRs) operate under execution uncertainty. The core problem is that assigning a task to a specific robot is not an isolated decision; it creates a congestion externality. A locally optimal assignment (e.g., the nearest robot or the one with the shortest predicted travel time) may force that robot through a bottleneck, thereby inducing disproportionate waiting times for the rest of the fleet.

Existing approaches often evaluate candidate robot-task pairs based on metrics attached solely to the selected robot (travel distance, completion time, workload) or focus on path feasibility after assignment. They frequently fail to quantify the incremental system-wide delay imposed on non-selected robots before the assignment is committed. This gap is most critical near shared bottlenecks and intersections, where a slightly longer focal route could prevent significant downstream system delays.

2. Methodology: PACE

The author proposes Predictive Assignment with Congestion Externalities (PACE), an online scheduling policy designed to internalize these externalities during the assignment phase. The methodology consists of three main components:

Stochastic Counterfactual Rollouts: To estimate the congestion externality, PACE employs paired short-horizon stochastic rollouts using Common Random Numbers (CRN). For every feasible robot-task pair $(i, k)$ :
1. A baseline rollout simulates the fleet's future behavior under the current plan (where task $k$ is not assigned to robot $i$ ).
2. A candidate rollout simulates the fleet's behavior if task $k$ is assigned to robot $i$ .
3. Both rollouts use the same realization of execution uncertainty (multiplicative disturbance on traversal times) to ensure a fair comparison.
4. The marginal congestion externality ( $\hat{E}_{ik}$ ) is calculated as the difference in cumulative waiting time accumulated by all robots other than the candidate robot $i$ between the candidate and baseline scenarios.
Externality-Aware Cost Function: The assignment cost for a pair $(i, k)$ combines the robot's own predicted completion cost ( $\hat{T}_{ik}$ ) and the estimated fleet-wide externality ( $\hat{E}_{ik}$ ). Both are normalized within the current candidate set to handle scale differences. The objective function minimizes:
$c_{ik} = \alpha \mathcal{N}_t(\hat{T}_{ik}) + \beta \mathcal{N}_t(\hat{E}_{ik})$
where $\alpha$ and $\beta$ are weighting parameters. If $\beta=0$ , the policy reduces to a standard rolling-horizon self-cost baseline.
Rolling-Horizon Execution: The optimization problem is solved as a matching problem (using the Hungarian algorithm) to assign tasks to robots or defer them. The resulting assignments are executed through a shared, conflict-free Safe Interval Path Planning (SIPP) layer. This separation ensures that performance gains are attributed to assignment decisions rather than variations in collision avoidance mechanisms.

3. Key Contributions

Formalization of Assignment-Induced Externality: The paper formally defines and quantifies the marginal waiting imposed on the rest of the fleet by a specific robot-task assignment, treating it as a distinct cost component.
Estimation via Paired Rollouts: It introduces a practical method to estimate these externalities online using paired stochastic simulations with common random numbers, allowing for robust comparison under execution uncertainty.
Integration into Online Scheduling: The study integrates this externality signal into a rolling-horizon assignment framework, demonstrating that optimizing for system-wide flow requires looking beyond the focal robot's completion time.

4. Experimental Results

The study evaluates PACE across four layout families (regular aisles, narrow bottlenecks, cross-intersections, and MAPF benchmarks) under varying fleet sizes, task intensities, and execution noise distributions (Gaussian, log-normal, burst delays).

Estimator Accuracy: The online externality estimator shows strong rank correlation ( $r_s = 0.87$ ) with an offline reference. It successfully identifies the offline best candidate in 72% of cases (Hit@1) and includes it in the top 3 candidates 94% of the time. Accuracy improves with traffic density, as externality effects become more pronounced.
System Performance: PACE achieves the highest throughput and lowest mean/P95 flowtimes, particularly in layouts with high interaction potential (intersections, bottlenecks) and when the system approaches capacity.
Robustness: The performance gains persist under execution uncertainty and distribution shifts. The benefits are non-monotonic with respect to load: they are minimal in sparse traffic (where externalities are near zero), peak near saturation (where bottlenecks are critical), and diminish in persistent overload (where most assignments lead to congestion).
Ablation Studies: Removing the externality feedback ( $\beta=0$ ) nearly eliminates the performance gain over the self-cost baseline. This confirms that the improvement stems from the assignment-level externality feedback rather than path safety or candidate pruning alone.

5. Significance and Claims

The paper claims that PACE provides a mechanism to shift multi-robot scheduling from a "focal robot" perspective to a "system-wide" perspective without requiring global re-planning of all paths.

Contextual Value: The author asserts that externality-aware scheduling is most valuable during congestion-prone periods and in layouts with scarce intersection or bottleneck capacity. In lightly loaded operations, simple self-cost assignment remains adequate.
Complementary Role: The method is positioned not as a replacement for path planners (like SIPP or MAPF) but as a complement. While path layers enforce feasible movement, PACE determines which robot receives which task to avoid creating avoidable congestion in the first place.
Operational Insight: The study demonstrates that accepting a modest increase in a focal robot's travel distance can yield significant system-wide efficiency gains by redistributing traffic away from bottlenecks. This trade-off emerges endogenously from the current traffic state rather than being a fixed heuristic.

The author concludes that the framework effectively quantifies the "assignment-induced congestion externality," offering a robust approach to dynamic task assignment in uncertain, high-density warehouse environments. Future work is suggested to validate the framework on physical fleets and extend it to heterogeneous capacities and task bundling.