A Data-Driven Intermittent Online Coverage Path Planning Method for AUV-Based Bathymetric Mapping

Abstract

Bathymetric mapping with Autonomous Underwater Vehicles (AUVs) receives increased attentions in recent years. AUVs offer a lower operational cost and smaller carbon footprint with reduced ship usage, and they can provide higher resolution data when surveying the seabed at a closer distance if compared to ships. However, advancements are still needed to improve the data quality of AUV-based surveys. Unlike mobile robots with deterministic mapping performance, multibeam sonars used in AUV-based bathymetric mapping often yields inconsistent swath width due to the varied seabed elevation and surficial properties. As a result, mapping voids may exist between planned lawnmower transects. Although this could be solved by planning closer lawnmower paths, mission time increases proportionally. Therefore, an onboard path planner is demanded to assure the defined survey objective, i.e., coverage rate. Here in this paper, we present a new data-driven coverage path planning (CPP) method, in which the vehicle automatically updates the waypoints intermittently based on an objective function constructed using the information about the exploration preference, sonar performance, and coverage efficiency. The goal of the proposed method is to plan a cost-effective path on-the-fly to obtain high quality mapping result meeting the requirements in coverage rate and uncertainty. The proposed CPP method has been evaluated in a simulated environment with a 6DOF REMUS AUV model and a realistic seafloor topography. A series of trials has been conducted to investigate the performance affected by the parameters in the objective function. We also compared the proposed method with traditional lawnmower and spiral paths. The results show that the weight assignment in the objective function is critical as they affect the overall survey performance. With proper weight settings, the AUV yields better survey performance, coverage rate and coverage efficiency, compared to traditional approaches. Moreover, the proposed method can be easily adjusted or modified to achieve different coverage goals, such as rapid data gathering of the entire region, survey of irregular workspace, or maintaining real time path planning.

1. Introduction

Seabed bathymetry is vital for a growing variety of uses, including marine geological research, oil and gas exploration, military and defense applications, safety and disaster prediction models, et al. [1]. Humans began mapping seafloor over a century ago, still, more than 80% of the area is under-sampled. Recognizing this fact, an international project with the objective of facilitating the complete mapping of the world ocean, Seabed 2030, have been launched by the General Bathymetric Chart of the Oceans (GEBCO) and the Nippon Foundation [1]. Autonomous underwater vehicles (AUVs) are proved to be effective to perform mapping tasks [2]. Compared to normal ships, AUVs offer a lower operational cost and smaller carbon footprint with reduced ship usage, and they can provide higher resolution data when surveying the seabed at a closer distance due to the fact that the transversal mapping resolution decreases with the standoff distance [3].

In recent years, many researchers have applied AUVs [2,4] to perform bathymetric mapping where multibeam sonars are mainly used. Other sonars, including single-beam sonars, side-scan sonars, and interferometric sonars, are also used. However, single beam sonars yield sparse data points, and side-scan sonars provide high resolution images instead of 3D point clouds. Interferometric sonars are special side-scan sonars which can produce bathymetry image through differential phase technique. However, they require sophisticated signal processing algorithms to get a satisfied result [5].

An important issue to be addressed in seafloor mapping with AUVs is the path planning. A good survey path provides efficient and complete coverage on the workspace, while a poorly planned path yields a tremendous amount of redundant samples or leaves possible voids in the workspace. In the literatures [2,4,6,7,8], lawnmower pattern paths (also known as boustrophedon paths) were popularly used, which is presented by simple back-and-forth transects spaced at a constant inter-distance. Lawn mowing and underwater bathymetric survey both require complete coverage of a specific area, however, the lawnmower blade has a consistent cutting coverage, while the width of the multibeam sonar swath varies due to the elevation changes of the seabed. As a result, a constant inter-distance as in lawnmower paths will not be effective in bathymetric mapping. For example, a narrow inter-distance will increase the overall mission time and produce significant overlaps and redundant samples. In contrast, a wide inter-distance will result in possible voids between transects.

Moreover, the multibeam footprints increase with the standoff distance. For a typical multibeam sonar, the distance between the beams and the bottom are different. This causes non-uniform confidence along the swath [9]. The term confidence here refers to the possibility of obtaining valid data and the accuracy of the measurement. The greater the footprint size, the weaker the echos from the seafloor, the fewer number of soundings that will be received [10], and the lower the confidence. Thus, the footprints of multibeam need to be considered to get high quality bathymetric maps.

In this paper, we look into the characteristics of multibeam sonar and propose a data-driven coverage path planning (CPP) method to promote bathymetric mapping with AUVs. The main contributions of this paper include:

• (1). The path of the proposed method is intermittently planned based on collected data. The intermittent planner has lower requirement on real-time computing; hence, could be potentially implemented on low size, weight, power and cost (SWaP-C) embeded computers.

• (2). The path planner uses a new reward function to optimize multiple objectives. The function is designed to account for coverage gain and sonar performance with an additional term to encourage exploring unknown workspace.

• (3). The reward values for the coverage gain and sonar sensing are computed adaptively. The objective function relies on the predicted sonar swath which is determined based on in-situ measurements instead of a pre-defined constant.

The remainder of the paper is organized as follows. In Section 2, we present a review of related work. In Section 3, we introduce our CPP algorithm in details. Simulation results are summarized in Section 4 with in-depth discussion and comparison. Finally, we conclude the paper with future research recommendations in Section 5.

2. Related Work

Path planning is a fundamental problem in robotics. An efficient path planning system would greatly improve mission efficiency and results. New algorithms in sampling-based methods [11,12], networked systems [13,14], and energy-optimized solution [15] is advancing the field rapidly. Bathymetric mapping studied in this paper could be referred to as a CPP problem which aims to determine a path that passes over all points of an area or volume of interest while avoiding obstacles. CPP problems are widely studied in a variety of applications, such as cleaning robots, painting robots, unmanned aerial vehicles (UAVs) [16], demining robots, lawnmowers [17], mine countermeasure (MCM) surveys with AUVs [18], etc..

The solutions to the CPP problems can be divided into two main groups, area-based and cell-based. In the former group, the workspace can be divided into several areas [19] or be considered as an entire area. In each area, the robot navigates in preset trajectories, mostly lawnmower pattern [16], or spiral pattern [20]. These methods require prior knowledge of the target area and they are able to accomplish covering task in a relatively short period [18]. Area-based approaches have been adopted in various applications. In [19], an area decomposition algorithm is proposed to divide obstacle-exist workspace into obstacle-free areas and obstacle areas. A lawnmower path is then planned to cover individual areas. In [8], a depth-constrained autonomous bathymetric mapping strategy is introduced. The AUV can autonomously divide the target area online according to the depth data, so the lawnmower coverage will operate effectively in each area and transit efficiently between areas. Another adaptive method is presented in [21]. In order to reduce energy consumption of UAVs in sensing tasks, the inter-distance between the parallel transects of lawnmower path are properly adjusted and the returning path is also utilized to cover extra areas. In [22], the target region is segmented by depth features, and lawnmower path are planned in each subregion with different inter-distances. In this way, the coverage overlapping is minimized. A novel informative path planning method handling with spline trajectories is proposed in [23]. The path is generated by a online data-driven optimization algorithm. Its global goal is to collect information effectively rather than complete coverage.

In the bathymetric mapping task, the swath width changes with terrain, so it is dilemmatic to determine the inter-distance between parallel transects for lawnmower paths and spiral paths. Small inter-distance will result in a long overall traveling distance and a wide inter-distance will lead to low coverage rate. This is a drawback shared by most area-based methods.

In the cell-based approaches, the workspace is divided into small cells. The cell shape can be square, circle, hexagon, et al., depending on different mission requirements [16]. Cell-based methods are usually adaptive, using algorithms such as Genetic Algorithm, Wavefront Algorithm, and objective function based algorithms, which plans the path on-the-fly [16]. In [18], a data-driven and multiobjective CPP method is proposed for mine countermeasure survey of AUVs. The proposed algorithm is composed of information theory and branch entrophy and its goal is to determine the desired heading in a hexagonally decomposed workspace. The final path is irregular and shows a better performance than lawnmower path and random track in non-convex workspace. In [24], a topologically organized bioinspired neurodynamics model based on the grid map is constructed to represent the dynamic environment. A gradient-based algorithm is built to search targets in 3-D underwater environments with obstacles. Manjanna et al. [25] proposed an anytime planning technique for efficient data gathering using point-sampling based on non-uniform data-driven coverage. Their online selective sampling algorithm plans a path for an ASV to perform high density measurements in hotspot regions. Bircher et al. [26] proposed a path planning method for autonomous inspection of micro aerial vehicles. It plans on-the-fly in a receding horizon fashion by sampling possible future configurations in a geometric random tree, so that the vehicle can effectively avoid obstacles.

Cell-based planning methods have advantages on real-time adjustment and obstacle avoidance. On the other side, a large number of cells will inevitably cost computing resources and storage space. As a result, these approaches are usually limited to exploring small areas [16].

3. Proposed Method

The method proposed in this paper can be considered as a combination of area-based approach and cell-based approach. The basic trajectory is composed of waypoints and lines that connect them, like area-based approach, so the coverage area will not be limited by computing resources. In the meantime, the workspace is divided into cells, so that the measured data and sensor attributes can be properly processed to assist online path planning.

3.1. Problem Statement

In this research, AUVs are assumed to navigate at a constant depth, in a rectangular workspace. We define three frames in our work, namely the earth frame, vehicle frame, and sensor frame, as illustrated in Figure 1. As the path is planned in the horizontal plane, only x-axis and y-axis are shown in the figure. The origin of the earth frame is set at a known latitude and longitude on the sea surface. The x-axis is pointed north, y-axis is pointed east and z-axis is pointed downward. The origin of the vehicle frame is set at the center of gravity, x-axis pointing forward and y-axis pointing at starboard side. As the sensor is fixed to the vehicle, we assume the sensor frame has the same orientation as the vehicle frame. We could further assume the origin of the sensor frame is coincident with the vehicle frame for small AUVs with the sonar mounted near (<1 m) the origin of the vehicle frame. The workspace is set in the earth frame and decomposed into square cells. The cell size determines the resolution of the resultant bathymetric map, which is 1 m in this paper. The bathymetry data obtained by the multibeam sonar is a set of points in the sensor (vehicle) frame. For a point ${\mathbf{p}}_k^v$ in the vehicle frame, we can transfer it into the earth frame by:

(1)${\mathbf{p}}_k^e={\mathbf{T}}_v^e{\mathbf{p}}_k^v$

where the subscript k denotes the data index, superscripts, v and e, denote the affiliated frames, and $\mathbf{T}$, the transformation matrix, is obtained based on the location of the vehicle frame and its orientation in the earth frame, which are normally estimated by global navigation satellite system (GNSS) and attitude and heading reference system (AHRS).

The sonar data point in the earth frame, ${\mathbf{p}}_k^e$, can be projected into a cell in the workspace $⟨x,y⟩$. We define the observation condition of a cell as a binary variable, $O\left(M_{x,y}\right)$. If there is an observation made in the cell, $O\left(M_{x,y}\right)$ become 1 marked as observed, otherwise it remains 0 noted as unexploited. The mission goal is to explore the workspace until the overall observation condition have exceeded the user-defined goal, i.e., the overall percentage of the number of observed cells.

In our method, the successive transect is calculated during the mission instead of preprogrammed. The conception is illustrated in Figure 2. The vehicle will plan the successive pair of waypoints after one transect is finished. In this way, our path planning algorithm runs intermittently at the end of each transect based on the collected data. Initially, user could program the starting point of the mission. When the algorithm is analyzing the candidate transects, it will consider both zonal and meridional transects. The flexibility allows the user to further include other factors into the objective function, e.g., the adversal effects posed by the ocean current. The distance between the candidate transects is also adjustable. A large distance could be selected for a large workspace for computation efficiency. Herein, we select 1 m distance that matches the gridded map resolution.

3.2. Intermittent Path Planning Method

An objective function is proposed to quantify the “rewards” for each candidate transect. It consists of three components: exploration preference (E), sonar sensing performance (S) and coverage gain (C). As indicated in Equation (2), the successive transect, $j^{★}$, is selected by the maximum value from the objective function.

(2)$j^{★}=argma{x}_j(W_e{E}^j+W_s{S}^j+W_c{C}^j)$

where j is the candidate transect as described in Figure 2 , and $W_e$, $W_c$, $W_s$ are weights that can be adjusted, but subject to $W_e+W_c+W_s=1$. $E^j$, $C^j$ and $S^j$ are rescaled values, ranging from 0 to 100. $E^j$ is the exploration reward, $S^j$ is the sonar sensing reward and $C^j$ is the coverage gain reward. They will be specifically discussed in the later subsections.

It should be noted that the transects do not necessary cross the overall workspace. We exclude the covered segments near the endpoints to reduce extra trajectory, as shown in Figure 3. The width of segments equals the predicted swath width which is the minimum observed swath width from the collected sonar data during the survey. The excluded rectangles should contain as many covered cells as possible and there should be no void cells in them. The resultant waypoints for the j-th transect is defined as ${\mathbf{W}}^j=[⟨x_1^j,y_1^j⟩,⟨x_2^j,y_2^j⟩]$. For zonal transects, the two waypoints have the same y-coordinate, $y_1^j=y_2^j=y^j$ and for meridional transects, the two waypoints have the same x-coordinate $x_1^j=x_2^j=x^j$.

After the waypoints has been generated, the transition sequence will be determined based on their distance to the current vehicle position. The vehicle will move towards the closer waypoint first then follow the transect moving towards the other waypoint. The algorithmic representation of the path planner is summarized in Algorithm 1.

Algorithm 1: function pathplanner

3.3. Exploration Reward

The exploration reward is introduced to encourage the vehicle to explore unsurveyed areas that is far away from previous transects. By doing so, the collected data can be properly interpolated to obtain a reasonable map when the preset coverage rate is low or when the mission is terminated unexepctedly. Meanwhile, this strategy can avoid overlap and gather information efficiently at the early stage. The exploration reward $E^j$ is defined as the minimum distance to the completed parallel transects:

(3)$E^j=\left\{\begin{array}{ccc}\hfill min(y^j-{\mathbf{W}}_y^z),& & \mathrm{zonal}\mathrm{transects}\hfill \\ \hfill min(x^j-{\mathbf{W}}_x^m),& & \mathrm{meridional}\mathrm{transects}\hfill \end{array}\right.$

where ${\mathbf{W}}_y^z$ is all the past zonal transects and ${\mathbf{W}}_x^m$ is all the past meridional transects.

For comparison, in a lawnmower path, the vehicle will navigate in a nearby transect once the current transect is finished, while in a spiral path, the vehicle will choose a far transect [16]. As a result, lawnmower type paths focus on sequential individual sections and spiral type paths precedently explore the outline of a region [20]. Take curve fitting as an analogy, lawnmower methods get the data points from one end to another, spiral methods get the data points from two ends to the center, in comparison, $E^j$ tends to get the points from the ends and the middle. The latter operation could provide sufficient data to bound the uncertainty when interpolating the bathymetric over the workspace.

3.4. Sonar Sensing Reward

The sonar sensing reward is introduced to choose the proper transects that will result in better sonar confidence. The beams of multibeam sonars distribute uniformly in the profiling sector, whereas their echoes from the bottom terrain are not even. They are affected by the ray angle of a specific beam related to the centerline, $\alpha$, and the composition of sediments [9]. As the latter factor has a random effect to each part of a region, herein, we only consider the former factor. Assuming the bottom is flat, the footprint of a circular beam will be an ellipse if $\alpha$ is not zero, and the area of the ellipse increases with $\alpha$, as shown in Figure 4. According to [9], larger footprint will result in higher uncertainty. Assuming the footprint area is $A_0$ when $\alpha$ is zero, and the area increases to $A_{\alpha }$ at a specific $\alpha$. The sensing confidence, $S\left(\alpha \right)$, could be computed by dividing $A_0$ by $A_{\alpha }$, where $A_0$ is

(4)$A_0=\pi ·{(h·tan\left(\beta \right))}^2$

where $\beta$ is the half beamwidth and h is the altitude. The area of the elliptical footprint $A_{\alpha }$ can be calculated by:

(5)$A_{\alpha }=\pi ·e_a·e_b$

where $e_a$ and $e_b$ are the half length of the major and minor axis, respectively. Their values can be derived by projective geometry method.

(6)$e_a=(h·tan(\alpha +\beta )-h·tan(\alpha -\beta ))/2$

(7)$e_b=h·tan\left(\beta \right)/cos\left(\alpha \right)$

Figure 4 depicts the sensing confidence $S\left(\alpha \right)$ with assumed values, $h=30$ m and $\beta =0.5^{°}$. As shown in the figure, the observations obtained underneath the sonar have higher sensing confidence with gradually increasing uncertainty in the transversal direction.

For the j-th transect, we predict the potential coverage area $A^j$ based on the candidate path and the minimum sonar swath $min\left(S_k\right)$. The candidate path consists of the candidate transect connecting two waypoints and the transition path from the current vehicle location to the first waypoint. For each unexplored cell, $O\left(M_{x,y}\right)$ =0, inside $A^j$, we compute its cross-track distance, $e_{x,y}$, to the j-th transect. Consequently, $\alpha$ can be calculated by $\alpha =atan(e_{x,y}/\overline{h})$, where $\overline{h}$ is the mean vehicle altitude computed from gained sonar measurements. By substituting it into $S\left(\alpha \right)$, we get the following equation.

(8)$S\left(e_{x,y}\right)=\frac{{\left(tan\left(\beta \right)\right)}^2}{(tan(atan(e_{x,y}/\overline{h})+\beta )-tan(atan(e_{x,y}/\overline{h})-\beta ))/2·tan\left(\beta \right)/cos\left(atan(e_{x,y}/\overline{h})\right)}$

By applying the above equation, we can get the confidence of each cell. Subsequently, we define the sensing reward for the j-th transect by the mean confidence $\overline{S}\left(e_{x,y}\right)$ of the unexplored cells in $A^j$:

(9)$S^j=\overline{S}\left(e_{x,y}\right)|⟨x,y⟩\in A^j\&O\left(M_{x,y}\right)=0$

The sensor confidence will also be used as a metric to evaluate the quality of the obtained bathymetric map by inspecting the sensor confidence of each cell in the workspace. A cell may be observed during several transects and each observation will increase its confidence. Assuming $S(x,y|k)$ is the sensor confidence for a specific cell in the k-th transect and it is observed n times. The overall sensor confidence $S(x,y|1:k)$ of this cell is calculated by:

(10)$S(x,y|1:k)=1-\prod _{k=1}^n(1-S(x,y|k))$

3.5. Coverage Gain Reward

The coverage gain reward represents the possible coverage efficiency along a candidate path, which comprises of the candidate transect and the transition path. The coverage efficiency is denoted as the coverage gain normalized by the traveling distance on the candidate path, which is proportional to the traveling time.

Using the minimum sonar swath gained from the collected sonar data, we could estimate the predicted coverage along the candidate path. The total coverage gain reward of the corresponding candidate path is computed by the following equation.

(11)$C^j=\sum (1-O\left(M_{x,y}\right))/L^j|⟨x,y⟩\in A^j$

where $L^j$ is the length of the candidate path.

4. Experimental Validation in Simulated Environments

4.1. Simulation Setup

In order to validate the performance of the proposed CPP method, a simulator is built in MATLAB, which is composed of terrain model, sonar model, AUV model, guidance algorithm and path planner, as illustrated in Figure 5.

The terrain model is applied to simulate the terrain of seafloor. It is generated by a fractal terrain generator based on diamond-square algorithm [27]. The sonar model generates sonar data points and swath width based on the information from the AUV model and the terrain model. The proposed method is realized by the path planner, producing waypoints intermittently based on the sonar data. Meanwhile, the guidance model computes the desire heading for tracking the waypoints, and the AUV model makes maneuvers.

A ray-tracing sonar model [28] is implemented to simulate the sonar propagation and measurements. The sound propagation is simulated with rays, which are distributed every 1.8${}^{°}$ in a 120${}^{°}$ section. The first intersection point between a specific ray and the terrain is recorded as a detected point that can be represented into the earth frame using the transformation function (Equation (1)). These sonar data points are used to update the observation conditions for the corresponding cells and the swath widths are used for predicting future coverage in the path planning stage, as described in Algorithm 1.

To track the waypoints, the Line-of-sight (LOS) guidance law is applied [29]. The desired yaw will be continuously calculated based on the current position and the coordinates of the previous waypoint and the current desired waypoint.

The desired yaw is input to the AUV model, which is built in the Simulink environment. As the AUV is assumed to maneuver in a plane, and the velocity is set to a constant value, yaw angle is the only control object. The desired yaw and the current yaw are input to a PID controller to adjust the rudder angle, which is then imported into the 6DOF REMUS hydrodynamic model [30] developed based on conventional marine vehicle model [31], and the position and pose of the AUV is updated.

4.2. Results

To test the performance of the proposed approach, a series of experiments were conducted. The target region is bounded by 200 m and 700 m zonally and 200 m and 900 m meridionally. The depth of the terrain is modelled between 40 m to 80 m. The AUV is constrained at the depth of 30 m and moving in a constant speed of 1 m/s. We summarize the simulation setup parameters in Table 1.

We have run 16 simulations with different weights for the three rewards in the terrain shown in Figure 2. As mentioned before, each weight has a range from 0 to 1, and the sum of the weights has to be 1. We use the following rules to select the weights in order to cover all possibilities in our simulation runs. First, we pick $W_e$ from five options, 0, 0.25, 0.5, 0.75, and 1. Then, $W_c$ and $W_s$ are selected from the same options to satisfy the requirement that the sum of the weights has to be 1. The above rule produces 15 pairs of weights. Then, the 16-th pair is selected when all three weights are equal to 0.33. The resultant runtime to reach 99% coverage rate for each run is shown in Figure 6. The sizes of the spheres indicate the total mission runtime for each experiment. In other words, the larger sphere means a longer runtime, therefore, lower coverage efficiency. It is clear that the coverage efficiencies are relatively low when $W_c$ or $W_s$ is 0, which proves the effectiveness of the coverage gain reward and sonar sensing reward. When $W_e$ is set at 0, the vehicle is not encouraged to explore distant area, so the resultant path is similar to lawnmower pattern, except that it is adaptive and greedy. Zero $W_e$ can have a benefit on coverage efficiency according to Figure 6, when we don’t care much about interpolating the map. Consequently, the weight setups with zero $W_c$ or zero $W_s$ are excluded, and 7 groups of weights that are encircled in Figure 6 are further inspected, as listed in Table 2.

Figure 7 shows the overall path and mapping uncertainty in run #2, which has the highest overall coverage efficiency, and Figure 8 compares the results of two typical runs, run #5 and #6, . The sensor confidence of each cell is calculated by Equation (10) and represented by the colors described in the sidebar. The vehicle path is displayed with grayscale lines showing elapsed mission time in the top colorbar while the side colorbar indicating the seafloor depth. The corresponding runtimes for different gray scales are described in the topbar. As the velocity of the AUV is 1 m/s, the runtime also equals the traveling distance.

For comparison, we have conducted three lawnmower pattern surveys with inter-distance of 62 m, 50 m, and 42 m. Moreover, two spiral pattern surveys are also conducted with minimum line space of 45m and 33 m. In these runs, the inter-distances are determined by limiting the maximum numbers of transects. For example, the total number of transects is 8 with 62 m inter-distance. Figure 9 shows the result of the lawnmower path with 42 m inter-distance and the result of the spiral path with 46 m zonal inter-distance and 33 m meridional inter-distance.

Now let’s look into these figures. Due to the overlap between the transects, the observation confidence of the cells in each path is high enough in general. Low confidence cells usually appear in turning points, where the consecutive transversal sonar swath is further apart at the further end. As the lawnmower path and the spiral path shown in Figure 9 both follow a series of preset waypoints, to ensure high coverage rate, their inter-distances need to be narrow enough to avoid any mapping void. On the other hand, for the proposed method, the inter-distances are able to change adaptively.

In Figure 7, the path is similar to lawnmower pattern transecting only in meridinoal direction. This is due to the exclusion of the exploration reward. We could observe that the AUV made 6 transects through the workspace, then performed additional transect to cover the remained voids. This adaptive feature guarantees the coverage requirements that may not be achievable in lawnmower pattern planned with a wide inter-distance.

Figure 8 presents the resulting path from simulation run #5 and #6, where the exploration reward are enabled. Distinguished resulting paths are found compared to that shown in Figure 7. The total traveling distances of run #5 and #6 are 10,500 m and 10,800 m respectively, which are longer than the path shown in Figure 7. However, the advantage still exists with this setup. As shown in Figure 8, the AUV explores distant areas with priority. As a result, more information will be gained if the mission was ended unexpectedly, and the obtained maps are more suitable for interpolation.

The labeled transects in Figure 8 reveal that run #6, which has a larger $W_e$, is more likely to explore distant areas than run #5, while the coverage efficiency of run #5, carrying a larger $W_c$, is slightly higher. The results indicate that it is possible to optimize the path for different mission requirements by adjusting the weights.

Figure 10 shows the comparison of coverage capabilities in different simulation runs. The height of each bar represents the runtime. The color layers indicate different coverage rate bands, 60 to 80% (blue), 80% to 90%(orange), 90% to 99% (gray) and above 99% (yellow). For each layer, the shorter its height, the higher the coverage efficiency. Totally, 12 different paths that belong to 3 different strategies are compared.

As shown in Figure 10, the coverage efficiency of a spiral path is slightly lower than a lawnmower path with similar inter-distance. A problem for spiral paths is the inter-distance between zonal transects and the inter-distance between meridional transects are different if the target region is a rectangle. If the aspect ratio of the workspace is large, the coverage efficiency of the spiral path will become very low. As a result, a lawnmower path is a better choice than a spiral path if there aren’t extra requirements.

For both spiral paths and lawnmower paths, their performance are closely related to the inter-distance, which is hard to choose without sufficient prior knowledge of the target region. As shown in Figure 10, at a wider inter-distance, spiral and lawnmower surveys (the 8th and the 10th bar) both produce an low coverage rate (less than 99%). To guarantee the required coverage rate, we will have to set a smaller inter-distance in these situations. Thus, we choose the lawnmower path with 42 m inter-distance as the reference when evaluating the proposed method.

According to Figure 10, most results of the proposed method have advantages over the lawnmower result (42 m inter-distance) when the coverage rate is under 90%, indicating that the proposed method has high coverage efficiency at most of mission time. Meanwhile, the run #2 reaches 99% coverage rate much faster than the lawnmower method, indicating that if the weights are adjusted properly, the proposed method can have advantages over lawnmower method on coverage efficiency during every stage of a mission. Moreover, the runs with zero $W_e$ result in relatively higher coverage efficiency compared to the other runs, revealing that pursuing global coverage in early stage (when $W_e$ is not 0) will have a trade-off in coverage efficiency in the long run, anyhow, in a limited range.

Figure 11 shows the comparison of the overall confidences of the maps obtained from different simulation runs. The overall confidence of a map is defined as the average confidence of the cells in the workspace, and is represented by the height of the corresponding bar in the figure. The confidence of each cell is obtained by Equation (10). The color layers indicate different runtime bands, 0 to 3000 s (orange), 3000 s to 6000 s(yellow), 6000 s to the final runtime labeled on the top of each bar (green). As shown in the figure, for lawnmower paths and spiral paths, the resultant confidence is closely related the inter-distance. A Wider inter-distance leads to higher confidences in the early stages (3000 s runtime and 6000 s runtime), but a lower final confidence. In contrast, the resultant confidence from the runs with the proposed method has a more consistent value as high as 0.98. More importantly, these runs also show a higher confidence at early stage in orange and yellow layers.

Since the above trials are all based on the same terrain shown in Figure 2, we continue to verify the performance of the proposed method in different terrain models. The coverage goal is again set at 99%. Figure 12 shows the results on different terrains with the same objective weights of run #2 in Table 2. The terrain in the left picture of Figure 12 is generated using the same function but different elevation settings, while the terrain on the right is an actual topography from the bathymetric data of Narragansett Bay, Rhode Island, USA, provided in [33]. In both trials, we kept the vehicle moving at a similar altitude as the trials shown in Table 2, and the workspace size was set to be the same. The total traveling distances in the two terrains are 8368 m and 7371 m, respectively, which are shorter than the lawnmower path shown in Figure 9. These results indicate the proposed CPP method has a consistent performance on different terrain models.

5. Discussion

According to test results, the proposed CPP method has some major advantages over the traditional lawnmower paths and spiral paths, as summarized below:

• (1). The characteristics of multibeam sonar are taken into consideration to get high quality bathymetric map. By selecting proper weights, the proposed method is able to obtain a map with higher confidence than lawnmower paths or spiral paths in every stage of a mission.

• (2). The data-driven approach can autonomously adapt to various terrains, different depth of the vehicle, and different dimensions of target area.

• (3). The proposed algorithm can guarantee high coverage rate as path planning won’t stop until the preset coverage goal is achieved.

• (4). The proposed method has higher coverage efficiency than lawnmower path during the early stage, and has the potential to achieve higher overall coverage efficiency by choosing proper weights.

• (5). Low coverage rate map obtained by the proposed method is more suitable for interpolation than that obtained by lawnmower surveys or spiral surveys.

• (6). The parameters of the proposed method can be adjusted under different mission goals. For example, if the mission time is adequate for a full coverage mission, $W_e$ can be set to 0, so that high coverage efficiency can be achieved. Otherwise, non-zero $W_e$ is a better choice for proper interpolation.

In the proposed model, we use the minimum swath width observed to predict the future swath width. This is a conservative choice to minimize the possibility of generating mapping void during the early stage. It can be replaced by the average swath width observed if fast coverage at the early stage is required.

In principle, the proposed algorithm also works with convex irregular workspace. We just need to add two steps at the beginning. (1) Find the maximum bounding box. (2) Assign the cells outside the workspace but inside the bounding box to be explored ones. Then everything else works the same. For non-convex workspace, we could adopt area decomposition to divide the workspace into several convex domains. Then our CPP method can be applied in each domain. However, the overall algorithm efficiency may decrease due to the additional cell decomposition process. We plan to have further research in non-convex workspace and compare the algorithm performance with some existing solutions [18].

We set a constant vehicle depth in our approach, which is a practical and commonly-adopted setup in AUV-based bathymetric survey. However, in the real situation, the depth may change due to imperfect controller tuning or due to the user’s command. In both cases, the altitude change will result in significant change in swath width, which leads to inaccurate estimate when predicting the potential coverage in the CPP algorithm. In order to handle the above situation, the CPP algorithm could be modified to construct a mathematical equation between depth and swath width. Then use the equation to estimate the swath width for a future transect at a different depth.

Here we provide a preliminary evaluation about the energy performance on selected physical systems. In a 500 m × 700 m target region, the mission time is in the order of 2.5 to 3 h. In our project, we plan to use a micro-AUV with 244 watt-hour energy (Alkaline battery). Without any payload, the AUV could last 30 h. Therefore, the AUV is estimated to have a power consumption of about 8 watts. We plan to integrate a bathymetric sonar and a backseat driver computer with a power consumption of 15 watts and 10 watts, respectively. Based on the mentioned numbers, the AUV with the mapping payload (the sonar and the computer) has an estimated endurance slightly over 7 h.

Currently, the CPP and the simulation environment are implemented in MATLAB. On a laptop, 1.8GHz quad-core Intel i7, the run time of the CPP is 96 s. We expect that the run time will be further reduced to less than 60 s when implemented in C++ on an embedded computer, e.g., NVIDIA Jetson TX-2 (6 CPU cores and 256 GPU cores). Since the CPP only runs intermittently when the AUV is on the surface, 1 minute run time is acceptable. Currently, the inter-distance between each pair of adjacent candidate transects is 1 meter. As a result, we will have 1200 candidate transects in a 500 m by 700 m workspace. There are two options to further reduce the CPP run time. First, one could increase the inter-distance to reduce the total number of candidate transects. Second, one could use GPU computing to parallelize the reward estimation for candidate transects.

To properly apply the proposed method, we shall first confirm the target coverage rate. If it is high, we can choose the setup of run #2. The resultant path will be adaptive lawnmower pattern. If the target coverage rate is low, we can choose the setup of run #7, in the meantime, replace $min\left(S_k\right)$ with $mean\left(S_k\right)$. The resultant path will have high coverage efficiency and the unexplored areas can easily be interpolated. Indeed, the weight groups tested in this paper only cover part of possible choices, they can still be optimized to get better performance if necessary.

6. Conclusions and Future Work

This research presents a CPP method for bathymetric mapping with AUVs. Collected data, sensor performance, exploration preference and coverage efficiency are taken into consideration in the algorithm. Test results in simulated environment with 6DOF REMUS AUV model show that the weight assignment in the objective function is critical as they affect the survey performance. With proper weight settings, the AUV yields better survey performance, coverage rate and coverage efficiency, compared to traditional lawnmower and spiral approaches. Moreover, the proposed method can be easily adjusted or modified to achieve different coverage goals.

From our parameter studies in the simulated environment, we found the weights setting of $W_e=0$, $W_s=0.5$, and $W_c=0.5$ produces the most efficient survey. Further experiment has done on different terrains with the same weight setting to confirm the result. Although the exploration reward is set to 0 in the best weight setting, we still suggest to include a small weight for E to assure the quality of the survey products obtained from the missions with unexpected terminations due to AUV endurance or systematic problems.

We plan to further improve the proposed CPP method from the following aspects. (1) The performance of the proposed method in convex and non-convex irregular workspace will be studied. (2) Practical factors such as the adversal effects posed by the ocean current and positioning error of sensors will be taken into consideration. (3) Multi-vehicle CPP will be studied based on the proposed method. (4) The proposed algorithm will be integrated into our on-board ROS (Robot Operating System) and field trials will be conducted.

Author Contributions

J.S. performed the computations and wrote the manuscript. M.Z. developed the theory, revised the manuscript and supervised the project. All authors have read and agreed to the published version of the manuscript

Funding

This project is supported by the Department of the Navy, Naval Undersea Warfare Center, Division Keyport, under the Grant Number N00253-19-1-0005.

Conflicts of Interest

The authors declare no coflict of interest.

Figures and Tables

Figure 1. The workspace and the configuration of the frames.

Figure 2. The conception of the proposed CPP method. The vehicle will plan the successive pair of waypoints after one transect is finished. Different colors of the terrain represent different depths, as illustrated in the sidebar.

Figure 3. Conception of reducing transect length by examining the current observation and the predicted observation condition in a candidate transect. The transversal width of the predicted coverage is determined to be the minimum swath width observed during the mission, min(Sk).

Figure 4. Sensor confidence based on footprints. The drafts of footprints in a swath are added to illustrate the origin of the curve. The labeled areas are calculated based on practical parameters, that is h¯=30 m, β=0.5°. The unit of the areas is m2.

Figure 5. Structure of the simulator

Figure 6. Test results with different objective weights are presented in different color spheres. The radius of each sphere represents the runtime to reach the coverage rate of 99%. The bigger of the sphere, the lower of the corresponding coverage efficiency.

Figure 7. Simulation results in run #2. The path is displayed with grayscale line, the colorbar indicates the overall confidence of each cell, and red rectangle bounds the workspace.

Figure 8. Comparison of the results of run #5(left one) and run #6 (right one). The labeled transects reveal that run #6, which has a larger We, is more likely to explore distant areas than run #5.

Figure 9. Simulation results of a lawnmower path (left one) and a spiral path (right one). For the former, the inter-distance between the transects is 42 m. For the latter, the inter-distance between the zonal transects is 46 m, and the inter-distance between the meridional transects is 33 m.

Figure 10. Coverage capabilities of different strategies and parameters.

Figure 11. Confidence comparison of different strategies and parameters. The confidence refers to the average confidence of the cells in the workspace.

Figure 12. Path planning results of proposed method in different terrains. Both the trials applied the setup of run #2. The left terrain is generated by the same function mentioned in the previous subsection and the depth of the vehicle stays unchanged. The right terrain is generated by bathymetric data of Narragansett Bay, and the depth of the vehicle is set at 0 for this trial.

Table 1

Setup of the simulation model.

Parameters	Values
Region	500 m × 700 m
Average depth of terrain	60 m
Depth of the AUV	30 m
Angular coverage of multibeam	120${}^{°}$
Sampling frequency of multibeam	2 Hz
Velocity of AUV	1 m/s
Initial position of AUV	(200, 200)
Forward-looking angle of sonar [32]	0${}^{°}$
Staring angle of sonar	90${}^{°}$ (downward-looking)
Cell size of workspace	1 m

Table 2

Runs with different weight setups.

Run Number	1	2	3	4	5	6	7
$W_e$	0	0	0	0.25	0.25	0.5	0.33
$W_c$	0.75	0.5	0.25	0.25	0.5	0.25	0.33
$W_s$	0.25	0.5	0.75	0.5	0.25	0.25	0.33