Research On Improved NSGA-Ⅱ Algorithm For UVA Path Planning

With the rapid development of automation technology,path planning has been rapidly developing and applied prominently in the fields of artificial intelligence such as naval ships,robots and unmanned aerial vehicles(UAV).Path planning of UAV aims to achieve the optimal trajectory planning from the start point to the target point under the complex environmental constraints and the UAV’s own physical constraints.As the rapid development of automation and informatization,more and more requirements in complex environments are put forward for UAV’s track planning.UAV should not only respond quickly,but also perform multiple tasks and tend to have conflicts among multiple tasks.Therefore,the design of complex mathematical model of trajectory planning and algorithm to solve multiple optimization objectives are particularly significant.In the thesis,one of the multi-objective genetic algorithm(MOGA): the non-dominated sorting genetic algorithm with elitist strategy(NSGA-Ⅱ)is used to study three-dimensional UAV track planning in complex environment.The main research works are as follows:1.According to the theory of multi-objective optimization,the mathematical modeling of UAV trajectory planning in 3d environment is established.Combined with the three-dimensional environment,the model comprehensively considers the constraints of the maximum horizontal turning Angle,the maximum dive Angle or climb Angle and the flight height to establish the evaluation indexes of UAV path planning optimization,including the distance of the mission cost,threat cost,and concealability cost.2.Considering the limitations of convergence and diversity of traditional NSGA-Ⅱ in solving the UAV’s multi-objective 3d path planning,a new multi-objective double populations NSGA-Ⅱ algorithm is presented.Two independent populations are set to search optimization independently by NSGA-Ⅱ algorithm,the two populations migrate across generations,and then groups evolve independently in the new algorithm.the comparison between the simulation results of the new double-populations NSGA-Ⅱ algorithm and the traditional NSGA-Ⅱ algorithm proves that the new double-populations NSGA-Ⅱ algorithm has more advantages in the convergence and robustness and is more suitable for UAV 3d trajectory planning.3.In view of the defects of the double-populations NSGA-Ⅱ algorithm in artificially setting the proportion during the migration of two populations,a new algorithm,called RNSGA-Ⅱ algorithm which is supporting reinforcement learning,is proposed.According to the variation of population’s diversity,reinforcement learning is used to dynamically optimize the proportion parameters of various inter-group migration.In this way,the population diversity is maintained and the contradiction between convergence speed and global convergence is solved to some extent.The simulation results show that the RNSGA-Ⅱ algorithm has obvious superiority over other algorithms in convergence accuracy,robustness and diversity.