Research On Reliable Path Planning Algorithms In Dynamic Uncertain Environments

With the improvement of computing power and the progress of control technology,UAV is more and more widely used in industrial production and daily life.Path planning is one of the core issues in the field of UAV,and multi-target surveillance is an important application of path planning.Swarm intelligence is a kind of intelligent computing.It has the advantages of fast convergence,low computing cost and strong optimization ability.It is widely used in function optimization,traveling salesman problem,dependent optimization problem and job scheduling.At present,the research of multi-target surveillance is limited to static environment or random obstacle environment.In fact,the dynamic obstacles in the real scenario often show obvious regularity.According to the collection of obstacle information,obstacle characteristics and physical kinematics,the dynamic obstacles can be modeled to predict their change dynamics,which helps to improve the reliability of the path and reduce the repeated calculation and resource waste caused by the change of obstacles.In order to alleviate the limitations of previous work,this thesis proposes a dynamic obstacle modeling method,and designs a set-based comprehensive learning particle swarm optimization with local search to solve the reliable path planning problem in dynamic environment.The innovations of this thesis are as follows:（1）A new method of dynamic obstacle modeling is proposed.According to the working environment of UAV and the possible situation in reality,a problem model of multi-target surveillance in dynamic environment is designed.The moving cost between any two targets depends not only on the path length,but also on the path threat weighted by collision penalty.Four kinds of dynamic obstacle models with different characteristics and difficulties,including sudden appearance,slow movement and periodic appearance,are designed and analyzed for experimental research.The instance in the TSP library is introduced,and the nodes in the instance are used as the surveillance target of UAV.The dynamic obstacle model and the target set in the TSP instance constitute the example of dynamic environment multi-target surveillance used in this thesis.A simulation method is proposed to evaluate the solution obtained by the algorithm optimization.When evaluating the path,the moving process of UAV will be simulated,and the obstacle position will be predicted according to the moving time,so as to calculate the path threat.The reliable path is a path without threat.（2）An adaptive set-based comprehensive learning particle swarm optimization with local search（S-CLPSO+LS）is proposed.On one hand,the local search operator is introduced to strengthen the search of the neighborhood of the optimal individual;On the other hand,an adaptive path adjustment method is introduced.After detecting the change of obstacle model,the path is automatically adjusted to adapt to the change.The algorithms for the reliable path optimization problem of multi-target surveillance under dynamic obstacles is analyzed by experiments.Two frontier algorithms and one improved algorithm are used for comparison.The experimental results show that compared with the three algorithms,the S-CLPSO+LS has advantages in path length optimization ability,obstacle avoidance ability,stability in finding feasible path and adaptability to dynamic obstacles.In most experimental cases,the objective function value obtained by S-CLPSO+LS is the best.Aiming at the influence of different collision penalty weights on the obstacle avoidance ability of the algorithm,this thesis analyzes the parameter through experiments.According to the results,a larger collision penalty weight can reduce the path threat and increase the probability of obtaining a feasible solution to a certain extent,but it may also increase the path length.（3）The obstacle model and optimization algorithm proposed in this thesis are verified in the real environment.In this thesis,dynamic obstacle model and set-based comprehensive learning particle swarm optimization with local search are successfully applied to path planning in 3D real map of New Zealand,and fine-grained paths are generated by combining with A* algorithm.Experiments are carried out on four dynamic scenarios,and the data results and moving path are discussed.In addition,this thesis also studies the response methods of UAV when the dynamic obstacle scenario changes.The experimental results show that the UAV can adapt to this change through detection and adaptive path re-planning.