PaperlayerView exact revision on arXiv

Source-linked AI summary

Trajectory-Initialized Neural Double Q-Routing for Large-Scale Overhead Hoist Transport Systems

Cheng Gu, Qiusheng Zhao, Anbang Liu, Shaochong Lin, Max Z. J. Shen

arXiv:2608.30512v1cs.LGcs.AImath.OC

TL;DR

Large-scale OHT routing faces time-varying traffic costs that static shortest paths cannot capture, while tabular Q-routing limits information sharing across routing contexts. Neural Double Q-routing uses a shared value network with offline trajectory initialization and online adaptive refinement; across nine matched settings, it lowers mean completion time versus tabular Double Q-routing by 0.8%–8.8%, with benefits depending on fleet size and arrival rate.

  • Problem

    Static shortest-path routing cannot account for time-varying OHT traffic costs, while tabular Q-routing learns destination–node–neighbor values independently and limits information sharing across sparsely visited contexts.

  • Method

    Neural Double Q-routing replaces destination-indexed tables with a shared state–action value network, warm-starts it using mixed simulator trajectories, and refines it online with Double-Q updates, local congestion correction, and event-stratified replay.

  • Results

    Mean completion time decreases by 0.8%–8.8% versus tabular Double Q-routing across all nine settings; the method performs best in six 150- and 200-OHT settings, while Dijkstra is best in three 100-OHT settings.

  • Takeaways & Limitations

    The framework provides a compact, adaptive routing approach with setting-dependent performance benefits and startup gains from offline initialization.

  • Takeaways & Limitations

    The evaluation is based on matched simulations, and unreported utilization and congestion-source statistics prevent attributing performance patterns to a specific capacity regime.

Abstract

from arXiv · show

Large-scale industrial robot fleets share constrained physical infrastructure, making vehicle travel times dependent on safety separation, intersection access, downstream blocking, and station contention. We study this problem in overhead hoist transport (OHT) systems, a representative ceiling-mounted material-handling system used in semiconductor fabs. Static shortest-path routing cannot account for these time-varying traffic costs, whereas tabular Q-routing adapts online but learns each destination--node--action value independently, limiting information sharing across sparsely visited routing contexts and making startup behavior sensitive to inaccurate value estimates. We propose Neural Double Q-routing, which replaces destination-indexed tables with a shared state--action value network. The network is warm-started through return-to-go regression on mixed simulator-generated routing trajectories and then refined online using Double-Q updates, local congestion correction, and event-stratified structured replay. Across nine matched fleet-size--arrival-rate settings with 100, 150, and 200 OHTs, the proposed framework reduces mean completion time relative to tabular Double Q-routing by $0.8\%$--$8.8\%$. It achieves the lowest mean completion time among all compared methods in the six 150- and 200-OHT settings, whereas Dijkstra remains best in the three 100-OHT settings. Completed-task counts remain within $1\%$ of tabular Double Q-routing in eight of nine settings, and 95th-percentile completion time decreases in eight settings. In two matched startup scenarios, offline initialization increases the number of completed tasks by up to $23\%$ and reduces tail completion time by up to $15\%$.

I. INTRODUCTION

OHT routing must manage time-varying congestion on shared guideways, while conventional shortest paths and tabular Q-routing have complementary limitations. Neural Double Q-routing addresses these issues with a shared, warm-started value model refined online and evaluated across matched fleet settings.

  • OHT travel times depend on safety spacing, intersection access, shared segments, downstream blocking, queues, and station contention.
  • Static shortest-path routing cannot represent current traffic, while congestion-aware methods depend on prescribed edge-penalty quality.
  • Approximately 2.59 million tabular Q entries are required for 608 destinations and 4257 directed edges, with each destination–node–neighbor tuple learned independently.
  • Neural Double Q-routing uses a shared candidate-edge scorer, mixed-trajectory return-to-go initialization, Double-Q refinement, local residual correction, and event-stratified replay.
  • 0.8%–8.8% lower mean completion time than tabular Double Q-routing was achieved across all nine matched settings.
  • The lowest mean completion time occurred in six 150- and 200-OHT settings, while Dijkstra remained best in the three 100-OHT settings.

A. Routing Within OHT Control

OHT route guidance is distinct from scheduling, dispatching, rebalancing, traffic prediction, and link-weight control because it directly selects the next hop for an assigned vehicle. The paper places Neural Double Q-routing within this interface while sharing value information across routing contexts.

  • Dispatching assigns vehicles, rebalancing positions idle capacity, and route guidance selects the next hop for a vehicle with an assigned task.
  • Traffic-aware alternatives commonly predict congestion or modify edge costs before a conventional path-construction algorithm selects a route.
  • Neural Double Q-routing directly evaluates controller-admitted outgoing edges using task, route-progress, topology, and bounded local-traffic context.
  • Tabular Q-routing stores separate destination–node–neighbor values, whereas the proposed model shares one fleet-wide state–action function across split nodes, destinations, vehicles, and task phases.
  • Neural approximation, destination conditioning, and Double-Q targets are identified as established components rather than individually new contributions.

D. Trajectory-Based Initialization and Online Adaptation

The paper treats offline learning as trajectory-based value initialization rather than conservative offline policy optimization, then adapts the shared value online to congestion and service events. This combines startup guidance with continued online refinement.

  • Simulator trajectories from Dijkstra, Q-routing, and Double Q-routing provide supervised return-to-go targets for initializing the shared value function.
  • The offline stage does not optimize a separate conservative policy; it initializes the same value function later refined by online Double-DQN updates.
  • Event-stratified replay assigns transitions to mutually exclusive OHT event classes with predefined quotas and loss weights.
  • A recent edge- and task-phase-specific TD residual changes current action rankings outside the bootstrap target, allowing local adaptation without recursively propagating residuals.
  • The framework combines established components within an OHT-specific deployment architecture rather than claiming novelty for neural approximation, Double Q-learning, or offline pretraining alone.

A. Guideway Model and Split-Based Routing Process

The simulator models OHT routing on a directed guideway where decisions occur at split nodes and vehicles traverse intervening degree-one segments. A shared value function uses vehicle, destination, topology, task-phase, and local-traffic features for each feasible next hop.

  • A. Guideway Model and Split-Based Routing Process: The simulated guideway contains 3684 nodes, 4257 directed edges, and 608 destinations, with every split having at most two outgoing edges.
  • A. Guideway Model and Split-Based Routing Process: Routing decisions occur when a vehicle reaches a split, after which it follows degree-one segments until the next split or task endpoint.
  • A. Guideway Model and Split-Based Routing Process: Each routing choice contributes one discount step, while realized holding time enters the interval reward.
  • B. Fleet-Wide Learning and Decision Representation: Transitions from all vehicles update one shared value function, while each vehicle makes local next-hop selections using its own task state and traffic summaries.
  • B. Fleet-Wide Learning and Decision Representation: The state includes node and destination indices, shortest-path distance, node degrees, task phase, load/unload status, and recent congestion-waiting time.
  • B. Fleet-Wide Learning and Decision Representation: Each candidate action includes edge geometry and progress, occupancy, queue length, and six bounded local-pressure summaries.

C. Decision-Interval Dynamics and Routing Criterion

The routing process evaluates choices at split nodes over variable-length decision intervals, with rewards combining realized travel time, congestion-related warnings, and route progress. The resulting semi-Markov criterion accounts for movement, waiting, blocking, risk, and advancement while reporting both average and tail completion outcomes.

  • Decision-Interval Dynamics: Decision intervals span the physical edges traversed after a split-node choice until the next split or task-phase endpoint.Different choices therefore cover different numbers of edges and elapsed times.
  • Decision-Interval Dynamics: Interval elapsed time includes movement, waiting for separation or right-of-way, and downstream blocking or resource-admission delays.Waiting and blocking depend on the rest of the fleet, making transitions stochastic for a fixed map and candidate edge.
  • Routing Criterion: Rewards accumulate realized edge-level time and deadlock warnings, while risk and route progress are evaluated once for the selected action.Risk aggregates occupancy, queues, bottleneck pressure, spillback, and one-hop downstream pressure.
  • Routing Criterion: The domain-weighted criterion retains physical units for movement, waiting, and blocking while adding anticipatory risk, warning, and progress terms.These shaping terms are learned criterion components rather than potential-difference transformations of elapsed time.
  • Evaluation: Performance is evaluated over T = 1000 s using mean completion time, completed tasks, and 95th-percentile completion time.The additional metrics distinguish unfinished work from delays concentrated in the completion-time tail.

IV. OFFLINE-TO-ONLINE NEURAL DOUBLE Q-ROUTING

The method combines a shared neural value representation with offline initialization and online refinement. Logged trajectories initialize the networks, while Double-Q learning, local corrections, and structured replay adapt routing to changing conditions.

  • Method Overview: Neural Double Q-routing is organized as offline initialization followed by online Double-Q refinement, local congestion correction, and event-stratified replay.The implementation label used in tables and figures is QNeuralDouble.
  • Shared Representation: A shared neural value function replaces independent destination-node-action entries and transfers information across structurally similar routing situations.The approach retains the local graph-feasible action interface while using one scoring function across the guideway.
  • Shared Representation: The network scores each feasible next hop from a joint state-action feature vector, with larger predicted return-to-go values preferred.The two-hidden-layer MLP has 5,825 parameters versus approximately 2.59 million tabular entries on the evaluated guideway.
  • Shared Representation: Because parameters are shared across nodes and destinations, each update changes a fleet-wide scoring function rather than an isolated table entry.The paper cautions that lower estimate variance is not treated as evidence of value accuracy.

B. Offline Return-to-Go Warm Start

The warm start pretrains the shared value network on mixed routing trajectories before operation. Return-to-go targets respect routing boundaries, and the learned weights initialize both online and target networks for subsequent Double-Q learning.

  • Offline Warm Start: The network is pretrained on logged decision-interval trajectories generated by Dijkstra, Q-routing, and Double Q-routing.This replaces an uninformative random startup estimate with an offline prior.
  • Return-to-Go Targets: Each trajectory record contains the state, action, reward, next state, and a terminal task-phase marker used to form regression targets.The target is computed within trajectory segments ending at terminal indices.
  • Return-to-Go Targets: Return accumulation resets across episode, vehicle, task, target, task-phase, and terminal-segment boundaries.Rewards from distinct routing episodes are not combined.
  • Network Initialization: The learned weights initialize both the online and target networks, with batches balanced by operating cell, behavior policy, and collection seed.Each behavior policy contributes data collected with three seeds.
  • Online Refinement: Double-Q learning separates action selection from evaluation to address overestimation from noisy bootstrap values.The method uses γ = 0.99 on the embedded decision chain, with interval duration already represented in the reward.
  • Online Refinement: Target-network Polyak averaging stabilizes learning, with τ = 0.005 and Huber-loss online updates.Updates begin after 64 replay records and occur every four observed transitions.

D. Congestion-Aware Online Adaptation

Online adaptation combines a shared value estimate with recent local congestion evidence and replay that preserves rare traffic and service events. The action score can respond locally without recursively propagating residual corrections through the learned bootstrap.

  • Local Congestion Correction: The local congestion correction combines the shared return estimate with an exponentially averaged local TD residual and a count-based uncertainty penalty.The correction addresses short-lived bottlenecks that the shared model may lag behind.
  • Local Congestion Correction: Local residuals are maintained by edge and task-phase, with exact records preferred over phase-pooled fallbacks and no correction when no record exists.The residual update uses α = 0.05 and clips values to [-5, 5].
  • Adaptation Schedules: The correction weight increases with observed local residuals, while the initial uncertainty penalty decays over 5,000 transitions.The schedules are λt = 0.5 min(t/5000, 1) and βt = 0.3 max(1 −t/5000, 0).
  • Action Selection: The executed action maximizes the corrected score, while the base network continues off-policy learning from the Double-Q target.Keeping residuals outside the bootstrap lets recent observations change current rankings without recursively propagating them.
  • Event-Stratified Replay: Structured replay labels each transition as normal, congested, blocked, near-deadlock, or load/unload bottleneck using an explicit severity order.Non-normal transitions enter a recent event pool and receive configured class shares and loss weights.
  • Event-Stratified Replay: When event classes are unavailable, replay fills missing allocations first from other event records and then from general replay.The table specifies labels, nominal whole-batch shares, and TD-loss weights.

V. EXPERIMENTAL EVALUATION

The evaluation compares routing methods across matched fleet-size and arrival-rate settings, then examines warm starts and online-component deletions. Neural Double Q-routing improves long-horizon completion time against tabular Double Q-routing, while startup and ablation results quantify initialization and component effects.

  • Setup: Nine matched cells sweep 100, 150, and 200 OHTs across arrival rates of 1.0, 1.5, and 2.0 task s−1 over a 1000 s horizon.Methods share task streams, initial vehicle placement, and random seeds within each cell; metrics include CT Mean, Completed, and CT P95.
  • Long-horizon results: QNeuralDouble reduces CT Mean relative to QDouble in every cell by 0.8%–8.8%, with completed-task counts within 1% in all but one cell.Table II reports matched-scene results across the fleet × arrival-rate sweep.
  • Long-horizon results: At 150 OHTs, CT Mean reductions versus QDouble range from 3.4%–8.8%, while CT P95 improves by 3.4%–6.2%.These results identify the strongest relative CT Mean improvements in the evaluated sweep.
  • Warm-start analysis: Warm starts improve Early CT by 1.3% and 2.1% and increase completed tasks by 22.2% and 23.1% across the two startup scenarios.The startup window is the first 200 s; CT P95 decreases by 7.2% and 15.0% in the same scenarios.
  • Component analysis: Replacing Double-Q with a single estimator causes the largest neural-component CT Mean penalty at +5.78 s, followed by removing local correction at +4.87 s and structured replay at +1.61 s.Removing local correction and structured replay together gives a +7.32 s penalty, while the full-framework comparison with tabular Double-Q is +17.22 s.

VI. DISCUSSION AND LIMITATIONS

The framework improves mean completion time across the matched simulation sweep, while its benefits vary by fleet size and arrival rate. Startup initialization improves early throughput and tail latency, but the evaluation remains bounded by simulation and limited comparator coverage.

  • Each online component has a positive mean contribution in the selected ablation cell, although local correction and structured replay effects are not additive.
  • Dijkstra has the lowest CT Mean in all three 100-OHT cells, while QNeuralDouble performs best in all 150- and 200-OHT cells.
  • The study uses one fab layout and simulator, omits physical validation and several external neural or multi-agent baselines, and fixes task dispatching.
  • Future work includes duration-aware discounting, potential-based shaping, and sensitivity analysis for reward weights and deadlock-warning thresholds.
  • 0.8%–8.8% lower CT Mean than tabular Double Q-routing across all nine settings.
  • Offline initialization raises tasks completed during the first 200 s by up to 23% and reduces startup tail latency by up to 15%.

APPENDIX A ADDITIONAL ANALYSES AND IMPLEMENTATION DETAILS

The appendix compares tabular and neural routing complexity and documents the feature representation used by the shared value network. Neural parameter growth is independent of destination, node, and edge counts, while decision-time cost depends on feasible next hops.

  • A. Complexity analysis: 2.59M independent tabular parameters arise from 608 destinations and 4257 directed edges in the evaluated guideway.Double Q-routing doubles this to around 5.18M entries.
  • A. Complexity analysis: 5825 neural parameters replace the table using a two-hidden-layer MLP with 24 input features and 64 hidden units.The parameter count is independent of |D|, |V|, and |E|.
  • A. Complexity analysis: O(k(dϕh + h2)) neural decision cost evaluates each of k feasible next hops, versus O(k) tabular lookups.Binary split nodes require at most two forward passes of about 5800 multiply-adds.
  • B. Full state and action feature definitions: The 10-dimensional state encodes normalized location, target, distance, degree, load/unload status, task phase, and recent waiting time.
  • B. Full state and action feature definitions: The 14-dimensional action vector represents candidate-hop identity, edge and remaining distances, progress, degrees, occupancy, and queue information.

C. Value-estimate stability of tabular vs. neural Q-routing

Value-estimate stability is assessed by snapshot standard deviations near convergence for tabular and neural routers. The reported figure indicates lower fluctuation for the shared neural estimates, while the configuration is fixed across the sweep.

  • σ(Q̂) measures fluctuations in value estimates near convergence using periodic final-window snapshots.
  • Fig. 7 shows higher tabular variation across most of the guideway and lower variation for the shared neural value function.The pattern is consistent with parameter sharing, but the figure measures stability rather than value accuracy.
  • The reported configuration is held fixed across the fleet-by-arrival-rate sweep.
  • Offline data combine three behavior policies and three seeds with equal sampling across operating cell, policy, and seed strata.
  • The reward combines realized-time penalties with local risk, route-progress, and warning terms, using separate movement, waiting, and blocking weights.
Loading 2608.30512v1…