US-20260126801-A1 - SYSTEM AND METHOD FOR GENERATING A COVERAGE PATH PLANNING FOR AUTONOMOUS UNDERWATER VEHICLES

US20260126801A1US 20260126801 A1US20260126801 A1US 20260126801A1US-20260126801-A1

Abstract

The invention relates to a method for generating a coverage path planning (CPP) for Autonomous underwater vehicles (AUVs) with nadir gaps. The method includes (i) receiving an area of interest, a count of the AUVs, a respective starting point of the AUVs, and an operational constraint from a user through a user device, (ii) generating a path with a nadir gap based on the area of interest using a pair of lines method, (iii) determining a path planning method from one or more path planning methods based on an operational priority and the starting point of the AUVs, and (iv) dividing the path into a plurality of segments by applying the determined path planning method on the path based on the starting point of the AUVs, thereby each segment is assigned to each AUV.

Inventors

Kamalakar Karlapalem
Charu Sharma
Nikhil Chandak

Assignees

INTERNATIONAL INSTITUTE OF INFORMATION TECHNOLOGY, HYDERABAD

Dates

Publication Date: 20260507
Application Date: 20250813
Priority Date: 20241105

Claims (13)

1 . A processor-implemented method for generating a coverage path planning (CPP) for a plurality of Autonomous underwater vehicles (AUVs) with nadir gaps, wherein the method comprises: receiving input from a user through a user device that is communicatively connected to the central server through a network, wherein the input comprises an area of interest, a count of the plurality of AUVs, a respective starting point of the plurality of AUVs, and an operational constraint; generating, using a pair of lines method, a path with a nadir gap based on the area of interest, wherein the path comprises a plurality of waypoints on a two-dimensional (2D) plane; determining a path planning method from a plurality of path planning methods based on an operational priority and the starting point of the plurality of AUVs; generating the CPP for the plurality of AUVs by dividing the path into a plurality of segments by applying the determined path planning method on the path based on the starting point of the plurality of AUVs, thereby each segment is assigned to each AUV; and transmitting the generated CPP to the plurality of AUVs that are communicatively connected to the central server through the network.
2 . The processor-implemented method of claim 1 , wherein the operational constraint comprises minimizing a maximum distance travelled by at least one of the plurality of AUVs or minimizing a total number of turns executed by any one of the plurality of AUVs.
3 . The processor-implemented method of claim 1 , wherein the plurality of path planning methods comprises a partition zigzag method and a turn-aware zigzag method.
4 . The processor-implemented method of claim 3 , wherein the partition zigzag method iteratively assigns the segments of the path P to each AUV by, (i) identifying a first highest index j 1 ≤L for a first AUV when a total distance travelled by the first AUV from a first starting point S 1 to first waypoint P 1 , traversing intermediate waypoints, and returning to the first starting point S 1 is less than or equal to a threshold distance (x) S 1 is ≤x, wherein the first highest index is a second starting point, wherein the highest index for the AUV is the furthest point in its path that the AUV reaches before returning to its starting point; (ii) identifying a second highest index for a second AUV when a total distance travelled by the second AUV from the second starting point and returning to the second starting point is less than or equal to the threshold distance; (iii) repeating the process for each subsequent AUV, determining the highest index j i for each AUV i starting from j i−1 , such that the AUV travels at most distance or the threshold distance x before returning to its starting position S i ; (iv) maintaining a running sum of distances at each waypoint to enable efficient computation of partitioning indices; (v) applying a boolean step function on the path obtained from the pair of lines method, to evaluate whether a sum of the distances travelled by the plurality of AUVs, based on the highest indices j 1 ,j 2 , . . . ,j N identified for each AUV, is equal to the total distance of the path generated for the plurality of AUVs; (vi) assigning the highest indices to the corresponding AUVs if the sum of the distance travelled by the plurality of AUVs is equal to the total distance of the path, wherein the Boolean step function f(x) determines whether the path P can be divided into N parts such that each AUV travels the threshold distance from and returning to its deployment location; and (vii) iteratively assigning waypoints to each AUV using (a) an initial index j 0 =1 for the first AUV; (b) computing distance constraints to determine j i for each AUV i; (c) verifying whether all waypoints are covered using the function f(x).
5 . The processor-implemented method of claim 4 , wherein the partition zigzag method comprises (i) performing a binary search on the boolean step function f(x) to obtain an optimal threshold distance if the sum of the highest indices identified for the plurality of AUVs is not equal to the total distance of the path generated using the pair of lines method, wherein the method performs the binary search on the f(x) to determine the minimum value of x* for which the path can be partitioned into N part; (ii) executing f(x*) to compute partition indices j i and assigning final path segments to each AUV using the computed indices P i =[S i ,P j i-1 ,P j t-1 +1 ,p j i-1 +2 , . . . ,p j i ,S i ], wherein each AUV travels from its starting point S i to the waypoints p j i-1 ,p j i-1 +1 ,p j i-1 +2 , . . . ,p j i , and returns to S i .
6 . The processor-implemented method of claim 5 , wherein the partition zigzag method comprises executing the boolean step function as binary search for finding the optimal threshold distance to compute optimal indices for each of the plurality of AUVs to assign respective segments to each AUV.
7 . The processor-implemented of claim 3 , wherein the turn-aware zigzag method iteratively assigns the segments of the path P to each AUV by, identifying a first highest index j i corresponding to a turning point p j i in the path P for a first AUV when a total distance travelled by the first AUV from a first starting point S i and returning to the first starting point S i is less than or equal to a threshold distance (x), wherein the first highest index is a second starting point, wherein the highest index for the AUV is a point reached by the AUV before turning to a different direction, wherein the highest index is identified by defining the function f(x) that accounts for turns in AUV trajectories; identifying a second highest index j i +1 corresponding to a turning point p j i +1 in the path P for a second AUV when the total distance travelled by the second AUV from the second starting point and returning to the second starting point is less than or equal to the threshold distance; applying a boolean step function on the path obtained from the pair of lines method, to evaluate whether a sum of the distances travelled by the plurality of AUVs, based on the highest indices j 1 ,j 2 , . . . ,j N identified for each AUV, is equal to the total distance of the path generated for the plurality of AUVs; assigning the highest indices to the corresponding AUVs if the sum of the distance travelled by the plurality of AUVs is equal to a total distance of the path generated, wherein the Boolean step function f(x) determines whether the path P can be divided into N parts such that each AUV travels the threshold distance from and returning to its deployment location; and iteratively assigning waypoints to each AUV using: (a) an initial index j 0 =1 for the first AUV; (b) computing distance constraints to determine j i for each AUV i; (c) verifying whether all waypoints are covered using the function f(x).
8 . The processor-implemented method of claim 7 , wherein the turn-aware zigzag method comprises (i) performing a binary search on the boolean step function to obtain a minimal optimal threshold distance where the sum of distance between the highest indices identified for the plurality of AUVs is not equal to the total distance of the path generated for using the pair of lines method, wherein the method performing the binary search on f(x) to determine the minimum value of x* for which the path can be partitioned into N part; and (ii) executing f(x*) to compute partition indices j i and assigning final path segments to each AUV using the computed indices P i =[S i ,p j i −1 ,p j i-1 +1 ,p j i-1 +2 , . . . ,p j i ,S i ], wherein each AUV travels from its starting point S i to the waypoints p j i-1 ,p j i-1 +1 ,p j i-1 +2 , . . . ,p j i and returns to S i .
9 . The processor-implemented method of claim 8 , wherein the turn-aware zigzag method comprises executing the boolean step function as binary search for finding the optimal threshold distance to compute optimal indices for each of the plurality of AUVs to assign respective segments to each AUV.
10 . The processor-implemented method of claim 4 , wherein the total distance travelled by each AUV is a sum of (i) a first distance that is a distance from a starting point to a first point in its assigned segment, (ii) a second distance that is a sum of distances between consecutive points within the assigned segment, and (iii) a third distance that is a distance from a last point in the segment back to the starting point.
11 . The processor-implemented method of claim 1 , wherein the Pair of Lines method comprises: placing the first AUV at a specific coordinate (dS,0) of sensor's footprint of the first AUV aligns with an edge of the area of interest; moving the first AUV in a first direction along a vertical path, enabling the sensors to capture data from a rectangular strip of the area of interest, wherein the movement creates a nadir blind zone within the strip; turning the first AUV at a boundary of the area of interest to initiate horizontal motion in a direction perpendicular to the vertical path; adjusting the sensor footprint of the first AUV during the horizontal motion by aligning a second footprint of the sensor overlaps with the nadir blind zone; navigating the first AUV along a second vertical path in a reverse direction of the first vertical path to capture data from the rectangular strip that includes the nadir blind zone; and iteratively repeating the steps of turning, adjusting, and navigating along subsequent vertical and horizontal paths in a back-and-forth pattern to shift the sensor footprint for complete coverage of the area of interest, thereby minimizing data gaps and overlaps between adjacent strips to optimize coverage efficiency.
12 . The processor-implemented method of claim 4 , wherein the partition zigzag method executes a linear time O(L) traversal over the waypoints of path P to evaluate the f(x) by computing: (i) a distance from the starting position S i to the first assigned waypoint p j i-1 ; (ii) a summation of distances between consecutive waypoints in the assigned segment; (iii) a distance from the last assigned waypoint p j i back to the starting position S i ; (iv) determining whether all waypoints are covered by verifying that j N =L for the last AUV.
13 . A system for generating a coverage path planning (CPP) for a plurality of Autonomous underwater vehicles (AUVs) with nadir gaps, wherein the system comprises: a central server that comprises: a memory that comprises a set of instructions; a processor that executes the set of instructions and is configured to: receive input from a user through a user device that is communicatively connected to the central server through a network, wherein the input comprises an area of interest, a count of the plurality of AUVs, a respective starting point of the plurality of AUVs, and an operational constraint; generate, using a pair of lines method, a path with a nadir gap based on the area of interest, wherein the path comprises a plurality of waypoints on a two-dimensional (2D) plane; determine a path planning method from a plurality of path planning methods based on an operational priority and the starting point of the plurality of AUVs; generate the CPP for the plurality of AUVs by dividing the path into a plurality of segments by applying the determined path planning method on the path based on the starting point of the plurality of AUVs, thereby each segment is assigned to each AUV; and transmit the generated CPP to the plurality of AUVs that are communicatively connected to the central server through the network.

Description

BACKGROUND Technical Field The embodiments herein gradually relate to autonomous underwater vehicles (AUVs) and their application in underwater surveillance, exploration, and environmental monitoring, specifically, to coverage path planning (CPP) methods and systems designed to manage and optimize the coordinated movement of multiple AUVs to achieve full area coverage in underwater environments, particularly in the presence of nadir gaps where sensing coverage is limited or partial. Description of the Related Art In recent years, autonomous underwater vehicles (AUVs) have become essential tools in underwater surveillance, exploration, and environmental monitoring. These vehicles offer an efficient, cost-effective, and safe means to gather data from marine environments, which are often difficult and hazardous for human divers to access. A key challenge in these applications is Coverage Path Planning (CPP), where the objective is to ensure that the entire area of interest is surveyed without gaps, in a time-efficient manner. This challenge becomes particularly pronounced in the presence of nadir gaps, which are blind zones directly beneath the AUVs where sensor coverage is lacking. Traditionally, CPP has been extensively studied for single AUV operations. Various strategies have been proposed to mitigate nadir gaps during single-AUV missions, such as the “Pair of Lines” method. However, the rapid advancement of AUV technology has led to the deployment of multiple AUVs in coordinated missions, which offers the potential to significantly improve coverage efficiency and reduce mission time. Despite this, there has been a lack of solutions specifically addressing CPP for multi-AUV operations, particularly in the presence of nadir gaps. Multi-AUV CPP introduces additional challenges, such as the need for efficient collaboration between vehicles to ensure complete coverage while minimizing the likelihood of collisions. Furthermore, the optimization of secondary objectives, such as minimizing the maximum distance travelled by any AUV and reducing the total number of turns, becomes critical in such missions. Each of these objectives is associated with trade-offs that must be carefully balanced Therefore, there arises a need to address the aforementioned technical drawbacks for a system to generate CPP for AUVs in underwater surveillance missions, accounting for nadir gaps. SUMMARY In view of the foregoing, an embodiment herein provides a method for generating a coverage path planning (CPP) for a plurality of Autonomous underwater vehicles (AUVs) with nadir gaps. The method includes receiving input from a user through a user device that is communicatively connected to the central server through a network. The input includes an area of interest, a count of the plurality of AUVs, a respective starting point of the plurality of AUVs, and an operational constraint. The method includes generating a path with a nadir gap based on the area of interest, using a pair of lines method. The path includes a plurality of waypoints on a two-dimensional (2D) plane. The method includes determining a path planning method from a plurality of path planning methods based on an operational priority and the starting point of the plurality of AUVs. The method includes generating the CPP for the plurality of AUVs by dividing the path into a plurality of segments by applying the determined path planning method on the path based on the starting point of the plurality of AUVs, thereby each segment is assigned to each AUV. The method includes transmitting the generated CPP to the plurality of AUVs that are communicatively connected to the central server through the network. In some embodiments, the operational constraint includes minimizing a maximum distance travelled by at least one of the plurality of AUVs or minimizing a total number of turns executed by any one of the plurality of AUVs. In some embodiments, the plurality of path planning methods includes a partition zigzag method and a turn-aware zigzag method. In some embodiments, the partition zigzag method iteratively assigns the segments of the path P to each AUV by (i) identifying a first highest index j1≤L for a first AUV when a total distance travelled by the first AUV from a first starting point S1 to first waypoint P1, traversing intermediate waypoints, and returning to the first starting point S1 is less than or equal to a threshold distance (x) S1 is ≤x, (ii) identifying a second highest index for a second AUV when a total distance travelled by the second AUV from the second starting point and returning to the second starting point is less than or equal to the threshold distance, (iii) repeating the process for each subsequent AUV, determining the highest index ji for each AUV i starting from j(i-1), such that the AUV travels at most distance or the threshold distance x before returning to its starting position Si, (iv) maintaining a running sum of distances at each waypoint to en