CN106292673A - A kind of method for optimizing route and system - Google Patents

Abstract

The present invention is suitable for field of computer technology, it is provided that a kind of method for optimizing route and system, the method includes: after utilizing polynomial transformation to correct image, detects the edge of barrier in image；The summit of described barrier is marked, and forms first path by choosing the summit of described barrier；Described first path is passed sequentially through intersection and mutation operation, forms the second path；According to default summit quantity, described second path is chosen subpath, and judges can go directly between the Origin And Destination in described subpath, to determine path optimizing.The present invention is by processing image so that in image, the profile of barrier becomes apparent from, in order to improve the degree of accuracy of path planning, on the basis of global path planning, successively subpath is processed, improve the degree of accuracy of path planning further, improve machine task efficiency.

Description

A kind of method for optimizing route and system

Technical field

The invention belongs to field of computer technology, particularly relate to a kind of method for optimizing route and system.

Background technology

Path planning is indispensable important component part in intelligent robot navigation technology, is also present stage intelligent machine The main direction of studying of device people research, good path planning can be saved the robot substantial amounts of activity duration and reduce machine The loss of people, especially plays even more important effect in Post disaster relief field.Affect path planning and have two aspects: one is From aerial photographing image, owing to being limited to environment and technology, the angle of shooting can not be exactly perpendicularly to ground, therefore shooting angle The profile of the barrier on ground there is is the biggest impact, easily causes erroneous judgement, thus affect planning effect；Another is to use Global path planning method is in the case of environmental information is all known, finds road preferably by global path planning Footpath, amount of calculation is too big, and real-time is not good enough.

Summary of the invention

It is an object of the invention to provide a kind of method for optimizing route and system, it is intended to solve path planning in prior art It is limited to picture quality and data amount of calculation, causes to find more optimal path in the short time.

On the one hand, the invention provides a kind of method for optimizing route, described method comprises the steps:

After utilizing polynomial transformation to correct image, the edge of barrier in image is detected；

The summit of described barrier is marked, and forms first path by choosing the summit of described barrier；

Described first path is passed sequentially through intersection and mutation operation, forms the second path；

According to default summit quantity, described second path is chosen subpath, and judges the starting point in described subpath And can go directly between terminal, to determine path optimizing.

On the other hand, the invention provides a kind of path optimizing system, described system includes:

Graphics processing unit, after being used for utilizing polynomial transformation to correct image, to the edge of barrier in image Detect；

First path forms unit, for being marked the summit of described barrier, and by choosing described barrier Summit formed first path；

Second path forms unit, for described first path passes sequentially through intersection and mutation operation, forms second Path；And

Path optimization's unit, for according to default summit quantity, chooses subpath in described second path, and judges institute State and can go directly between the Origin And Destination in subpath, to determine path optimizing.

The embodiment of the present invention is by processing image so that in image, the profile of barrier becomes apparent from, in order to Improve the degree of accuracy of path planning, on the basis of global path planning, successively subpath is processed, improve further The degree of accuracy of path planning, improves machine task efficiency.

Accompanying drawing explanation

Fig. 1 is the flowchart of the method for optimizing route that the embodiment of the present invention one provides；And

Fig. 2 is the structural representation of the path optimizing system that the embodiment of the present invention two provides；

Detailed description of the invention

In order to make the purpose of the present invention, technical scheme and advantage clearer, below in conjunction with drawings and Examples, right The present invention is further elaborated.Should be appreciated that specific embodiment described herein only in order to explain the present invention, and It is not used in the restriction present invention.

Below in conjunction with specific embodiment the present invention implemented and is described in detail:

Embodiment one:

Fig. 1 shows the flowchart of the method for optimizing route that the embodiment of the present invention one provides, for convenience of description, only Showing the part relevant to the embodiment of the present invention, details are as follows:

In step S101, after utilizing polynomial transformation to correct image, the edge of barrier in image is carried out Detection.

In embodiments of the present invention, image generating, transmit, process, send and during the process such as reception, inevitably By interference and the impact of various noises, such as in atmospheric environment, scattering can be produced due to light in atmosphere and absorb, making Obtain some greyish white effect of local possible generation of image, cause the contrast of image to decline seriously, the most even can affect image Visual effect and cannot be carried out next step process.Therefore, the first image to air-robot collection carries out pretreatment, preferably Ground, the denoising method that can use is median filtering method and morphology denoising.To the correct image after denoising, utilize coordinate Between polynomial transformation carry out this nonlinear distortion of approximate representation, and choose some control point to eliminate distortion.

Specifically, on image point (x, y), point after utilizing polynomial transformation to be corrected (f, g), formula 1 is as follows:

$\left\{\begin{array}{c}x=\underset{i=0}{\overset{n}{\mathrm{\Σ}}}\underset{j=0}{\overset{n-i}{\mathrm{\Σ}}}{a}_{ij}{f}^i{g}^j\\ y=\underset{i=0}{\overset{n}{\mathrm{\Σ}}}\underset{j=0}{\overset{n-i}{\mathrm{\Σ}}}{b}_{ij}{f}^i{g}^j\end{array}\right.$

Wherein, a_ij, b_ijFor polynomial coefficient, n is number of times, utilizes known control point to solve.

If control point number is identical with the number of unknown number in equation group, then can be with direct solution equation group；And one As image distortion correction process, in order to obtain higher calibration accuracy, control point number can be unknown more than in equation group The number of number, by seeking the best fit approximation solution under error sum of squares minimum criteria, specific practice is as follows:

It is to L control point, minimum by the error sum of squares after fitting of a polynomial, it may be assumed that

$\mathrm{\ϵ}=\underset{l=1}{\overset{L}{\mathrm{\Σ}}}{\[x-\underset{i=0}{\overset{n}{\mathrm{\Σ}}}\underset{j=0}{\overset{n-i}{\mathrm{\Σ}}}{a}_{ij}{f}_l^i{g}_l^j\]}^2=\min$

Then have:

$\frac{\∂\mathrm{\ϵ}}{\∂a_{st}}=2\underset{l=1}{\overset{L}{\mathrm{\Σ}}}(\underset{i=0}{\overset{n}{\mathrm{\Σ}}}\underset{j=0}{\overset{n-i}{\mathrm{\Σ}}}{a}_{ij}{f}_l^i{g}_l^j-x_l)f_l^s{g}_l^t=0$

Can obtain, formula 2:

$\underset{l=1}{\overset{L}{\mathrm{\Σ}}}\left(\underset{i=0}{\overset{n}{\mathrm{\Σ}}}\underset{j=0}{\overset{n-i}{\mathrm{\Σ}}}{a}_{ij}{f}_l^i{g}_l^j\right)f_l^i{g}_l^j=\underset{i=0}{\overset{n}{\mathrm{\Σ}}}\underset{j=0}{\overset{n-i}{\mathrm{\Σ}}}{a}_{ij}\left(\underset{l=1}{\overset{L}{\mathrm{\Σ}}}{f}_l^{i+s}{g}_l^{j+t}\right)=\underset{l=1}{\overset{L}{\mathrm{\Σ}}}{x}_l{f}_l^s{g}_l^t$

In like manner have, formula 3:

$\underset{l=1}{\overset{L}{\mathrm{\Σ}}}\left(\underset{i=0}{\overset{n}{\mathrm{\Σ}}}\underset{j=0}{\overset{n-i}{\mathrm{\Σ}}}{b}_{ij}{f}_l^i{g}_l^j\right)f_l^i{g}_l^j=\underset{i=0}{\overset{n}{\mathrm{\Σ}}}\underset{j=0}{\overset{n-i}{\mathrm{\Σ}}}{b}_{ij}\left(\underset{l=1}{\overset{L}{\mathrm{\Σ}}}{f}_l^{i+s}{g}_l^{j+t}\right)=\underset{l=1}{\overset{L}{\mathrm{\Σ}}}{y}_l{f}_l^s{g}_l^t$

In above-mentioned formula, L is the number at control point, s=0,1,2 ..., n；T=0,1,2 ..., n-s；s+t≤n.

Formula 2 and formula 3 all comprise (n+1) (n+2)/2, then can form system of linear equations, solve a_ijAnd b_ij, bring into Formula 1 just can obtain the point after correction (f, g).

Calibration accuracy is relevant with correction degree of polynomial n used, and the degree of polynomial is the highest, and error of fitting is the least, but Along with n increases, number of coefficients increases, and causes amount of calculation to sharply increase, to general non-linear distortion, generally use three times multinomial Formula is fitted, and method is fairly simple effectively, and accuracy is higher, and this up-to-date style 1 can be written as:

$\left\{\begin{array}{c}x=a_{00}+a_{01}f+a_{02}{f}^2+a_{03}{f}^3+a_{10}g+a_{11}fg+\\ a_{12}{f}^{2}g+a_{20}{g}^2+a_{21}{\mathrm{fg}}^2+a_{30}{g}^3\\ y=b_{00}+b_{01}f+b_{02}{f}^2+b_{03}{f}^3+b_{10}g+b_{11}fg+\\ b_{12}{f}^{2}g+b_{20}{g}^2+b_{21}{\mathrm{fg}}^2+b_{30}{g}^3\end{array}\right.$

Further, the edge of barrier in image is carried out detection to include:

Utilize median filtering method that described figure is carried out denoising, remove the noise in described image and retain edge Information；

Each pixel in described image being calculated Grad, respectively x direction and y direction is done convolution algorithm, formula is such as Under:

$F_x=\left(\begin{array}{cc}-1& 1\\ -1& 1\end{array}\right)F_y=\left(\begin{array}{cc}-1& 1\\ -1& 1\end{array}\right)$

Can be calculated:

Described Grad is carried out non-maximum restraining；

Carrying out rim detection according to high threshold and Low threshold, and be attached edge, described high threshold is set as institute State Low threshold three times.

In step s 102, the summit of barrier is marked, and forms the first via by choosing the summit of barrier Footpath.

In embodiments of the present invention, it is G by the obstacle tag in image_nAnd the apex marker of barrier is M_mun, its In, G_nRepresent the numbering of barrier, be labeled as successively: G₀,G₁,G₂…G_n, M_munRepresent the numbering on summit in barrier；According to institute The starting point determined and terminal, obtain from all paths of origin-to-destination, and path is made up of the summit of barrier；From path Choosing first path, the selected probability in path is:

$p_i=\frac{f_i}{{\mathrm{\Σ}}_{j=1}^N{f}_j}$

Wherein, p_iRepresent the selected probability of path i, f_iRepresenting the adaptive response of path i, N represents the total of all paths Number.

Using path as population, path is as individuality, from each summit of origin-to-destination process as gene in path, Selecting excellent individuality from population, and eliminate bad gene, the purpose choosing first path from path is property Can directly entail the next generation by good individuality.In population, individual selected probability is directly proportional to the size of its fitness, if planting The size of group is N, and the fitness of one of them individual i is f_i, fitness function is to take bigger value S_maxDeduct path length Degree S, path S is the biggest, and fitness f is the least；Path S is the least, and fitness f is the biggest, according to fitness function, fitness The probability that the individuality of the least (path is the longest) is eliminated is the biggest, and the probability that the individuality of fitness the biggest (path is the shortest) is eliminated is more Little.It is formulated as follows:

F=S_max-S

The path overall length of process between starting point to current individual that S therein represents, and S_maxThen much larger than S.From upper Stating formula visible, the path between starting point of current point is the shortest, and fitness is the biggest, chooses the follow-on probability of entrance with suitable Response is directly proportional.

In step s 103, first path is passed sequentially through intersection and mutation operation, forms the second path.

In embodiments of the present invention, the operation that intersects is to be recombinated by portion gene individual for two parents in population, Generate new two new individualities, be to choose a less Probability p when carrying out individual selection_a, then randomly select a probability Number p_b, work as p_b>p_aTime, in the most selected entrance chiasmatic cistern, wait for intersection operation, such as: p can be selected_a=0.2, and p_b Randomly choosing a number in (0,1), the number so the selected probability more than 0.2 will be bigger, it is ensured that most Individuality has all carried out intersecting operating, and the individuality carrying out intersecting is the most, and in population, the multiformity of gene is the biggest, more can produce excellent Good gene.

Mutation operation refers to be changed the characteristic of individuality by random some gene changed in individuality, thus is formed new Individual, although variation individual must be excellent genes, but this has very important effect to the multiformity of increase population, because of Less, so it is made a variation by choose here less probability for producing the probability of excellent individuality.Such as choose One fixing Probability p_c=0.8, then randomly select the several p in (0,1)_d, work as p_d>p_cTime, the individuality the most currently chosen becomes Different, the individual relative morphed in such population is less, so can both ensure not produce a lot of bad individuality, can protect again The multiformity of card population.

In step S104, according to default summit quantity, the second path is chosen subpath, and judges in subpath Can go directly between Origin And Destination, to determine path optimizing.

In embodiments of the present invention, the physical features value on each barrier summit in described image is calculated；By described second path From the off, according to default summit quantity, subpath is chosen successively；Calculate the length of described subpath, and select physical features The set on value summit between the physical features value of starting point and the physical features value of terminal of subpath.

If can go directly between the Origin And Destination in described subpath, then the straight line path that beginning and end connects is determined For path optimizing；If can not go directly between the Origin And Destination in described subpath, then in the set on described summit, lookup is 1 or 2 summits of no existence so that the path through described 1 or 2 summit is less than the length of described subpath, if There are described 1 or 2 summits, then by the path through described 1 or 2 summit.

The embodiment of the present invention is by processing image so that in image, the profile of barrier becomes apparent from, in order to Improve the degree of accuracy of path planning, on the basis of global path planning, successively subpath is processed, improve further The degree of accuracy of path planning, improves machine task efficiency.

Embodiment two:

Fig. 2 shows the structural representation of the path optimizing system that the embodiment of the present invention two provides, for convenience of description, only Show the part relevant to the embodiment of the present invention.This path optimizing system includes: graphics processing unit 21, first path are formed Unit the 22, second path forms unit 23 and path optimization's unit 24, wherein:

Graphics processing unit 21, after being used for utilizing polynomial transformation to correct image, to the limit of barrier in image Edge detects.

In embodiments of the present invention, image generating, transmit, process, send and during the process such as reception, inevitably By interference and the impact of various noises, such as in atmospheric environment, scattering can be produced due to light in atmosphere and absorb, making Obtain some greyish white effect of local possible generation of image, cause the contrast of image to decline seriously, the most even can affect image Visual effect and cannot be carried out next step process.Therefore, the first image to air-robot collection carries out pretreatment, preferably Ground, the denoising method that can use is median filtering method and morphology denoising.To the correct image after denoising, utilize coordinate Between polynomial transformation carry out this nonlinear distortion of approximate representation, and choose some control point to eliminate distortion.

Specifically, graphics processing unit 21 includes: image correction unit and edge detection unit, wherein:

Image correction unit, for on described image point (x, y), the point after utilizing polynomial transformation to be corrected (f,g)。

Edge detection unit, specifically for:

Utilize median filtering method that described figure is carried out denoising, remove the noise in described image and retain edge Information；

Each pixel in described image is calculated Grad, respectively convolution algorithm is done in x direction and y direction；

Described Grad is carried out non-maximum restraining；

Carrying out rim detection according to high threshold and Low threshold, and be attached edge, described high threshold is set as institute State Low threshold three times.

First path forms unit 22, for being marked the summit of barrier, and by choosing the summit of barrier Form first path.

First path forms unit and includes:

Indexing unit, being used for the obstacle tag in described image is G_nAnd the apex marker of described barrier is M_mun, wherein, G_nRepresent the numbering of described barrier, be labeled as successively: G₀,G₁,G₂…G_n, M_munRepresent summit in described barrier Numbering；

Path forms unit, for starting point and terminal determined by basis, obtains from all paths of origin-to-destination, Described path is made up of the summit of described barrier；

First path forms subelement, for choosing first path from described path.

In embodiments of the present invention, it is G by the obstacle tag in image_nAnd the apex marker of barrier is M_mun, its In, G_nRepresent the numbering of barrier, be labeled as successively: G₀,G₁,G₂…G_n, M_munRepresent the numbering on summit in barrier；According to institute The starting point determined and terminal, obtain from all paths of origin-to-destination, and path is made up of the summit of barrier；From path Choosing first path, the selected probability in path is:

$p_i=\frac{f_i}{{\mathrm{\Σ}}_{j=1}^N{f}_j}$

Wherein, p_iRepresent the selected probability of path i, f_iRepresenting the adaptive response of path i, N represents the total of all paths Number.

Using path as population, path is as individuality, from each summit of origin-to-destination process as gene in path, Selecting excellent individuality from population, and eliminate bad gene, the purpose choosing first path from path is property Can directly entail the next generation by good individuality.In population, individual selected probability is directly proportional to the size of its fitness, if planting The size of group is N, and the fitness of one of them individual i is f_i, fitness function is to take bigger value S_maxDeduct path length Degree S, path S is the biggest, and fitness f is the least；Path S is the least, and fitness f is the biggest, according to fitness function, fitness The probability that the individuality of the least (path is the longest) is eliminated is the biggest, and the probability that the individuality of fitness the biggest (path is the shortest) is eliminated is more Little.It is formulated as follows:

F=S_max-S

The path overall length of process between starting point to current individual that S therein represents, and S_maxThen much larger than S.From upper Stating formula visible, the path between starting point of current point is the shortest, and fitness is the biggest, chooses the follow-on probability of entrance with suitable Response is directly proportional.

Second path forms unit 23, for first path passes sequentially through intersection and mutation operation, forms the second tunnel Footpath.

In embodiments of the present invention, the operation that intersects is to be recombinated by portion gene individual for two parents in population, Generate new two new individualities, be to choose a less Probability p when carrying out individual selection_a, then randomly select a probability Number p_b, work as p_b>p_aTime, in the most selected entrance chiasmatic cistern, wait for intersection operation, such as: p can be selected_a=0.2, and p_b Randomly choosing a number in (0,1), the number so the selected probability more than 0.2 will be bigger, it is ensured that most Individuality has all carried out intersecting operating, and the individuality carrying out intersecting is the most, and in population, the multiformity of gene is the biggest, more can produce excellent Good gene.

Mutation operation refers to be changed the characteristic of individuality by random some gene changed in individuality, thus is formed new Individual, although variation individual must be excellent genes, but this has very important effect to the multiformity of increase population, because of Less, so it is made a variation by choose here less probability for producing the probability of excellent individuality.Such as choose One fixing Probability p_c=0.8, then randomly select the several p in (0,1)_d, work as p_d>p_cTime, the individuality the most currently chosen becomes Different, the individual relative morphed in such population is less, so can both ensure not produce a lot of bad individuality, can protect again The multiformity of card population.

Path optimization's unit 24, for according to default summit quantity, chooses subpath in the second path, and judges sub-road Can go directly between Origin And Destination in footpath, to determine path optimizing.

In embodiments of the present invention, the physical features value on each barrier summit in described image is calculated；By described second path From the off, according to default summit quantity, subpath is chosen successively；Calculate the length of described subpath, and select physical features The set on value summit between the physical features value of starting point and the physical features value of terminal of subpath.

If can go directly between the Origin And Destination in described subpath, then the straight line path that beginning and end connects is determined For path optimizing；If can not go directly between the Origin And Destination in described subpath, then in the set on described summit, lookup is 1 or 2 summits of no existence so that the path through described 1 or 2 summit is less than the length of described subpath, if There are described 1 or 2 summits, then by the path through described 1 or 2 summit.

The embodiment of the present invention is by processing image so that in image, the profile of barrier becomes apparent from, in order to Improve the degree of accuracy of path planning, on the basis of global path planning, successively subpath is processed, improve further The degree of accuracy of path planning, improves machine task efficiency.

In embodiments of the present invention, each unit can be realized by corresponding hardware or software unit, and each unit can be independent Soft and hardware unit, it is also possible to be integrated into a soft and hardware unit, at this not in order to limit the present invention.

The foregoing is only presently preferred embodiments of the present invention, not in order to limit the present invention, all essences in the present invention Any amendment, equivalent and the improvement etc. made within god and principle, should be included within the scope of the present invention.

Claims (10)

1. a paths planning method, it is characterised in that described method comprises the steps:

After utilizing polynomial transformation to correct image, the edge of barrier in image is detected；

The summit of described barrier is marked, and forms first path by choosing the summit of described barrier；

Described first path is passed sequentially through intersection and mutation operation, forms the second path；

According to default summit quantity, described second path is chosen subpath, and judges the starting point in described subpath and end Can go directly between point, to determine path optimizing.

2. the method for claim 1, it is characterised in that described utilize the polynomial transformation step to correct image Suddenly, including:

For on described image point (x, y), point after utilizing polynomial transformation to be corrected (f, g), calculating formula is as follows:

$\left\{\begin{array}{c}x=\underset{i=0}{\overset{n}{\Σ}}\underset{j=0}{\overset{n-i}{\Σ}}{\mathrm{\α}}_{ij}{f}^i{g}^j\\ y=\underset{i=0}{\overset{n}{\Σ}}\underset{j=0}{\overset{n-i}{\Σ}}{b}_{ij}{f}^i{g}^j\end{array}\right.$

Wherein, a_ij, b_ijFor polynomial coefficient, n is number of times, utilizes known control point to solve.

3. the method for claim 1, it is characterised in that the described step that the edge of barrier in image is detected Suddenly, including:

Utilize median filtering method that described figure is carried out denoising, remove the noise in described image and retain edge letter Breath；

Each pixel in described image being calculated Grad, respectively x direction and y direction is done convolution algorithm, formula is as follows:

$F_x=\left(\begin{array}{cc}-1& 1\\ -1& 1\end{array}\right)F_y=\left(\begin{array}{cc}-1& 1\\ -1& 1\end{array}\right)$

Can be calculated:

Described Grad is carried out non-maximum restraining；

Carrying out rim detection according to high threshold and Low threshold, and be attached edge, described high threshold is set as described low Three times of threshold value.

4. the method for claim 1, it is characterised in that the described summit to described barrier is marked, and passes through The summit choosing described barrier forms the step of first path, including:

It is G by the obstacle tag in described image_nAnd the apex marker of described barrier is M_mun, wherein, G_nRepresent described The numbering of barrier, is labeled as successively: G₀,G₁,G₂…G_n, M_munRepresent the numbering on summit in described barrier；

Starting point determined by according to and terminal, obtain from all paths of origin-to-destination, and described path is by described barrier Summit composition；

Choosing first path from described path, the selected probability in described path is:

$p_i=\frac{f_i}{{\mathrm{\Σ}}_{j=1}^N{f}_j}$

Wherein, p_iRepresent the selected probability of path i, f_iRepresenting the adaptive response of path i, N represents the sum in all paths.

5. the method for claim 1, it is characterised in that described according to default summit quantity, in described second path Choose subpath, by judging that can described subpath go directly, to determine the step of path optimizing, including:

Calculate the physical features value on each barrier summit in described image；

By described second path from the off, according to default summit quantity, subpath is chosen successively；

Calculate the length of described subpath, and select physical features value between the physical features value of the starting point of subpath and the physical features of terminal The set on the summit between value.

6. method as claimed in claim 5, it is characterised in that described according to default summit quantity, in described second path Choose subpath, and judge can go directly between the Origin And Destination in described subpath, to determine the step of path optimizing, also Including:

If can go directly between the Origin And Destination in described subpath, then the straight line path that beginning and end connects is defined as excellent Change path；

If can not go directly between the Origin And Destination in described subpath, then search whether to have 1 in the set on described summit Individual or 2 summits so that the path through described 1 or 2 summit is less than the length of described subpath, if existing described 1 or 2 summits, then by the path through described 1 or 2 summit.

7. a path optimizing system, it is characterised in that described system includes:

Graphics processing unit, after being used for utilizing polynomial transformation to correct image, is carried out the edge of barrier in image Detection；

First path forms unit, for being marked the summit of described barrier, and by choosing the top of described barrier Point forms first path；

Second path forms unit, for described first path passes sequentially through intersection and mutation operation, forms the second path； And

Path optimization's unit, for according to default summit quantity, chooses subpath in described second path, and judges described son Can go directly between Origin And Destination in path, to determine path optimizing.

8. system as claimed in claim 7, it is characterised in that described graphics processing unit includes:

Image correction unit, for on described image point (x, y), point after utilizing polynomial transformation to be corrected (f, g)。

9. system as claimed in claim 7, it is characterised in that described graphics processing unit also includes edge detection unit, tool Body is used for:

Utilize median filtering method that described figure is carried out denoising, remove the noise in described image and retain edge letter Breath；

Each pixel in described image is calculated Grad, respectively convolution algorithm is done in x direction and y direction；

Described Grad is carried out non-maximum restraining；

Carrying out rim detection according to high threshold and Low threshold, and be attached edge, described high threshold is set as described low Three times of threshold value.

10. system as claimed in claim 7, it is characterised in that described first path forms unit and includes:

Indexing unit, being used for the obstacle tag in described image is G_nAnd the apex marker of described barrier is M_mun, its In, G_nRepresent the numbering of described barrier, be labeled as successively: G₀,G₁,G₂…G_n, M_munRepresent the volume on summit in described barrier Number；

Path forms unit, for starting point and terminal determined by basis, obtains from all paths of origin-to-destination, described Path is made up of the summit of described barrier；

First path forms subelement, for choosing first path from described path.