PaperlayerView exact revision on arXiv

Source-linked AI summary

HiRAD: A Flexible Large-Scale AGV Routing System

Yunjie Huang, Ruizhong Wu, Mengxuan Zhang, Frodo Kin Sun Chan, Yan Nei Law, Lei Li

arXiv:2609.09752v1cs.ROcs.AI

TL;DR

Large-scale AGV routing must reconcile flexibility, collision avoidance, and continuous kinematics with practical computation. HiRAD addresses this using high-resolution spatiotemporal modeling, hierarchical direction–velocity control, and asynchronous inference, and reports faster routing with improved makespan across tested environments.

  • Problem

    AGV routing must simultaneously provide flexibility and kinematic constraints while remaining collision-free and efficient.

  • Method

    HiRAD combines high-resolution spatiotemporal modeling with hierarchical direction–velocity control and asynchronous decision-making for continuous-space AGV routing.

  • Results

    HiRAD outperforms state-of-the-art solutions and improves routing efficiency across random maps and warehouse environments.

  • Takeaways & Limitations

    HiRAD supports flexible, collision-free, and kinematically constrained AGV routing with inference efficiency intended for real-world warehouse operation.

  • Takeaways & Limitations

    Continuous formulations can increase policy-optimization complexity as spatial resolution, action directions, and velocity choices expand.

Abstract

from arXiv · show

Automatic Guided Vehicles (AGVs) substantially boost warehouse throughput, but routing large-scale AGV fleets remains challenging. Classical Multi-Agent Pathfinding solvers suffer from exploding combinatorial complexity and super-quadratic runtime, while relying on idealized grid or piecewise-linear motion models that mismatch real-world kinematics. Recent Reinforcement Learning (RL) solutions improve flexibility via decentralized agent policies but depend on discretized spatiotemporal representations, require millions of episodes to converge, and incur full-map observation at every step, which leads to large models, slow convergence, and high inference latency that violates real-time industrial control constraints. To address these bottlenecks, we propose HiRAD, a hierarchical RL framework for continuous-space AGV routing with real-time guarantees: (1) a step-level spatiotemporal representation that translates continuous motion into a differentiable RL problem, (2) a hierarchical strategy that splits heading choice from velocity control to reduce the action space, and (3) an asynchronous event-driven decision pipeline that lowers inference complexity from O(n^2) to O(n) and cuts per-step latency by as much as 71 percent. Across random graphs and two warehouse maps, HiRAD reduces makespan by 45 percent to 63 percent and shortens end-to-end runtime.

1 Introduction

Large-scale AGV routing must balance collision-free operation, flexibility, kinematic constraints, and efficiency, but existing planning and RL approaches struggle to satisfy these requirements together. HiRAD addresses this gap with high-resolution modeling, hierarchical control, and asynchronous decision-making.

  • Motivation: Existing AGV systems must provide collision-free operation, flexibility, kinematic compliance, and efficient task completion simultaneously.Achieving flexibility and kinematic constraints together remains difficult.
  • Motivation: Discrete environments simplify routing but can mismatch real-world motion and violate collision-free guarantees.Continuous modeling improves realism but enlarges the search space and increases decision-making time.
  • Motivation: AGV routing is an NP-Hard Multi-Agent Path Finding problem with substantial scalability and flexibility challenges.Classical planners can be computationally slow, while flexible RL methods may sacrifice kinematic constraints.
  • HiRAD: HiRAD combines continuous-environment modeling, hierarchical control, and asynchronous optimization to support flexible and efficient large-scale routing.The paper reports that extensive experiments outperform state-of-the-art solutions.
  • HiRAD: HiRAD adapts step-based RL to continuous environments through high-resolution spatiotemporal modeling.The approach uses finer-grained space and time aligned with AGV kinematics.
  • HiRAD: HiRAD reduces routing complexity by separating direction decisions from velocity control and by using asynchronous decision-making.Its asynchronous framework uses observation pruning and map-oriented priority to reduce complexity from quadratic to linear.

2 Related Work

AGV pathfinding research spans local and global planning, classical multi-agent optimization, and decentralized learning. These approaches trade off environmental information, scalability, computational speed, and flexibility.

  • Pathfinding settings: Local pathfinding uses partial environmental information, whereas global warehouse routing assumes a known environment modeled with grids or topological graphs.Global methods include geometric, probabilistic, sampling-based, and graph-search approaches.
  • Classical methods: Dynamic rerouting and classical optimization methods are often unsuitable for real-time multi-agent pathfinding because rerouting is time-consuming or processing is slow and batch-oriented.The cited approaches include single-agent conflict resolution, Ant Colony, Particle Swarm, and Genetic Algorithms.
  • Learning methods: Deep reinforcement learning and graph neural networks improve flexibility by selecting actions from current environmental information and decentralized training.Related systems include value-network and hierarchical RL approaches for multi-robot pathfinding.

3 Problem Formulation

The problem formulation models warehouse AGVs as agents moving on a grid toward task destinations, while augmenting each time step with velocity to represent kinematic motion. The objective is to compute collision-free paths minimizing fleet-level travel measures.

  • Environment: An AGV network is represented by an m×k grid map, with each AGV occupying one grid while completing a start-to-destination task.The basic action set contains four neighboring moves and a stay action.
  • State representation: The formulation augments each AGV location at time t with a scalar velocity v_t.The velocity is associated with each time step in the high-resolution representation.
  • Objective: The C-RL-MAPF objective computes collision-free paths for all AGVs while minimizing makespan and flowtime.Makespan is the maximum path length, whereas flowtime is the total path length.
  • Action representation: The discrete action specifies the intended neighboring cell, while velocity determines how that intent is realized over the control interval.This separates directional intent from motion execution.

4 High-Resolution Spatiotemporal Modeling

High-Resolution Spatiotemporal modeling approximates continuous AGV motion with finer spatial and temporal discretization. It preserves acceleration and deceleration behavior while controlling the state and action-space growth of a naive continuous formulation.

  • HRS design: HRS combines a fine-grained HR-Map with a finer HR-Step so discrete RL can approximate continuous environments efficiently.The HR-Map refines space and the HR-Step increases temporal decision resolution.
  • HRS design: An HR-Map divides each coarse grid into c×c smaller cells, producing a refined map M_c with spatial resolution controlled by c.The original map is recovered when c=1.
  • HRS design: An HR-Step divides a coarse decision interval δ into Δt=δ/c higher-resolution decision intervals.This enables AGVs to make decisions at finer temporal resolution.
  • Motion modeling: AGVs move between HR-Map cells at varying speeds corresponding to acceleration, constant velocity, or deceleration across HR-Steps.The fine-grained discrete model is described as equivalent to continuous environments while retaining computational efficiency.
  • Action modeling: HRS-RL-MAPF represents each action as direction and velocity, with velocity changing across steps to reflect acceleration and deceleration.The action is written as a_t=(d a_t,v_t).
  • Complexity: As c approaches infinity, continuous formulation complexity grows with refined spatial dimensions, action directions, and velocity choices.The expanded velocity and action ranges increase policy-optimization complexity.
  • Complexity: HRS controls this growth by restricting motion to a small set of kinematically feasible velocity modes and using HR-step decisions.This limits effective action and velocity dimensions compared with a naive continuous formulation.

5 HiRAD AGV Routing Framework

HiRAD separates AGV routing into coarse direction planning and fine-grained velocity control, using high-resolution spatiotemporal modeling to execute continuous motion under kinematic constraints. Its control modules coordinate collision avoidance through exclusion zones, priority handling, and predefined velocity modes.

  • Framework overview: HiRAD decouples navigation into a Macro RL-Routing Layer for coarse collision-free directions and a Micro Velocity-Control Layer for safe fine-grained motion.The macro layer uses coarse-map information, while the micro layer executes motion on the HR-Map; Alt-DVC integrates both layers.
  • Macro-RL-Routing Layer: Macro-RL-Routing reuses a single-agent policy trained on randomly generated coarse maps to produce fleet-level direction actions from partial observations.The policy encodes local view windows and guidance vectors with an LSTM, producing action distributions and state values.
  • Micro Velocity-Control Layer: Micro Velocity-Control maps macro directions to feasible continuous motion using predefined velocity modes with acceleration, maximum-speed, and deceleration stages.Examples include moving to the next grid, continuous cruising, stopping, and moving to the second grid.
  • High-resolution spatiotemporal control: The HR-step framework supports continuous execution when AGVs stop at grid centers, velocity modes satisfy three-stage kinematic constraints, and decision time is shorter than movement time.The stated conditions are formalized in Lemma 1, with HRS modeling and HR-step control claimed to enable continuous kinematically constrained operation.
  • Alternating Decision–Velocity Control: Alt-DVC detects potential collisions through active-zone and exclusive-zone intersections, then resolves conflicts with priority scheduling and deceleration decisions.Potential collisions are detected online; priority handling determines whether an AGV proceeds, slows, or stops.

6 Inference Efficiency Optimization

HiRAD reduces inference overhead by avoiding unnecessary macro decisions for moving AGVs and replacing global pairwise conflict checks with map-indexed priority lookup. These changes target the latency of synchronous control so decisions remain faster than physical execution.

  • Synchronous inference cost: Synchronous Alt-DVC incurs O(nb^2T + n^2T) time because observation preparation and priority scheduling scale with fleet size.The quadratic term comes from testing each AGV against higher-priority AGVs at every step.
  • Observation pruning: Asy-DVC queries the macro policy only for AGVs at decision points, while moving AGVs use micro-level velocity evaluation.Kinematic constraints make heading changes actionable only when an AGV can stop and reorient, allowing policy inference to be pruned for moving vehicles.
  • Map-oriented priority: Map-oriented priority replaces global pairwise conflict checks with grid-indexed lookup against the highest-priority AGV at relevant destination grids.Moves are accepted when locally highest priority; otherwise the AGV slows, stops, or defers to replanning.
  • Optimized complexity: Asy-DVC combines observation pruning at O(1/4 nb^2T) with map-oriented priority at O(nT), reducing overall inference complexity toward linear fleet scaling.The supplied analysis states these two terms as the optimized complexity components.

7 Experiment

Experiments evaluate HiRAD and scalable baselines across random maps and warehouse layouts using common map and task sets. HiRAD scales to larger fleets, while HiRAD-Asy improves runtime and warehouse scalability.

  • Experiment design: Experiments use random maps and two warehouse networks, with all methods evaluated on the same map and task sets.Random-map fleets range from 64 to 2048 AGVs; Warehouse Layout-A uses networks G1 and G2 with fleets of 100 to 400.
  • Scalability: Classical baselines fail beyond 64 AGVs in the reported random-map settings, whereas PRIMAL and HiRAD handle fleets up to 2048 AGVs.CBS also fails to provide results for 64 AGVs, while ICBS and ODrM* cannot provide results above 64 AGVs.
  • Random-map performance: At 64 AGVs, ICBS has the shortest makespan and flow path but requires 446.92s, while ODrM* completes planning in 12.01s with ε=1.5.The reported comparison separates path quality from runtime among classical methods.
  • Random-map performance: HiRAD generally achieves lower runtime and makespan than PRIMAL, with makespan approximately 3–4 times faster on map 40 and 2–3 times faster on map 80.The comparison attributes the speed difference to HiRAD allowing some AGVs to operate at high velocity rather than using only discrete step-by-step actions.
  • Random-map performance: HiRAD and PRIMAL successfully plan paths for almost all AGVs across scenarios, while HiRAD’s completed-agent count increases as fleet size grows.At 2048 AGVs on map 160, PRIMAL’s successfully reached targets drop within the endurance time, whereas HiRAD continues to increase.
  • Warehouse performance: HiRAD-Asy scales more effectively than HiRAD-Alt and PRIMAL on larger warehouse maps and fleets because of its higher time efficiency.The warehouse evaluation reports stronger scalability for the optimized asynchronous version.

8 Conclusion

HiRAD targets practical AGV routing by combining RL adaptability with collision-free operation, continuous kinematic constraints, and efficient execution. The framework models continuous motion through discrete RL decisions while addressing the resulting complexity and real-world control requirements.

  • HiRAD addresses the gap between RL-based routing and practical warehouse operation under collision-free, flexible, and kinematically constrained motion.The conclusion identifies discrete assumptions and centralized planning as barriers to practice.
  • AGV routing models represent maps, fleets, tasks, local observations, actions, transitions, rewards, and policies within an RL-MAPF formulation.Discrete actions include four neighboring-grid moves and staying still; invalid moves are rejected or penalized.
  • Discrete RL inference is linear in total flow time, but its resulting paths cannot be implemented directly in real life.The limitation motivates extending RL routing to continuous environments with kinematic constraints.
  • Continuous RL-MAPF adds velocity, acceleration, and deceleration constraints while requiring AGVs to stop at grid centers for turning or remaining stationary.Velocity changes satisfy |v_t+1 − v_t| ≤ amax.
  • Continuous-time discretization can create many decision points, making fine-grained modeling substantially more demanding than discrete-time routing.Theoretically, decisions may occur at any point in time, so practical discretization can produce many small time steps.

B.2 HRS RL-MAPF Modeling

HRS RL-MAPF incorporates velocity into step-based actions to approximate continuous motion while limiting the complexity of finer spatial and temporal modeling. Increasing velocity resolution enlarges action and state spaces, complicates rewards, slows convergence, and raises inference demands.

  • HRS RL-MAPF represents each action as direction plus velocity, with velocity changes encoding acceleration, constant speed, or deceleration.Velocity corresponds to the number of cells moved per HR-Step.
  • The action space grows from |d_a| to |d_a|×|v| when velocity is added, increasing policy-optimization difficulty as velocity resolution rises.The enlarged combinatorial space makes exploration harder.
  • The HRS state space grows from (m×k×|d_a|)^|N| to (c^m×c^k×|d_a|×|v|)^|N|, making exploration harder.The passage also identifies more complex reward design caused by positional-error-sensitive stopping.
  • T_conv ∝ |S| × |A|, so enlarged state and action spaces slow convergence and produce inefficient exploration.Direct velocity control can also cause overshooting or oscillations when stopping at grid centers.
  • Inference requires c times more decisions than the discrete version, while each decision must execute in less than 1/c of the discrete decision time.

C Macro-RL-Routing Layer

The Macro-RL-Routing Layer directs AGVs toward destinations without collisions on a coarse map. Its role is to generate global routing decisions before finer-grained control.

  • The Macro-RL-Routing Layer guides AGVs to their destinations without collisions on a coarse map.

C.1 Macro-RL-Routing Training

Macro-RL-Routing training first learns a single-agent policy on randomly generated coarse maps, then increases map difficulty through curriculum learning. Training uses obstacle variation, adaptive rewards, and an actor-critic network with temporal context.

  • Training begins with a single-agent policy on randomly generated coarse maps because full-fidelity training with hundreds of AGVs is computationally expensive.Obstacle probability is selected from 0, 0.1, and 0.2, with valid start-to-destination passages.
  • Curriculum learning increases difficulty from 10×10 obstacle-free maps to 100×100 maps with obstacle probability 0.2.
  • The reward design penalizes movement, stopping, and collisions while scaling the goal reward from +5 to +55 with map size and difficulty.The scaling prevents accumulated movement penalties on larger maps from outweighing goal completion rewards.
  • The routing network uses an actor-critic framework to encode local views and destination guidance, process temporal context with an LSTM, and output actions and state values.

C.2 Alternating Decision-Velocity Control

The section defines conditions for continuous AGV operation under kinematic constraints, including grid-center stopping, physically valid velocity modes, and real-time decision efficiency. It then connects the HRS model and HR-step RL decisions to continuous operation, while allowing resolution parameters to vary by physical system.

  • RL Real-Time Applicability Conditions: Continuous AGV operation requires grid-center stopping, kinematically valid velocity modes, and decisions completed before movement makes them invalid.These conditions preserve the grid network, physical movement correspondence, and conflict avoidance among moving AGVs.
  • HRS-Continuous Equivalence: The proposed HRS modeling combined with HR-step-based RL decision-making enables continuous AGV operation under kinematic constraints.This is stated as the HRS-Continuous Equivalence theorem.
  • HRS-Continuous Equivalence: The velocity-mode construction uses staged stopping and movement decisions to place AGVs at grid centers while respecting the modeled motion process.The proof describes Mvx, Mxx, and Mvv behavior across neighboring grids and time steps.
  • Parameter Alignment: The example uses c=10, but resolution parameters and velocity modes can change with the physical system when obtained through measurement and alignment.The stated conditions remain unchanged despite parameter changes.
Loading 2609.09752v1…