1. Introduction
Unmanned surface vehicles (USVs) have attracted considerable interest as valuable tools for various maritime applications, including ocean surveillance, environmental monitoring, and search-and-rescue operations. USVs are being increasingly recognized as indispensable in modern marine exploration because of their ability to navigate autonomously and collect data even in hazardous environments. Coverage path planning (CPP), which aims to systematically and efficiently explore a designated region of interest (ROI), is one of the key technologies enabling the effective operation of USVs in such missions, ensuring complete coverage.
The coverage path planning problem has been studied extensively for many years, but several challenges remain, including addressing geometric characteristics of ROI, environmental factors, extending to multi-agent systems (Tan et al., 2021) and considering the dynamic characteristics of USVs. First, challenges related to the geometric characteristics of the ROI arise as its shape becomes more complex, requiring effective methodologies to achieve efficient coverage. Methodologies have been proposed to address these challenges by dividing a given region into small sub-regions for efficient coverage, particularly for areas with concave or irregular shapes rather than simple convex polygons (Li et al., 2011; Nielson et al., 2019; Mayilvaganam et al., 2022; Yang et al., 2023). Second, environmental factors also play a crucial role in determining the efficiency of coverage path planning, especially in maritime environments where currents, winds, and waves influence the motion of USVs. Zhao and Bai (2024) examined the effects of water currents on conventional back-and-forth coverage path planning strategies, showing that the optimal sweep direction for minimizing energy consumption is not necessarily aligned with the minimum width of the region. Third, collaborative challenges in multi-agent systems represent another emerging area of focus.
Efficient task allocation among multiple USVs is critical for minimizing the overall coverage time and ensuring effective cooperation. Recently, Luo and Su (2024) proposed an enhanced ant colony optimization (ACO) algorithm for task allocation and collision-free path generation in multi-USV systems. They also introduced a locking sweeping method (LSM) to estimate the path costs efficiently in obstacle-laden environments. Li et al. (2023) proposed a task allocation strategy for heterogeneous multi-agent search and rescue (SAR) missions, where different USVs are assigned tasks based on their search and rescue capabilities (SRC). Their method distributes the coverage workload by considering factors such as sensor capabilities, maneuverability, and cruising velocity. Deng et al. (2025) developed a UAV-USV collaborative water surface coverage and cleaning strategy, where UAVs conduct aerial inspections while USVs execute the physical collection tasks. They developed a dynamic task scheduling algorithm based on particle swarm optimization (PSO) to allocate cleaning tasks efficiently to USVs in real-time, minimizing the waiting time and improving the overall mission efficiency.
Finally, the dynamic characteristics of USV must be considered when performing coverage missions. In many cases, USVs are under-actuated systems that impose constraints on lateral (sway) motion. In addition, the minimum turning radius of the USV plays an important role in planning feasible paths because sharp turns can lead to impractical or inefficient trajectories. Guo et al. (2024) proposed an improved creeping line search method to handle these issues. This method smooths the connecting path segments of parallel paths with Bezier curves, considering the dynamic characteristics of USVs. Sudha et al. (2024) proposed a Dubins curves-based coverage path planning approach for environmental monitoring using a USV, where parallel coverage tracks are generated and joined with Dubins curves to ensure smooth and dynamically feasible paths.
The efficiency of coverage path planning can be enhanced significantly when multiple USVs collaborate in formation to carry out tasks. Formation control, a well-established field in multi-agent systems, enables USVs to move collectively while maintaining relative positions within the group. The advantages of formation control include improved operational efficiency, reduced mission time, and scalability for exploring larger areas. Applying formation control to coverage missions allows multiple agents to share exploration tasks, improving efficiency compared to single-agent operations. Several researchers have explored various types of uncrewed vehicles to address the challenges of integrating coverage path planning and formation control. For uncrewed ground vehicles (UGVs), Cao et al. (2019) proposed an optimal coverage path planning algorithm for tractor formations. Using a probabilistic roadmap (PRM), this study aimed to minimize path redundancy and overlapping coverage areas while maintaining efficiency in convex, non-convex, and regions containing obstacles. Similarly, Tran et al. (2023) developed a dynamic leader–follower formation control methodology for multi-UGV systems, enabling optimal coverage and obstacle avoidance under budget constraints in dynamic environments. In the context of uncrewed aerial vehicles (UAVs), Cao et al. (2022) used consensus-based formation control for coverage missions and developed a centralized algorithm that combined an improved PRM with an artificial potential field (APF) approach to achieve efficient path coverage. Muñoz et al. (2021) proposed a leader–follower triangular formation control method for UAVs. The method was designed to facilitate smooth coverage while avoiding obstacles in urban environments. Although these studies highlight the potential of formation control methodologies in coverage missions for multi-agent systems, they focused primarily on maintaining fixed formations or modifying various formations for obstacle avoidance. Furthermore, research specifically targeting formation control-based coverage missions using USVs is limited.
The objective of this study was to develop an optimal coverage path planning methodology combined with flexible formation tracking control for USVs. In terms of coverage path planning, previous studies have focused primarily on coverage with single-agent or multi-agents without explicitly considering formation control. This study adopted well-established coverage path planning techniques, such as convex decomposition and traveling salesman problem (TSP)-based optimization, and further integrates these techniques with formation control approaches. In addition, this study proposes a flexible formation control approach that dynamically adjusts formations based on the shape of the target region because fixed formation methods often lack the adaptability required to conform to the geometric characteristics of the target area, resulting in inefficient coverage. The proposed method significantly enhances the coverage efficiency and minimizes redundant coverage in complex environments by enabling formations to adapt dynamically. This paper is organized as follows. Section 2 describes the coverage path planning methodology and the flexible formation control techniques employed for USVs. Section 3 reports cooperative coverage simulations for various shapes of target areas and the coverage results to compare the performance of flexible and fixed formations. Finally, Section 4 presents the conclusions of this study and outlines the directions for future research.
2. Cooperative Coverage Methodology
The methodology proposed in this study is divided into two main components, as shown in Fig. 1. In coverage path planning, the boundaries of irregular terrains on the given map were approximated into polygonal shapes using the Douglas–Peucker algorithm to model the ROI. The ROI was then subdivided into optimal sub-regions. Subsequently, the optimal visiting order of these sub-regions was determined. Coverage paths were generated for each sub-region and combined to form the overall coverage path. The leader–follower structure was used in cooperative coverage using formation control. The leader follows the optimal coverage path, while the followers are controlled through leader–follower-based formation control to maintain the desired formation and effectively cover the given ROI. This integrated approach ensured systematic and efficient coverage of the target area.
2.1 Coverage Path Planning Methodology
2.1.1 Optimal decomposition of the ROI
In this study, the interior extension of edges (IEE) methodology proposed by Nielsen et al. (2019) was used to perform optimal decomposition. Fig. 2 shows the structure of the decomposition process. When a complex-shaped ROI was given, the concave vertices of the region were first identified, as shown in Fig. 2(a). These vertices were then extended from their adjacent edges, as shown in Fig. 2(b). This process resulted in an initial subdivision where sub-regions were generated. Nevertheless, the initial subdivision often produced an excessive number of sub-regions, necessitating a merging process to reduce redundancy, as shown in Fig. 2(c). Potential merging options were identified to address this by evaluating which initial sub-regions can be combined into convex shapes. Among these options, the optimal merging strategy was determined through integer optimization, which aimed to minimize the total width of the resulting sub-regions. This optimization was performed using the Branchand-Bound method combined with Cutting Plane techniques to ensure efficient and reliable solutions (Nemhauser and Wolsey, 1988). Fig. 2(d) shows the final optimized merging result.
2.1.2 Optimal visiting order for decomposed sub-regions
After dividing the ROI into convex sub-regions, the next step was to determine the optimal sequence for visiting these sub-regions. This problem was modeled as a TSP, where each sub-region was represented as a node in a graph, and the distance between nodes was defined by the distance between the centroids of the sub-regions. A genetic algorithm (GA) was used to solve this problem efficiently. The order crossover (OX) operator was used to preserve the order of elements when generating offspring because determining the sequence is crucial in the TSP. Therefore, this operator helped maintain the (a) Coverage path planning (b) Cooperative coverage using formation control properties required to find the optimal visiting sequence (Abdoun and Abouchabaka, 2012). In addition, the fitness function was defined as the total travel distance between sub-regions in a given visiting sequence. A swap mutation operator was also incorporated to introduce diversity into the population and avoid premature convergence. By applying this methodology, the GA effectively determined the optimal visiting sequence, minimizing the total travel distance between sub-regions and ensuring an efficient exploration of the entire target area.
2.1.3 Coverage path planning for sub-regions
For each convex sub-region, this study generated local coverage paths using a back-and-forth pattern, a traditional approach in coverage path planning. The path generation process involved the following steps, as shown in Fig. 3. First, the sub-region of ROI was defined, as shown in Fig. 3(a). Second, the pair of edges and vertices with the minimum width was identified within the given region to determine the most efficient sweep direction. The sweep direction (Fig. 3(b)) was defined as the direction perpendicular to the edge with the minimum width. This minimum width was used to minimize the number of turns required to cover the region because fewer turns lead to a more efficient coverage path (Li et al., 2011). Third, once the optimal sweep direction was determined, a series of parallel lines perpendicular to the sweep direction were constructed within the region, as shown in Fig. 3(c). These lines were spaced by the coverage width b of the USVs and used to generate intersection points that served as waypoints for the coverage path. When the width of the region was not an exact multiple of the coverage width, the interval between parallel lines was adjusted to ensure consistent spacing within the given region (Zhao et al., 2024). Finally, the generated waypoints were connected in a back-and-forth pattern to form the coverage path, as shown in Fig. 3(d). Efficient coverage was accomplished by spacing the parallel lines such that the waypoints were offset by half of the coverage width b/2 from the boundary of the ROI.
2.2 Formation Control Methodology for USVs
2.2.1 USV dynamics model & control methodology
The coordinate systems shown in Fig. 4 were used to model the dynamics of the USV. The motion of the USV was described with respect to two reference frames: the inertial coordinate system (O – X – Y ) and the body-fixed coordinate system (Ob – Xb – Yb). The inertial coordinate system, fixed to the Earth, was used to describe the global position of the USV, while the body-fixed coordinate system was attached to the geometric center of the USV and moved with it. The kinematic and dynamic models of the USV were formulated as follows (Fossen, 2011):
where η = [x,y,ψ]T represents the position and heading of the USV, while ν = [u,v,r]T denotes the velocity vector of the USV. R(ψ) is the standard rotation matrix. The matrix M represents the inertia matrix. C denotes the Coriolis–centripetal matrix, and D refers to the damping matrix. τ is the control input vector, representing the forces and moments generated by the USV. Finally, w is the external force vector representing environmental disturbances such as wind, waves, or currents.
In this study, a nonlinear model predictive control (NMPC) approach was adopted to control each USV, considering its nonlinear dynamic characteristics. Model predictive control (MPC) is a widely used control method that determines the optimal control inputs over a finite time horizon. Its ability to handle multivariable systems and incorporate various constraints into the optimization process makes it quite applicable to a wide range of systems, including USVs. A quadratic optimization objective function was formulated to ensure stable trajectory tracking, as shown in Eq. (3). The control inputs that minimize this function were calculated using the sequential quadratic programming (SQP) algorithm (Rawlings and Mayne, 2009; Nocedal and Wright, 2006).
where Θ = [X̃,ΔU] encapsulates the optimization variables. X̃ = X − Xdesired represents the state deviation from the desired value, and the term ΔU corresponds to the incremental change in the control inputs. P, Q, and R are positive-definite weight matrices. The parameters NP and NC represent the prediction horizon and control horizon, respectively, which define the time window over which the optimization is performed.
2.2.2 Flexible formation control algorithm
This paper proposes a flexible formation tracking control algorithm based on a leader–follower structure to adapt dynamically to the shape of the given coverage area for efficient coverage. The leader–follower structure consists of a leader and multiple followers, where the leader follows the given path, and the followers are controlled to maintain a predefined relative distance or position with respect to the leader. This structured arrangement is referred to as a formation. The state of the leader USV is denoted as η0 = [x0,y0,ψ0]T, and the state of the ith follower USV is denoted as ηi = [xi,yi,ψi]T, as shown in Fig. 5. The desired state of the ith follower USV is defined as
η i d = [ x i d , y i d , ψ i d ] T ψ i d
Fig. 6 describes the process of determining a flexible formation for efficient coverage. The waypoints Pk, define the given coverage path and the sweep direction of the path is represented by θs as shown in Fig. 6(a). Fig. 6(b) presents the schematics of the desired formation. The desired formation of ith follower USV is denoted as Li and is defined using the distance from the leader USV di and the formation slope αi, as follows:
At each waypoint, the slope of the edge Em, which is the edge most adjacent to the waypoint Pk, is defined as θEm. The slope of the formation of follower USV was set to align with θEm or θEm + π to effectively cover the given coverage region, depending on the followers’ position. When a new waypoint is reached and the formation is updated, the slope of the formation is determined to prevent the follower USVs from crossing each other’s paths during the formation transition. For example, Fig. 6(c) shows the case for the path point P4, where the closest edge is E1. In this case, the first follower USV aligns its formation slope α1 with θE1, while another follower USV, such as the second USV, aligns its slope α2 with θE1 + π. This adjustment ensures that the formation was dynamically aligned with the geometry of the coverage region while preventing the follower USVs from crossing paths, enabling efficient and collision-free coverage.
Furthermore, the distance of the formation di was determined to ensure that the individual coverage areas of the USVs did not overlap while achieving maximum coverage efficiency. The distance di was calculated to achieve this:
Fig. 6(d) presents this process, which shows how the formation distances are calculated to achieve efficient coverage.
In this study, the MPC controller for each follower USV used a predicted state of the leader to define the reference state. This process ensured a smooth transition of the desired positions of the follower USVs over the prediction horizon. In particular, the reference trajectory of follower i at time step k was calculated as follows:
where Li(k + j) is the formation vector incrementally updated according to
where δLi is an incremental change vector that prevents excessive or abrupt changes to the formation vector. In this study, δLi was defined by reflecting the characteristics of coverage path planning. For example, when transitioning the formation from l1 at waypoint P1 to l2 at waypoint P2, the following were set
where T(P1,P2) represents the time required to transition from waypoint P1 to waypoint P2, based on the search velocity Vs and the path distance d(P1, P2) between two waypoints. Incrementally updating the formation vector in this manner helps avoid sudden movements of USVs and ensures a smoother transition of the formation during coverage operations.
3. Results and Discussion
3.1 Cooperative Coverage Simulation for Various Polygonal-Shaped ROIs
The following section addresses the cooperative coverage simulation of USVs using the proposed flexible formation-tracking control method. For the coverage simulation of the USVs, the Cybership 2 (Skjetne et al., 2005) was used as the USV dynamics model. In this study, three USVs formed a straight-line formation, and each USV was assumed to have a circular coverage area, as shown in Fig. 7. The performance of the proposed flexible formation control method was evaluated by designing a fixed formation such that its slope aligns with the sweep direction θs of the coverage path. In the fixed formation control method, the formation remained unchanged while covering the given region unless the sweep direction θs changed.
The effectiveness of the proposed algorithm was validated by constructing cooperative coverage scenarios for various polygonal ROIs. Three scenarios were designed based on the complexity of the coverage path planning, as shown in Fig. 8. The first scenario involved a convex polygonal ROI, which was the simplest case because it did not require decomposition. The second and third scenarios consisted of concave polygonal ROIs, with the third scenario incorporating obstacle regions. These latter scenarios required decomposition, and the complexity of the decomposition process increased with the (a) Given coverage path (b) Desired formation (c) Formation adjustment (d) Determine formation distance addition of obstacle regions. Figs. 8 (a), (b), and (c) show the regions for Case 1 (convex polygon), Case 2 (concave polygon), and Case 3 (concave polygon with obstacle areas), respectively. Figs. 8 (d), (e), and (f) presented the resulting coverage paths generated for these regions. The coverage path for Case 1 in Fig. 8(d) showed a simple back-and-forth pattern because no decomposition is required for the convex polygonal ROI; thus, the computational time was minimal (0.41 s). In contrast, for Cases 2 and 3, the presence of concave vertices necessitated decomposition, which was performed through the optimal decomposition process described in Section 2.1. In Case 2, the initial decomposition yielded 16 sub-regions, generating 80 possible merge options. The optimal merging process reduced these sub-regions to 5, requiring a total computation time of 3.44 s. For the more complex polygonal ROI in Case 3, which included obstacle regions, the initial decomposition resulted in 24 sub-regions and 103 potential merge options. The optimal merging subsequently reduced the sub-regions to 7, and the increased complexity led to a total computational time of 5.44 s. These differences show that the number of initial sub-regions and associated merge options significantly affect the computational complexity. Although computational complexity increased with the complexity of the ROI, the measured computation times (ranging from approximately 0.4 s to 5.4 s) were reasonable, suggesting that the proposed CPP algorithm is suitable for practical applications. Cooperative coverage simulations were conducted using the generated coverage paths, utilizing formation control for multiple USVs to ensure efficient and effective coverage of the given regions.
Fig. 9 presents the results of the cooperative coverage simulation, where Figs. 9 (a), (b), and (c) show the results when USVs maintained a fixed formation during the coverage mission. Figs. 9 (d), (e), and (f) illustrate the results when a flexible formation was used. The green areas represent the regions of the ROI successfully covered by the USVs, while the red areas indicate unnecessary coverage outside the ROI. Maintaining a fixed formation resulted in a significant amount of unnecessary coverage areas outside the given ROI compared to the flexible formation approach, as shown in Fig. 9. In the fixed formation cases, such as the top-left region in Fig. 9(a), unintended exploration outside the ROI can be observed near its boundaries because the fixed formation does not reflect the geometric characteristics of the ROI. In addition, certain portions of the ROI near the boundaries, such as the middle-left region in Fig. 9(b), were insufficiently covered because of the limited adaptability of the fixed formation. In contrast, the flexible formation approach significantly reduced unnecessary coverage outside the ROI and sufficiently covered the regions near the boundaries, as shown in Figs. 9 (d), (e), and (f). The flexible approach ensured that the USVs remained within the given ROI throughout the coverage mission by dynamically adjusting the USV formation to match the boundaries of the ROI. Fig. 10 compares two distinct transition scenarios (transition cases 1 and 2) to illustrate the effectiveness of the proposed flexible formation method during waypoint transitions in Case 1. Each subfigure shows three different time intervals. In Figs. 10(a) and 10(b) (transition scenario 1), the fixed formation (a) causes the follower USVs to deviate outside the ROI boundary, whereas the flexible formation (b) keeps all USVs within the ROI by adapting to the geometry of the boundary. Similarly, Figs. 10(c) and 10(d) (transition scenario 2) confirmed a similar trend: the fixed formation (c) exhibited unnecessary coverage outside the ROI, while the flexible formation (d) effectively maintained coverage inside the boundary. These comparisons showed that the flexible approach significantly reduced the redundant coverage and ensured the trajectories of all USVs remained within the ROI.
The following three performance metrics (coverage rate, redundant coverage rate, and total travel distance ratio) were defined to compare coverage performance and quantitatively evaluate the coverage results:
(10)
where SROI represents the total area of the given ROI. Sc is the area successfully covered by the USVs. Sr denotes the unnecessary coverage area outside the ROI, and Stotal is the total area covered by the USVs during the coverage. In addition, Dtotal is the total travel distance of all USVs, NUSV is the number of USVs, and Dpath is the total coverage path length. Table 1 lists the results of the three performance metrics. Applying the proposed flexible formation control method reduced the redundant coverage rate by approximately 2–5% and increased the coverage rate by 1–2% in most cases, except for Case 1, as shown in Fig. 9. These results show that, compared to fixed formations, the flexible formation control method allows the USVs to cover the given ROI more effectively while minimizing the unnecessary coverage areas. The mission execution time was not included as a performance metric because both fixed and flexible formation methods use identical leader–follower algorithms, resulting in identical mission execution times determined primarily by the leader USV.
3.2 Cooperative Coverage Simulation for ROI Based on Real Marine Environments
This section considers cooperative coverage simulation scenarios for ROIs based on real marine environments. The ROIs were constructed using maps of actual maritime regions where USVs are expected to operate. The scenarios were developed based on the port area in Ulsan, South Korea (Case 4) and the surrounding region of the Dadohaehaesang National Park near Yeosu, South Korea (Case 5), as shown in Figs. 11 (a) and (d). The ROIs were modeled by approximating the irregular boundaries of the given terrain, as shown in Figs. 11 (b) and (e). The extracted ROIs were then processed using the proposed coverage path planning methodology, resulting in the coverage paths shown in Figs. 11 (c) and (f). The given ROIs based on realistic terrain maps were divided into more sub-regions compared to previous scenarios in section 3.1. The island-containing region in Case 5 (Fig. 11(b)) introduces additional complexity as the island is treated as an obstacle region, requiring a more extensive decomposition process. Specifically, the port region in Case 4 initially resulted in 33 sub-regions, generating 233 possible merge options, and was optimally merged into nine sub-regions, requiring a total computation time of 17.83 s. Similarly, the island-containing region in Case 5 initially yielded 36 sub-regions, producing 214 possible merge options, and was subsequently merged into eight optimal sub-regions, with a total computation time of 15.81 s. These increased computation times reflect the higher complexity arising from the larger number of initial sub-regions and corresponding merge options. Despite the complexity, the measured total computation times (~15–18 s) remain reasonable for practical applications, particularly for offline or pre-mission path planning. These calculated coverage paths were used to perform cooperative coverage simulations; Fig. 12 presents the results. Table 2 lists the quantitative results based on the three performance metrics defined in section 3.1. When the USVs followed the given coverage paths, all cases achieved a coverage rate of more than 97% for the given complex areas. Hence, the present coverage path planning methodology used in this study can effectively generate coverage paths even for complex ROIs based on real marine environments. Similar to the findings in Section 3.1, applying the proposed flexible formation control method reduced the redundant coverage rate by approximately 2–3% while slightly increasing the coverage rate by about 1%. Regarding the total travel distance ratio (Table 2), the fixed and flexible formation methods yielded similar values across all real marine environment scenarios, indicating no significant difference in total travel distance. These results confirmed that even in complex ROIs based on real marine environments, the proposed flexible formation control method outperformed the fixed formation method by minimizing unnecessary coverage areas and efficiently covering the given ROI without a significant increase in the total travel distance.
4. Conclusion
This study developed an optimal coverage path planning methodology utilizing flexible formation tracking control for multiple USVs. First, to effectively cover complex-shaped ROIs, the given areas were decomposed into multiple convex sub-regions and merged to minimize the total width, resulting in optimal sub-regions. A GA was then used to determine the optimal visiting sequence of the sub-regions, and coverage paths were generated in a back-and-forth pattern for each sub-region and then connected. Finally, a flexible formation tracking control algorithm was designed to enable multiple USVs to cover the designated areas. The effectiveness of the proposed methodology was validated through simulations of various types of polygonal ROIs, including convex, concave, regions containing obstacles, and regions based on real marine environments. All cases achieved a coverage completion rate of over 95% when they followed the generated coverage paths. In addition, compared to fixed formation control, the flexible formation control algorithm showed improved coverage completeness and reduced unnecessary coverage areas. The proposed coverage path planning methodology provided high coverage completeness for complex ROIs and enhanced the coverage efficiency through the application of the proposed flexible formation control algorithm. This study did not explicitly address certain practical assumptions, such as communication limitations, time delays, and other operational constraints inherent in real-world marine environments. Therefore, future research will focus on developing robust or adaptive controllers, including event-triggered control strategies to address various communication limitations and robust control methods for compensating time delays. Furthermore, environmental disturbances, such as wind, waves, and currents, will also be incorporated to ensure stable and efficient coverage path planning.
PDF Links
PubReader
ePub Link
Full text via DOI
Download Citation
Print
