Search

CN-121977553-A - Water surface unmanned ship path planning method based on improved cuckoo algorithm

CN121977553ACN 121977553 ACN121977553 ACN 121977553ACN-121977553-A

Abstract

The invention discloses a water surface unmanned ship path planning method based on an improved cuckoo algorithm, the invention introduces a self-adaptive step length updating mechanism combining a pheromone factor and a heuristic factor in the iterative process of the cuckoo algorithm. The pheromone factor guides searching to be conducted towards a history high-quality solution direction by referring to a positive feedback mechanism of an ant colony algorithm, the heuristic factor dynamically adjusts a step length direction according to a distance between a current optimal solution and a candidate solution to enhance local development capability, and the dynamic weight adjustment strategy is used for self-adaptively balancing global exploration and local searching in an iterative process, and discrete path points output by the algorithm are subjected to connectivity optimization by using a Dijkstra algorithm to obtain a continuous and collision-free navigable path. The invention obviously improves the convergence speed and the solving quality of path planning and enhances the autonomous navigation capability of the unmanned surface vessel in a complex environment.

Inventors

  • MA XIANGYI
  • SUN CHUANG
  • TANG ZONGYONG
  • WANG CHAO
  • YAN PENG

Assignees

  • 宜昌测试技术研究所

Dates

Publication Date
20260505
Application Date
20251229

Claims (8)

  1. 1. The water surface unmanned ship path planning method based on the improved cuckoo algorithm is characterized by comprising the following steps of: Step 1, establishing a two-dimensional gridding environment model, and setting a starting point and an ending point of the unmanned surface vehicle; Step 2, initializing a cuckoo population, setting a pheromone matrix and related parameters, and carrying out maximum iteration times; Step 3, introducing an adaptive step length updating mechanism combining a pheromone factor and a heuristic factor and dynamically adjusting weight in the iteration process of the cuckoo algorithm, and generating a new solution according to an improved Lewy flight formula; step 4, calculating fitness of the new solution, and reserving better individuals as new candidate solutions; step 5, performing discarding operation on the partial solutions according to the discovery probability to generate new nests and performing boundary constraint; step 6, updating the pheromone factors, evaluating the historical solution, and avoiding premature convergence; step 7, calculating fitness values of all solutions again, and reserving a better solution; step 8, iterating repeatedly until the termination condition is met, and outputting an optimal path point set; And 9, performing connectivity processing on the optimal path point set by adopting a Dijkstra algorithm to obtain a complete and continuous collision-free path.
  2. 2. The method according to claim 1, wherein the adaptive step size update mechanism in step 3 comprises: A pheromone factor, the value of which is updated according to the performance of the historical solution; heuristic factor, its value is calculated based on the distance between current solution and global optimal solution; And the dynamic weight adjustment strategy is used for adjusting the weights of the pheromone factors and the heuristic factors in the iterative process.
  3. 3. The method of claim 2, wherein the update formula of the pheromone factor is: Wherein, the Representing the volatilization rate of the pheromone; Is an evaluation candidate solution The objective function value of the mass, called the individual fitness function, is usually used to determine, in minimizing the problem, Smaller values indicate that the candidate solution is more optimal; is the pheromone record of the t iteration of the ith individual.
  4. 4. The method of claim 2, wherein the heuristic factor The calculation formula of (2) is as follows: Wherein, the Is the current solution; is the current optimal solution; Is the current solution And global optimal solution The Euclidean distance between the two reflects the similarity or the proximity degree between the two.
  5. 5. The method of claim 2, wherein in the dynamic weight adjustment strategy, pheromone weights And heuristic weights According to the iteration schedule Dynamically determining, wherein the calculation formula is as follows: Wherein t is the current iteration number, Is the maximum number of iterations.
  6. 6. The method according to claim 1, wherein the updating of the pheromone factor in the step 6 further comprises normalizing the pheromone factor: Wherein, the For the normalized pheromone factor, And Representing minimum and maximum pheromone values of all individuals in the current population respectively; Is a minimum value to avoid zero errors.
  7. 7. The method of claim 1, wherein the improved lewy flight formula in step 3 is: Wherein, the As a step-size factor, In order to obtain the random number of the Lewy, Is a normalized heuristic factor.
  8. 8. The method according to any one of claims 1-7, wherein in step 9, the Dijkstra algorithm is used to process the connectivity of the optimal set of path points, in particular to perform a connection and smoothing process on the discrete path points, so as to ensure the continuity and collision-free performance of the output path.

Description

Water surface unmanned ship path planning method based on improved cuckoo algorithm Technical Field The invention belongs to the technical field of ship path planning, and particularly relates to a water surface unmanned ship path planning method based on an improved cuckoo algorithm. Background Compared with the traditional manned ship, the unmanned ship on the water surface has the advantages of small volume, strong maneuverability, controllable risk and the like, and can replace personnel to execute complex tasks in severe and high-risk marine environments. The method is widely applied to the scenes of ocean mapping, island patrol, offshore traffic monitoring, military reconnaissance, emergency rescue and the like, plays an increasingly critical role in modern ocean engineering, and the path planning method directly determines the safety of unmanned ship navigation and the reliability of task completion. The path planning algorithm can be divided into a traditional algorithm and an intelligent algorithm at present, the traditional algorithm can be divided into a geometric model searching algorithm and an artificial potential field algorithm, the probability abstract algorithm, and the intelligent algorithm can be divided into a group intelligent algorithm, an evolution algorithm and a human heuristic algorithm. The traditional algorithm has poor adaptability to environmental space change, and the human heuristic-based method, such as reinforcement learning and deep learning, has potential in processing complex environments and realizing autonomous decision, but has the problems of large resource consumption, long training time, dependence on a large amount of sample data and the like, so that the application in the underwater environment with limited resources is limited. In contrast, swarm intelligence algorithms exhibit their unique advantages, which are highly adaptive, robust, and parallel computing capabilities, and relatively low demands on resources. Compared with the similar algorithm, the cuckoo algorithm has the advantages of few parameters, simple realization and the like. Its synergy with the lewy flight mechanism gives the algorithm excellent global optimization capability. Implementation of the cuckoo algorithm will be based on the following three idealized rules: Provision 1. Each cuckoo only lays one egg at a particular time and randomly selects a parasitic nest to place the bird egg. Provision 2. Each generation reserves the parasitic nest with the best hatching conditions among all the parasitic nests selected randomly to the next generation, namely elite reservation mechanism. The number of parasitic nests which can be selected is set to be a fixed value, the host birds have a certain probability of finding foreign bird eggs, and the finding probability is that. Once found, the host bird has two options, one to destroy the bird's egg directly or push it out of the nest, and one to discard the nest and to reselect a new location to create the nest. Yang and Deb proposed a cuckoo search algorithm in 2009 to effectively solve the complex optimization problem by simulating parasitic brooding behavior of cuckoo. Li X et al propose new updating strategies based on optimal individuals and random individuals, combining the new strategies together by linearly decreasing probability rules. A new search strategy based on an orthogonal learning strategy is also presented to enhance the search capabilities of the basic cuckoo search algorithm. Liu Qing et al propose a multi-strategy fused golden sine cuckoo search algorithm, introduce a La Ding Chao cube sampling method to initialize a population, and enhance the population diversity of the CS algorithm. Xie Yongcheng et al incorporate genetic operators, 2-opt, metropolis criteria for simulated annealing algorithms, and insert, exchange, reverse order methods into the cuckoo search algorithm. In a complex environment path planning task, the traditional cuckoo algorithm has the following defects that (1) the Lewy flight searching process is too random and lacks an effective guiding mechanism, so that the randomness of the searching direction is large, (2) the convergence speed is low, and (3) the cuckoo algorithm is easy to sink into local optimum in a complex environment, so that the reliability of path planning is affected. Disclosure of Invention In view of the above, the invention provides a water surface unmanned ship path planning method based on an improved cuckoo algorithm, which aims to solve the problems of strong randomness, slow convergence speed, easy sinking into local optima and the like of the traditional cuckoo algorithm in a complex marine environment, thereby improving the reliability, the safety and the task execution efficiency of unmanned ship path planning. The technical scheme for realizing the invention is as follows: A water surface unmanned ship path planning method based on an improved cuckoo algorithm comprises the follo