Research On Non-convex Optimization Algorithms For UAV Path Planning Problems

Recently,the application of Unmanned Aerial Vehicles(UAVs)shows vigorous growth for residential,commercial and military use.Researchers show more interest in UAV,because people find it particularly suitable for the job repetitive,dangerous or harmful to human.Besides,high potential can be seen in some applications,such as aerial photo,ground mapping,emergency detection and antisubmarine warfare.Path planning is defined as the autonomous routing on the purpose of cost minimization and collision avoidance.In UAV applications,it plays a pivotal role.Although there are some effective algorithms,on the basis of the new development of optimal control theory and Artificial Intelligence,proposed for the path planning applications,UAV path planning is still challenging.The research on the modeling of UAV path planning is limited and finding a systematic model for the problem is difficult.Some further modifications are needed for the traditional UAV path planning models,because they are too simple to be used in some situations.Heuristic methods and numerical methods have been utilized in the modification,but neither can be perfect.The convergence and optimality of most of the popular heuristic methods can not be proved before simulating,which limits their more extensive applications.Although for the numerical methods,the convergence can be guaranteed in some situations,there is a critical defect that the computation efficiency is quite low for solving the complex models derived by the numerical methods.From above,it is important to modify the model of UAV path planning problem and to propose a systematic model,which can be calculated and solved quickly and efficiently,with certain optimality and convergence requirement satisfied.Focused on UAV path planning problem,the dissertation studies optimal control theory to analyze the problem and proposes an integrated model.Non-convex programming and Mixed Integer Nonlinear Programming(MINLP)methods are applied in the proposed series of algorithms for different conditions.What is more,the optimality and convergence of algorithms are rigorously discussed for the sake of stability and efficiency of calculation.The main points and major contributions of the thesis are as follows.(1)Systematical models of the UAV path planning problem.The traditional obstacle avoidance,collision avoidance and plume avoidance constraints are modified and improved,and inter-sample constraints are introduced.More proper cost function and constraints are added.As the basis of subsequent calculation and analysis,an integrated model frame of UAV path planning problem is founded and their related transformation is presented.(2)An ascending-dimension convexification method for problems with special non-convex control constraints.UAV path planning problem with certain control constraints are modeled as MINLP,whose corresponding continuous problem is non-convex.The idea of ascendingdimension convexification is introduced in Generalized Benders Decomposition method.After the ascending-dimension convexification,the problem can be solved by the computing efficient convex programming and MILP.In addition,the optimality of the algorithm is rigorously analyzed.(3)A sequential convex programing method for problems with non-convex state constraints.Considering the path planning problem with generalized non-convex state and control constraints,through mathematical transformation,the problem is modeled as a standard nonconvex programming problem.Based on the idea of sequential convex programming,the non-convex parts of the problem is linearized to approximate the original non-convex problem by a series of convex programming,which greatly improves the computation efficiency.The global convergence and optimality of the algorithm is rigorously proved.(4)A penalty boundary sequential convex programming method for non-convex optimal control problems.By this,the sequential convex programming method for non-convex programming is improved in some situations.The exact penalty strategy is introduced to deal with infeasible initial guess.A new projection point is calculated in each iteration to increase the similarity between the newly generated feasible region and the original one,which reduces the number of iteration and improve the computation efficiency.What is more,the modified method is rigorously proved to globally convergent with certain optimality.(5)A continuous convex programming method for non-convex problems with logical variables.In some applications with logical conditions,some binary variables need to be introduced to UAV path planning problem,therefore the problem becomes a MINLP.Using penalty strategy,the binary variables can be converted to continuous variables and the original non-convex discrete problem can be approximated by a series of continuous convex programming.Since there are no integer variables in the new problem,therefore the efficiency is improved greatly.In addition,the output of the algorithm is proved to be convergent to some specific point of the original problem.