CN109508016A - Water quality sampling cruise ship path planning optimal method - Google Patents

Abstract

The invention discloses a kind of water quality sampling cruise ship path planning optimal methods, belong to lake basins water quality sampling and Path Planning Technique field.The method obtains the global optimum path from starting point to target point first in the two-dimensional coordinate figure of lake surface, using A* algorithm；Then same area path or more new location area cartographic information in the local optimum path replacement A* algorithm for using Artificial Potential Field Method to obtain zone of ignorance；Global optimum path is obtained after integrating to all path points.The present invention uses A* algorithm combination modified embedded-atom method, the advantages of two methods algorithm can be made full use of, a kind of water quality sampling cruise ship path planning optimal method is provided, this method efficiently solves path planning problem and local minimum problem under component environment unknown situation, reduce equipment cost, furthermore algorithm search is high-efficient, spends time cost few.

Description

Water quality sampling cruise ship path planning optimal method

Technical field

The invention mainly relates to lake basins water quality samplings and Path Planning Technique field.One kind is referred specifically in environment divisionWater quality cruise ship path planning optimization method under unknown situation.

Background technique

As the mankind make full use of environment, many environmental problems increasingly show, and wherein the quality of water environment is to peopleDaily life have significant impact, therefore the monitoring of lake water quality of river is particularly important.Water quality monitoring need to water quality intoRow sampling, so improving the efficiency of water quality sampling, the cost of reduction water quality sampling can generate direct influence to water quality monitoring.OneThe suitable current environment of kind, the method that can quickly cook up sampling optimal path can improve significantly sampling efficiency while reduce samplingCost.Currently have many conventional methods and intelligent method is made to solve the path planning problem of cruise ship.A star algorithm (A*Algorithm, referring to bibliography [1]: Chen Y, Chen J Y.Application of Jacobian defined directinteraction coefficient in DRGEP-based chemical mechanism reduction methodsusing different graph search algorithms[J].Combustion and Flame,2016,174:77-84.) and Artificial Potential Field Method is wherein more classical algorithm, and A* algorithm can quickly solve path planning problem known to environment,It is inefficient for the path planning of circumstances not known.Artificial Potential Field Method is (referring to bibliography [2]: Yao P, Zhao S.Three-Dimensional Path Planning for AUV Based on Interfered Fluid Dynamical SystemUnder Ocean Current [J] .IEEE Access, 2018,6:42904-42916.) it is then a kind of for simple environmentThe effective settling mode of path planning problem, in the path planning problem existing defects of processing complex environment.Therefore, using A* algorithmIn conjunction with modified embedded-atom method, the advantages of two kinds of algorithms can be made full use of, path under component environment unknown situation is efficiently solvedPlanning problem.The algorithm solves the problems, such as local minimum, reduces equipment cost, and furthermore algorithm search is high-efficient, spends the timeCost is few.

Summary of the invention

In order to solve the problems in the existing technology, the present invention therefore, using A* algorithm combination modified embedded-atom method,The advantages of two methods algorithm can be made full use of, provides a kind of water quality sampling cruise ship path planning optimal method, this methodPath planning problem under component environment unknown situation is efficiently solved, equipment cost is reduced, furthermore algorithm search is high-efficient, spendsTime cost is few.

A kind of water quality sampling cruise ship path planning optimal method provided by the invention, specifically comprises the following steps:

Step 1: with the image of unmanned plane camera acquisition lake surface, image procossing is carried out using Grid Method, obtains lake surface twoCoordinate diagram is tieed up, zone of ignorance blank clear space domain representation carries out selection and the portion of path point in lake surface two-dimensional coordinate figureAdministration；

Step 2: in the two-dimensional coordinate figure of lake surface, the global optimum road from starting point to target point is obtained using A* algorithmDiameter；

Step 3: to obtained global optimum path from starting point to target point retrieval, judge whether current path point is targetPoint, if so, turning step 7；If not target point, further judge whether current path point is zone of ignorance, if it is not,Turn step 4；Otherwise turn step 5.

Step 4 stores current path point, and marches to next path point, updates current path point, returns to step 3.

Step 5 detects zone of ignorance environment using laser range finder if current path point is zone of ignorance,Local optimum path is obtained using modified embedded-atom method, turns step 6；Else if being unable to get local optimum path, then existZone of ignorance cartographic information is updated in two-dimensional coordinate figure, returns to step 2.

Step 6: same area path in the local optimum path replacement A* algorithm that Artificial Potential Field Method is obtained returns to the 4thStep；

Step 7 integrates the path point in global optimum path.

The integration refers to:

From the off, the path point after retrieving, judges whether starting point and the line of this path point pass through barrier, i.e.,Whether with barrier intersection point is had, if next path point is retrieved in continuation backward without intersection point；If there is intersection point, with current searching routeThe previous path point of point is anchor point, connection source and anchor point, and is that new starting point continuation is retrieved backward with anchor point, is gone forward side by sideRow barrier intersection point judgement, until retrieving to target point.

Described is as follows the step of obtaining local optimum path using modified embedded-atom method:

Step 5.1: the lake surface information obtained using laser range finder is carried out image procossing and is converted into two-dimensional coordinate gridFigure, setting improve Artificial Potential Field algorithm relevant parameter, including investigative range r, gravitation gain coefficient k, repulsion gain coefficient m,The number of iterations j, barrier influence distance d, step-length p；

Step 5.2: cartographic information in completion investigative range, whether the local path target point after determining map rejuvenation is barrierHinder object: if YES, then returning to step 2；If NO, then it calculates current path point position X and influences apart from interior barrierRepulsion F_repWith the gravitation F of target point_att；

Repulsion F of the barrier to current path point position X_repCalculation formula is as follows:

Wherein

U_repIt (X) is improvement repulsion potential field function, X_oPosition of a certain barrier in two-dimensional coordinate is represented, m repairs for repulsionPositive divisor index, Xg are position of the target point in two-dimensional coordinate, F_rep1、F_rep2Respectively repulsion is decomposed works as in barrier directionThe component in target point direction is directed toward in preceding path point direction, current path point.As current path point position X and Obstacle Position X_o'sDistance | X-Xo | when being greater than barrier influences distance d, barrier generates current path point without active force.With cruise ship and meshThe distance of punctuate is closer, and the repulsion being subject to is smaller, solves the problems, such as the goal nonreachable of traditional artificial potential field method.

F_rep1、F_rep2Specific formula is as follows:

It is obtained by formula, as the value of n is bigger, the repulsion that obtained current path point is directed toward target point direction is bigger,Effect is more obvious, but calculation amount is also gradually increased, and is increased algorithm time cost, is learnt by many experiments in two-dimensional coordinateMiddle selection n=2 both can guarantee the accuracy of result while reduce calculation amount, shorten Riming time of algorithm；

Step 5.3: calculating target point to the gravitation of current path point, calculate in influence apart from interior barrier to current roadThe repulsion of diameter point obtains the resultant force of gravitation and repulsion suffered by the current path point；

Step 5.4: it calculates the resultant force of current path point and determines whether resultant force is 0, it is random using orientation if it is 0A method is taken, next path point is found；If not being 0, according to resultant direction traveling one step suffered by current path pointDistance；

Step 5.5: judging if YES, then to adopt in path is advanced with the presence or absence of problem is shaken repeatedly in certain two pointWith randomized is oriented in step 5.4, if NO, then the resultant direction traveling one step being subject to according to current path point away fromFrom；

Step 5.6: determining whether to reach 2000 upper limits of the number of iterations, still can not reach target point, if YES, thenReturn to step 2；If NO, then it reaches target point and records travel path point in Artificial Potential Field Method later；

The present invention has the advantages that

(1) image procossing is carried out to target lake environment image, lake surface image is converted to two-dimensional grid image coordinate, savedAbout cruise ship time for cooking up optimal path.

(2) present invention is able to solve the path planning problem under circumstances not known, allows image capture device precision not high, canTo carry out fuzzy acquisition to environment, equipment cost has been saved, it is higher to the adaptability of environment.

(3) the invention proposes modified embedded-atom method, the ship that cruises is less prone to problem in the searching process of path, improvesThe stability of path planning algorithm, so that the effect of path planning is also more stable.

(4) to the integration of optimal path point, the total angle of rotation degree of cruise foot on the way is shortened, cruise shipping agency is reducedThe total distance sailed, thus for save water quality sampling cruise ship electric quantity consumption play the role of it is very big so that cruise ship continuation of the journeyAbility improves.

Detailed description of the invention

Fig. 1 is the water quality sampling cruise total block flow diagram of ship path planning in the present invention；

Fig. 2 is the A* algorithm flow chart in the present invention；

Fig. 3 is the modified embedded-atom method local paths planning flow chart in the present invention.

Specific embodiment

The present invention is described in detail with reference to the accompanying drawing.

The present invention provides a kind of water quality sampling cruise ship path planning optimal method, is combined and is improved manually using A* algorithmPotential field method finds optimal path.Process as shown in Figure 1, water quality sampling cruise ship paths planning method provided by the invention, specificallyInclude the following steps:

Step 1: acquiring lake surface image with unmanned plane camera, image procossing obtains lake surface two-dimensional coordinate figure.

Since the limitation of unmanned plane camera device precision can not acquire detailed lake surface image, there are partial region image lettersBreath is not zone of ignorance entirely, carries out image procossing using Grid Method and obtains lake surface two-dimensional coordinate figure, zone of ignorance blank is without barrierHinder region to indicate, the selection and deployment of path point are carried out in lake surface two-dimensional coordinate figure；

Step 2: the global optimum path from starting point to target point is obtained using A* algorithm on lake surface two-dimensional coordinate figure,As shown in Fig. 2, specifically comprising the following steps:

(2.1) according to the lake surface two-dimensional coordinate figure of acquisition, the relevant parameter of A* algorithm is set, OPEN list is starting point, is depositedStorage was searched for but still unbeaten non-obstacle object point, CLOSE list be obstructed paths point and the path point passed by,Optimal_path is that empty array is used for optimal storage path point；

(2.2) from current path point to 8 direction neighbour's lattice extensions around, path reachable around current path point is foundPoint excludes in CLOSE list obstructed paths point and the path point passed by, calculates separately other path point valuation functionsf(X)；

The valuation functions formula is as follows:

F (X)=h (X)+g (X)

Wherein h (X) is distance of the starting point to current path point X, and g (X) is distance of the current path point X to target point, away fromIt is specific as follows from the Euclidean distance calculation formula that calculation formula is two-dimensional space:

(X₁,Y₁)、(X₂,Y₂) it is different coordinates, d is coordinate (X₁,Y₁) and (X₂,Y₂) the distance between two points.

(2.3) valuation functions f (X) the smallest path point as next path point and is stored in Optimal_path arrayIn；If its valuation functions is updated in the existing OPEN list of remaining path point, conversely, being then directly stored in OPEN list；

(2.4) when reaching next path point, current path point is updated, this path point is stored in CLOSE list, determines thisWhether path point is target point, is then to terminate, obtains global optimum path；It is no, then return step (2.2).

Step 3: judging whether current path point is mesh to obtained global optimum path from starting point to target point retrievalPunctuate, if so, going to step seven；If not target point, further judge whether current path point is zone of ignorance, if notIt is to go to step four；Otherwise five are gone to step.

Step 4 stores current path point, and marches to next path point, updates current path point, return step three.

Step 5 detects zone of ignorance environment using laser range finder if current path point is zone of ignorance,Local optimum path is obtained using modified embedded-atom method, goes to step six；Else if be unable to get local optimum path, then,Update zone of ignorance cartographic information in two-dimensional coordinate figure, return step two.

When the ship that cruises is travelled according to global optimum's path point by way of zone of ignorance, using laser range finder to zone of ignoranceEnvironment is detected, using modified embedded-atom method, using current path point as local path starting point, laser range finder detection rangeGlobal path point is local path target point at 2/3, plans local optimal path；If final path, basis cannot be obtainedDetection result updates zone of ignorance cartographic information, return step two.

Described obtains local optimum path, process as shown in Figure 3 using modified embedded-atom method, the specific steps are as follows:

(5.1) the lake surface information obtained using laser range finder is carried out image procossing and is converted into two-dimensional coordinate grid map, ifSurely the relevant parameter of Artificial Potential Field algorithm is improved, including investigative range is 5 lattice *, 5 lattice, gravitation gain coefficient k is 14, repulsion gainCoefficient m is 4.2, the number of iterations j is 2000, barrier influence distance d is 2.5, step-length l is 0.5；

(5.2) completion zone of ignorance cartographic information, whether the local path target point after determining map rejuvenation is barrier:It is, then return step two；It is no, then it calculates current path point X and influences the repulsion F apart from interior barrier_repWith the gravitation of target pointF_att；

Repulsion F of the barrier to current path point X_repCalculation formula is as follows:

Wherein

F_rep1、F_rep2Respectively repulsion, which is decomposed, is directed toward current path point direction, current path point direction target point in barrierThe component in direction, m are repulsion modifying factor index, and Xg is position of the target point in two-dimensional coordinate.U_repIt (X) is improvement repulsionPotential field function, X_oPosition of a certain barrier in two-dimensional coordinate is represented, when current path point is at a distance from barrier | X-X_o| it is bigWhen barrier influences distance d, barrier generates current path point without active force.As distance objective point is closer, repulsion is got overIt is small, solve the problems, such as goal nonreachable.

It is obtained by above-mentioned two formula:

It is obtained by formula, as the value of n is bigger, obtained repulsion is bigger, and effect is more obvious, and same calculation amount increases,N=2 is selected both to can guarantee the accuracy of result while having reduced calculation amount in two-dimensional coordinate.

Gravitation F of the target point to current path point_attCalculation formula is as follows:

F_att=-grad [U_att(X)]=k (X_g-X)

Wherein:

U_attFor gravitational potential field function, current path point is proportional to target point and current path point to suffered gravitationSquare of distance, proportionality coefficient k.

(5.3) target point is calculated to the gravitation of current path point, and calculates influence apart from interior barrier to current path pointRepulsion, and then obtain the resultant force of the gravitation and repulsion；

(5.4) determine whether resultant force is 0: being, then a method is taken using orientation at random；It is no, then according to suffered by current path pointThe resultant direction traveling one step distance arrived；

(5.5) judge to shake problem repeatedly with the presence or absence of certain two point in path is advanced, as current path point X (i) withPath point X (i-2) is identical, i be path point serial number, then it is assumed that the two path points are shaken, at this point, then using orientation withMachine takes a method, finds next path point, updates current path point, no, then is advanced according to the resultant direction that current path point is subject toOne step distance updates current path point；

(5.6) determine whether current path point is target point, if it is, record travel path point, obtains local optimumPath terminates；Otherwise determine whether to reach 2000 upper limits of the number of iterations, if it is, return step (5.3), otherwise basisThe resultant direction traveling one step distance that current path point is subject to updates current path point.

Step 6: same area path in the local optimum path replacement A* algorithm that Artificial Potential Field Method is obtained, returns to stepRapid four.

Step 7: N number of path point in global optimum path is integrated, specifically:

From starting point x₁Along the global optimum path searching route point { x backward of planning_k| k=2,3, N } and, traversal is adjacentNearly barrier node, if x₁、x₂Line and barrier without intersection point, then continue to retrieve backward, until x₁With x_mThe line of (m≤N)Across barrier, x is taken_m-1As anchor point, with x₁With x_m-1As endpoint, by x₁With x_m-1Line replacement same endpoints between roadDiameter, and with x_m-1As new starting point, continue searching route point backward, until reaching target point.

The orientation that the present invention uses in step (5.4), step (5.5) takes a method at random, the specific steps are as follows:

Step A: it is the line L of current path point X and target point；

Step B: the straight line across X and vertical L is done, and takes two o'clock a, b apart from X unit step-length on straight line；

Step C: the point X on line L apart from X unit step-length is taken₁It does across X₁And the straight line of vertical L, and take on straight line away fromFrom X₁Two o'clock c, d of one step；

Step D: in a, b, c, d, X₁Appoint to take in 5 points and is a little used as next path point.

Claims (5)

Translated fromChinese

1.水质采样巡航船路径规划最优化方法，其特征在于：所述方法具体包括如下步骤，1. A water quality sampling cruise ship path planning optimization method, characterized in that: the method specifically comprises the following steps,第1步：用无人机摄像头采集湖面的图像，采用栅格法进行图像处理，得到湖面二维坐标图，未知区域用空白无障碍区域表示，在湖面二维坐标图中进行路径点的选取与部署；Step 1: Use the drone camera to collect the image of the lake surface, and use the grid method to process the image to obtain a two-dimensional coordinate map of the lake surface. The unknown area is represented by a blank barrier-free area, and the path points are selected in the two-dimensional coordinate map of the lake surface. and deployment;第2步：在湖面的二维坐标图中，利用A*算法得到自起点至目标点的全局最优路径；Step 2: In the two-dimensional coordinate diagram of the lake surface, use the A* algorithm to obtain the global optimal path from the starting point to the target point;第3步：对得到的全局最优路径从起点向目标点检索，判断当前路径点是否为目标点，如果是，转第7步；如果不是目标点，进一步判断当前路径点是否为未知区域，如果不是，转第4步；否则转第5步；Step 3: Retrieve the obtained global optimal path from the starting point to the target point, determine whether the current path point is the target point, if so, go to step 7; if it is not the target point, further determine whether the current path point is an unknown area, If not, go to step 4; otherwise, go to step 5;第4步，存储当前路径点，并行进至下一个路径点，更新当前路径点，返回第3步；Step 4, store the current waypoint, and proceed to the next waypoint, update the current waypoint, and return to step 3;第5步，如果当前路径点为未知区域，利用激光测距仪对未知区域环境进行探测，采用改进人工势场法获取局部最优路径，转第6步；否则如果无法得到局部最优路径，则更新二维坐标图中的未知区域地图信息，返回第2步；Step 5, if the current path point is an unknown area, use the laser range finder to detect the environment of the unknown area, use the improved artificial potential field method to obtain the local optimal path, and go to step 6; otherwise, if the local optimal path cannot be obtained, Then update the map information of the unknown area in the two-dimensional coordinate map, and return to step 2;第6步：将人工势场法得到的局部最优路径替换A*算法中相同区域路径，返回第4步；Step 6: Replace the local optimal path obtained by the artificial potential field method with the same regional path in the A* algorithm, and return to step 4;第7步，对全局最优路径中的路径点进行整合。Step 7: Integrate the waypoints in the global optimal path.2.根据权利要求1所述的水质采样巡航船路径规划最优化方法，其特征在于：第2步所述的利用A*算法得到全局最优路径，具体包括如下步骤：2. The water quality sampling cruise ship path planning optimization method according to claim 1, characterized in that: the use of the A* algorithm described in the second step to obtain the global optimal path specifically comprises the following steps:(2.1)根据获取的湖面二维坐标图，设定A*算法的相关参数，OPEN列表为起点，存储搜索过但尚未走过的非障碍物点，CLOSE列表为障碍物路径点和已经走过的路径点，Optimal_path为空数组用于存储最优路径点；(2.1) According to the acquired two-dimensional coordinate map of the lake, set the relevant parameters of the A* algorithm, the OPEN list is the starting point, and the non-obstacle points that have been searched but have not been walked are stored, and the CLOSE list is the obstacle path points and the ones that have been walked , Optimal_path is an empty array to store the optimal waypoint;(2.2)自当前路径点向周围8个方向邻格扩展，寻找当前路径点周围可达的路径点，排除CLOSE列表中的障碍物路径点和已经走过的路径点，分别计算其它路径点评估函数；(2.2) Expand from the current waypoint to the surrounding 8 directions, find the accessible waypoints around the current waypoint, exclude the obstacle waypoints and the waypoints that have been traveled in the CLOSE list, and calculate the evaluation of other waypoints respectively. function;(2.3)将评估函数最小的路径点作为下一路径点并存入Optimal_path数组中；其余路径点若已存在OPEN列表中，则更新其评估函数，反之，则直接存入OPEN列表；(2.3) Take the path point with the smallest evaluation function as the next path point and store it in the Optimal_path array; if the remaining path points already exist in the OPEN list, update their evaluation functions, otherwise, directly store them in the OPEN list;(2.4)到达下一路径点时，更新当前路径点，将此路径点存入CLOSE列表中，判定此路径点是否为目标点，是，则结束，得到全局最优路径；否，则返回步骤(2.2)。(2.4) When the next path point is reached, update the current path point, store the path point in the CLOSE list, and determine whether the path point is the target point. (2.2).3.根据权利要求1所述的水质采样巡航船路径规划最优化方法，其特征在于：第5步所述的采用改进人工势场法得到局部最优路径的步骤如下：3. water quality sampling cruise ship path planning optimization method according to claim 1, is characterized in that: the step of adopting improved artificial potential field method described in the 5th step to obtain local optimal path is as follows:步骤5.1：利用激光测距仪得到的湖面信息，进行图像处理转化为二维坐标栅格图，设定改进人工势场算法的相关参数，包括探测范围、引力增益系数、斥力增益系数、迭代次数、障碍物影响距离和步长；Step 5.1: Use the lake surface information obtained by the laser rangefinder to convert the image into a two-dimensional coordinate grid map, and set the relevant parameters of the improved artificial potential field algorithm, including the detection range, the gravitational gain coefficient, the repulsive force gain coefficient, and the number of iterations , Obstacle influence distance and step length;步骤5.2：判定地图更新后的局部路径目标点是否为障碍物：如果为是，则返回第2步；如果为否，则计算当前路径点位置X与影响距离内障碍物的斥力F_rep和目标点的引力F_att；Step 5.2: Determine whether the local path target point after the map update is an obstacle: if so, return to step 2; if no, calculate the repulsion force F_rep and the target between the current path point position X and the obstacle within the influence distance gravitational force F_att of the point;所述的障碍物对当前路径点位置X的斥力F_rep计算公式如下：The formula for calculating the repulsion force F_rep of the obstacle to the current path point position X is as follows:其中inU_rep(X)为改进斥力势场函数，X_o代表某一障碍物在二维坐标中的位置，m为斥力修正因子指数，Xg为目标点在二维坐标中的位置，F_rep1、F_rep2分别为斥力分解在障碍物指向当前路径点方向、当前路径点指向目标点方向的分力；U_rep (X) is the improved repulsion potential field function, X_o represents the position of an obstacle in the two-dimensional coordinates, m is the repulsion correction factor index, Xg is the position of the target point in the two-dimensional coordinates, F_rep1 , F_rep2 is the component force of the repulsion force decomposition in the direction of the obstacle pointing to the current waypoint and the current waypoint pointing to the target point;F_rep1、F_rep2具体公式如下：The specific formulas of F_rep1 and F_rep2 are as follows:步骤5.3：计算目标点对当前路径点的引力，计算处于影响距离内障碍物对当前路径点的斥力，得到所述当前路径点所受到的引力和斥力的合力；Step 5.3: Calculate the gravitational force of the target point on the current waypoint, calculate the repulsion force of the obstacle within the influence distance to the current waypoint, and obtain the resultant force of the gravitational force and the repulsive force on the current waypoint;步骤5.4：计算当前路径点的合力并判定合力是否为0，如果为0，则采用定向随机取点法，找到下一路径点；如果不为0，则根据当前路径点所受到的合力方向行进单位步长距离；Step 5.4: Calculate the resultant force of the current path point and determine whether the resultant force is 0. If it is 0, use the directional random point selection method to find the next path point; if it is not 0, proceed according to the direction of the resultant force on the current path point. unit step distance;步骤5.5：判断在路径行进中是否存在在某两个点反复震荡问题，如果为是，则采用定向随机取点法，如果为否，则根据当前路径点受到的合力方向行进单位步长距离；Step 5.5: Judging whether there is a problem of repeated oscillations at two points during the path travel, if so, adopt the directional random point selection method, if not, travel the unit step distance according to the direction of the resultant force received by the current path point;步骤5.6：判定是否达到迭代次数2000次上限，如果是，则记录行进路径点，得到局部最优路径，否则判断当前路径点是否为局部目标点，如果是则得到局部最优路径，结束；否则，返回步骤5.3。Step 5.6: Determine whether the upper limit of the number of iterations is 2000. If so, record the travel path point and obtain the local optimal path. Otherwise, determine whether the current path point is the local target point. If so, get the local optimal path and end; otherwise , go back to step 5.3.4.根据权利要求1所述的水质采样巡航船路径规划最优化方法，其特征在于：第7步所述的整合是指：4. The water quality sampling cruise ship path planning optimization method according to claim 1, characterized in that: the integration described in the 7th step refers to:从起点开始，检索之后的路径点，判断起点与此路径点的连线是否穿过障碍物，即是否与障碍物有交点，若无交点，继续向后检索下一路径点；若有交点，则以当前检索路径点的前一路径点为锚定点，连接起点和锚定点，并以锚定点为新的起点继续向后检索，并进行障碍物交点判断，直至检索至目标点。Start from the starting point, retrieve the next path point, and judge whether the line connecting the starting point and this path point passes through the obstacle, that is, whether there is an intersection with the obstacle. If there is no intersection, continue to search for the next path point; Then take the previous path point of the current retrieval path point as the anchor point, connect the starting point and the anchor point, and continue to search backward with the anchor point as the new starting point, and judge the intersection of obstacles until the retrieval reaches the target point.5.根据权利要求1所述的水质采样巡航船路径规划最优化方法，其特征在于：所述的定向随机取点法，具体步骤如下：5. water quality sampling cruise ship path planning optimization method according to claim 1, is characterized in that: described directional random point method, concrete steps are as follows:步骤A：做当前路径点X与目标点的连线L；Step A: Make the connection line L between the current path point X and the target point;步骤B：做穿过X且垂直L的直线，并在直线上取距离X单位步长的两点a、b；Step B: Make a straight line passing through X and perpendicular to L, and take two points a and b at a distance of X unit steps on the straight line;步骤C：取连线L上距离X单位步长的点X₁做穿过X₁且垂直L的直线，并在直线上取距离X₁单位步长的两点c、d；Step C: Take the point X₁ on the connection line L at a distance of X unit steps to make a straight line that passes through X₁ and is perpendicular to L, and takes two points c and d at a distance of X₁ unit steps on the straight line;步骤D：在a、b、c、d、X₁5点中任取一点作为下一路径点。Step D: Take any point among the 5 points a, b, c, d and X₁ as the next path point.