Abstract
Dynamic material handling (DMH) involves the assignment of dynamically arriving material transporting tasks to suitable vehicles in real time for minimising makespan and tardiness. In real-world scenarios, historical task records are usually available, which enables the training of a decision policy on multiple instances consisting of historical records. Recently, reinforcement learning has been applied to solve DMH. Due to the occurrence of dynamic events such as new tasks, adaptability is highly required. Solving DMH is challenging since constraints including task delay should be satisfied. A feedback is received only when all tasks are served, which leads to sparse reward. Besides, making the best use of limited computational resources and historical records for training a robust policy is crucial. The time allocated to different problem instances would highly impact the learning process. To tackle those challenges, this paper proposes a novel adaptive constrained evolutionary reinforcement learning (ACERL) approach, which maintains a population of actors for diverse exploration. ACERL accesses each actor for tackling sparse rewards and constraint violation to restrict the behaviour of the policy. Moreover, ACERL adaptively selects the most beneficial training instances for improving the policy. Extensive experiments on eight training and eight unseen test instances demonstrate the outstanding performance of ACERL compared with several state-of-the-art algorithms. Policies trained by ACERL can schedule the vehicles while fully satisfying the constraints. Additional experiments on 40 unseen noised instances show the robust performance of ACERL. Cross-validation further presents the overall effectiveness of ACREL. Besides, a rigorous ablation study highlights the coordination and benefits of each ingredient of ACERL.
Introduction
In the bustling environment of a modern "smart" factory, a fleet of Automated Guided Vehicles (AGVs) acts as the circulatory system, moving materials between workstations. However, managing these fleets is a logistical challenge: new tasks arrive unpredictably, vehicles may experience delays, and strict deadlines (tardiness constraints) must be met to maintain production flow.
This paper addresses the problem of Dynamic Material Handling (DMH). Unlike static scheduling, DMH requires real-time decision-making in the face of dynamic events. Current Reinforcement Learning (RL) solutions face three major hurdles: sparse rewards (feedback is only available at the end of a shift), strict constraints (balancing speed with task delays), and generalization (maintaining performance across different warehouse layouts or noisy data). To solve these, we introduce ACERL, a framework that combines evolutionary strategies with adaptive scenario sampling.
Methodology
ACERL (Adaptive Constrained Evolutionary Reinforcement Learning) introduces three key innovations to tackle the complexities of AGV scheduling:
1. Natural Evolution Strategies (NES)
Instead of using standard backpropagation, which often struggles with the sparse rewards of a full warehouse shift, ACERL maintains a population of "actors" (neural networks). It perturbs their parameters with Gaussian noise and updates the "parent" policy based on which perturbations performed best. This gradient-free approach is naturally more robust to the "all-or-nothing" feedback typical of DMH environments.
2. Intrinsic Stochastic Ranking (ISR)
To handle constraints without the instability of manual penalty weight tuning, ACERL uses a stochastic ranking system. Actors are evaluated within their specific scenarios and ranked primarily by their ability to satisfy constraints and secondarily by their efficiency (makespan). This ensures the evolutionary process prioritizes feasibility before optimizing for speed.
3. Adaptive Instance Sampler (AIS)
Training on every historical record equally is computationally inefficient. ACERL utilizes an Upper Confidence Bound (UCB) approach to dynamically select training scenarios. By focusing resources on instances where the current policy is struggling, the AIS ensures the model develops a more generalized understanding of the problem space.
Experimental Evaluation
The researchers evaluated ACERL using the DMH-GYM simulator across several datasets:
- Training/Test Sets: 16 distinct problem instances (DMH-01 to DMH-16) drawn from different distributions.
- Robustness Set: 40 additional unseen instances with varying levels of random perturbations to task arrival times.
- Cross-Validation: A "leave-one-out" setup to test how well the model transfers to entirely different scenario distributions.
Key Results
ACERL was compared against five state-of-the-art RL/CRL algorithms (including MAPPO and RCPOM) and classic dispatching rules:
- Constraint Satisfaction: ACERL achieved 100% constraint satisfaction on training instances and 97% on unseen test instances. In contrast, the previous best RL method (RCPOM) only managed approximately 60-63%.
- Efficiency: The framework consistently achieved the lowest (best) makespan across nearly all test cases.
- Real-Time Performance: The trained policy can make a scheduling decision in just 2 milliseconds, easily meeting the requirements for real-time industrial deployment.
- Robustness: Even when task arrival times were heavily "noised," ACERL maintained high performance, whereas traditional dispatching rules like First-Come-First-Served (FCFS) saw significant degradation.
Conclusion
ACERL provides a robust and efficient solution for AGV scheduling by prioritizing constraint satisfaction through stochastic ranking and utilizing adaptive sampling to improve generalization. While the model shows some performance gaps when faced with extreme out-of-distribution scenarios, its ability to maintain 100% feasibility in training and high robustness in testing marks a significant advancement for real-world industrial RL. Future work will focus on scaling the state space for massive warehouses and applying ACERL to other constrained domains like power grid optimization.
Summary updated