Research On UAV Path Planning Algorithm

In recent years,the rapid development of automatic control,wireless communications and intelligent information processing technology has promoted the development and prosperity of unmanned aerial vehicle(UAV)technology.At present,UAVs have been used in military,public and civil fields as emerging technologies.In some applications,UAVs are required to fly from given source locations to destinations to perform various tasks.In the case that the source locations are far away from the destinations,path planning strategies should be designed for UAVs by considering the factors such as geographic location information and the characteristics of UAVs to ensure that the tasks can be completed efficiently.This thesis conducts research on UAV path planning algorithms,the specific contents are as follows:First,this thesis describes the current status of UAV research,introduces related applications of UAVs,classifies and summarizes UAV path planning algorithms.In view of the scenario where multiple UAVs in a certain area need to perform specific tasks,considering the weak endurance of the UAVs,charging stations can be deployed to provide charging services for the UAVs to achieve long-range flight.An algorithm for UAV path planning and charging station deployment is proposed based on cost function optimization.A cost function is defined as the weighted sum of the total time of the UAV task execution and the deployment cost of the charging stations and the joint UAV path planning and charging station deployment problem is formulated as a cost minimization problem.Since the optimization problem is NP-hard,which is difficult to solve.,this thesis decomposes the original optimization problem into two sub-problems,i.e.,UAV path planning sub-problem and charging station deployment sub-problem.To solve the UAV path planning sub-problem,the optimal flight paths between any two points in the flight area is determined based on the A * algorithm,and then multiple optimal paths are obtained for each UAV based on the K-shortest path algorithm.Based on the obtained UAV candidate path selection strategy,the genetic algorithm is used to solve the charging station deployment sub-problem,thereby obtaining a joint UAV path planning and charging station deployment strategy.For a scenario where multiple UAVs need to fly to target points to perform tasks,it is assumed that a certain number of charging stations have been deployed in the flight area of UAVs,and each UAV can perform different types of tasks.Considering the constraints on the task execution capability of UAVs,the service requirements of tasks and the deployment strategy of charging stations,we formulate the UAV path planning and task execution problem as an optimization problem which minimizes the total time required for the UAVs to execute tasks.Since the optimization problem is a mixed integer nonlinear optimization problem,this thesis decomposes the optimization problem into a path selection sub-problem and a task execution sub-problem,and applies the A* algorithm,Floyd-Warshall algorithm and improved Kuhn-Munklers algorithm to solve the two sub-problems,and obtain the UAV joint path selection and task execution strategy.