1. Introduction
The ocean is a complex dynamical system. To understand ocean dynamics and increase accuracy of ocean models, measurements need to be taken with high spatio-temporal resolution according to the ocean phenomena under investigation [1,2,3,4].
Unmanned marine vehicles (UMVs), such as unmanned surface vehicles (USVs), gliders, and autonomous underwater vehicles (AUVs), equipped with sensors, have been widely employed to collect informative data of all kinds over scientific interest areas, for example, salinity, temperature, and chlorophyll content of the ocean, for applications of ecosystem monitoring, pollution management, marine resources exploration, and utilization [5,6,7,8,9,10]. However, a key challenge arises in that the vehicles are subject to limited energy resource or mission time, which limits data collection of the vehicle in one mission [11,12,13,14]. Therefore, it is of vital importance that the UMV can automatically plan an informative trajectory in variable ocean environments while satisfying constraints on collision avoidance, limited energy, and pre-specified mission time [15,16,17].
A variety of informative path planning methods have been proposed for adaptive sampling in an ocean environment. Mixed integer linear programming (MILP) is applied to find the path of AUV for adaptive sampling in the region of the greatest uncertainty [18]. The branch and bound (BNB) method is proposed for informative path planning to maximize the average reduction in variance of the estimated field [19]. MILP and BNB methods are easy to be implemented but are limited to discrete domains and often scale poorly in the size of the ocean environment. Rapidly exploring information gathering (RIG) algorithms are proposed to find a trajectory that maximizes an information quality metric within a pre-specified budget constraint [20]. While RIG algorithms can achieve efficient information gathering in continuous space with motion constraints, informative heuristics is not applied to guide the robot to higher information quality areas. Ma et al.[21,22] present an informative path planning method to maximize information gathering through sampling the environment; however, the method only provides guarantees on suboptimal solutions. A multi-objective particle swarm optimization (MOPSO) with a fuzzy comprehensive evaluation (FCE) method is proposed to formulate AUVs adaptive sampling problem while considering a spatiotemporal ocean environment and energy constraints [23]. The method can plan an AUV path in continuous space but requires heavy computational burden in a high dimensional search space.
Sample-based algorithms, such as rapidly-exploring random tree (RRT) [24], probabilistic roadmap (PRM) [25], and variants of them, with the advantage of generating a collision-free path quickly in continuous space, have been studied extensively in the past years. Rapidly-exploring random tree star (RRT*) [26], a variant of standard RRT, is guaranteed asymptotic optimality and has been widely used for solving the path planning problem [27,28,29,30,31]. Therefore, RRT* can be an alternative choice to be employed in the informative path planning problem for adaptive sampling. However, when it comes to maximum information gathering, standard RRT* is inefficient because the heuristics of distance in the algorithm structure gives no positive guidance for UMVs to collect informative data in regions of high scientific interest. Therefore, this research presents a variant of RRT*, referred to as rapidly-exploring adaptive sampling tree star (RAST*), that combines inspirations from RRT* with the tournament selection method and informative heuristics to achieve efficient searching of informative data in continuous space.
The novelty of RAST* includes: (1) utilizing the tournament selection method in replacement of random sample, so that more new branches will fall in higher scientific interest areas, which can result in finding optimal solutions quickly and saving computation time; (2) modifying the heuristic procedure from distance to information gathering per hour in order to grow branches that can gain more information with less traveling time. To our knowledge, this is the first work to integrate a tournament selection method, informative heuristic function, and sample-based algorithm into a unified path planner. To evaluate the performance of the proposed RAST* path planner, different scenarios are designed to compare the proposed RAST* path planner with rapidly-exploring random sampling tree star (RRST*), rapidly-exploring adaptive sampling tree (RAST), and particle swarm optimization (PSO). Additionally, proof-of-concept field experiments are performed in Lake Zhiyuan to assess the superiority and effectiveness of the proposed RAST* path planner.
The remainder of this research is organized as follows. Section 2 gives a detailed description of the mathematical model of the path planning problem for adaptive sampling. Section 3 outlines four path planning methods. Section 4 presents numerical experiments and results of different scenarios. Section 5 presents field experiments and results. Section 6 draws the conclusions and discusses future works.
2. Problem Formulation
This section formulates the path planning problem for adaptive sampling using a UMV. The objective is to find optimal pathP*among all feasible pathsPthat maximizes information gathering over an ocean area with features of scientific interestAand ocean currentsVcwhile considering constraints of obstaclesOand pre-specified mission timeT.
LetAbe the utility map generated by the needs of marine scientists and assumed to be known a priori. UMVs equipped with a CTD sensor or chlorophyll fluorometer can be used to measure the scientific interest areas. The utility map, a two-dimensional (2D) matrix with probability value in[0,1] , is a combination of features of scientific interest, such as salinity, chlorophyll fluorescence, dissolved oxygen, turbidity, etc. [32] The areas with a higher probability value of interest in the utility map are where scientists desire the UMVs to detect and collect relevant informative data. Ocean currents dataVcare obtained from the National Oceanic and Atmospheric Administration (NOAA). The utility mapA is generated based on sea temperature data from NOAA in this research. For more details, see: https://www.ncdc.noaa.gov/.
In practice, the path planning problem for UMV adaptive sampling operation is generally solved for long-term missions with durations of several days and trajectory lengths of hundreds of kilometers. The effect of vehicle dynamics is considered negligible and the vehicle is regarded as a point for the scale of this planning problem.
Considering that a UMVVis deployed to travel with velocityVfrom its initial positionP1= [x1,y1] to detect and collect ocean data, the potential path is represented by a sequence of discrete pointsP={P1,P2,...,Ph}, where h is the number of discrete points along the path andPhis the final position for the whole mission.
The path planning problem for adaptive sampling can be expressed as
P*=argmaxP∈PIG(V,V,Vc,A,O,T)s.t.V.=0,∀i∈{1,2,...,h}Pi∉OT<T
whereIGis the fitness function representing the information gathering for the whole mission.
2.1. Fitness Function Evaluation
Since informative data is associated with probability value of interest in the utility map, the goal of this research can be equivalently transformed to maximize the total probability value of interest along a potential path. Therefore, the fitness function can be formulated as the integral of probability value of interest along a potential path.
IG=∫1hA(Pi)·εi·di
εi=1,ifdistance(Pi,Pj)>dmin,∀j=1,...,i−10,else
whereA(Pi)is the probability value surrounding sample pointPi,εiis a parameter that evaluates whether the current position of the UMV in ocean environments has been sampled,dminis the sensor range. If the distance between the current positionPiof the UMV and the sampled waypoints is larger thandmin, the probability valueA(Pi)will be recorded, in case of repeated sampling.
2.2. Traveling Time Calculation
The UMV is assumed to keep constant thrust power and, equivalently, constant speed V during the whole mission. Influenced by ocean currentsVc, the water-referenced velocity of the UMV at a sample point in position(x,y) at time t can be obtained from Equation (4).
ut=Vcut−xy+Vcosϕtvt=Vcvt−xy+VsinϕtVt=ut2+vt2
whereVcut−xyandVcvt−xyare the velocity components of ocean currentsVcin position(x,y)at time t,ϕtare the heading angle of the UMV at time t.
Hence, traveling time T for one potential path can be calculated by the sum of time required for each discrete line segment.
T=∑i=1i=h−1|Pi+1−Pi|Vt
whereVtshould be recalculated for each discrete line segment.
3. Methods This section presents four path planning methods for adaptive sampling. The key idea is to generate the trajectory of UMV that maximizes information gathering over an ocean area with features of scientific interest in variable ocean environments. In addition, constraints of obstacles in environments and a pre-specified mission time of UMV is taken into consideration. Meanwhile, configuration space is pre-defined by marine scientists based on their interests. It can be any type of feature field, such as error variances, represented by uncertainty, or physical features of interest (temperature, salinity, eddies, etc.). A more generic setting is the higher value of a certain position in the feature field, indicating that it is generally worthwhile to send the UMV to take measurements. For close-to-reality test, the data for the features used in this study were obtained from the NOAA, in which irregularly shaped islands are regarded as obstacles. Normalized sea temperature data are utilized as the utility map. 3.1. RAST* RAST* builds a tree structure by connecting a set of nodes sampled from the configuration space and returns an optimal collision-free path. The pseudocode of RAST* is shown in Algorithm 1.
RAST* starts with initial nodeqinitinVertexand empty sets of E andVinvalid. In the main loop, instead of using the random sample procedure, the tournament selection method in Algorithm 2 is newly applied to electqtsamongMcandidate nodes that are randomly sampled from the configuration spaceA. (Line 3) Then, theHeuristicNodefunction in Algorithm 3, with ocean currents taking into consideration when calculating the traveling time, is newly developed to find the nodeqmaximumamong all existing nodes inVertexsuch that the vector line fromqmaximumtoqtsis with the maximum information gathering per hour. If ocean currents are greater than the maximum speed of the UMV, the algorithm will not generate branches towards this direction and will choose other nodes to extend branches. (Line 4) After that,qnewis generated by extending a step with step sizeδfromqmaximumtoqtsbased on Algorithm 4. (Line 5) If the line segment betweenqmaximumandqnewis collision free, which is checked by Algorithm 5 (Line 6), Algorithm 6 will be applied to find out a neighbor nodes setQm. If the distance from any nodes inVertextoqnewis less than radius r, the node will be included in the neighbor nodes setQm. Then, Algorithm 7 is executed to find the nodeqmaxthat can make the path, fromqinitpassing connected nodes until reachingqmaxthen toqnew, with the maximum information gathering per hour. (Line 7–15) Searching is performed by the newly developedHeuristicPathfunction. If the line segment betweenqmaxandqnewis collision free (Line 16), a new nodeqnewwill be added inVertex, a new branch(qmax,qnew)will be added in E,qmaxwill be the parent node ofqnew, the traveling time and information gathering fromqinittoqnewwill be calculated. (Line 17–21) Additionally, if traveling time fromqinittoqnewexceeds the pre-specified mission timeT,qnewwill be marked as the invalid nodesVinvalid. (Line 22–24) At the end of the main loop, the ratioPris calculated as the number of invalid nodes to the number of all existing nodes. (Line 27) The operator terminates the optimization when the first time that P exceeds a predefined maximum ratio valuePrand outputs the optimal path together with correlated information gathering.
RAST* differentiates itself from the other variants of RRT* in that tournament sample procedure and informative heuristic function are newly developed for path optimization in the algorithm structure. The arrangement of the tournament sample makes RAST* attempt to grow branches towards high scientific interest areas. The reason why the informative heuristic function is denoted as information gathering per hour is that it is beneficial to gain more information with less traveling time. To this end, these two contributions will result in generating the optimized path of UMV with more information gathering for an adaptive sampling mission.
Algorithm 1 RAST* |
Input: Utility mapA, ocean currents dataVc, velocity of UMVV, initial position of UMVqinit, obstaclesO, pre-specified mission timeT, tournament parameterM, step sizeδ, radius r, predefined maximum ratio valuePr. 1: Vertex←{qinit};Edge←⌀;Vinvalid←⌀;Graph=(Vertex,Edge); 2: whileP<Prdo 3: qts←TournamentSample(A,M); 4: qmaximum←HeuristicNode(qts,Vertex); 5: qnew←Steer(qmaximum,qts,δ); 6: if CollisionFree(qmaximum,qnew) then 7: Qm←Near(Vertex,qnew,r); 8: qmax←qmaximum; 9: cmax←HeuristicPath(qnew,qmaximum,qinit); 10: for eachqm∈Qmdo 11: if HeuristicPath(qnew,qm,qinit)>cmaxthen 12: cmax←HeuristicPath(qnew,qm,qinit); 13: qmax←qm; 14: end if 15: end for 16: if CollisionFree(qmax,qnew) then 17: Vertex←Vertex∪{qnew}; 18: Edge←Edge∪{(qmax,qnew)}; 19: qnew.Parent←qmax; 20: qnew.T←Time(qnew,Vertex,Edge); 21: qnew.IG←FitnessFun(qnew,Vertex,Edge); 22: ifqnew.T>Tthen 23: Vinvalid←Vinvalid∪{qnew}; 24: end if 25: end if 26: end if 27: P=Ratio(Vinvalid,Vertex); 28: end while 29: returnGraph=(Vertex,Edge); Output: The best fitness value and its correlated paths as the optimal solutions. |
Algorithm 2 Tournament Sample |
1: functionTournamentSample(A,M) 2: SelectMrandom points {q1,q2,...,qM} from the utility mapA; 3: qts←q1; 4: fori=2toMdo 5: ifA(qi)>A(qts)then 6: qts←qi; 7: end if 8: end for 9: returnqts 10: end function |
Algorithm 3 Heuristic Node |
1: functionHeuristicNode(qts,Vertex) 2: vn = Length(Vertex); %Find out how many nodes exist inVertex 3: mr = 0; 4: fori=1tovndo 5: IGi=Information(qi,qnew); %The information can be gathered fromqitoqnew 6: Ti=Time(qi,qnew); 7: ratei=IGi/Ti; 8: ifratei>mrthen 9: qmaximum←qi. 10: mr=ratei; 11: end if 12: end for 13: returnqmaximum 14: end function |
Algorithm 4 Steer |
1: functionSteer(qmaximum,qts,δ) 2: D = distance(qmaximum,qts); 3: if D >δthen 4: qnew=qts+(qmaximum−qts)∗δ/D 5: else 6: qnew←qmaximum 7: end if 8: returnqnew 9: end function |
Algorithm 5 Collision Free |
1: functionCollisionFree(qi,qj) 2: if Line segment fromqitoqjdoesn’t collide with obstacles. then 3: return 1 4: else 5: return 0 6: end if 7: end function |
Algorithm 6 Near |
1: functionNear(Vertex,qnew,r) 2: Qm←⌀ 3: Find out how many nodes exist inVertexand record the number as v. 4: fori=1to v do. 5: ifdistance(qi,qnew)<rthen 6: Qm←Qm∪qi 7: end if 8: end for 9: returnQm 10: end function |
Algorithm 7 Heuristic Path |
1: functionHeuristicPath(qnew,qm,qinit) 2: P=Connection(qnew,qm,qinit); %Connect branches from(qnew,qm)back to the initial positionqinit 3: IG=FitnessFun(P); 4: T=Time(P); 5: cmax=IG/T; 6: returncmax 7: end function |
RRST* is a variant of RRT*, and the idea behind this variant is similar to RAST* except that RRST* retains the random sample procedure of RRT* in Line 3. As for RRST*, Line 3 is replaced asqts←RandomSample(A); and the rest of the procedures of RRST* are the same as RAST*, shown in Algorithm 8. The RRST* randomly selects a pointqtsfrom the configuration space to extend its branch. Hence, the main advantage of RRST* is that it samples the configuration space with more randomness. Due to the randomness of RRST*, RRST* may need more iterations to find the optimized solution, and result in requiring more computational time than RAST*.
Algorithm 8 RRST* |
Input: Utility mapA, ocean currents dataVc, velocity of UMVV, initial position of UMVqinit, obstaclesO, pre-specified mission timeT, step sizeδ, radius r, predefined maximum ratio valuePr. 1: Vertex←{qinit};Edge←⌀;Vinvalid←⌀;Graph=(Vertex,Edge); 2: whileP<Prdo 3: qts←RandomSample(A); 4: qmaximum←HeuristicNode(qts,Vertex); 5: qnew←Steer(qmaximum,qts,δ); 6: if CollisionFree(qmaximum,qnew) then 7: Qm←Near(Vertex,qnew,r); 8: qmax←qmaximum; 9: cmax←HeuristicPath(qnew,qmaximum,qinit); 10: for eachqm∈Qmdo 11: if HeuristicPath(qnew,qm,qinit)>cmaxthen 12: cmax←HeuristicPath(qnew,qm,qinit); 13: qmax←qm; 14: end if 15: end for 16: if CollisionFree(qmax,qnew) then 17: Vertex←Vertex∪{qnew}; 18: Edge←Edge∪{(qmax,qnew)}; 19: qnew.Parent←qmax; 20: qnew.T←Time(qnew,Vertex,Edge); 21: qnew.IG←FitnessFun(qnew,Vertex,Edge); 22: ifqnew.T>Tthen 23: Vinvalid←Vinvalid∪{qnew}; 24: end if 25: end if 26: end if 27: P=Ratio(Vinvalid,Vertex); 28: end while 29: returnGraph=(Vertex,Edge); Output: The best fitness value and its correlated paths as the optimal solutions. |
3.3. RAST
RAST is a variant of RRT. The main loop of the RAST follows the general structure outlined in Algorithm 9. As can be seen from Algorithms 1 and 9, the difference between these two algorithms lies in that RAST lacks the procedures of connecting more “informative” branches in Line 7–15 in Algorithm 1. Even though, this approach can guide the branches to grow towards high scientific interest areas. However, similar to RRT, RAST is not asymptotically optimal.
Algorithm 9 RAST |
Input: Utility mapA, ocean currents dataVc, velocity of UMVV, initial position of UMVqinit, obstaclesO, pre-specified mission timeT, tournament parameterM, step sizeδ, predefined maximum ratio valuePr. 1: Vertex←{qinit};Edge←⌀;Vinvalid←⌀;Graph=(Vertex,Edge); 2: whileP<Prdo 3: qts←RandomSample(A,M); 4: qmaximum←HeuristicNode(qts,Vertex); 5: qnew←Steer(qmaximum,qts,δ); 6: if CollisionFree(qmax,qnew) then 7: Vertex←Vertex∪{qnew}; 8: Edge←Edge∪{(qmax,qnew)}; 9: qnew.Parent←qmax; 10: qnew.T←Time(qnew,Vertex,Edge); 11: qnew.IG←FitnessFun(qnew,Vertex,Edge); 12: ifqnew.T>Tthen 13: Vinvalid←Vinvalid∪{qnew}; 14: end if 15: end if 16: P=Ratio(Vinvalid,Vertex); 17: end while 18: returnGraph=(Vertex,Edge); Output: The best fitness value and its correlated paths as the optimal solutions. |
3.4. PSO
PSO is a population-based stochastic optimization algorithm discovered through simulation of the social behavior of a bird flock [33]. PSO is possessed with the advantages of easy implementation and sufficient solution diversity. Therefore, PSO is compared with the three aforementioned methods. The overview of the PSO path planner can be found in [34,35], and the pseudo code of PSO is shown in Algorithm 10.
3.5. Computational Complexity
The time complexity for RRT is discussed in detail in [26] and given as O(nlogn), where n denotes the total number of iterations. Time complexity is defined as the amount of time that is required by the algorithm to find the solution. RAST*, RRST*, and RAST are inspired by RRT, the additional steps of intelligent sampling procedure that have been introduced in these three algorithms have complexities that are insignificant enough to have an effect on the complexity of the algorithm. Hence, these three algorithms have almost the same time complexity as that of RRT, but the value of n can be significantly reduced in terms of RAST*. RAST* is able to generate better solutions because the newly generated nodes are concentrated towards high scientific interest regions.
Algorithm 10 PSO |
Input: Utility mapA, ocean currents dataVc, velocity of UMVV, initial position of UMVP1, obstaclesO, pre-specified mission timeT, parameterc1,c2, w andwdamp, population size K, maximum number of iterationsIterand number of control points n. 1: Initialize the position and velocity of each particle. 2: fori = 1 toIterdo 3: for k = 1 to K do 4: vk(i+1)=w·vk(i)+c1·Rand1·(ppbest(i)−p(i))+c2·Rand2·(pgbest(i)−pk(i)) 5: pk(i+1)=pk(i)+vk(i+1) 6: IGk(i+1)=FitnessFun(pk(i+1)) 7: ifIGk(i+1)<IGpbest(i)then 8: ppbest(i+1)=pk(i+1) 9: else 10: ppbest(i+1)=ppbest(i) 11: end if 12: ifIGpbest(i+1)<IGgbestthen 13: pgbest(i+1)=ppbest(i+1) 14: else 15: pgbest(i+1)=pgbest(i) 16: end if 17: end for 18: w=w·wdamp 19: end for Output: The best fitness value and its correlated paths as the optimal solutions. |
4. Numerical Experiments
To evaluate the performance of the proposed RAST* for solving the path planning problem for adaptive sampling, all numerical experiments are carried out in Matlab R2018a under Windows 10 on a computer with Intel(R) Core(TM) i7-6700HQ CPU @ 3.40GHz / 16.0 GB RAM. The proposed RAST* is compared with RRST*, RAST, and standard PSO. The parameters of PSO are set asc1=1,c2=1,w=1, andwdamp=0.98, population sizeK=500, maximum number of iterationsIter=100and number of control pointsn=5. The sensor rangedminis set as 1 km. In particular, the influence of parameters (step sizeδ, maximum ratio valuePr) of RAST* is analyzed before performing scenarios.
The utility map is generated based on sea temperature data from NOAA in the Gulf of Mexico in this research. The website of NOAA provides netCDF files for users to do research. Matlab can decode the netCDF files and draw a figure based on a two dimensional array. Figure 1 shows the geographical map for the Gulf of Mexico, and two areas are selected for scenario 1 and 2.
4.1. Preliminary: Parameter Analysis
RAST* has two parameters to adjust that are step sizeδand maximum ratio valuePr , since the best values of these two parameters differ on different problems. To find proper values, statistical parameter analyses are performed over a scientific interest area of 100 km × 70 km for adaptive sampling in a variable ocean environment without obstacles. Computation time and information gathering are applied to evaluate the performance. Results are presented in Figure 2.
Step size sets the distance between the current node and newly generated node. As can be observed from Figure 2a, the larger the step size is, the lower the computation time is, but the less the information gathering is. A step size of 1 km is too computation time consuming when compared to the other three step sizes, although it returns the maximum information gathering. A step size of 7 km is the other way around. A step size of 3 and 5 km have almost the same information gathering, but a step size of 3 km has a higher computation time. Therefore,δ=5is the proper value for the step size in this research.
The maximum ratio value determines the termination condition. It can be noted from Figure 2b that the larger the ratio value is, the higher the computation time is and the more the information gathering is. SincePr=30%andPr=50%have almost the same information gathering andPr=30%is with less computation time,Pr=30%is the proper value for the maximum ratio value in this research.
4.2. Scenario 1: Adaptive Sampling in Variable Ocean Environment without Obstacles
This scenario discusses the performance of RAST*, RRST*, RAST, and PSO over a scientific interest area without obstacles in the Gulf of Mexico on 24 December 2017. The utility map is the normalized sea temperature data of100×70grids and each grid represents an area of 1 km × 1 km.
Figure 3 displays the results of the optimized paths produced by the four path planners. A UMV, with a constant speed of 2 m/s, starts from(20,5)and follows the planned path to collect information within pre-specified mission time of 50 h. The utility map denotes the probability value of scientific interest (blue = low scientific interest, yellow = high scientific interest), from which we can observe that the proposed RAST* produces the optimal path that explores and covers high scientific interest areas.
Moreover, a 50-run Monte Carlo simulation, which refers to that the numerical simulation is run repeatedly 50 times to check the performance (standard deviation) of each algorithm, is conducted, and results are shown in Table 1. It can be noted that RAST* and RRST* return a similar mean fitness value and standard deviation, but RAST* is computationally faster than RRST*. It is clearly discussed in Section 3.5 that RAST*, RRST*, and RAST have the same time complexity as that of RRT, that is O(nlogn), where n denotes the total number of iterations. It means that RAST* can find the optimal solution with less iterations. The main reason for this is that RRST* searches the configuration space with randomness, while RAST* focuses more on high scientific interest areas. This demonstrates the advantage of applying the tournament selection method in the sample phase. RAST, without checking a more "informative” branch, performs poorly in all respects, which reveals that RAST needs significantly more number of iterations to find the optimized solution than that of RAST*. PSO is suboptimal compared to RAST*.
We can conclude that the proposed RAST* is superior to RRST* in terms of computation time, and RAST* is more efficient and effective than RAST and PSO, when performing adaptive sampling in a variable ocean environment without obstacles. 4.3. Scenario 2: Adaptive Sampling in Variable Ocean Environment with Obstacles
In this scenario, we examine the performance of RAST*, RRST*, RAST, and PSO over a scientific interest area with obstacles in the Gulf of Mexico on 24 December 2017. The utility map is the normalized sea temperature data of100×70grids, and each grid represents an area of 1 km × 1 km.
Figure 4 shows a comparison of the optimized paths produced by the four path planners in an obstacle environment. A UMV, with a constant speed of 2 m/s, starts from(95,5) and follows the planned path to collect information within a pre-specified mission time of 50 h. As can be noticed, the way passing through obstacles differs on different algorithms. The path of RAST goes downstream and makes good use of ocean currents so as to save traveling time, but the chosen road is with low scientific interest. The path of RRST* makes a detour around obstacles and wastes traveling time on where scientific interest is not high. RAST* and PSO choose the road that will encounter a short period of counter current but leads to high scientific interest areas quickly. Consequently, RAST* and PSO result in gaining more information than RRST* and RAST, as shown in "Maximum IG” in Table 2.
From Table 2, it can be concluded that neither PSO nor RAST can be selected for practical application because the standard deviation of PSO is too large and RAST is computation time consuming. RRST* lacks competitiveness due to low computational efficiency when compared to RAST*.
Among the four path planners, RAST* outperforms RRST*, RAST, and PSO, when performing adaptive sampling in variable ocean environment with obstacles. 4.4. Robustness Assessment
To further verify the performance of each algorithm, three different tests with different grid maps are presented to assess the robustness and performance of these algorithms. The first test involves ten randomly selected grid maps of50×35grids, and each grid represents an area of 3 km × 3 km. The second test involves ten randomly selected grid maps of100×70grids and each grid represents an area of 1 km × 1 km. The third test involves ten randomly selected grid maps of200×140 grids and each grid represents an area of 0.5 km × 0.5 km. The above three tests were performed with randomly selected areas from NOAA in the Gulf of Mexico on 24 December 2017. The input parameter of each algorithm is the same as those in Section 4.1. The information gathering of each algorithm about the three tests are shown in Table 3, Table 4 and Table 5.
As can be seen from the results in these tables, it is worth noting that in such scenarios, the RAST* still has a significantly higher chance of collecting more ocean data than the other three algorithms within pre-specified mission time. This indicates that the ability of information gathering of RAST* outperforms the RRST*, RAST, and PSO. In summary, these three tests demonstrate the robustness and performance of the proposed RAST*. 5. Field Experiments
To assess the superiority and effectiveness of the four path planners, field experiments were performed in Lake Zhiyuan, Shanghai, China. An autonomous surface vehicle (ASV), with easy deployment and real time data transmission, is employed to maximize water sample acquisition over a virtual scientific interest area with a pre-specified mission time. The ASV, shown in Figure 5a, is actuated by one thruster and one rudder at the back, and equipped with a lithium-ion rechargeable battery, an inertial measurement unit (IMU) and real-time kinematic GPS for localization, a pixhawk and wireless data transmission module for remote control, and some measurement devices, such as temperature sensor and depth sensor.
It is assumed that the lake is calm with very little movement of water and the currents of the lake are ignored. The ASV is tasked to travel with the speed of 1.2 m/s and finish the sampling mission in 60 s. The utility map for field experiments is a combination of real obstacles in the Zhiyuan Lake and the NOAA temperature data in a randomly selected region. Numerical experiments are performed to generate the off-line optimal path for field experiments, shown in Figure 5b. During field experiments, the ASV follows discrete waypoints of an optimized trajectory generated by the four path planners. The performance characteristics of ASV are recorded and transmitted back to the ground station through a data transmission module in real time and the Mission Planner software can output the executed trajectory of the ASV, as shown in Figure 5c,d,e,f.
Table 6 records information gathering of ASV along executed paths based on the four path planners in the virtual utility map with the same constant speed of ASV and the same mission time. It can be noted that the ASV, following the optimized path generated by the RAST* path planner, can gather more information than the other three path planners.
Experimental results further demonstrate the superiority and robustness of the proposed RAST*. 6. Conclusions In this research, we presented a novel variant of the sample-based path planning method for adaptive sampling. The proposed RAST* method integrates a tournament selection method, informative heuristic function, and tree structure of RRT* into a unified path planner. This arrangement enhances exploration and coverage in high scientific interest areas while saving computation time. We validate the proposed RAST* path planner through numerical experiments with a variable ocean environment. The numerical results show that RAST* generates a collision-free and near optimal path of the UMV with more information gathering and less computation time while satisfying constraints on pre-specified mission time, when compared to RRST*, RAST, and PSO. Furthermore, results of field experiments demonstrate the superiority and effectiveness of the proposed RAST* path planner.
In the future, we plan to consider more complicated scenarios, such as avoiding dynamic obstacles [36,37], real-time path re-planning [38,39,40] and cooperation of multiple vehicles [41,42]. Another extension of this work is to develop adaptive stepsize [43] in the RAST* algorithm for further saving computation time.
Algorithms | Maximum IG | Mean IG | Std | Mean Computation Time (s) |
---|---|---|---|---|
RAST* | 244.3 | 222.0 | 9.67 | 35.7 |
RRST* | 247.2 | 227.5 | 9.65 | 115.6 |
RAST | 213.6 | 192.3 | 9.65 | 3463.7 |
PSO | 239.9 | 212.2 | 14.01 | 60.9 |
Algorithms | Maximum IG | Mean IG | Std | Mean Computation Time (s) |
---|---|---|---|---|
RAST* | 237.8 | 220.1 | 9.83 | 103.1 |
RRST* | 229.7 | 220.1 | 5.45 | 609.9 |
RAST | 213.3 | 191.0 | 8.89 | 2161.7 |
PSO | 236.6 | 198.2 | 12.85 | 149.4 |
Scenario | RAST* | RRST* | RAST | PSO |
---|---|---|---|---|
1 | 85.5 | 83.7 | 74.0 | 83.4 |
2 | 89.7 | 85.1 | 83.5 | 86.9 |
3 | 76.3 | 71.8 | 70.8 | 71.1 |
4 | 96.6 | 97.0 | 92.5 | 96.4 |
5 | 78.6 | 75.0 | 74.8 | 73.6 |
6 | 81.2 | 80.5 | 75.6 | 76.5 |
7 | 85.0 | 83.6 | 81.9 | 81.6 |
8 | 88.1 | 85.5 | 83.2 | 86.3 |
9 | 83.3 | 81.2 | 78.5 | 80.9 |
10 | 91.5 | 90.3 | 86.2 | 89.2 |
Scenario | RAST* | RRST* | RAST | PSO |
---|---|---|---|---|
1 | 153.7 | 152.1 | 152.8 | 155.4 |
2 | 224.2 | 203.9 | 182.3 | 219.6 |
3 | 214.6 | 212.5 | 208.5 | 198.7 |
4 | 200.3 | 178.8 | 179.7 | 197.3 |
5 | 218.8 | 205.9 | 199.8 | 214.7 |
6 | 214.2 | 175.8 | 148.2 | 200.1 |
7 | 165.5 | 160.7 | 158.4 | 169.5 |
8 | 187.3 | 189.8 | 165.6 | 185.9 |
9 | 225.6 | 158.9 | 161.5 | 219.7 |
10 | 186.4 | 185.6 | 181.8 | 172.9 |
Scenario | RAST* | RRST* | RAST | PSO |
---|---|---|---|---|
1 | 409.5 | 372.4 | 405.6 | 407.8 |
2 | 488.6 | 456.0 | 458.4 | 454.4 |
3 | 476.7 | 432.6 | 426.6 | 465.4 |
4 | 409.4 | 365.9 | 335.8 | 387.6 |
5 | 415.2 | 402.3 | 389.6 | 359.1 |
6 | 389.1 | 380.4 | 365.0 | 390.5 |
7 | 495.8 | 455.9 | 468.9 | 489.2 |
8 | 438.0 | 408.9 | 398.6 | 388.4 |
9 | 491.6 | 495.4 | 466.1 | 480.3 |
10 | 377.9 | 355.1 | 341.2 | 358.6 |
Algorithms | IG |
---|---|
RAST* | 29.03 |
RRST* | 28.68 |
RAST | 23.75 |
PSO | 25.88 |
Author Contributions
C.X. and Z.Z. proposed the main idea and wrote the manuscript; C.X. designed the algorithm and performed the numerical simulations; C.X., H.Z., D.L., Z.Z. and C.Y. worked together to develop the platform and run the field experiments; Z.Z. and L.L. supervised the research work. All authors have read and agreed to the published version of the manuscript.
Funding
This work is supported by the National Natural Science Foundation of China under Grant No.41706108 and No.41527901, the Shanghai Sailing Program under Grant No.17YF1409600, and the open project of Qingdao National Laboratory for Marine Science and Technology under Grant No.QNLM2016ORP0104.
Conflicts of Interest
The authors declare no conflict of interest.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
© 2020. This work is licensed under http://creativecommons.org/licenses/by/3.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.
Abstract
This research presents a novel sample-based path planning algorithm for adaptive sampling. The goal is to find a near-optimal path for unmanned marine vehicles (UMVs) that maximizes information gathering over a scientific interest area, while satisfying constraints on collision avoidance and pre-specified mission time. The proposed rapidly-exploring adaptive sampling tree star (RAST*) algorithm combines inspirations from rapidly-exploring random tree star (RRT*) with a tournament selection method and informative heuristics to achieve efficient searching of informative data in continuous space. Results of numerical experiments and proof-of-concept field experiments demonstrate the effectiveness and superiority of the proposed RAST* over rapidly-exploring random sampling tree star (RRST*), rapidly-exploring adaptive sampling tree (RAST), and particle swarm optimization (PSO).
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer