A kind of underwater hiding-machine path planning system based on harmonic search algorithmTechnical field
The present invention relates to a kind of paths planning method, particularly to a kind of underwater hiding-machine path planning system based on harmonic search algorithm.
Background technology
Path planning problem is long-standing, has application in the research of robot field and aircraft, and path planning can be divided into again global path planning (static path planning) and local paths planning (active path planning) two kinds. Global path planning be according to priori when external environment is all known, the process in a collisionless path from starting point to impact point is cooked up according to certain criterion, and local paths planning is with the result of global path planning for guidance, utilize the local message that external sensor receives on its basis, around avoiding within the time short as far as possible, original unknown obstacle, produces the process of new route. This shows that the path planning no matter being dynamic or static will depend on the route programming result of the overall situation. The penetration path planning of underwater hiding-machine belongs to the one of global path planning, only also to take into account the exposure cost in path while considering collision prevention.
Path planning problem for the overall situation has had a variety of solution at present, as: the traditional algorithms such as Artificial Potential Field Method, logical sight method, in recent years along with the development of optimized algorithm, the particularly rise of intelligent optimization algorithm, greatly having promoted the development of paths planning method, genetic algorithm (GeneticAlgorithm), ant group algorithm (AntColonyAlgorithm) and particle cluster algorithm (ParticleSwarmOptimizers) have all had been applied among path planning. Compared to traditional path planning algorithm, intelligent algorithm has the advantage of oneself uniqueness, such as, traditional Artificial Potential Field Method is relatively difficult to setting up of Artificial Potential Field, when Artificial Potential Field build unreasonable time algorithm be easily trapped into locally optimal solution, and genetic algorithm and ant group algorithm are just absent from these problems.
Summary of the invention
It is an object of the invention to provide a kind of underwater hiding-machine paths planning method based on harmonic search algorithm.
The object of the present invention is achieved like this:
A kind of underwater hiding-machine paths planning method based on harmonic search algorithm, comprises the following steps:
(1) Step1. initiation parameter, and discretized space. When initializing except will by the parameter initialization of HS algorithm except, also to initialize several parameter, i.e. the free node number of every paths, the node number for evaluating path cost inserted of every section of path, two regulate weightWith. After parameter initialization completes, it is possible to space dimension being divided, the degree of concrete division is relevant with free node number.
(2) Step2. initializes harmony data base. Every paths means that a harmony vector, and each free node in path means that a tone, and harmony data base is made up of the HMS paths of stochastic generation in prominent anti-space.
(3) Step3. generates a new route: the three kinds of modes generated by new harmony generate a new path. For a three-dimensional path planning problem, if as stated above willAxle discretization, then each free node just can be byCoordinate figure andCoordinate figure (depth value) fixes, and will consider respectively when tone is finely tunedThe fine setting step-length of both directionWith. Such asIndividual free node is (In the plane of individual division), itsAxial coordinate is fixing, only to itCoordinate is finely tuned, if its coordinate is, then region should be positioned at through this point of fine setting, wherein,��
(4) Step4. updates harmony data base: adopt the evaluation function shown in formula (4-3) that newly-generated path is evaluated, if the new route path more worst than in harmony data base is good, then just replace worst path with new route, otherwise give up new route.
(5) Step5. judges whether to meet termination condition, and termination condition is typically set to a fixing cycle-index, and when arriving this cycle-index, algorithm terminates, and exports optimal path, otherwise returns Step3 and continues executing with.
Advantages of the present invention and effect:
(1) harmonic search algorithm of present invention application is subject to the inspiration of Cooperative Evolutionary Algorithm, coevolution thought is incorporated among HS algorithm, it is proposed that cooperation harmonic search algorithm (CHS). Being found by the test of standard test functions, CHS algorithm, compared to former algorithm, is greatly improved in convergence precision and convergence rate, and relative SGA and PSO algorithm, CHS algorithm can farthest avoid premature problem.
(2) by adopting CHS algorithm, HS algorithm, genetic algorithm and particle cluster algorithm to carry out the emulation experiment of path planning under simple and complicated two kinds of environment, experiment show CHS algorithm feasibility on path planning and the suitability, simultaneously compared with genetic algorithm and particle cluster algorithm, the path cost that CHS algorithm calculates is less, and path is also more smooth.
Accompanying drawing explanation
Fig. 1 is the flow chart of the paths planning method based on HS algorithm.
Detailed description of the invention
Below in conjunction with accompanying drawing citing, the present invention is described in more detail:
It is the paths planning method flow chart based on HS algorithm in conjunction with Fig. 1, Fig. 1. A kind of underwater hiding-machine paths planning method based on harmonic search algorithm, comprises the following steps:
(1) Step1. initiation parameter, and discretized space. When initializing except will by the parameter initialization of HS algorithm except, also to initialize several parameter, i.e. the free node number of every paths, the node number for evaluating path cost inserted of every section of path, two regulate weightWith. After parameter initialization completes, it is possible to space dimension being divided, the degree of concrete division is relevant with free node number.
(2) Step2. initializes harmony data base. Every paths means that a harmony vector, and each free node in path means that a tone, and harmony data base is made up of the HMS paths of stochastic generation in prominent anti-space.
(3) Step3. generates a new route: the three kinds of modes generated by new harmony generate a new path. For a three-dimensional path planning problem, if as stated above willAxle discretization, then each free node just can be byCoordinate figure andCoordinate figure (depth value) fixes, and will consider respectively when tone is finely tunedThe fine setting step-length of both directionWith. Such asIndividual free node is (In the plane of individual division), itsAxial coordinate is fixing, only to itCoordinate is finely tuned, if its coordinate is, then region should be positioned at through this point of fine setting, wherein,��
(4) Step4. updates harmony data base: adopt the evaluation function shown in formula (4-3) that newly-generated path is evaluated, if the new route path more worst than in harmony data base is good, then just replace worst path with new route, otherwise give up new route.
(5) Step5. judges whether to meet termination condition, and termination condition is typically set to a fixing cycle-index, and when arriving this cycle-index, algorithm terminates, and exports optimal path, otherwise returns Step3 and continues executing with.