CN117109622B - UUV ant colony path planning method for bidirectional search under multiple obstacles - Google Patents

Abstract

The invention aims to solve the problems that the traditional ant colony method is easy to sink into a local optimal path and the iteration time is too long in path planning, and the like, and discloses a UUV ant colony path planning method for bidirectional searching under multiple obstacles, which specifically comprises the following steps: based on the traditional ant colony method, aiming at most obstacles with irregular shapes, the obstacles are ideal to be grid-shaped and uniform in size; when the traditional ant colony method starts from a starting point to a target point, a optimizing route from the target point to the starting point is introduced, and the optimizing speed is increased under the addition of the two optimizing routes; and the cross points and the communication relation between the cross points are introduced, meanwhile, the number of the cross points is limited to avoid slow calculation, and finally, the optimal path is found through the cross points, the communication relation and the quick backtracking of the concentration value of the pheromone. The method reduces the iteration time of the traditional ant colony method on path planning and reduces the possibility of easily sinking into a local optimal solution.

Description

UUV ant colony path planning method for bidirectional search under multiple obstacles

Technical Field

The invention relates to the field of unmanned submersible vehicle (Unmanned underwater vehicle, UUV) path planning, in particular to a UUV ant colony path planning method for bidirectional search under multiple obstacles.

Background

With the development of technology, the research and development of the ocean field in the current society is more and more important, the UUV application field is wider and wider, not only is the UUV applied to the military field, but also more and more UUV appears in the scientific research and commercial field, the development of ocean resources and the investment of ocean safety and national defense in the country are more and more, and then a more perfect method is needed in UUV path planning to help the UUV to reach the specified target more accurately and rapidly.

The common path planning method includes a D-algorithm, a wolf algorithm, a tabu search algorithm, an a-algorithm, a particle swarm algorithm, an RRT tree algorithm, an ant colony method, and the like. Compared with other algorithms, the ant colony method has the advantages of simplicity, convenience in understanding, strong adaptability, good robustness and the like. However, the following problems are involved in the application of the ant colony method in the path planning field:

(1) The convergence rate problem, the ant colony method needs a large amount of iteration and a large amount of calculation to find a better path, so the convergence rate is slow to be an unavoidable disadvantage;

(2) The problem of local optimal solution is that the ant colony method is a local search algorithm, so that the problem that the final path does not reach the minimum value but is suboptimal solution easily occurs.

Meanwhile, compared with the present invention, the following methods have the following disadvantages:

the improved method provided in the paper Dijkstra-ant colony algorithm-based parking system path planning research has the following disadvantages: firstly, dijkstra search paths are carried out, so that the search time is increased;

patent CN 116643566A, "a path planning method based on ant colony algorithm D-artificial potential field fusion", provides an improved method, which has the following disadvantages: the multiple modules operate cooperatively, which costs a lot of cost; the calculation is complex, and the path update speed is slower.

The UUV ant colony path planning method for bidirectional searching under multiple obstacles reduces the searching time and reduces the possibility that the traditional ant colony method is easy to fall into a local optimal solution.

Disclosure of Invention

The invention provides the following technical scheme for solving the problems of low convergence speed, easy occurrence of local optimal solution and the like in the path planning process: the UUV ant colony path planning method for bidirectional searching under multiple obstacles is designed, a batch of ants are placed at a starting point and a target point when the ant colony method data are preprocessed on the basis of the traditional ant colony method, searching is carried out from the starting point to the target point and from the target point to the starting point, a rapid searching map is achieved, and the problem of low searching speed is solved; meanwhile, when two ants search paths towards respective target points to generate meeting crossing points, a set is created, position coordinates of the crossing points, the concentration of pheromones between the two points and the communication relation between the crossing points are recorded, all crossing points are traced back through the record of the concentration of the pheromones between the crossing points, and the optimal path is found through the crossing point with the maximum concentration value of the pheromones, so that the problem that the traditional ant colony method is easy to fall into the local optimal path is solved. The method specifically comprises the following steps:

step 1:

establishing a two-dimensional planar grid map of UUV in the same planar environment, wherein grids are 1m 1X 1m equal in size, the map size is X X Y, and each grid is marked with X _i Y _j Where i, j represent the index, and since the grid sizes are all 1 x 1m, m represents length unit meters, the center point coordinates of each grid are expressed as:

step 2:

initializing parameters and defining a set J;

step 3:

dividing ant equally into two groups T ₁ And T ₂ Respectively delivering to a starting point A and a target point B, wherein T ₁ The ants search the path from A to B, T ₂ The ants search the path from B to A, and then enter step 4;

step 4:

the next arriving node is found for two groups of ants by adopting the roulette mode, wherein the state transfer function is as follows:

wherein,is the probability of ants selecting from node i to node j; τ _ij (t) isThe concentration of pheromones on the paths of the node i and the node j; allowed _k Is the solution space for the ant to select the next node; alpha is a pheromone importance factor; beta is a heuristic importance factor; η (eta) _ij (t) is a heuristic function, the expression of which is:

η _ij (t)＝1/d _ij (3)

wherein d _ij Is the distance between i, j;

step 5:

judging whether two groups of ants meet or not, if so, storing the crossing points of the ants in a set J, and storing the communication relation between the crossing points and the concentration value of the pheromone in the set J, and then entering a step 6; otherwise, returning to the step 4;

step 6:

judging whether the ants complete the path, if so, entering step 7; otherwise, returning to the step 4;

step 7:

judging whether the number of the crossing points reaches saturation, if so, entering a step 11; otherwise, enter step 8;

step 8:

judging whether the ants reach the maximum number, if so, entering a step 9; otherwise, returning to the step 3;

step 9:

updating the pheromone, wherein the updated pheromone adopts the following formula:

τ _ij (t+1)＝(1-ρ)*τ _ij (t)+ Δτ _ij (5)

wherein τ _ij (t) is the concentration of pheromones on the paths of node i and node j;representing the concentration of pheromone released by the kth ant between i and j; Δτ _ij Representing the sum of pheromone concentrations of ants between i and j; ρ represents the pheromone volatilization coefficient, and the value is generally between 0 and 1; n represents the maximum number of ants, and then step 10 is entered;

step 10:

judging whether the maximum iteration times are reached, if so, entering a step 11; otherwise, returning to the step 3;

step 11:

defining and initializing a set S, and entering a step 12;

step 12:

putting the intersection with the maximum pheromone concentration between the starting point A and the intersection into S, deleting the intersection from J, and entering step 13;

step 13:

comparing the concentration of pheromone directly connected with the crossing point in S and the crossing point in J, and entering step 14;

step 14:

judging whether to delete the crossing point with obviously low pheromone concentration in J, and entering step 15 after deleting; otherwise, go to step 12;

step 15:

judging whether all the intersections in J are traversed, if yes, entering a step 16; otherwise, returning to the step 12;

step 16:

and backtracking the coordinates of the crossing points existing in the S, calculating a theoretical shortest path, outputting the shortest path, and ending. The invention has the following beneficial effects:

1. according to the method, on the basis of a search path from a starting point to a target point in a traditional ant colony method, a search path from the target point to the starting point is introduced, so that the optimizing speed is increased, and the possibility that unidirectional search is easy to sink into local optimization is reduced;

2. according to the method, on the basis of utilizing the concentration of the pheromone of the traditional ant colony method, the intersection points and the communication relation are introduced, and the path search is carried out through the connection between the intersection points, so that the probability of easily generating local optimal paths is reduced;

3. the method introduces the communication relation between the cross points and records the pheromone concentration value between the cross points, and iteratively searches the optimal path according to the pheromone concentration of the communication relation between the cross points, thereby improving the efficiency of path searching and shortening the searching time.

Drawings

Fig. 1 is a flow chart of a UUV ant colony path planning method for bidirectional searching under multiple obstacles;

FIG. 2 is a grid numbering schematic;

FIG. 3 is a diagram showing the path of two ants looking for their respective target points;

FIG. 4 shows a cross-point diagram after two groups of ants meet;

FIG. 5 is a graph showing the relationship between the points of intersection and the connection between two ants;

FIG. 6 is a final formed path diagram;

fig. 7 is a converging curve change chart.

Detailed Description

Fig. 1 is a flow chart of a UUV ant colony path planning method for bidirectional searching under multiple obstacles, which comprises the following steps:

step 1:

establishing a two-dimensional planar grid map of UUV under the same planar environment, idealizing the obstacles into black grids in the grid map, wherein the obstacles less than one grid expand into one grid, the obstacles exceeding one grid are composed of a plurality of grids, the white grids represent passable areas, the black grids represent the obstacles, the UUV cannot pass, the grids are all 1m X1 m equal size (m represents length unit meter), the map size is X X Y, and each grid is marked with the reference sign X _i Y _j Wherein i, j represent the index, e.g. grid a of FIG. 2 is represented by X ₁ Y ₁ Since the grid sizes are all 1 x 1, the center point coordinates of each grid are expressed as:

step 2:

initializing parameters, wherein the number of ant colonies is N=100, the importance factor of the pheromone is alpha=1, the importance factor of the heuristic function is beta=7, the volatilization factor of the pheromone is p=0.3, the total release amount of the pheromone is d=0, and the maximum iteration number is N _max =80, and defines a set J for storing meeting points of two ants, also called crossing points and their pheromone-related information;

step 3:

dividing ant equally into two groups T ₁ And T ₂ Respectively delivering to a starting point A and a target point B, wherein T ₁ The ants search the path from A to B, T ₂ Group ants search for paths from B to a. Initializing a tabu list, putting a starting point A and a target point B into the tabu list, and then entering a step 4;

step 4:

through the current concentration of pheromone and the nodes existing in the tabu list, the next arriving node is searched for two groups of ants by adopting a roulette mode, wherein the state transfer function is as follows:

wherein,is the probability of ants selecting from node i to node j; τ _ij (t) is the concentration of pheromones on the paths of node i and node j; allowed _k Is the solution space for the ant to select the next node; alpha is an important degree factor of the pheromone, and is the importance degree of the ant on the concentration of the pheromone when selecting the next node, and the larger the value of alpha is, the ant can select a path with the larger concentration of the pheromone to select the next node; beta is the importance factor of the heuristic function, is the importance degree of ants on the heuristic function pheromone when selecting the next node, and the larger the beta is, the more the ants tend to select the heuristic function pheromone with larger valueThe position is moved, eta _ij (t) is a heuristic function, the expression of which is:

η _ij (t)＝1/d _ij (3)

wherein d _ij Is the distance between i, j;

step 5:

judging whether two groups of ants meet or not by judging the point coordinate values stored in the tabu list, storing the intersection points of the ants in a set J if the ants meet, storing the communication relation between the intersection points and the concentration value of the pheromone in the set J, and then entering a step 6; otherwise, returning to the step 4;

step 6:

judging whether the ants complete the path, if so, entering step 7; otherwise, returning to the step 4;

step 7:

judging whether the number of the crossing points reaches saturation or not by comparing the number of the crossing points of the round with the number of the crossing points of the upper round, if the number and the number are not changed, indicating that the crossing points reach saturation, and entering a step 11; otherwise, enter step 8;

step 8:

judging whether the ants reach the maximum number, if so, entering a step 9; otherwise, returning to the step 3;

step 9:

since the number of ants reaches the maximum number at this time, the pheromone is updated at this time, wherein the update pheromone is updated by using the global pheromone, and the formula is as follows:

τ _ij (t+1)＝(1-ρ)*τ _ij (t)+Δτ _ij (5)

wherein τ _ij (t) is the node i and node j pathsThe concentration of the pheromone;representing the concentration of pheromone released by the kth ant between i and j; Δτ _ij Representing the sum of pheromone concentrations of ants between i and j; ρ represents the pheromone volatilization coefficient, and the value is generally between 0 and 1; n represents the maximum number of ants, and then step 10 is entered;

step 10:

judging whether the maximum iteration times are reached, if so, entering a step 11; otherwise, returning to the step 3;

step 11:

defining and initializing a set S, and entering a step 12;

step 12:

putting the intersection with the maximum pheromone concentration between the starting point A and the intersection into S, deleting the intersection from J, and entering step 13;

step 13:

comparing the concentration of pheromone directly connected with the crossing point in S and the crossing point in J, and entering step 14;

step 14:

through the comparison of the step 13, the relation of the concentration of the pheromone between the crossing points can be clearly obtained, whether the crossing point with obviously low concentration of the pheromone in J is deleted or not is judged, and the step 15 is carried out after the deletion; otherwise, go to step 12;

step 15:

judging whether all the intersections in J are traversed, if yes, entering a step 16; otherwise, returning to the step 12;

step 16:

and backtracking the coordinates of the crossing points existing in the S, calculating a theoretical shortest path, outputting the shortest path, and ending. The method is simulated by Matlab software, and fig. 3, 4 and 5 are simulation diagrams of search paths of UUV under multiple obstacles, wherein the coordinate axis unit is m. FIG. 3 is a diagram showing two groups of ants searching for their respective target points, in which it can be seen that the ants perform the optimizing process from the starting point A to the target point B and the optimizing process from the target point B to the starting point AAnd (5) processing. FIG. 4 shows a cross-point diagram of two groups of ants after meeting, as can be seen in the figure, the ants are numbered X ₁₁ Y ₁₀ And is numbered X ₁₅ Y ₁₂ The grid of (c) creates intersections, which will be recorded in set J at this time. Fig. 5 is a graph of the intersection points and the communication relations between the intersection points generated by three times of searching for the target points by two groups of ants, and it can be seen that the intersection points at 21 positions and the communication relations between the intersection points are generated by the ants after three times of iteration. Fig. 6 and fig. 7 are respectively a final result diagram and a convergence graph of a UUV searching a path under multiple obstacles, in which it can be seen that the path length is greatly floated before the iteration number is 30 times; after the iteration times are 30 times, the path length is gradually stabilized; when the iteration is carried out for 35 times, the minimum path is reached, the optimizing speed is high, and the minimum path length is 30.2m to reach stability.

Claims (1)

1. A UUV ant colony path planning method for bidirectional searching under multiple obstacles is characterized by comprising the following steps:

step 1:

establishing a two-dimensional planar grid map of the UUV in the same planar environment, wherein grids are 1m X1 m equal in size, m represents length unit meter, the map size is X X Y, and each grid is marked with the reference sign X _i Y _j Where i, j represent the index, and since the grid sizes are all 1 x 1, the center point coordinates of each grid are expressed as:

step 2:

initializing parameters and defining a set J;

step 3:

dividing ant equally into two groups T ₁ And T ₂ Respectively delivering to a starting point A and a target point B, wherein T ₁ The ants search the path from A to B, T ₂ The ants search the path from B to A, and then enter step 4;

step 4:

the next arriving node is found for two groups of ants by adopting the roulette mode, wherein the state transfer function is as follows:

wherein,is the probability of ants selecting from node i to node j; τ _ij (t) is the concentration of pheromones on the paths of node i and node j; allowed _k Is the solution space for the ant to select the next node; alpha is a pheromone importance factor; beta is a heuristic importance factor; η (eta) _ij (t) is a heuristic function, the expression of which is:

η _ij (t)＝1/d _ij (3)

wherein d _ij Is the distance between i, j;

step 5:

judging whether two groups of ants meet or not, if so, storing the crossing points of the ants in a set J, and storing the communication relation between the crossing points and the concentration value of the pheromone in the set J, and then entering a step 6; otherwise, returning to the step 4;

step 6:

judging whether the ants complete the path, if so, entering step 7; otherwise, returning to the step 4;

step 7:

judging whether the number of the crossing points reaches saturation, if so, entering a step 11; otherwise, enter step 8;

step 8:

judging whether the ants reach the maximum number, if so, entering a step 9; otherwise, returning to the step 3;

step 9:

updating the pheromone, wherein the updated pheromone adopts the following formula:

τ _ij (t+1)＝(1-ρ)*τ _ij (t)+Δτ _ij (5)

wherein τ _ij (t) is the concentration of pheromones on the paths of node i and node j;representing the concentration of pheromone released by the kth ant between i and j; Δτ _ij Representing the sum of pheromone concentrations of ants between i and j; ρ represents the pheromone volatilization coefficient, and the value is generally between 0 and 1; n represents the maximum number of ants, and then step 10 is entered;

step 10:

judging whether the maximum iteration times are reached, if so, entering a step 11; otherwise, returning to the step 3;

step 11:

defining and initializing a set S, and entering a step 12;

step 12:

putting the intersection with the maximum pheromone concentration between the starting point A and the intersection into S, deleting the intersection from J, and entering step 13;

step 13:

comparing the concentration of pheromone directly connected with the crossing point in S and the crossing point in J, and entering step 14;

step 14:

judging whether to delete the crossing point with obviously low pheromone concentration in J, and entering step 15 after deleting; otherwise, go to step 12;

step 15:

judging whether all the intersections in J are traversed, if yes, entering a step 16; otherwise, returning to the step 12;

step 16:

and backtracking the coordinates of the crossing points existing in the S, calculating a theoretical shortest path, outputting the shortest path, and ending.