CN110442128A - AGV paths planning method based on feature point extraction ant group algorithm - Google Patents

Abstract

The present invention provides a kind of AGV paths planning methods based on feature point extraction ant group algorithm, this method includes environmental modeling and path planning, environmental modeling includes the foundation of grid map and the extraction of characteristic point, according to the AGV Environmental Map Information being known in advance, after three-dimensional barrier is projected to two-dimensional surface grid map, barrier perspective view is divided into the identical grid of size, barrier shade is subjected to expansion again, obtain initial figure, the vertex of wherein black barrier grid is extracted, and adjacency matrix is reconfigured by the judgement of grid feasibility, path planning is carried out between characteristic point using ant group algorithm, finally obtain the clear path from origin-to-destination.The problem of the method overcome traditional ant group algorithm point by point search inefficiency has effectively saved the time calculated, improves search efficiency, keeps the path cooked up more smooth；With stylish grid feasibility judgment method, it is more advantageous to the safe and reliable operation of AGV.

Description

AGV path planning method based on feature point extraction ant colony algorithm

technical field

The present disclosure relates to the technical field of AGV path planning in computer algorithms, in particular to an AGV path planning method based on feature point extraction ant colony algorithm.

Background technique

The existing AGV path planning method is to first establish a grid environment model consistent with the AGV operating environment through environmental modeling, and then determine the starting point and end point on the environment model, and use the ant colony algorithm to find a path from the starting point to the end point. Obstacle-free path. However, although this method can successfully obtain an obstacle-free path from the start point to the end point, its search process belongs to a grid-by-frame search, which has a certain blindness. During the search process, a large number of non-optimal solutions will be searched, making the convergence speed slow and serious. It affects the efficiency of algorithm calculation. At the same time, only judging its feasibility based on whether the grid is an obstacle grid will cause the planned path to frequently pass through the vertices of obstacles, affecting the safe operation of the AGV.

SUMMARY OF THE INVENTION

In order to solve the problems in the prior art, the present disclosure proposes an AGV path planning method based on feature point extraction ant colony algorithm. After constructing the operating environment model of the AGV through the grid method, the method extracts the vertex grid of the black obstacle grid as the feature point, and uses the ant colony algorithm to search the path between these vertex grids, which can effectively guide the The search process reduces the calculation amount of the algorithm during planning, and since the connection between the original grids is broken after the feature point extraction, the new method of judging the feasibility of the grid is used to judge the relationship between the grids. The connection relationship, the resulting path is safer and smoother, which is more conducive to the operation of the AGV.

In a first aspect, the embodiments of the present disclosure provide an AGV path planning method based on feature point extraction ant colony algorithm, including the following steps: determining the position of obstacles in the AGV operating map, and projecting the three-dimensional positions of the obstacles to On the two-dimensional plane; segment the obstacle projection map projected on the two-dimensional plane; perform expansion processing on the obstacle shadow in the segmented obstacle projection map, and set it as the black obstacle grid. The vertex grid is extracted as a feature point; the feasibility of the extracted grid is judged and an adjacency matrix is constructed; a number of initial parameter values of the ant colony algorithm are set and all the ants of the current generation are placed at the starting point for path search; The transition probabilities and the non-zero grids in the constructed adjacency matrix select the next grid until the end point is reached.

In one of the embodiments, the dividing the obstacle projection map projected onto the two-dimensional plane includes: dividing the obstacle projection map into grids of the same size, and the number of grids is a*a.

In one of the embodiments, performing expansion processing on the obstacle shadow in the segmented obstacle projection image includes: if there is an obstacle shadow in the grid after segmenting the obstacle projection image, then It is set to a black obstacle grid, otherwise it is set to a white no obstacle grid.

In one embodiment, performing feasibility judgment on the extracted grid and constructing an adjacency matrix includes: constructing an adjacency matrix D, the size of which is a ² *a ² .

In one embodiment, the setting of multiple initial parameter values of the ant colony algorithm includes: m is the number of ants in each generation, n is the total number of generations of ants, and τ(0) is the initial pheromone concentration;

Tabu table Tabu is the cell structure size of m*n, which is used to record the route that each ant walks, and the size of the path length matrix PL is m*n, which is used to record the length of the route that each ant crawls in each generation;

Initialize the pheromone decay coefficient ρ, the pheromone heuristic factor α, the distance heuristic factor β, the number of iterations t; and

Set the initial parameter values for the start and end points.

In one embodiment, the method further includes: judging whether all the ants of the current generation have completed the path search, and if all the searches are completed, recording the number of iterations, where the number of iterations t=t+1; and judging whether the number of iterations t satisfies the number of iterations If the requirements are met, the shortest path is output; if the requirements of the number of iterations are not met, the pheromone is updated and the operation of dispatching the next generation of ants is performed; the dispatched operation of the next generation of ants is regarded as the current generation, and all ants of the current generation are Route search is performed at the starting point.

In one embodiment, the method further includes: judging whether all the ants of the current generation have completed the path search, and if the search has not been completed, selecting the next grid according to the transition probability and the non-zero grid in the adjacency matrix until reaching the end point .

In one embodiment, the extracting the vertex grid set as the black obstacle grid as the feature point includes: taking all the four vertex corner grids of the individual black obstacle grids, all the combined black obstacle grids All vertex and concave corners of the grid are extracted as feature points.

In one embodiment, the feasibility judgment on the extracted grid includes: if there is a black obstacle grid between the two vertex grids, determining that the two vertex grids are invisible and mutually infeasible Grid; if there is no black obstacle grid between the two vertex grids, judge whether the connection line between the two vertex grids passes through the vertex of the black obstacle grid, if it passes through the vertex of the black obstacle grid, then It is determined that the two vertex grids are invisible and mutually infeasible grids. If the vertex of the black obstacle grid is not passed, the two vertex grids are determined to be visible and mutually feasible grids.

In one embodiment, it also includes: the transition probability formula is:

where τ _ij (t) is the pheromone concentration between grids i and j when the iteration number is t, is the distance heuristic function between grids i and j when the number of iterations is t, and allowed _s is the grid represented by s when D(i, s)≠0 in the adjacency matrix D.

In one embodiment, the pheromone formula is:

τ _ij (t+1)=(1-ρ)τ _ij (t)+Δτ _ij (t)

Among them, τ _ij (k+1) is the pheromone concentration between grids i and j when the number of iterations is t, and Δτ _ij (t) is the information left by the current generation of ants between grids i and j sum of prime increments, is the pheromone increment left by the kth ant between grids i and j when the number of iterations is t.

The invention provides an AGV path planning method based on feature point extraction ant colony algorithm. The method includes environment modeling and path planning. The environment modeling includes the establishment of a grid map and the extraction of feature points. According to the pre-known AGV environment Map information, after projecting the three-dimensional obstacles to the two-dimensional plane grid map, divide the obstacle projection map into grids of the same size, and then inflate the shadow of the obstacles to obtain the initial grid map, in which the black obstacles are divided The vertices of the grid are extracted, and the adjacency matrix is reconstructed by judging the feasibility of the grid. The ant colony algorithm is used to plan the path between the feature points, and finally an obstacle-free path from the starting point to the end point is obtained. This method The AGV path planning method of the present invention overcomes the problem of low point-by-point search efficiency of the traditional ant colony algorithm, effectively saves calculation time, improves search efficiency, and makes the planned path smoother; at the same time, the new grid The feasibility judgment method can effectively solve the disadvantage that the planned path is too close to the obstacle, and is more conducive to the safe and reliable operation of the AGV.

Description of drawings

In order to illustrate the technical solutions of the embodiments of the present disclosure more clearly, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments:

1 is a flowchart of steps of an AGV path planning method based on feature point extraction ant colony algorithm in an embodiment of the present invention;

2 is a flowchart of steps of an AGV path planning method based on feature point extraction ant colony algorithm in another embodiment of the present invention;

3 is an obstacle projection diagram of the actual environment in an AGV path planning method based on feature point extraction ant colony algorithm in an embodiment of the present invention;

4 is a grid diagram of an actual environment in an AGV path planning method based on feature point extraction ant colony algorithm in an embodiment of the present invention;

5 is a distribution diagram of numbered vertex grids in an AGV path planning method based on feature point extraction ant colony algorithm in an embodiment of the present invention;

Fig. 6 is a grid feasibility judgment analysis diagram in an AGV path planning method based on feature point extraction ant colony algorithm in an embodiment of the present invention; and

FIG. 7 is a simulation result diagram of path planning in this environment in an AGV path planning method based on feature point extraction ant colony algorithm in an embodiment of the present invention.

Detailed ways

The present application will be further described in detail below with reference to the accompanying drawings and embodiments.

In the following introduction, the terms "first" and "second" are used for descriptive purposes only, and should not be construed as indicating or implying relative importance. The following introduction provides multiple embodiments of the present disclosure, and the different embodiments may be substituted or combined in combination, so this application should also be considered to include all possible combinations of the same and/or different embodiments described. Thus, if one embodiment includes features A, B, C and another embodiment includes features B, D, the application should also be considered to include all other possible combinations of one or more of A, B, C, D example, although this example may not be explicitly described in the following content.

In order to make the purpose, technical solutions and advantages of the present invention clearer, the following examples and in conjunction with the accompanying drawings, the specific implementation of an AGV path planning method based on feature point extraction ant colony algorithm of the present invention will be further described in detail. It should be noted that the present disclosure relates to the technical field of velocity and temperature measurement in the near-wall boundary layer of a turbomachine rotating channel. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention.

As shown in Figure 1, it is a schematic flowchart of an AGV path planning method based on feature point extraction ant colony algorithm in one embodiment, which specifically includes the following steps:

Step 101: Determine the position of the obstacle in the AGV operation map, and project the three-dimensional position of the obstacle on a two-dimensional plane.

Step 102, segment the obstacle projection image projected onto the two-dimensional plane.

Specifically, the segmentation of the obstacle projection image projected onto the two-dimensional plane includes: dividing the obstacle projection image into grids of the same size, and the number of grids is a*a.

Step 103: Dilation is performed on the shadow of the obstacle in the segmented obstacle projection map, and the vertex grid set as the black obstacle grid is extracted as a feature point.

Specifically, extracting the vertex grid set as the black obstacle grid as the feature point includes: taking all the four top corner grids of all the individual black obstacle grids, all the top corners of all the combined black obstacle grids and A grid of concave corners is extracted as feature points.

Specifically, inflating the obstacle shadow in the segmented obstacle projection image includes: if there is an obstacle shadow in the grid after segmenting the obstacle projection image, setting it as a black obstacle grid , otherwise set to a white unobstructed grid.

Step 104: Judging the feasibility of the extracted grid and constructing an adjacency matrix.

Specifically, judging the feasibility of the extracted grid and constructing an adjacency matrix includes: constructing an adjacency matrix D, the size of which is a ² *a ² .

Further, judging the feasibility of the extracted grid includes: if there is a black obstacle grid between the two vertex grids, then determining that the two vertex grids are invisible and are mutually infeasible grids; If there is no black obstacle grid between the vertex grids, it is judged whether the connection line between the two vertex grids passes through the vertex of the black obstacle grid. If it passes through the vertex of the black obstacle grid, the two vertex grids are judged. Invisible, they are mutually infeasible grids. If the vertex of the black obstacle grid is not passed, it is determined that the two vertex grids are visible and mutually feasible grids.

Step 105: Set multiple initial parameter values of the ant colony algorithm and place all ants of the current generation at the starting point to perform a path search.

Specifically, the setting of multiple initial parameter values of the ant colony algorithm includes: m is the number of ants in each generation, n is the total number of generations of ants, and τ(0) is the initial pheromone concentration;

Tabu table Tabu is the cell structure size of m*n, which is used to record the route that each ant walks, and the size of the path length matrix PL is m*n, which is used to record the length of the route that each ant crawls in each generation;

Initialize the pheromone decay coefficient ρ, the pheromone heuristic factor α, the distance heuristic factor β, the number of iterations t; and set the initial parameter values of the starting point and the ending point.

Step 106: Select the next grid according to the transition probability and the non-zero grid in the constructed adjacency matrix until the end point is reached.

Specifically, the transition probability formula is:

where τ _ij (t) is the pheromone concentration between grids i and j when the iteration number is t, is the distance heuristic function between grids i and j when the number of iterations is t, and allowed _s is the grid represented by s when D(i, s)≠0 in the adjacency matrix D.

In addition, in one embodiment, the AGV path planning method based on the feature point extraction ant colony algorithm proposed by the present disclosure further includes: judging whether all the ants of the current generation have completed the path search, and if the search has been completed, recording the number of iterations once, wherein, The number of iterations t=t+1; judge whether the number of iterations t meets the requirements of the number of iterations, and if so, output the shortest path; if it does not meet the requirements of the number of iterations, update the pheromone and perform the operation of dispatching the next generation of ants; The operation of a generation of ants is regarded as the current generation, and all ants of the current generation are placed at the starting point to perform a path search.

Among them, it should be noted that the pheromone formula is

τ _ij (t+1)=(1-ρ)τ _ij (t)+Δτ _ij (t)

Among them, τ _ij (k+1) is the pheromone concentration between grids i and j when the number of iterations is t, and Δτ _ij (t) is the information left by the current generation of ants between grids i and j sum of prime increments, is the pheromone increment left by the kth ant between grids i and j when the number of iterations is t.

Further, in one embodiment, the AGV path planning method based on the feature point extraction ant colony algorithm proposed by the present disclosure further includes: judging whether all ants of the current generation have completed the path search; The non-zero grid in the adjacency matrix selects the next grid until the end point is reached.

To sum up, in the existing path planning methods, the algorithm is often extended from all grids layer by layer, and the obstacle-free path from the starting point to the end point is obtained by grid-by-grid planning, which will make the calculation of the algorithm too large. , there are too many non-optimal solutions to search, resulting in the problem of low algorithm efficiency and too many iterations. The present invention extracts feature points from the grid image, and reduces the search range of the algorithm from all grids to all black obstacles. The vertex grid of the grid can reduce the calculation amount of the algorithm and speed up the convergence speed.

Further, the existing feasibility judgment between grids is judged by judging whether the eight grids around the current grid are obstacle grids. Not feasible. If it is a white non-obstacle grid, it is feasible between the two grids, which will cause the planned path to be unable to avoid the top corner of the black obstacle grid, thus affecting the safety of AGV operation. The new grid feasibility judgment adopted by the present invention sets the path passing through the vertex of the black obstacle grid as an infeasible path, so that the planned path is safer and smoother, which is beneficial to the operation of the AGV.

The AGV path planning method based on the feature point extraction ant colony algorithm proposed in the present disclosure overcomes the problem of low point-by-point search efficiency of the traditional ant colony algorithm, effectively saves calculation time, improves search efficiency, and makes the planned path smoother; At the same time, the new grid feasibility judgment method can effectively solve the disadvantage that the planned path is too close to the obstacle, which is more conducive to the safe and reliable operation of the AGV.

In order to more clearly understand and apply the AGV path planning method based on the feature point extraction ant colony algorithm proposed in the present disclosure, the following example is performed. It should be noted that the scope of protection of the present disclosure is not limited to the following examples.

Specifically, as shown in FIGS. 2-7 , FIG. 2 is a flowchart of steps of an AGV path planning method based on feature point extraction ant colony algorithm in another embodiment of the present invention. Specific steps are as follows

S1: Determine the position of the obstacles in the AGV operation map, and project the three-dimensional obstacles onto the two-dimensional plane. The obstacle projection map is shown in Figure 3.

S2: Divide the obstacle projection map into grids of the same size, and the number of grids is a*a.

S3: Inflate the shadow of the obstacle. As long as the shadow of the obstacle exists in the grid, it is set to a black obstacle grid, otherwise it is a white obstacle-free grid, as shown in Figure 4.

S4: Extract the vertex grid of the black obstacle grid as a feature point, and the numbered vertex grid distribution diagram is shown in Figure 5.

S5: Judging the feasibility of the extracted vertex grid, and reconstructing the adjacency matrix D, the size of which is a ² *a ² .

S6: Set the initial parameter value of the ant colony algorithm: m is the number of ants in each generation, n is the total number of generations of ants, τ(0) is the initial pheromone concentration, Tabu is the cell structure size of m*n, It is used to record the route that each ant walks. The size of the path length matrix PL is m*n, which is used to record the length of the route that each ant crawls in each generation; at the same time, the pheromone attenuation coefficient ρ and the pheromone heuristic factor α are initialized. The distance heuristic factor β, the number of iterations t, and the start and end points.

S7: Put all the ants of the current generation at the starting point, and start the path search.

S8: Select the next grid according to the transition probability and the non-zero grid in the adjacency matrix, until the end point is reached, and a path search is completed.

S9: Determine whether all the ants of the current generation have completed the path search, if all the search is completed, go to S10, otherwise return to S8.

S10: record the number of iterations, t=t+1.

S11: Determine whether the number of iterations t meets the requirements of the number of iterations, and if so, output the shortest path, otherwise, enter S12, and the final optimal route is shown in Figure 7.

S12: Update the pheromone, and send the next generation of ants, and return to S7.

Further, in the step S4, the extracted feature points include: four vertex angles of all individual black obstacle grids, and all vertex angles and concave corners of all combined black obstacle grids.

Further, in the step S5, the method for judging the feasibility of the grid is, as shown in FIG. 6 , if there is a black obstacle grid between the two vertex grids, it is determined that the two vertex grids are not visible, and they are each other. Infeasible grid; if there is no black obstacle grid between the two vertex grids, judge whether the line connecting the two vertex grids passes through the vertices of the black obstacle grid. , then it is determined that the two vertex grids are invisible and mutually infeasible grids. If the vertex of the black obstacle grid is not passed, the two vertex grids are determined to be visible and mutually feasible grids.

Further, in the step S8, the transition probability formula for the ants to select the next grid is:

where τ _ij (t) is the pheromone concentration between grids i and j when the iteration number is t, is the distance heuristic function between grids i and j when the number of iterations is t, and allowed _s is the grid represented by s when D(i, s)≠0 in the adjacency matrix D.

Further, in the step S12, the update formula of the pheromone is:

τ _ij (t+1)=(1-ρ)τ _ij (t)+Δτ _ij (t) (2)

Among them, τ _ij (k+1) is the pheromone concentration between grids i and j when the number of iterations is t, and Δτ _ij (t) is the information left by the current generation of ants between grids i and j sum of prime increments, is the pheromone increment left by the kth ant between grids i and j when the number of iterations is t.

To sum up, the AGV path planning method based on the feature point extraction ant colony algorithm proposed in the present disclosure overcomes the drawbacks of the traditional ant colony algorithm path planning, and improves the performance by extracting feature points and a new grid feasibility judgment method. The efficiency of the algorithm is improved, the planned path is safer and smoother, and better results are obtained. At the same time, this method can reduce the calculation amount of the algorithm during path planning, and at the same time make the planned path safer and smoother, which is conducive to the safe and reliable operation of the AGV.

The invention provides an AGV path planning method based on feature point extraction ant colony algorithm. The method includes environment modeling and path planning. The environment modeling includes the establishment of a grid map and the extraction of feature points. According to the pre-known AGV environment Map information, after projecting the three-dimensional obstacles to the two-dimensional plane grid map, divide the obstacle projection map into grids of the same size, and then inflate the shadow of the obstacles to obtain the initial grid map, in which the black obstacles are divided The vertices of the grid are extracted, and the adjacency matrix is reconstructed by judging the feasibility of the grid. The ant colony algorithm is used to plan the path between the feature points, and finally an obstacle-free path from the starting point to the end point is obtained. This method The AGV path planning method of the present invention overcomes the problem of low point-by-point search efficiency of the traditional ant colony algorithm, effectively saves calculation time, improves search efficiency, and makes the planned path smoother; at the same time, the new grid The feasibility judgment method can effectively solve the disadvantage that the planned path is too close to the obstacle, and is more conducive to the safe and reliable operation of the AGV.

An embodiment of the present invention further provides a computer-readable storage medium, where a computer program is stored on the computer-readable storage medium, and the program is executed by the processor in FIG. 1 .

Embodiments of the present invention also provide a computer program product including instructions. When the computer program product is run on a computer, the computer is caused to perform the method of FIG. 1 described above.

Those of ordinary skill in the art can understand that all or part of the processes in the methods of the above embodiments can be implemented by instructing relevant hardware through a computer program, and the program can be stored in a computer-readable storage medium. During execution, the processes of the embodiments of the above-mentioned methods may be included. The storage medium may be a magnetic disk, an optical disk, a read-only memory (Read-Only Memory, ROM), or a random access memory (Random Access Memory, RAM) or the like.

The above-mentioned embodiments only represent several embodiments of the present invention, and the descriptions thereof are specific and detailed, but should not be construed as a limitation on the scope of the patent of the present invention. It should be pointed out that for those of ordinary skill in the art, without departing from the concept of the present invention, several modifications and improvements can also be made, which all belong to the protection scope of the present invention. Therefore, the protection scope of the patent of the present invention should be subject to the appended claims.

The basic principles of the present disclosure have been described above with reference to specific embodiments. However, it should be pointed out that the advantages, advantages, effects, etc. mentioned in the present disclosure are only examples rather than limitations, and these advantages, advantages, effects, etc. should not be considered to be A must-have for each embodiment of the present disclosure. In addition, the specific details disclosed above are only for the purpose of example and easy understanding, but not for limitation, and the above details do not limit the present disclosure to be implemented by using the above specific details.

The block diagrams of devices, apparatuses, apparatuses, and systems referred to in this disclosure are merely illustrative examples and are not intended to require or imply that they must be connected, arranged, or configured in the manner shown in the block diagrams. As those skilled in the art will appreciate, these means, apparatuses, apparatuses, systems may be connected, arranged, configured in any manner. Words such as "including", "including", "having" and the like are open-ended words meaning "including but not limited to" and are used interchangeably therewith. As used herein, the words "or" and "and" refer to and are used interchangeably with the word "and/or" unless the context clearly dictates otherwise. As used herein, the word "such as" refers to and is used interchangeably with the phrase "such as but not limited to".

Also, as used herein, the use of "or" in a listing of items beginning with "at least one" indicates a separate listing, eg, a listing of "at least one of A, B, or C" means A or B or C , or AB or AC or BC, or ABC (ie A and B and C). Furthermore, the word "exemplary" does not imply that the described example is preferred or better than other examples.

The foregoing description has been presented for the purposes of illustration and description. This description, however, is not meant to limit embodiments of the present disclosure to the forms disclosed herein.

Claims (10)

1. a kind of AGV paths planning method based on feature point extraction ant group algorithm, which comprises the following steps:

It determines the position of barrier in AGV operation map, and the three-dimensional position of the barrier is projected on two-dimensional surface；

The barrier perspective view being projected on two-dimensional surface is split；

Expansionization processing is carried out to the barrier shade in the barrier perspective view after segmentation, and black obstacle will be set as The vertex grid of object grid is extracted as characteristic point；

Feasibility judgement is carried out to the grid extracted and constructs adjacency matrix；

Multiple initial parameter values of ant group algorithm are configured and route searching will be carried out when all ants of former generation are placed in starting point；

Next grid is selected according to the non-zero grid in the adjacency matrix of transition probability and construction until reaching home.

2. the AGV paths planning method according to claim 1 based on feature point extraction ant group algorithm, which is characterized in that The described pair of barrier perspective view being projected on two-dimensional surface is split and the processing of barrier expansionization includes: by the obstacle Object perspective view is divided into the identical grid of size, and the quantity of grid is a*a, if there are barrier shade in the grid after segmentation, It is then set to black barrier grid, is otherwise provided as white clear grid.

3. the AGV paths planning method according to claim 1 based on feature point extraction ant group algorithm, which is characterized in that The described pair of grid extracted carries out feasibility judgement and constructs adjacency matrix to include: construction adjacency matrix D, size a²* a²。

4. according to claim 1 be based on feature point extraction ant group algorithm AGV paths planning method, which is characterized in that institute State that be configured to multiple initial parameter values of ant group algorithm include: quantity that m is per generation population ant, n be ant in total Algebra, τ (0) are initial information element concentration；

Taboo list Tabu is that eucaryotic cell structure size is m*n, to record the route of each ant walking, path length matrix PL Size be m*n, the path length creeped to record each ant of every generation；

Initialization information element attenuation coefficient ρ, pheromones heuristic factor α, apart from heuristic factor β, the number of iterations t；And

The initial parameter value of beginning and end is configured.

5. according to claim 1 be based on feature point extraction ant group algorithm AGV paths planning method, which is characterized in that also Include: judgement when whether all ants of former generation are fully completed route searching, if being fully completed search, records an iteration time Number, wherein the number of iterations t=t+1；

Judge whether the number of iterations t meets the requirement of the number of iterations, exports shortest path if meeting；

If being unsatisfactory for the requirement of the number of iterations, updates pheromones and execute and next-generation ant is sent to operate；

The next-generation ant operation sent is considered as and works as former generation, will be searched when all ants of former generation are placed in starting point execution route Rope.

6. according to claim 1 be based on feature point extraction ant group algorithm AGV paths planning method, which is characterized in that also Include: whether judgement is fully completed route searching when all ants of former generation, if not being fully completed search, according to transition probability with And the non-zero grid in the adjacency matrix selects next grid until reaching home.

7. according to claim 1 be based on feature point extraction ant group algorithm AGV paths planning method, which is characterized in that institute State that extract the vertex grid for being set as black barrier grid as characteristic point include: by all independent black barriers Four apex angle grids of grid, all apex angles and re-entrant angle grid of all combination black barrier grids are mentioned as characteristic point It takes.

8. according to claim 1 be based on feature point extraction ant group algorithm AGV paths planning method, which is characterized in that institute If stating and carrying out feasibility judgement to the grid extracted includes: to sentence between two vertex grids there are black barrier grid Fixed two vertex grids are invisible, each other infeasible grid；

If black barrier grid is not present between two vertex grids, it is black to judge whether the line of two vertex grids passes through The vertex of color barrier grid, if determining that two vertex grids are invisible, each other not by the vertex of black barrier grid Feasible grid, if determining two vertex grids as it can be seen that feasible grid each other without the vertex of black barrier grid.

9. the AGV paths planning method according to claim 1 based on feature point extraction ant group algorithm, which is characterized in that Further include: the transition probability formula are as follows:

Wherein, τ_ijIt (t) is the pheromone concentration when the number of iterations is t between grid i and j,For iteration time The distance between grid i and j heuristic function when number is t, allowed_sFor in adjacency matrix D, the grid of behalf when D (i, s) ≠ 0 Lattice.

10. the AGV paths planning method according to claim 6 based on feature point extraction ant group algorithm, which is characterized in that The pheromones formula is

τ_ij(t+1)=(1- ρ) τ_ij(t)+Δτ_ij(t)

Wherein, τ_ij(k+1) for when the number of iterations is t, pheromone concentration between grid i and j, Δ τ_ij(t) for when former generation ant The sum of the pheromones increment that ant leaves between grid i and j,For when the number of iterations is t, kth ant is in grid The pheromones increment left between i and j.