Multi-Objective Reinforcement Learning for Large-Scale Tote Allocation in Human-Robot Collaborative Fulfillment Centers

This paper proposes a Multi-Objective Reinforcement Learning framework grounded in minimax policy learning and no-regret dynamics to optimize tote allocation in human-robot collaborative fulfillment centers, effectively balancing competing objectives like speed and space utilization while satisfying operational constraints in large-scale industrial settings.

The Gist

Imagine a massive, high-tech warehouse where robots and humans work side-by-side, like a dance team trying to pack millions of boxes (called "totes") into shelves. This is the world of Amazon's "Sequoia" system.

The paper you're asking about tackles a very specific, tricky problem in this dance: The Consolidation Shuffle.

The Problem: The "Too Full, Too Empty" Dance

Imagine your closet is a mess. You have some hangers with just one shirt, and others stuffed with ten. To make space for new clothes, you need to move shirts from the crowded hangers to the empty ones.

In the warehouse, this is called consolidation.

• The Goal: Move items from partially full totes to other totes to free up space for new inventory.
• The Catch: You have two types of dancers: Humans and Robots.
  • Humans are flexible. They can pick up weird, heavy, or fragile items. But they get tired, and they are expensive (they take up space in the workflow).
  • Robots are fast and consistent. But they can only handle specific types of items. If you give them a weird item, they drop it or get stuck.

The warehouse manager has to decide: Who moves this specific item? Which tote goes where?

If they make the wrong choice, the robots get stuck, the humans get overwhelmed, or the warehouse runs out of space. They need to balance three competing goals:

1. Speed: Get things done fast.
2. Space: Don't let the shelves get too full or too empty.
3. Balance: Don't let the robot queue get too long while the humans sit idle (or vice versa).

The Old Way: The "Weighted Score" Trap

Traditionally, managers tried to solve this by creating a single "score." They would say, "Speed is worth 50 points, Space is worth 30 points, and Balance is worth 20."

The problem? It's rigid.

• If the warehouse is suddenly flooded with new orders, they need to prioritize speed, but the score is still stuck on the old weights.
• If they change the weights manually, they might accidentally break the system (e.g., prioritizing speed so much that the robots crash).
• It's like trying to drive a car by only looking at the speedometer, ignoring the gas gauge and the engine temperature.

The New Way: The "Tug-of-War" Game

The authors propose a smarter way using Multi-Objective Reinforcement Learning (MORL). Instead of one boss giving orders, they set up a Tug-of-War game between two characters:

1. The Learner (The Agent): This is the AI trying to move the totes. Its goal is to be as fast and efficient as possible.
2. The Regulator (The Referee): This is a smart overseer watching the Learner. Its job is to make sure the Learner doesn't break the rules (like overloading the robots or running out of space).

How the game works:

• Round 1: The Learner tries to move totes as fast as it can. It ignores the rules a bit to get a high score.
• The Referee's Move: The Referee sees the Learner is breaking the rules (e.g., "Hey, you're overloading the robot station!"). The Referee slaps a "penalty" on the Learner.
• Round 2: The Learner tries again. Now, it has to balance speed with the penalty. It learns to slow down just enough to keep the robots happy.
• The Dance: They repeat this thousands of times. The Learner gets faster, and the Referee gets smarter about how much to penalize.

Eventually, they reach a Perfect Balance (Minimax Equilibrium). The Learner finds a strategy that is fast and respects all the rules, without anyone needing to manually tell it "Speed is 50% important." The system figures out the perfect mix on its own.

The Magic Trick: The "Oscillating" Solution

Here is the clever part the paper discovered.

In theory, the "perfect" solution is a mixture. Imagine the AI says: "For the next 10 minutes, I'll be super fast but risky. For the next 10 minutes, I'll be super slow but safe." If you average those two, you get a perfect result.

But in real life, you can't switch back and forth every 10 minutes; it's chaotic. You need one single strategy that works all the time.

The paper proves that even though the AI is technically "oscillating" between different strategies during training, if you look closely, it naturally stumbles upon a single, steady strategy that satisfies all the rules perfectly. It's like a tightrope walker who wobbles left and right while learning, but eventually finds a steady path that keeps them from falling.

The Results: Why It Matters

The team tested this in a super-accurate computer simulation of a real Amazon warehouse.

• Old methods (single-objective) either crashed the robots or moved too slowly.
• The new method learned a single policy that:
  • Kept the robots from getting overloaded.
  • Kept the humans from getting bored.
  • Moved items faster than the random baseline.
  • Crucially: It did all this without a human ever having to tweak the settings.

The Takeaway

This paper shows that we can teach AI to manage complex, real-world systems (like warehouses) by letting it play a game of "push and pull" against a virtual referee. Instead of hard-coding rules, the AI learns to find the "sweet spot" where speed, safety, and efficiency all coexist. It's a major step toward making our future warehouses run smoother, faster, and with less human guesswork.

Technical Summary

1. Problem Definition

The paper addresses the tote consolidation problem in large-scale, human-robot collaborative fulfillment centers (e.g., Amazon's "Sequoia" system).

• Context: Inventory is stored in containers called "totes." To optimize storage space and throughput, partially filled totes must be consolidated (items moved from a "source" tote to a "destination" tote) to free up space for new inbound inventory.
• Challenge: This process involves heterogeneous agents:
  • Human Stations: Can handle complex/irregular items but consume processing capacity from other workflows.
  • Robotic Stations: Highly consistent but limited by item properties (e.g., deformable or reflective items).
• Objectives: The system must balance competing Key Performance Indicators (KPIs):
  1. Throughput Efficiency (ETPH): Maximizing the number of totes emptied per hour.
  2. Space Utilization: Maintaining a specific balance of tote types (e.g., limiting "large" totes).
  3. Load Balancing: Ensuring a balanced Source-to-Destination (S/D) ratio.
  4. Capacity Constraints: Preventing queue overflows at both human and robotic stations.
• Limitation of Existing Methods: Traditional scalarization (combining objectives into one weighted sum) fails because weights must be fixed in advance, making the system sensitive to weight selection and unable to adapt to shifting priorities or dynamic constraints.

2. Methodology

The authors formulate the problem as a Constrained Multi-Objective Reinforcement Learning (MORL) task modeled as a Markov Decision Process (MDP).

A. Theoretical Framework: Zero-Sum Game

The constrained optimization problem is reformulated as a zero-sum Lagrangian game between two players:

1. The Learner: Selects a policy distribution $D$ to maximize the primary objective (throughput) while satisfying constraints.
2. The Regulator: Selects Lagrange multipliers $\lambda$ to minimize the Lagrangian, effectively penalizing constraint violations.

The goal is to find a Minimax Equilibrium of the Lagrangian function $L(D, \lambda)$.

B. Algorithm: Best-Response vs. No-Regret Dynamics

To solve the minimax problem without knowing objective preferences in advance, the authors employ a repeated game framework:

• Learner (Best-Response): At each round $t$, given the current multipliers $\lambda_t$, the learner solves a single-objective RL problem using Deep Q-Networks (DQN). The reward is scalarized as:
  $$r_\lambda = r_0 + \sum \lambda_i (\alpha_i - r_i)$$
• Regulator (No-Regret): The regulator updates the multipliers $\lambda_t$ using Online Gradient Descent (OGD) based on the constraint violations observed from the learner's policy.
• Convergence: Over $T$ rounds, the time-averaged strategies $(\bar{D}, \bar{\lambda})$ converge to an approximate minimax equilibrium.

C. Addressing "Error Cancellation"

A theoretical challenge in time-averaged solutions is error cancellation: a mixture of policies might satisfy constraints on average (e.g., one policy violates a constraint while another over-satisfies it), but no single policy in the mixture is feasible.

• Contribution: The authors introduce a theoretical framework proving that even if only the mixture is guaranteed to be feasible, it is possible to probabilistically extract a single iterate (a specific policy from the training sequence) whose Lagrangian value is close to the minimax value and satisfies all constraints.

D. MDP Formulation

• State Space ($X$): Includes global floor statistics (total large totes, empty totes per hour), queue lengths at human/robot stations, tote occupancy, item counts, and time.
• Action Space ($A$): For a selected tote slot, decide to: (1) Ignore, or (2) Assign as Source/Destination to either a Human or Robot station.
• Rewards:
  • $r_0$: Throughput (ETPH).
  • $r_{1-4}$: Penalty terms for violating constraints (large tote ratio, S/D ratio, human queue capacity, robot queue capacity).

3. Key Contributions

1. Novel MORL Formulation: Proposes a specific MORL framework for human-robot collaborative fulfillment that explicitly models heterogeneous station capabilities and dynamic operational constraints.
2. Theoretical Advancement: Develops a framework to handle the "error cancellation" problem in constrained RL. They prove that a single feasible policy can be extracted from the time-averaged solution sequence, bridging the gap between theoretical guarantees (which apply to mixtures) and practical deployment (which requires single policies).
3. Empirical Validation: Demonstrates strong performance on realistic warehouse simulations, showing the method outperforms baselines in balancing KPIs.

4. Experimental Results

The authors evaluated their approach using an event-driven simulator of a large-scale fulfillment center.

• Single-Objective Baseline: Standard DQN optimized for ETPH alone achieved high throughput but severely violated capacity constraints (e.g., massive queue overflows).
• MORL Performance:
  • Constraint Satisfaction: The time-averaged policy successfully converged to satisfy all constraints (S/D ratio, capacity limits) while maintaining high throughput.
  • Single Policy Feasibility: Empirically, the algorithm frequently discovered single stationary policies during training that satisfied all constraints simultaneously, not just the mixture.
  • Trade-off Analysis: The MORL policy achieved a balanced trade-off (ETPH $\approx$ 20.52) compared to the unconstrained policy (ETPH $\approx$ 61.81 but with massive violations) and a random baseline (ETPH $\approx$ 9.19).
  • Lagrange Multipliers: The regulator's multipliers oscillated to track constraint satisfaction, tightening when violations occurred and relaxing when constraints were met, demonstrating adaptive weight learning.

5. Significance

• Industrial Impact: This work demonstrates that MORL is a viable solution for high-stakes, high-dimensional industrial decision-making where multiple conflicting objectives and hard constraints exist.
• Scalability: The approach scales to large state spaces using deep RL and avoids the need for manual weight tuning, which is a major bottleneck in traditional multi-objective optimization.
• Human-Robot Synergy: It provides a principled method for dynamically allocating work between humans and robots based on real-time constraints and item properties, maximizing the strengths of both.
• Theoretical-Practical Bridge: By solving the "error cancellation" issue, the paper moves constrained RL from theoretical mixtures to deployable, single-policy solutions, making it applicable to real-world systems where a single consistent policy is required.