cs.RONov 9, 2026

Graph-Based RL for Sequential Rendezvous Planning with Multiple Patrolling USVs

Authors: Seung Woo Han, Hyeon Bin Yeo, Seung Heon Oh

Organizations: Naval Future Innovation Research Group, ROK Navy, Republic of Korea · Seoul National University, Seoul, Republic of Korea · Inha University, Incheon, Republic of Korea

Abstract

In patrol missions involving multiple unmanned surface vehicles (USVs), a designated command USV can support fleet management by sequentially rendezvousing with each patrolling USV. These operations require motion-feasible route planning and priority-aware rendezvous sequencing, with the objective of minimizing mission completion time and total tardiness relative to priority-dependent due dates. We propose a framework combining grid-based path planning, surrogate travel-time prediction, and graph-based reinforcement learning. The path planner accounts for ocean currents and approximates turn-rate constraints through multi-stage maneuvers, with path feasibility empirically validated through trajectory-tracking simulations. For rendezvous sequencing, a Feasible Transition Graph (FTG) represents candidate rendezvous events and temporally feasible transitions, enabling a graph neural network to exploit spatiotemporal rendezvous relationships for policy learning. A surrogate predicts travel times from compact current and motion features to avoid repeated path searches during FTG construction and policy training. Evaluation using grid-based path planning shows statistically significant average objective reductions of 10.5%, 3.5%, and 1.5% compared with greedy, MLP-RL, and 2-step lookahead greedy, respectively. The policy achieves these improvements while requiring approximately 1/35 of the latter's computation time. It maintains its advantage over MLP-RL under unseen priority-tier settings, with larger gains as fleet size increases.

Explore similar work

CardsList
  1. Path planning for unmanned naval surface vehicles

    Jul 2, 2026Daniel G. Schwartzunmanned surface vehicle navigationRobot Navigation

  2. Towards Reliable Aerial Ground Vehicle Collaboration: An Integrated Planning and Autonomy Framework for Field Deployment

    Jul 7, 2026Md Safwan Mondal, Luca Russo, James D. Humann +2Vehicle RoutingMulti-Robot Coordination