MadDE-NDA: Collision-Free Time-Optimal Planning of Underwater Gliders in Time-Varying Currents via Adaptive Niching Dual-Archive Differential Evolution

This project presents a state-of-the-art GPU-accelerated 4D path planning framework designed for Autonomous Underwater Gliders (AUGs) operating in complex, time-varying ocean environments. To overcome the curse of dimensionality and the spatiotemporal causal chain in long-range missions, we propose a fixed-dimensional B-spline trajectory encoding combined with a novel evolutionary optimizer, MadDE-NDA (Niching Dual-Archive Differential Evolution). By leveraging massive GPU parallelism, the framework rigorously evaluates dynamic feasibility and continuous-domain collision safety in seconds.

Key Features

• 📉 Fixed-Dimensional B-Spline Encoding: Transforms the traditional variable-length, profile-wise routing problem into a compact, fixed-dimensional search space using B-spline control points in a local coordinate system, significantly improving optimization efficiency for long-endurance missions.
• 🧬 Adaptive Niching Dual-Archive Evolution (MadDE-NDA): Introduces dual cooperative archives for quality retention and diversity preservation, coupled with a stagnation-triggered niching scheme. This prevents premature convergence and robustly explores highly multimodal route corridors induced by complex terrain and currents.
• 🛡️ Strict Continuous 3D Obstacle Avoidance: Utilizes a Euclidean Signed Distance Field (ESDF) combined with adaptive Sphere Tracing (Ray Marching). This completely eliminates the “tunneling effect” of traditional discrete sampling, ensuring absolute safety against high-resolution GEBCO seabed topography.
• 🚀 GPU-Accelerated 4D Dynamic Verification: Employs parallel 4th-order Runge-Kutta (RK4) integration on the GPU to strictly evaluate time-varying kinematics using 4D CMEMS ocean data. The population-level parallel architecture reduces evaluation time by orders of magnitude (up to 18.6× speedup), making time-optimal planning computationally tractable.

Research Motivation

The central idea of this work is to make long-range underwater glider planning simultaneously compact, physically executable, collision-safe, and computationally tractable. Unlike short-range geometric path planning, a practical underwater glider mission is a 4D planning problem: the vehicle moves in 3D space while the ocean current changes over time. Therefore, the final route must not only be short or smooth, but also reachable under current disturbances and safe with respect to real seabed terrain.

Main challenges of DE-based long-range underwater glider 4D path planning, including variable-length decision variables, spatiotemporal causal coupling, and missed collisions under sparse fixed-step checking.

End-to-End Framework

The framework can be understood as a closed-loop optimization-and-verification pipeline:

GEBCO bathymetry + CMEMS currents → ESDF construction → B-spline encoding → Chord-length waypoint decoding → RK4 dynamic verification → ESDF sphere tracing → GPU fitness evaluation → MadDE-NDA optimization → collision-free time-optimal route

In each generation, candidate decision vectors define B-spline control-point offsets. These offsets are decoded into horizontal waypoints and reconstructed into 3D dive-climb profiles. The GPU backend then evaluates travel time, reachability, and collision penalties for the whole population. The resulting fitness values guide MadDE-NDA to update the population, archives, mutation probabilities, and archive-source sampling probabilities.

Problem Definition

Given a start point, a goal point, a prescribed dive depth, a fixed pitch angle, real seabed topography, and time-varying ocean currents, the planner searches for a route that minimizes total travel time while satisfying three types of constraints:

• Terminal reachability: the glider should arrive within the target region after executing a sequence of dive-climb cycles.
• Dynamic feasibility: for each segment, the horizontal velocity of the glider must be able to compensate the cross-current component and maintain the desired ground-track direction.
• Collision safety: the reconstructed 3D trajectory must remain outside the seabed obstacle region with a prescribed safety margin.

This formulation makes the task more demanding than ordinary 2D shortest-path planning, because the quality of a route depends on the arrival time at each segment, the local current encountered at that time, and the terrain clearance along the full 3D profile.

B-Spline Trajectory Encoding

MadDE-NDA does not directly optimize hundreds of heading commands. Instead, it represents the horizontal route using a cubic B-spline curve in a local coordinate system aligned with the start-goal direction. The longitudinal coordinates of the intermediate control points are fixed along the start-goal line, and only their lateral offsets are optimized. This design has two practical benefits:

• The decision dimension remains fixed and small even for long missions.
• The generated trajectory naturally progresses from the start region to the goal region, reducing unnecessary backtracking and detours.

After optimization, the continuous B-spline curve is decoded into waypoints using chord-length sampling. The chord interval is chosen according to the horizontal distance traveled in one dive-climb cycle, which links the optimized geometric path to the glider’s executable profile-level motion.

B-spline-based trajectory representation. Panel (a) should show fixed start/goal points and optimizable lateral control-point offsets; panel (b) should show chord-length waypoint decoding for dive-climb execution.

Dynamic Feasibility Verification

Because ocean currents are time-varying, the trajectory evaluation is sequential by nature. The arrival time and terminal position of one glide profile determine the current field encountered at the next profile. MadDE-NDA therefore verifies each candidate route through forward numerical simulation rather than treating segments as independent geometric edges.

For each decoded path segment, the planner performs RK4-based forward integration under the local current field. At each integration step, the cross-current component is checked against the glider’s horizontal velocity capability. If the glider cannot compensate the cross-current and maintain the desired direction, the segment is marked infeasible and penalized. This ensures that the final route is not only geometrically valid, but also physically executable under time-varying currents.

Geometric reachability analysis under ocean currents, including feasible, boundary-feasible, and infeasible cases depending on the cross-current magnitude.

Continuous-Domain Collision Checking

To improve safety over complex seabed terrain, the planner constructs a 3D Euclidean Signed Distance Field (ESDF) from GEBCO bathymetry. The ESDF provides signed distance queries: positive values indicate free space, whereas negative values indicate penetration into the seabed. Based on this representation, sphere tracing is used to check each descent/ascent segment of the reconstructed sawtooth trajectory.

Compared with fixed-step sampling, sphere tracing adaptively adjusts the checking step according to the local distance to obstacles. It can move quickly in open water and become conservative near seabed structures. This mechanism provides a better safety-efficiency balance for high-frequency population-level collision checking.

Comparison between ESDF-based sphere tracing and fixed-step sampling. The figure should emphasize that sparse uniform checks may skip collisions, whereas sphere tracing adapts its step size based on signed distance.

MadDE-NDA Optimizer

MadDE-NDA is developed on top of the original MadDE framework. The motivation is that underwater glider routing is often multimodal: several feasible route corridors may exist, and a population may converge prematurely to a locally feasible but globally inferior corridor. MadDE-NDA introduces three route-planning-oriented mechanisms:

GPU-Accelerated Population-Level Evaluation

The most expensive part of the planner is fitness evaluation: every candidate route must be reconstructed, dynamically integrated, checked for reachability, and verified for collision safety. To make this tractable, the framework offloads the evaluation stage to the GPU. The CPU manages evolutionary operations and population updates, while the GPU performs batched RK4 integration and ESDF-based sphere tracing for many candidate trajectories in parallel.

This design is especially suitable for evolutionary planning because each candidate solution can be evaluated independently at the population level, even though the profile sequence inside each candidate remains temporally coupled. In practice, the GPU backend substantially reduces the wall-clock cost of repeated fitness evaluations and makes long-range 4D underwater glider planning practical.

CPU-GPU division of labor. The CPU runs the DE loop and transfers decoded trajectory descriptors, while the GPU returns travel time, feasibility flags, and collision penalties after parallel evaluation.

Experimental Evidence

The experiments are designed to answer four practical questions: Can the planner find feasible routes? Does MadDE-NDA improve the MadDE backbone? Are the generated routes physically plausible? Is the GPU/ESDF implementation efficient enough for repeated population evaluation?

Simulation cases

Five real-world planning cases are constructed from GEBCO bathymetry and CMEMS current data in the northern South China Sea and adjacent Philippine Sea. The cases cover different mission lengths, dive depths, safety margins, and terrain-current conditions.

Geographical overview of the five planning regions, with square markers for starts and star markers for goals.

Compared algorithms and metrics

MadDE-NDA is compared with six representative DE variants: JADE, L-SHADE, SaDE, IMODE, MadDE, and NL-SHADE-LBC. All methods use the same B-spline decision representation, search bounds, and GPU-based fitness evaluation backend. Each algorithm is independently run 31 times on each case with a common budget of 25,000 fitness evaluations.

The comparison reports four groups of metrics:

• Success rate: whether a feasible route reaches the goal region under the prescribed constraints.
• Fitness: the composite optimization objective, including travel time and constraint penalties.
• Travel time: the mission-oriented physical objective measured in hours.
• Runtime: the wall-clock cost of optimization under the same evaluation backend.

Main quantitative findings

• Robust feasibility: MadDE-NDA obtains a success rate of 1.0 in all five cases, including the difficult Case 5 where several competing methods show reduced success rates.
• Overall fitness advantage: MadDE-NDA achieves the best average fitness in four of the five cases. The only exception is Case 3, where the proposed NDA mechanism still substantially improves the original MadDE backbone.
• Statistical ranking: Over all 5 × 31 = 155 matched runs, MadDE-NDA obtains the best Friedman average rank (2.9710). Under the Bonferroni-Dunn post-hoc test, it significantly outperforms JADE, L-SHADE, SaDE, IMODE, and NL-SHADE-LBC.
• Time-optimal benefit over MadDE: A supplementary paired Wilcoxon signed-rank test on travel time gives p = 7.58 × 10^-9. MadDE-NDA achieves shorter travel time than MadDE in 105 / 155 matched blocks, supporting the advantage of the proposed niching dual-archive design on the core time-optimal objective.
• Stable route quality: In representative visualizations, MadDE-NDA tends to generate smoother and less tortuous routes while maintaining clear terrain clearance.

Average fitness values of different algorithms over the five simulation cases.

Critical-difference diagram showing the average rank of each DE variant over 155 matched blocks.

Physical trajectory visualization

The 3D trajectory results show that the optimized routes are not merely abstract 2D curves. They are reconstructed into repeated dive-climb profiles over real bathymetric surfaces. Across the five cases, the trajectories remain collision-free and keep clear separation from high-relief seabed structures, demonstrating that the framework can integrate trajectory smoothness, current-aware reachability, and terrain safety into a unified planning result.

3D visualization of the representative median-fitness MadDE-NDA trajectories over the corresponding GEBCO seabed terrains.

Visual Results

Efficiency analysis

Two efficiency studies are included. First, the GPU backend is compared with a CPU-only backend for batch fitness evaluation. The steady-state GPU speedup ranges from approximately 4.7× to 18.65×, confirming that GPU acceleration is highly beneficial for repeated population-level evaluation. Second, the ESDF sphere-tracing checker is compared with dense and sparse fixed-step sampling. The results demonstrate that sphere tracing provides an efficient adaptive checking strategy while avoiding the missed-collision risk of sparse sampling.

GPU-versus-CPU benchmark showing mean batch-evaluation time and speedup across the five cases.

Comparison of dense fixed-step sampling, sparse fixed-step sampling, and ESDF-based sphere tracing in terms of checking time and ESDF query count.

What the Visual Results Show

The videos above provide dynamic views of the final planned routes. The 2D videos show the horizontal route evolution over the ocean-current background, while the 3D videos show the reconstructed dive-climb trajectory relative to seabed topography. Together, they demonstrate three core properties of the proposed method:

1. Current-aware routing: the route is shaped by the time-varying ocean environment rather than simply following the shortest geometric line.
2. Terrain-aware safety: the 3D trajectory avoids bathymetric obstacles and maintains safety margins.
3. Executable glider motion: the planned path can be reconstructed into repeated dive-climb profiles, matching the operational pattern of underwater gliders.

Status

This work is currently under review at Ocean Engineering. Data and Code will be made available on reasonable request.

BibTeX

If you find our work helpful, please consider citing it:

@article{li2026collision,
      title={Collision-Free Path Planning for Underwater Gliders in Time-Varying Currents via Dual-Archive Niching Differential Evolution}, 
      author={Li, Zezhong and Juan, Rongshun and Li, Yang and Liu, Shoufu and Wang, Tianshu and Shi, Shuaikun and Du, Leihao and Feng, Wanjun and Gao, Zhongke},
      journal={Ocean Engineering},
      year={2026}
}