Summary of the invention
In order to solve the above technical problems, the present invention provides a kind of mixing of unmanned plane unmanned boat to lay dispatching partyMethod.
In order to solve the above-mentioned technical problem, the present invention takes following technical scheme:
A kind of mixing of unmanned plane unmanned boat lays dispatching method, comprising the following steps:
S1, using A* path planning algorithm, the optimal collision prevention path of the unmanned boat for calculating separately out harbour to each target point,And the optimal collision prevention path of unmanned boat between each target point；
S2, use straight line path as harbour the unmanned plane path to each target point and the nothing between each target pointMan-machine path；
S3, the different speed according to possessed by unmanned plane unmanned boat, converts time loss for path distance, thus willUnmanned plane unmanned boat mixed scheduling is converted into isomery multiple traveling salesmen problem MTSP；
S4 converts multiple independent travelling salesmans for isomery multiple traveling salesmen problem MTSP using K-means clustering algorithm and asksInscribe TSP；
S5 is optimized using genetic algorithm, to obtain optimal unmanned plane unmanned boat mixed scheduling scheme.
Further, the step S1 is specifically included:
S101 obtains the map in related waters, and according to accuracy requirement and map size, to map carries out rasterizing, and marksRemember the waters that can pass through out, impassabitity waters, target point and harbour point, and named port point is node 1, target point is from node 2Start to calculate；
Harbour point or target point are put it into the list of entitled " OPEN " as starting point, and calculate value by S102Function f (n)；
The smallest node n of cost function in " OPEN " list is moved in the list of entitled " CLOSED " by S103, ifN is the target point place node in addition to starting point, then obtains solution path；If n is not the target point institute in addition to starting pointIn node, then next step S104 is gone to；
S104 finds the reachable all nodes of n node, removes the node in impassabitity waters and is already present on " OPEN "Node in list or " CLOSED " list, then calculate their cost function and put it into " OPEN " list；
S105 jumps to S103, and recycles, until finding solution path or determining without solution；
S106 jumps to S102, by the calculated result of cost function f (n), obtain harbour to each target point unmanned boatThe optimal collision prevention path of unmanned boat between optimal collision prevention path and each target point.
The step S2 is specifically included:
S201 establishes plane right-angle coordinate, obtains the coordinate value (x at harbour1,y1) and each target point coordinate value(x2,y2)、(x3,y3)、(x4,y4)……(xn,yn)；
S202 calculates harbour (x using Euclidean distance formula1,y1) arrive first aim point (x2,y2) unmanned plane roadDiameter distance:
S203, referring to S202, calculate separately out harbour to each target point unmanned plane path distance and each target pointBetween unmanned plane path distance.
The step S3 is specifically included:
S301 turns the harbour of the obtained unmanned boat of step S1 to the path between each target point and each target pointTurn to corresponding unmanned boat path distance L 'ij；
S302 obtains the average speed V of unmanned plane according to the actual parameter of unmanned plane unmanned boat usedUAVAnd unmanned boatAverage speed VUSV；
S303, by the unmanned plane path distance at harbour obtained in step S2 to each target point and each target point itBetween unmanned plane path distance, according to formula Tij=Lij/VUAV, obtain corresponding unmanned plane time loss Tij；
S304, by path distance obtained in step S301, according to formula T 'ij=L 'ij/VUSV, obtain it is corresponding nobodyShip time loss T 'ij；
S305, it is most short for target with time loss, unmanned plane unmanned boat is converted by unmanned plane unmanned boat mixed schedulingIsomery multiple traveling salesmen problem.
The step S4 is specifically included:
S401, if sharing N number of target point, the sum of unmanned plane and unmanned boat is K, then there is restrictive condition N > K, any to selectSelect K initial cluster center Z1(1), Z2(1) ..., ZK(1)；
Remaining sample is assigned to some in K cluster centre according to shortest distance principle by S402, it may be assumed that if
min{||X-Zi(k) | |, i=1,2 ..., K }=| | X-Zj(k) | |=Dj(k)
Then X ∈ Sj(k)；
X is any one in remaining sample, DjIt (k) is X to cluster centre Zj(k) Euclidean distance, SjIt (k) is clusterTo the set of the sample of Z (j)；
S403 calculates the new vector value Z of each cluster centrej(k+1), j=1,2 ..., K.
I.e. using mean vector as new cluster centre；
S404, if Zj(k+1)≠Zj(k), j=1,2 ..., K then return to S402, target point are reclassified, is laid equal stress onMultiple iterative calculation；If Zj(k+1)=Zj(k), j=1,2 ..., K, algorithmic statement, calculating finish, finally by the more travelling salesmans of isomeryProblem MTSP is converted into K independent traveling salesman problem TSP.
The step S5 is specifically included:
S501 first assumes that the carrier of the independent traveling salesman problem TSP is for the 1st independent traveling salesman problem TSPUAV generates initial population using the local search ability of greedy algorithm for genetic algorithm；
S502 is solved using genetic algorithm, and iterative process calculates fitness function individual in population first each timeValue, then successively executes selection, intersection, mutation operator；
S503 returns to S501, the carrier of independent traveling salesman problem TSP is changed to USV, thus an independent tripThe problem TSP of doing business respectively obtains two groups of solutions for UAV and USV；
S504 successively solves the 2nd, 3 ..., the solution of K independent traveling salesman problem TSP, equally, each independent travellingQuotient's problem TSP respectively obtains two groups of solutions for UAV and USV；
S505 reuses genetic algorithm, finds the optimum allocation mode of independent traveling salesman problem TSP Yu UAV, USV.
The path planning and task schedule of unmanned plane unmanned boat heterogeneous system can be achieved in the present invention, has and stablizes, efficientlyAdvantage.
Specific embodiment
To further understand the features of the present invention, technological means and specific purposes achieved, function, below with reference toPresent invention is further described in detail with specific embodiment for attached drawing.
As shown in Fig. 1, present invention discloses a kind of mixing of unmanned plane unmanned boat to lay dispatching method, including following stepIt is rapid:
S1, using A* path planning algorithm, the optimal collision prevention path of the unmanned boat for calculating separately out harbour to each target point,And the optimal collision prevention path of unmanned boat between each target point.
S2, use straight line path as harbour the unmanned plane path to each target point and the nothing between each target pointMan-machine path.
S3, the different speed according to possessed by unmanned plane unmanned boat, converts time loss for path distance, thus willUnmanned plane unmanned boat mixed scheduling is converted into isomery multiple traveling salesmen problem MTSP.
S4 converts multiple independent travelling salesmans for isomery multiple traveling salesmen problem MTSP using K-means clustering algorithm and asksInscribe TSP.
S5 is optimized using genetic algorithm, to obtain optimal unmanned plane unmanned boat mixed scheduling scheme.
For step S1, specifically include:
S101 obtains the map in related waters, and according to actual accuracy requirement and map size, to map carries out gridChange, and mark the waters that can pass through, impassabitity waters, target point and harbour point, and named port point is node 1, target pointIt is calculated since node 2, such as node 3, node 4, node 5 are all target point.Such as it can be according to the actual size of unmanned boatAnd its operational capabilities, selecting the length of square grid is 10 meters, can establish a three-dimensional array [x, y, t], store x respectivelyWaters information t at axis values, y-axis numerical value and point (x, y), wherein t=-1,0,1,2, respectively represent impassabitity waters, meshPunctuate, unmanned boat present position and the waters that can pass through.
Harbour point or target point are put it into the list of entitled " OPEN " as starting point, and calculate value by S102Function f (n), wherein f (n)=g (n)+h (n), h (n) are the position (nth point) where current unmanned boat and the road between starting pointDiameter distance, i.e., the distance of the starting point obtained by A* path planning algorithm to the path n point, h (n) can once be obtained by precedingH (n-1) adds the step-length currently moved and obtains；G (n) is linear distance of the nth point to terminal.
The smallest node n of cost function in " OPEN " list is moved in the list of entitled " CLOSED " by S103, ifN is the target point place node in addition to starting point, then obtains solution path；If n is not the target point institute in addition to starting pointIn node, then next step S104 is gone to.
S104 finds the reachable all nodes of n node, removes the node in impassabitity waters and is already present on " OPEN "Node in list or " CLOSED " list, then calculate their cost function and put it into " OPEN " list.
S105 jumps to S103, and recycles, until finding solution path or determining without solution.I.e. when all roadsAfter diameter is attempted, not without the path of other target points, then it is determined as between origin-to-destination without there are directapaths.
S106 jumps to S102, by the calculated result of cost function f (n), obtain harbour to each target point unmanned boatThe optimal collision prevention path of unmanned boat between optimal collision prevention path and each target point.Assuming that harbour point adds the total N of all target pointsIt is a, it is marked respectively, such as A point and B point, since the shortest path of A point to B point is also shortest path of the B point to A point, becauseThis needs cycle calculations N altogether！/ 2 times.
For step S2, specifically include:
S201 establishes plane right-angle coordinate, remaining target point is node 2, node 3 ... node n, obtains harbourCoordinate value (x1,y1) and each target point coordinate value (x2,y2)、(x3,y3)、(x4,y4)……(xn,yn), it can be with realityGeographical coordinate as above-mentioned coordinate value, facilitate the conversion in step S3.
S202 calculates harbour (x using Euclidean distance formula1,y1) arrive first aim point (x2,y2) unmanned plane roadDiameter distance:
S203, referring to S202, calculate separately out harbour to each target point unmanned plane path distance and each target pointBetween unmanned plane path distance.With step S106, N number of node is shared, but due to symmetric relation, needs cycle calculations altogetherN！/ 2 times.
The step S3 is specifically included:
S301 turns the harbour of the obtained unmanned boat of step S1 to the path between each target point and each target pointTurn to corresponding unmanned boat path distance L 'ij.Specific conversion thinking is as follows: in such as step S1, assuming initially that each gridLength is 10 meters, and due to being to obtain approximate path in grating map, two grids, which directly connect, is divided into two kinds, (1)Straight line connection, length is 10 meters at this time, and the connection of (2) oblique line, length is at this timeRice, thus corresponding unmanned boat path away fromFrom are as follows:A is straight line connection number all in path, and b is oblique line all in pathConnection number.
S302 obtains the average speed V of unmanned plane according to the actual parameter of unmanned plane unmanned boat usedUAVAnd unmanned boatAverage speed VUSV。
S303, by the unmanned plane path distance at harbour obtained in step S2 to each target point and each target point itBetween unmanned plane path distance, according to formula Tij=Lij/VUAV, obtain corresponding unmanned plane time loss Tij。
S304, by path distance obtained in step S301, according to formula T 'ij=L 'ij/VUSV, obtain it is corresponding nobodyShip time loss T 'ij。
S305, it is most short for target with time loss, unmanned plane unmanned boat is converted by unmanned plane unmanned boat mixed schedulingIsomery multiple traveling salesmen problem.By step S1 it is found that co-existing in N-1 target point, it is assumed that unmanned plane UAViThe target point of process isA, a+1, a+2 ..., b, then unmanned plane UAViPath time consumption are as follows:Similarly, it is assumed that unmanned boatUSViThe target point of process is c, c+1, c+2 ..., d, then unmanned boat USViPath time consumption are as follows:Due to whole system task completion time depend on all unmanned planes withoutTime-consuming longest individual, i.e. T in people's shiptotal=max { min [min (TUAVi),min(TUSVi)], then the MTSP problem can be withStatement are as follows: while optimal the target point method of salary distribution and path planning are found, so that TtotalIt is minimum.
In addition, being specifically included for step S4:
S401, if sharing N number of target point, the sum of unmanned plane and unmanned boat is K, then there is restrictive condition N > K, any to selectSelect K initial cluster center Z1(1), Z2(1) ..., ZK(1)。
Remaining sample is assigned to some in K cluster centre according to shortest distance principle by S402, it may be assumed that if
min{||X-Zi(k) | |, i=1,2 ..., K }=| | X-Zj(k) | |=Dj(k)
Then X ∈ Sj(k)；
S403 calculates the new vector value Z of each cluster centrej(k+1), j=1,2 ..., K.
I.e. using mean vector as new cluster centre.
S404, if Zj(k+1)≠Zj(k), j=1,2 ..., K then return to S402, target point are reclassified, is laid equal stress onMultiple iterative calculation；If Zj(k+1)=Zj(k), j=1,2 ..., K, algorithmic statement, calculating finish, finally by the more travelling salesmans of isomeryProblem MTSP is converted into K independent traveling salesman problem TSP.I-th of TSP can be stated are as follows: optimal path is found, so thatTTSPi=TUAVj(it is assumed that i-th of TSP is by unmanned plane UAVjExecute) it is minimum.T in S305 at this timetotalChange are as follows: Ttotal=max (TTSPi), i=1,2 ..., K.
For step S5, specifically include:
S501 first assumes that the carrier of the independent traveling salesman problem TSP is for the 1st independent traveling salesman problem TSPUAV generates initial population using the local search ability of greedy algorithm for genetic algorithm.Greedy algorithm is to solve TSP problemAlgorithm has principle simple, and the fast advantage of solving speed can effectively improve the quality of the initialization population of genetic algorithm.Its basic ideas is as follows: (1) randomly choosing a city first as starting point；(2) city having arrived at is removed, selection is mostClose city is as next city；(3) until all cities of traversal, from is turned again to, available one at this timePath.
S502 is solved using genetic algorithm, and iterative process calculates fitness function individual in population first each timeValue, then successively executes selection, intersection, mutation operator.Roulette wheel selection alternatively operator is used in the present embodiment, it can alsoTo use elitist selection mechanism or the two to mix selection；In view of the discreteness of TSP problem, intersect in this example, mutation operatorSelect binary coding mode.
S503 returns to S501, the carrier of independent traveling salesman problem TSP is changed to USV, thus an independent tripThe problem TSP of doing business respectively obtains two groups of solutions for UAV and USV.
S504 successively solves the 2nd, 3 ..., the solution of K independent traveling salesman problem TSP, equally, each independent travellingQuotient's problem TSP respectively obtains two groups of solutions for UAV and USV.
S505 reuses genetic algorithm, finds the optimum allocation mode of independent traveling salesman problem TSP Yu UAV, USV,K TSP problem and A UAV and B USV are corresponded, wherein A+B=K, so that TtotalIt is minimum.
For the optimization algorithm in S505, ant algorithm, particle swarm algorithm and simulated annealing etc. can also be used realExisting, algorithm above is the common knowledge of those skilled in the art.
The above is only present pre-ferred embodiments, is not intended to limit the present invention in any form, althoughThe present invention is disclosed as above with preferred embodiment, and however, it is not intended to limit the invention, any person skilled in the art,It does not depart within the scope of technical solution of the present invention, when the technology contents using the disclosure above make a little change or are modified to equivalent changeThe equivalent embodiment of change, but without departing from the technical solutions of the present invention, technology refers to above embodiments according to the present inventionMade any simple modification, equivalent change and modification, belong in the range of technical solution of the present invention.