An Improved A∗ Algorithm for UAV Path Planning Problems

Recently unmanned aerial vehicle (UAV) has been widely applied in military and civil fields due to its strong autonomic and adaptability. Compared with the manned vehicles, UAV has significant advantages in carrying out the dangerous work by keeping human life away from risks. Although UAV provides notable benefits to practical applications, it gives rise to a complex path planning problem. The optimal flying path of a UAV should be obtained such that the flight length and time cost can be reduced as much as possible. In this paper, we study the path planning problem and propose an improved A∗ algorithm to solve the problem. First, with the models of UAVs and regions, an exact formulation based on mixed integer linear programming (MILP) is introduced to completely search the solution space. Then, by improving the evaluation function and the node selection strategy, an improved A∗ algorithm is presented to produce an optimal flight path for UAVs. Experimental results show that the approach proposed is more effective to solve the path planning problem than the traditional algorithms.