CN105631540A - Underwater vehicle path planning system based on harmony search algorithm - Google Patents
Underwater vehicle path planning system based on harmony search algorithm Download PDFInfo
- Publication number
- CN105631540A CN105631540A CN201510988322.6A CN201510988322A CN105631540A CN 105631540 A CN105631540 A CN 105631540A CN 201510988322 A CN201510988322 A CN 201510988322A CN 105631540 A CN105631540 A CN 105631540A
- Authority
- CN
- China
- Prior art keywords
- path
- algorithm
- harmony
- coordinate
- data base
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
- G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
Landscapes
- Business, Economics & Management (AREA)
- Human Resources & Organizations (AREA)
- Engineering & Computer Science (AREA)
- Strategic Management (AREA)
- Economics (AREA)
- Marketing (AREA)
- Game Theory and Decision Science (AREA)
- Entrepreneurship & Innovation (AREA)
- Development Economics (AREA)
- Operations Research (AREA)
- Quality & Reliability (AREA)
- Tourism & Hospitality (AREA)
- Physics & Mathematics (AREA)
- General Business, Economics & Management (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Feedback Control In General (AREA)
Abstract
The invention provides an underwater vehicle path planning system based on harmony search algorithm. The following steps are comprised: (S1) initializing a parameter, and carrying out discrete processing on a space, (S2) initializing a harmony memory bank, (S3) generating a new path, (S4) updating the harmony memory bank, (S5) judging whether an ending condition is satisfied or not, and outputting an optimal path if so, otherwise returning to the step (3) to continue. According to the system, the idea of coevolution is introduced into the HS algorithm, and a cooperative harmony search (CHS) algorithm is provided. Through the testing of a standard testing function, compared with an original algorithm, the CHS algorithm has the advantage that the convergence accuracy and convergence speed are greatly improved, and compared with SGA and PSO algorithms, the e CHS algorithm has the advantage that the problem of premature convergence can be avoided to the largest degree.
Description
Technical 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.
Claims (1)
1. the underwater hiding-machine path planning system based on harmonic search algorithm, it is characterised in that: comprise 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,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.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510988322.6A CN105631540A (en) | 2015-12-27 | 2015-12-27 | Underwater vehicle path planning system based on harmony search algorithm |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510988322.6A CN105631540A (en) | 2015-12-27 | 2015-12-27 | Underwater vehicle path planning system based on harmony search algorithm |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN105631540A true CN105631540A (en) | 2016-06-01 |
Family
ID=56046447
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201510988322.6A Pending CN105631540A (en) | 2015-12-27 | 2015-12-27 | Underwater vehicle path planning system based on harmony search algorithm |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN105631540A (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106909145A (en) * | 2017-02-22 | 2017-06-30 | 武汉理工大学 | Unmanned hydrographical survey ship barrier real-time perception obstacle avoidance system and method |
| CN107329473A (en) * | 2017-07-09 | 2017-11-07 | 江西理工大学 | The robot polling path planing method searched for based on average harmony |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20130272202A1 (en) * | 2006-12-26 | 2013-10-17 | Dali Systems Co. Ltd. | Daisy-chained ring of remote units for a distributed antenna system |
| CN104197941A (en) * | 2014-09-16 | 2014-12-10 | 哈尔滨恒誉名翔科技有限公司 | Defense penetration path planning method of underwater vehicle based on harmony search algorithm |
| CN104317721A (en) * | 2014-11-12 | 2015-01-28 | 大连交通大学 | Regression test case selection method based on improved harmony search algorithm |
-
2015
- 2015-12-27 CN CN201510988322.6A patent/CN105631540A/en active Pending
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20130272202A1 (en) * | 2006-12-26 | 2013-10-17 | Dali Systems Co. Ltd. | Daisy-chained ring of remote units for a distributed antenna system |
| CN104197941A (en) * | 2014-09-16 | 2014-12-10 | 哈尔滨恒誉名翔科技有限公司 | Defense penetration path planning method of underwater vehicle based on harmony search algorithm |
| CN104317721A (en) * | 2014-11-12 | 2015-01-28 | 大连交通大学 | Regression test case selection method based on improved harmony search algorithm |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106909145A (en) * | 2017-02-22 | 2017-06-30 | 武汉理工大学 | Unmanned hydrographical survey ship barrier real-time perception obstacle avoidance system and method |
| CN107329473A (en) * | 2017-07-09 | 2017-11-07 | 江西理工大学 | The robot polling path planing method searched for based on average harmony |
| CN107329473B (en) * | 2017-07-09 | 2020-02-07 | 江西理工大学 | Robot inspection path planning method based on mean value and sound search |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Zhang et al. | Sequential approximate optimization for design under uncertainty problems utilizing Kriging metamodeling in augmented input space | |
| CN110928295B (en) | Robot path planning method integrating artificial potential field and logarithmic ant colony algorithm | |
| US9789651B2 (en) | Method for structure preserving topology optimization of lattice structures for additive manufacturing | |
| JP5475629B2 (en) | Trajectory planning method, trajectory planning system, and robot | |
| CN108241369B (en) | Method and device for avoiding static obstacle for robot | |
| CN103365293A (en) | Robot safety path planning method based on dynamic region division | |
| CN102331711A (en) | Formation control method for mobile autonomous robots | |
| CN113050648B (en) | Robot obstacle avoidance method and system | |
| CN114370878A (en) | Multi-AUV cooperative positioning method based on STACKF | |
| CN105631540A (en) | Underwater vehicle path planning system based on harmony search algorithm | |
| US10339370B2 (en) | Method and apparatus for determining obstacle collision by using object moving path | |
| CN104197941A (en) | Defense penetration path planning method of underwater vehicle based on harmony search algorithm | |
| WO2016129078A1 (en) | Route selection device and route selection program | |
| Biyela et al. | Development of an optimal state transition graph for trajectory optimisation of dynamic systems by application of Dijkstra's algorithm | |
| CN115016510A (en) | A robot navigation obstacle avoidance method, device and storage medium | |
| FI129592B (en) | Computer-aided modeling | |
| CN109543225A (en) | Control program generation method, device, storage medium and the electronic equipment of vehicle | |
| EP3904907A1 (en) | Methods and systems for tracking an object | |
| CN118092418A (en) | A control method for multiple UAVs to collaboratively track ground moving targets | |
| Wu et al. | Terminal guidance law for UAV based on receding horizon control strategy | |
| Xu et al. | Dual‐Model Reverse CKF Algorithm in Cooperative Navigation for USV | |
| Yang et al. | A grey wolf optimizer-based topology shaping method for uav swarm | |
| CN120632794B (en) | Multi-rover coverage method in priori unknown environment | |
| CN105737829A (en) | Harmony search algorithm-based underwater vehicle path planning system | |
| Wang et al. | An information fusion algorithm for INS/DVL/USBL integrated navigation system based on delay state unscented Kalman filter |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| WD01 | Invention patent application deemed withdrawn after publication | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20160601 |