Research on coverage path planning and iterative obstacle avoidance algorithm for deep-sea mining vehicles

Abstract

To address the challenges of full coverage path planning for deep-sea mining vehicles operating in complex benthic environments with variable terrain, this article proposes an iterative obstacle avoidance algorithm constrained by strict kinematics and safety margins. Moving beyond traditional planar assumptions, the operational space is modeled as a 2.5D environment where three-dimensional topographical features are systematically mapped into two-dimensional kinematic constraint costs. The algorithm employs an online perception and decision-making state machine based on the Boustrophedon strategy, utilizing a virtual boundary mechanism and analytical circular arc smoothing to resolve turning deadlocks in constrained spaces without resorting to computationally expensive global searches. Furthermore, to counteract chassis slip and gravity-induced drift inherent in traversing uneven seabeds, a closed-loop tracking system integrating a Terrain-Adaptive Extended Kalman Filter and Variable-weight Model Predictive Control is implemented. Extensive simulations on a realistic 1000m × 1000m seabed map demonstrate the superiority of the proposed method. Compared to advanced search-based baselines including Hybrid A* and Chaos A*, the proposed algorithm reduces the computational time by more than 42%, achieving a planning time of 24.09 s. While yielding a marginal reduction in the raw coverage ratio at 68.28%, statistical distribution analysis proves that the proposed method completely eliminates path generation within the extreme hazard zone, guaranteeing zero exposure to high-risk proximities. The results validate that the algorithm successfully balances highly efficient real-time computation with rigorous operational safety for deep-sea heavy equipment.

Keywords

Deep-sea mining vehicle coverage path planning iterative obstacle avoidance kinematic constraints path smoothing

Introduction

Deep-sea polymetallic nodules are critical strategic reserves, primarily distributed on seabed sediments thousands of meters deep. The operational efficiency of deep-sea mining vehicles relies directly on coverage path planning (CPP), which aims to maximize target area coverage with minimal overlap. Operating at depths below 6000m, these vehicles are virtually free from ocean currents and signal interference; however, they face severe unstructured terrain challenges, such as seamounts, trenches, and slopes. Furthermore, mining vehicles employ heavy tracked locomotion systems with significant inertia and strict minimum turning radius constraints. Traditional CPP algorithms must adequately account for these space terrain variations and kinematic limitations; otherwise, vehicles risk entering deadlocks in narrow spaces or excessively disturbing soft sediments due to frequent posture adjustments.

The CPP problem was first systematically defined by Choset et al.¹ and is currently widely applied in fields such as cleaning robots, agricultural harvesters, and autonomous underwater vehicles. Domestic and international scholars have proposed various classic planning algorithms for this problem. Boustrophedon cellular decomposition (BCD) is the most classic and widely used algorithm. This method decomposes free space into several monotone polygonal cells and employs reciprocating linear motion within each cell for coverage.^2–4 However, traditional BCD algorithms typically assume the environment is static and known, targeting simple geometric boundaries. When facing complex discrete obstacles within the environment, they often require complicated subregion connection strategies and struggle to directly handle the smooth turning problems of vehicles.^4,5 Addressing obstacle avoidance and path smoothing, grid-based wavefront propagation algorithms,⁶ Spanning Tree Coverage (STC) algorithms,⁷ and variants of the A* algorithm⁸ have been extensively proposed. Recently, chaos-inspired heuristics have further improved the exploration efficiency of A*-based methods. For instance, the Chaos A* algorithm has been applied to planar manipulators in known-obstacle environments,⁹ and the Lazy Chaos A* algorithm has been proposed for efficient path planning under semiknown exploration behaviors.¹⁰ Although these algorithms solve obstacle avoidance efficiently, the generated paths often consist of polylines. For vehicles with minimum turning radius limitations, such paths require postprocessing for smoothing, which often compromises the original obstacle avoidance safety.¹¹

In recent years, bio-inspired algorithms such as Genetic Algorithms,¹² Particle Swarm Optimization,¹³ and Neural Networks¹⁴ have also been introduced to the deep-sea mining field, primarily to solve path anti-entanglement, and global optimization problems in multivehicle cooperative operations. While these algorithms excel in global search capabilities, their real-time performance and computational efficiency often fail to meet engineering requirements when dealing with local microscopic geometric obstacle avoidance, particularly for emergency avoidance and U-turn planning of single vehicles in narrow spaces.¹⁵

In summary, while current research has made significant progress in handling kinematic constraints and three-dimensional (3D) environments, critical challenges remain for deep-sea mining applications, which motivates this study: (1) Many existing approaches either simplify the environment into a flat two-dimensional (2D) plane or process 3D volumetric data at a high computational cost. There is a lack of efficient mapping strategies that translate 3D seabed features (e.g. trenches and steep slopes) into 2.5D kinematic constraints for real-time local planning. (2) Although kinematic smoothing techniques exist, heavy equipment with strict minimum turning radii still frequently encounters planning deadlocks when negotiating irregular obstacles near workspace boundaries. (3) Algorithms typically output open-loop reference paths without considering terrain-induced posture disturbances inherent to deep-sea environments. A significant gap remains in integrating online planning with robust closed-loop control to guarantee that the generated paths are physically executable.

Addressing the aforementioned issues, this article proposes an iterative obstacle avoidance algorithm based on the Boustrophedon strategy, coupled with a robust closed-loop tracking framework. Specifically targeting the application scenario of deep-sea environments below 6000m—where ocean currents and signal interference are almost nonexistent but topographic variations are prominent—this study converts the 3D volumetric seabed into a 2.5D map. Large trenches and steep slopes are mapped as kinematic constraint costs on a 2D plane, while minor undulations are treated as posture disturbances. The main contributions of this study are highlighted as follows:(1) Proposed a terrain processing mechanism that efficiently decouples 3D seabed volumetric features into 2.5D kinematic constraints, successfully bridging the gap between ideal planar planning and real-world deep-sea terrain variability. (2) Designed an online iterative judgment algorithm utilizing “Virtual Boundary” and obstacle merging mechanisms, which effectively resolves planning deadlocks caused by strict minimum turning radius limitations in narrow boundary regions.(3) Developed a comprehensive closed-loop trajectory tracking module integrating a Terrain-Adaptive Extended Kalman Filter (TA-AEKF) and Variable-weight Model Predictive Control (V-MPC) to validate the real-time execution feasibility and kinematic safety of the planned paths under continuous terrain-induced disturbances.

The remainder of this article is organized as follows: chapter 2 details the proposed methodology, including the 2.5D terrain processing mechanism, the iterative obstacle avoidance planning algorithm with virtual boundaries, and the closed-loop tracking control framework based on TA-AEKF and V-MPC. Chapter 3 presents the comprehensive simulation results and performance analysis, validating the kinematic feasibility and control robustness of the proposed system in complex seabed environments. Finally, chapter 4 concludes the article and discusses directions for future work.

Algorithm design and closed-loop control framework

To ensure the safe and efficient operation of deep-sea mining vehicles in unstructured benthic environments, this article proposes a comprehensive, three-layered operational framework, as illustrated in Figure 1. The framework consists of: (1) a Perception & Pre-processing Layer that translates 3D seabed topographies into 2.5D kinematic constraints; (2) a Path Planning Layer that executes an iterative, nonholonomic coverage strategy using virtual boundaries to resolve spatial deadlocks; and (3) an Execution & Control Layer that ensures real-time trajectory tracking under severe terrain-induced disturbances. The detailed formulations of these modules are presented in the following subsections.

Figure 1.

Three-layered operational framework.

Deep-sea environment modeling and vehicle kinematics

2.5D seabed terrain mapping

Unlike ideal planar environments, the deep-sea benthic zone is characterized by unstructured 3D topographical features such as seamounts, trenches, and undulating sediments. To address the computational burden of planning directly in a 3D volumetric space while ensuring the safety of heavy-duty deep-sea mining vehicles, this study proposes a dimension-reduction mechanism. This mechanism systematically maps 3D terrain features into 2.5D kinematic constraints, forming a planar configuration space for real-time local planning.

Let the macroscopic deep-sea terrain be represented by a discrete 3D elevation map Z(x, y), where the base undulations are modeled using continuous Perlin noise to simulate natural seabed sediments, superimposed with localized Gaussian peaks and pits representing hazardous seamounts and trenches. For a vehicle navigating this environment, the primary threat is not the absolute depth, but the drastic changes in local elevation that could lead to chassis instability, severe slip, or rollover.

Therefore, the terrain gradient is continuously evaluated. The slope angle $θ_{s l o p e}$ at any grid coordinate (x, y) is calculated utilizing the bidirectional spatial gradients of the elevation map:

θ_{s l o p e} = \arctan (\sqrt{{(\frac{\partial Z}{\partial x})}^{2} + {(\frac{\partial Z}{\partial y})}^{2}})

(1)

To explicitly account for the climbing capability and kinematic safety limits of the tracked mining vehicle, a critical slope threshold $ω_{m a x}$ is defined. Based on the physical constraints of the vehicle, $ω_{m a x}$ is set to 5° in this study. The continuous slope map is then translated into a discrete kinematic cost map C(x, y). Regions where the slope exceeds the operational threshold ( $θ_{s l o p e} > ω_{m a x}$ ) are classified as absolute impassable obstacles ( $C = \infty$ ), while flatter regions remain traversable.

Furthermore, to guarantee that the planned paths do not graze the edges of these hazardous zones, the binarized obstacle map undergoes morphological dilation. The dilation radius r_dil is strictly determined by the vehicle's structural dimensions, specifically half of the vehicle's width (W_veh/2). This crucial transformation expands the physical boundaries of the topographical threats, thereby decoupling the complex 3D seabed features into a 2.5D planar representation. Consequently, path planning algorithms can operate highly efficiently on this 2.5D map, with the strict assurance that any collision-free path generated inherently satisfies the 3D topographical clearance requirements of the mining vehicle.

Kinematic model of the mining vehicle

Deep-sea mining vehicles are heavy-duty machines driven by continuous tracks, characterized by significant inertia, specific physical dimensions and non-omnidirectional constraints. To ensure that the generated paths are physically feasible, it is necessary to establish a kinematic model that integrates the vehicle's planar motion with three-dimensional terrain interference.

The vehicle is modeled as an oriented bounding box with a defined length L and width W. Its operational state at any given time t is defined by the vector $x = [x, y, ψ, β]^{T}$ , where (x, y) represents the coordinates of the vehicle's center of mass in the global frame, ψ the vehicle's heading angle (yaw), and $β$ the sideslip angle induced by terrain variations and track-soil interactions. The control input vector is $u = [v, ω]^{T}$ , comprising the commanded linear velocity and angular velocity.

When navigating the 2.5D seabed terrain discussed in the “2.5D Seabed Terrain Mapping” section, the local spatial gradients directly affect the vehicle's effective kinematics. Let the local terrain's roll angle be denoted as $ϕ$ and the pitch angle as $θ$ . The continuous-time kinematic equations incorporating these 3D terrain disturbances are established as follows:

\dot{x} = v \cos (θ) \cos (ψ + β)

(2)

\dot{y} = v \cos (θ) \sin (ψ + β)

(3)

\dot{ψ} = ω

(4)

In the above model, the effective forward velocity is strictly modulated by the terrain's pitch angle $\cos (θ)$ . Furthermore, the actual travel course deviates from the nominal heading angle ψ by the sideslip angle $β$ . This sideslip $β$ is a dynamic state continuously perturbed by gravity-induced drift components correlated with the local terrain's roll gradient $ϕ$ .

A critical operational limitation of the heavy tracked locomotion system is its inability to perform sharp pivots without excessively disturbing the soft benthic sediments. Therefore, the vehicle is subject to a strict minimum turning radius constraint, denoted as R_min. This nonholonomic constraint dictates that the path curvature $κ$ at any point s along the trajectory must satisfy:

| κ (s) | \leq κ_{m a x} = \frac{1}{R_{m i n}}

(5)

Equivalently, the control inputs are rigidly bounded by:

| ω | \leq \frac{v}{R_{m i n}}

(6)

By explicitly integrating the bounding box dimensions and the curvature constraint into the obstacle avoidance and path smoothing stages, the proposed algorithm ensures that the planned trajectories strictly adhere to the mechanical limitations of the mining vehicle. The complex terrain-induced posture disturbances mapped here will be further compensated for in the closed-loop tracking framework introduced in the “Closed-Loop Trajectory Tracking under Terrain Disturbances” section.

Iterative coverage path planning with kinematic constraints

Boustrophedon strategy and state machine

In ideal, obstacle-free areas, the deep-sea mining vehicle employs a classic Boustrophedon back-and-forth coverage strategy as its basic operating mode. As shown in Figure 2, this strategy achieves efficient traversal of the target area by alternately executing parallel straight-line scans (Straight Segment) and semicircular U-turn maneuvres (U-turn Segment). To strictly satisfy the incompleteness kinematic constraint of the minimum turning radius R_min defined earlier, the scanning row spacing between two adjacent parallel straight segments is precisely set to 2 R_min. This geometric design ensures that, upon reaching the operational boundary, the vehicle can smoothly transition to the next row via a standard continuous semicircular arc with curvature $κ_{m a x}$ , without the need for reversing or energy-intensive on-the-spot turning maneuvres, thereby minimizing the disturbance and shear damage caused by the tracks to fragile seabed sediments.

Figure 2.

Boustrophedon coverage algorithm.

However, the actual deep-sea environment is replete with various impassable terrain obstacles as described in the “2.5D Seabed Terrain Mapping” section. To maintain the safety and continuity of this coverage strategy in complex environments, this article models the mining vehicle's online path planning process as a finite state machine driven by local perception. The vehicle's operational behavior is strictly decoupled into three operational states: Straight, Detour, and U-turn. In the iterative execution sequence of the algorithm, the Straight state has the highest priority, aiming to drive the vehicle as far as possible toward the boundary to maximize the original coverage of a single pass; the system triggers the Detour state to perform a local deviation only when a potential collision threat is detected within the perception corridor ahead of the vehicle; the U-turn state serves as an inter-state transition mechanism, triggered not only when the vehicle approaches a physical boundary but also as a key means of breaking planning deadlocks when encountering complex obstacle topologies. The dynamic closed-loop switching logic of these three states constitutes the decision-making core of the iterative obstacle avoidance algorithm in this study.

Online deadlock resolution via virtual boundaries

To guarantee continuous coverage in complex benthic topologies, heavy mining vehicles with strict nonholonomic constraints must avoid planning deadlocks, which frequently occur when navigating narrow gaps or operating near workspace limits. The online decision-making process is formulated as a deterministic finite state machine consisting of three operational states: Straight, Detour, and U-turn. Instead of relying on computationally expensive global searches, the vehicle dynamically evaluates the feasibility of the path ahead and transitions between these states based on localized perception and kinematic safety margins. Straight movement is prioritized to maximize row coverage, while detours and U-turns are triggered strictly by localized collision threats or boundary proximity.

When multiple discrete obstacles are detected within the perception corridor, their respective detour trajectories may intersect, or avoiding one obstacle may inevitably lead to a collision with an adjacent one. To resolve such spatial conflicts, the algorithm employs a dynamic merging mechanism. If the required safety clearances of two obstacles, denoted by their bounding boxes O_i and O_j, overlap, they are mathematically fused into a unified bounding box O_new by extracting their extreme spatial coordinates. This operation guarantees that the subsequent detour planning is executed around a single, comprehensive geometric contour, thereby eliminating the risk of interobstacle entrapment.

Furthermore, severe deadlocks occur when obstacles are situated critically close to the operational boundaries, leaving insufficient space for a kinematically feasible U-turn. To address this, a virtual boundary mechanism is introduced to enforce a preemptive U-turn. The instantiation of a virtual boundary is triggered under two primary conditions: when the planned detour path intersects with the global map boundary (or its required U-turn space), or when executing a U-turn into the subsequent scanning row would immediately result in a collision with an obstacle situated in that new row. Upon detecting either conflict, the algorithm revokes the current detour judgment and constructs a virtual boundary $x_{v i r t u a l}$ at a safe distance from the conflict-causing obstacle $O_{c o n f l i c t}$ . The position of this virtual boundary is determined by the current travel direction and a predefined safety margin $Δ_{m a r g i n}$ . Specifically, $x_{v i r t u a l}$ is formulated as:

x_{v i r t u a l} = {\begin{matrix} x_{m i n}^{c o n f l i c t} - Δ_{m a r g i n}, & if moving left - to - right \\ x_{m a x}^{c o n f l i c t} + Δ_{m a r g i n}, & if moving right - to - left \end{matrix}

(7)

This rollback mechanism ensures the vehicle abandons the compromised scanning segment and safely transitions to the next row before entering any kinematic deadlock zone, regardless of its current heading or the source of the conflict.

The pseudocode implementing the above basic principles is as follows:

Detour path generation and analytical arc smoothing

To ensure the generated trajectories are physically executable for heavy-duty deep-sea mining vehicles, the planning algorithm must strictly adhere to the vehicle's nonholonomic kinematic limitations. Traditional grid-based or search-based algorithms frequently simplify the vehicle as a mass point, yielding jagged polyline paths. Executing such paths requires frequent on-the-spot pivots, which not only violate the mechanical minimum turning radius R_min constraint but also cause severe shear damage to fragile benthic sediments. Therefore, the proposed algorithm enforces a strict bound on the path curvature $κ (s)$ at any arc length s:

| κ (s) | \leq κ_{m a x} = \frac{1}{R_{m i n}}

(8)

The detour generation is formulated as a two-phase analytical process. Initially, a coarse polygonal detour is constructed based on the orthogonal safety distances required to clear the merged obstacle bounding box. Subsequently, a deterministic analytical arc smoothing algorithm is applied to replace the sharp corners with kinematically feasible tangent arcs, deliberately eliminating the need for computationally expensive iterative trajectory optimization.

Let h denote the vertical deviation distance of the detour segment. The analytical smoothing is systematically categorized into two distinct geometric scenarios:

Case 1: $h < 2 R_{m i n}$ . In scenarios with restricted lateral space, the detour is smoothed using two directly tangent arcs with equal radii R_min. For a detour extending above an obstacle, the central angle $θ$ of the tangent arcs is analytically derived from the spatial offset:

θ = \arccos (\frac{2 R_{m i n} - h}{2 R_{m i n}})

(9)

The centers of the respective arcs, O₁ and O₂, are explicitly determined such that the Euclidean distance between them satisfies $| | O_{2} O_{1} | | = 2 R_{m i n}$ . The resulting continuous trajectory seamlessly transitions from the straight scanning segment to the detour zone via these tangent curves, preserving strict continuity without exceeding curvature limits.

Case 2: $h \geq 2 R_{m i n}$ When the lateral deviation space is sufficiently broad, the smoothing is achieved by inserting straight intermediate segments between standard 90° arcs (each with radius R_min). Depending on the horizontal span of the obstacle, these intermediate segments either connect horizontally or incorporate additional vertical transitions, ensuring that the geometric path completely envelops the safety margin while maintaining the required turning radii (Figure 3).

Figure 3.

Circular arc smoothing algorithm.

By employing this deterministic geometric construction, the algorithm guarantees real-time computational efficiency with an O(1) time complexity. It outputs a rigorously safe, kinematically executable reference path, thereby laying a reliable foundation for the subsequent closed-loop tracking controller under terrain disturbances.

Closed-loop trajectory tracking under terrain disturbances

While the iterative planning layer successfully generates kinematically feasible and collision-free reference trajectories, executing these open-loop paths in a deep-sea benthic environment presents substantial control challenges. Heavy-duty tracked vehicles navigating unstructured 2.5D topographies continuously experience severe posture disturbances, including localized velocity attenuation due to pitch gradients and gravity-induced lateral drift caused by roll variations. Furthermore, practical underwater localization sensors are inherently subjected to significant environmental noise and measurement uncertainties. To guarantee that the planned trajectories are rigorously executable, a comprehensive closed-loop tracking framework is established. This system integrates a TA-AEKF for resilient vehicle state estimation and a V-MPC module to compute optimal, disturbance-rejecting steering commands.

Terrain-Adaptive Extended Kalman Filter

Standard state estimation techniques often assume simplified planar kinematics and constant noise distributions, rendering them inadequate for deep-sea vehicles subject to continuous 3D topographical interference. As established in the kinematic model, the vehicle's state vector is defined as $x = [x, y, ψ, β]^{T}$ , where the sideslip angle $β$ acts as a highly dynamic, unobservable variable heavily influenced by the localized terrain roll $ψ$ . To achieve robust localization, the proposed TA-AEKF dynamically fuses physics-informed kinematic predictions with online noise covariance adaptation.

During the prediction phase, the filter incorporates the localized spatial gradients directly into the vehicle dynamics. The sideslip angle $β$ is not merely modeled as a decaying state, but is actively predicted using a physics-informed steady-state estimation that synthesizes both gravity-induced drift and kinematic sliding components correlated with the terrain roll. To quantify the escalating unpredictability of the chassis traction on uneven sediment, the process noise covariance matrix $Q$ is formulated to be terrain-adaptive. Specifically, the process variance associated with the sideslip state is dynamically inflated as a function of the local roll gradient, defined as $q_{s l i p} \propto 1 + γ \tan^{2} (ϕ)$ , where $γ$ is a tuning coefficient. This spatial adaptation explicitly forces the Kalman gain to reduce its reliance on the ideal kinematic model when traversing perilous, highly tilted slopes.

Concurrently, the measurement noise covariance matrix $R_{k}$ , which essentially quantifies the positioning uncertainty caused by deep-sea acoustic multipath effects and transient signal attenuation, must also be dynamically calibrated. Instead of assuming a constant noise distribution, the TA-AEKF employs an online Sage-Husa fading memory estimator to prevent acoustic outliers from erroneously biasing the state estimation. Let $z$ represent the sensor measurements comprising only the observable states $[x_{o b s}, y_{o b s}, ψ_{o b s}]^{T}$ . The algorithm dynamically updates the measurement noise covariance matrix $R_{k}$ utilizing the statistical properties of the innovation sequence (the residual $y$ between the measurement and the predicted state). The adaptive update law is mathematically governed by:

R_{k} = (1 - b) R_{k - 1} + b (y_{k} y_{k}^{T} - H P_{k | k - 1} H^{T})

(10)

where b is the fading memory factor and

H

the observation matrix. By simultaneously modulating

Q

based on deterministic terrain geometry and

R

based on stochastic sensor residuals, the TA-AEKF successfully bridges the gap between the vehicle's nonlinear dynamics and the profound uncertainties of the benthic environment.

Variable-weight Model Predictive Control

The reference path generated in the planning layer, while kinematically feasible, requires a robust tracking controller to handle the high-inertia dynamics of the mining vehicle and the persistent external disturbances of the seabed. To achieve this, a V-MPC strategy is developed. Unlike conventional MPC which utilizes fixed penalty matrices, the V-MPC dynamically reshapes its cost function based on the local geometric characteristics of the path, ensuring a superior balance between tracking precision and control smoothness.

At each sampling interval, the tracking error model is discretized to predict the vehicle's future states over a finite prediction horizon N_p. The control objective is to minimize a quadratic cost function J, formulated as:

J = \sum_{i = 1}^{N_{p}} | | e (k + i | k) | |_{Q_{m}}^{2} + \sum_{i = 0}^{N_{c} - 1} | | Δ u (k + i | k) | |_{R_{m}}^{2} + ρ ε^{2}

(11)

where

e

represents the state tracking error,

Δ u

the control increment,

ρ ε^{2}

the soft constraint penalty, and

Q_{m}

and

R_{m}

the weighting matrices for the state error and control effort, respectively.

The core innovation of the V-MPC lies in the adaptive modulation of the weighting matrix $Q_{m}$ . In deep-sea coverage missions, the vehicle alternates between long straight segments and high-curvature detour arcs. On straight paths, the controller prioritizes heading stability and energy efficiency; however, during complex obstacle avoidance maneuvers, the priority must shift towards minimizing lateral deviation to avoid collisions. To implement this, the lateral error weight $q_{y}$ within $Q_{m}$ is defined as a function of the local reference curvature $κ$ :

q_{y} (κ) = q_{b a s e} (1 + η | κ |)

(12)

where

q_{b a s e}

is the nominal weight and

η

a sensitivity coefficient. When the vehicle encounters a detour arc, the weight on lateral error automatically increases, forcing the optimizer to penalize deviations more aggressively. Conversely, on straight segments (

κ = 0

), the weight relaxes to prevent unnecessary steering oscillations and reduce mechanical wear on the hydraulic tracks.

Furthermore, the V-MPC incorporates hard constraints on the control inputs (steering angle and velocity) and their rates of change to respect the physical limits of the vehicle's propulsion system. By solving this constrained optimization problem at each time step via quadratic programming, the V-MPC generates optimal steering commands that are inherently synchronized with the analytical smoothing logic of the planning layer. This synergy ensures that the vehicle maintains high-fidelity tracking performance even when navigating through narrow gaps or steep topographical gradients.

Matlab simulation and results analysis

To rigorously evaluate the feasibility and superiority of the proposed framework, extensive simulations were conducted within a synthesized deep-sea benthic environment. Moving beyond simplified planar assumptions, a high-fidelity 1000 m × 1000 m topography was generated. By integrating Perlin noise algorithms with Gaussian distribution functions, the simulation mathematically modeled the characteristic continuous undulations, steep seamounts, and trenches inherent to actual unstructured seabeds, as illustrated in Figure 4.

Figure 4.

Three-dimensional seabed map.

To ensure the physical validity and reproducibility of the experiments, the simulated deep-sea mining vehicle was configured with realistic geometric and kinematic constraints. The primary environmental configurations and vehicle parameters were detailed in Table 1. These parameters strictly reflected the physical limitations of heavy-duty deep-sea machinery, establishing a rigorously constrained foundation for the subsequent algorithm validation.

Table 1.

Kinematic parameters and environmental configurations.

Parameter	Symbol	Value
Vehicle length	L	12 m
Vehicle width	W	8 m
Minimum turning radius	R_min	15 m
Maximum operational velocity	v_max	1.0 m/s
Simulation map Dimension	$X_{m a x} \times Y_{m a x}$	1000 m × 1000 m
Safety margin threshold	$Δ_{m a r g i n}$	4 m

To benchmark the performance of the proposed framework, comparative simulations were conducted against two advanced search-based path planning methodologies frequently utilized in recent literature: Hybrid A* and Chaos A*. To ensure a rigorous and fair comparison, all three algorithms were constrained to the identical Boustrophedon macro-routing strategy. Consequently, any performance divergences were isolated exclusively to their localized obstacle avoidance mechanisms, boundary interactions, and the resultant closed-loop tracking execution.

As depicted in the 3D global trajectories (Figure 5) and the 2D localized projections (Figure 6), macroscopic observation indicated that all three algorithms successfully guided the vehicle through the complex terrain, achieving substantial area coverage. However, a critical examination of the localized detour behaviors and spatial reasoning revealed significant disparities in kinematic compliance and operational safety.

Figure 5.

Three-dimensional comprehensive trajectory comparison.

Figure 6.

Two-dimensional localized projections of the planned reference paths and actual closed-loop tracking trajectories.

In the 2D path visualizations shown in Figure 6, the solid red rectangular zones superimposed within the obstacle clusters represented the fused and inflated bounding boxes O_new. These zones delineated the absolute “no-go” regions, systematically calculated by expanding the raw spatial coordinates of the obstacles with the vehicle's geometric dimensions and the predefined safety margin $Δ_{m a r g i n}$ . When navigating around these highly constrained safety zones, the paths generated by Hybrid A* and Chaos A* exhibited rigid, fragmented, and geometrically unnatural detour patterns, which were inherent artifacts of grid-based spatial discretizations and heuristic node expansions. In contrast, the proposed algorithm utilized analytical arc smoothing to generate detours. This guaranteed strict C¹ continuity and inherently bounded the curvature within 1/R_min, allowing the physical vehicle's actual tracking trajectory (red line) to seamlessly and smoothly conform to the planned reference path (blue line).

More importantly, the fundamental discrepancy in spatial safety reasoning was starkly evident in the highly constrained and treacherous topographical region located in the bottom-right corner of the maps. As seen in the trajectories, both search-based A* variants forcefully attempted to explore and navigate through these narrow, high-risk gaps to maximize spatial coverage. For a heavy-duty mining vehicle, such aggressive exploration in severe benthic topologies significantly elevated the probability of kinematic deadlocks, severe sediment shear, and physical collisions. In stark contrast, the proposed algorithm inherently recognizes the insufficient operational space. Driven by the virtual boundary mechanism formulated in the “Online Deadlock Resolution via Virtual Boundaries” section, it preempted the potential deadlock by constructing a virtual wall and executing a safe, early U-turn rollback. This behavior definitively demonstrated that the proposed framework intelligently prioritized the absolute physical safety of the mining equipment over marginal, high-risk coverage gains.

To rigorously quantify these observations and directly address the comprehensive performance of the algorithms, a set of key performance indicators was evaluated, as summarized in Table 2.

Table 2.

Complete test results.

Algorithm	Obstacle density	Path length/m	Coverage ratio	Running time/s
Proposed method	3.22%	30,853.1	68.28%	24.090
Hybrid A*	3.22%	31,640.1	69.51%	41.790
Chaos A*	3.22%	30,901.3	69.17%	97.502

As detailed in Table 2, the proposed algorithm demonstrated a profound advantage in computational efficiency. By relying on analytical arc smoothing and deterministic state-machine decisions rather than exhaustive heuristic node searches, the proposed method reduced the planning running time to merely 24.09 s—achieving an efficiency improvement of over 42.3% compared to Hybrid A* and significantly outperforming Chaos A*. While the proposed algorithm yielded a marginally lower coverage ratio (68.28%) compared to the search-based alternatives, this statistical variance was not a deficiency but a deliberate and critical design tradeoff prioritizing operational safety, which was further elucidated through statistical distribution analysis.

To deeply evaluate the physical viability of the generated trajectories, Figure 7(a) illustrated the probability distribution of the vehicle's minimum distance to spatial obstacles during the entire mission. The vehicle's physical width demanded a strict 8m clearance. Alarmingly, the trajectories generated by Hybrid A* and Chaos A* exhibited a substantial probability density within the critical risk zone (<8 m). Their marginal gains in coverage ratio were fundamentally achieved by steering the vehicle dangerously close to obstacles, rendering them practically unusable for high-inertia deep-sea machinery. Conversely, the statistical distribution of the proposed algorithm was perfectly truncated at the safety threshold, strictly guaranteeing zero high-risk spatial exposure.Furthermore, Figure 7(b) profiled the terrain slopes traversed by the vehicle. The proposed algorithm inherently guided the vehicle along paths with milder gradients, actively avoiding steep topographical variations that could induce severe chassis slip or rollover.

Figure 7.

Statistical distributions evaluating the execution safety and tracking robustness.

Finally, Figure 7(c) presented the Absolute Cross-Track Error (CTE) distribution of the closed-loop tracking system. Aided by the continuous curvature of the analytical reference path and the adaptive optimization of the Variable-weight MPC, the overwhelming majority of the tracking errors were firmly constrained within an ultra-narrow margin (approaching 0 m). It is worth noting that the CTE distribution of the proposed algorithm exhibited a visible “long-tail” phenomenon. This tail corresponded to the transient kinematic deviations that occured when the heavy-duty vehicle simultaneously executed maximum-curvature detour arcs while traversing severe, localized seabed gradients. Under such extreme 3D topographical disturbances, sudden gravity-induced sideslip momentarily spiked before the V-MPC could fully compensate. However, rather than indicating a tracking failure, this long tail accurately reflected the realistic physical challenges of deep-sea environments. Crucially, the maximum extent of this error tail remained strictly bounded well within the predefined 4m safety margin. This definitively confirmed that the integrated TA-AEKF and V-MPC framework can robustly absorb and reject severe dynamic disturbances, ensuring that the theoretical safety boundaries planned in the kinematic layer are flawlessly and safely executed in the dynamic tracking layer.

Conclusion

This article presents a comprehensive Coverage Path Planning (CPP) and closed-loop tracking framework tailored for heavy-duty deep-sea mining vehicles operating in complex, unstructured benthic environments. To overcome the deficiencies of traditional planar algorithms in handling severe topographical variations, a dimension-reduction mechanism is introduced to systematically map 3D seabed features into 2.5D kinematic constraints. Furthermore, an online iterative decision-making algorithm incorporating virtual boundaries and analytical arc smoothing is proposed. This approach successfully resolves spatial deadlocks in constrained boundary regions while guaranteeing strict nonholonomic kinematic compliance. To ensure the physical executability of these trajectories under severe terrain-induced posture disturbances, a robust tracking system integrating a TA-AEKF and V-MPC is developed.

Extensive simulations conducted on a high-fidelity 1000 m × 1000 m topographical map definitively validate the superiority of the proposed framework. Quantitative comparisons demonstrate that the proposed algorithm achieves a total planning running time of merely 24.09 s, representing a computational efficiency improvement of over 42% compared to the advanced Hybrid A* baseline. More crucially, statistical analysis proves that the proposed method systematically eliminates path generation within the extreme hazard zone (< 8 m spatial clearance), achieving zero high-risk physical exposure. Concurrently, the integrated TA-AEKF and V-MPC controller effectively absorbs transient, gravity-induced sideslips, tightly constraining the dynamic cross-track errors within the designated safety margins and demonstrating profound robustness against complex seabed terrain variability.

Despite these theoretical and simulational advancements, certain limitations remain regarding the transition to physical deep-sea deployments. The current framework models environmental uncertainty and positioning noise under bounded stochastic assumptions; however, practical deep-sea operations face profound sensor limitations, such as severe acoustic multipath fading and optical backscatter in turbid waters. Additionally, highly nonlinear track-soil interactions, including dynamic chassis subsidence in soft benthic sediments, require further empirical investigation. Therefore, future work focuses on deploying the proposed algorithms onto physical underwater vehicle prototypes to rigorously validate the real-time implementation feasibility in real-world aquatic environments. Furthermore, by intergrating Doppler velocity log (DVL), ultra-short baseline, and inertial navigation system, research is directed toward developing tightly-coupled multi-sensor fusion frameworks to enhance perception resilience and tracking accuracy under extreme deep-sea uncertainty.

Footnotes

Acknowledgements

The authors would like to thank the technical staff and colleagues for their valuable suggestions on the simulation environment setup and their support during the early stages of algorithm verification. We also express our gratitude to the reviewers for their constructive comments that helped improve the quality of this article.

ORCID iD

Zhiying Wei

Ethical considerations

This study involves numerical simulations and robotic path planning algorithms based on theoretical models; it does not involve human participants, human data, human tissue, or animal experiments. Therefore, ethical approval was not required.

Funding

The authors received no financial support for the research, authorship, and/or publication of this article.

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Data availability statement

The simulation data supporting the findings of this study are available from the corresponding author upon reasonable request. However, the source code of the proposed algorithm is not publicly available due to project confidentiality restrictions and the proprietary nature of the research.

References

Choset

Pignon

. Coverage path planning: the boustrophedon cellular decomposition. In: Alexander

Zelinsky

(ed.) Field and service robotics. London: Springer, 1998, pp.203–209.

Gong

Kim

Lee

. Resilient multi-robot coverage path redistribution using boustrophedon decomposition for environmental monitoring. Sensors (Basel, Switzerland) 2024; 24: 7482.

Sun

Gao

. Complete coverage path planning based on improved area division. World J Eng Technol 2023; 11: 965–975.

Tan

Mohd-Mokhtar

Arshad

. A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms. IEEE Access 2021; 9: 119310–119342.

Yang

, et al. Coverage path planning based on region segmentation and path orientation optimization. Agriculture 2025; 15: 1479.

Zhang

. Mobile robot path planning based on a generalized wavefront algorithm. Math Probl Eng 2020; 2020: 6798798.

Jayalakshmi

Nair

Sathish

. MRSimEx-DSTC: a dynamic spanning tree coverage approach for multi-robot exploration and coverage path planning. IEEE Access 2025; 13: 163085–163102.

, et al. Robot obstacle avoidance optimization by A* and DWA fusion algorithm. PLoS ONE 2024; 19: e0302026.

Muhammed

Flaieh

Humaidi

. Embedded system design of path planning for planar manipulator based on chaos A* algorithm with known-obstacle environment. J Eng Sci Technol 2022; 17: 4047–4064.

10.

Flaieh

Humaidi

. Lazy Chaos A*: a novel chaos-inspired algorithm for efficient 3R robot arm path planning based on semi-known exploration behavior. Proc Inst Mech Eng C J Mech Eng Sci 2025; 240: 09544062261416796.

11.

Liu

, et al. High-fidelity and curvature-continuous path smoothing with quadratic Bézier curve. IEEE Trans Intell Veh 2024; 9: 3796–3810.

12.

Debnath

, et al. An integrated geometric obstacle avoidance and genetic algorithm TSP model for UAV path planning. Drones 2024; 8: 302.

13.

, et al. Global path planning method based on improved particle swarm optimization algorithm. In: 2025 IEEE 6th International Seminar on Artificial Intelligence, Networking and Information Technology (AINIT), 2025. IEEE.

14.

Xing

Wang

Liu

. An algorithm of complete coverage path planning for deep-sea mining vehicle clusters based on reinforcement learning. Adv Theor Simul 2024; 7: 2300970.

15.

Kojima

, et al. Real-time model predictive control of vehicles with convex-polygon-aware collision avoidance in tight spaces. arXiv preprint arXiv:2505.04935 (2025).