text: Path planning is important for the autonomy of Unmanned Aerial Vehicle (UAV), especially for scheduling UAV delivery. However, the operating environment of UAVs is usually uncertain and dynamic. Without proper planning, collisions may happen where multiple UAVs are congested. Besides, there may also be temporary no-fly zone setup by authorities that makes airspace unusable. Thus, proper pre-departure planning that avoids such places is needed. In this paper, we formulate this problem into a Constraint Satisfaction Problem to find a collision-free shortest path on a dynamic graph. We propose a collision-free path planning algorithm that is based on A* algorithm. The main novelty is that we invent a heuristic function that also considers waiting time. We later show that, with added waiting penalty, the proposed algorithm is optimal because the heuristic is admissible. Implementation of this algorithm simulates UAV delivery using Singapore's airspace structure. Our simulation exhibits desirable runtime performance. Using the proposed algorithm, the percentage of collision-free routes decreases as number of requests per unit area increases, and this percentage drops significantly at boundary value. Our empirical analysis could aid the decision-making of no-fly zone policy and infrastructure of UAV delivery.
  @cite_1: UAV route planning is to plan a feasible route for the UAV considering the time of the UAV reaching the target, fuel consumption, mission requirements and the terrain and threat distribution in the flight area and other factors, in order to ensure the completion of the mission. We describe an improved algorithm of A∗ search approach which called sparse A∗ search approach in detail, including its content and process, and carried out a simulation experiment. And based on its disadvantages, we give an optimized method.
  @cite_4: Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies.
summary: Given we have global information regarding the the existing schedules of UAVs and their current locations, we can optimize the route through off-line planning. One natural way is using A* algorithm. A* algorithm @cite_4 is a best-first, efficient and optimal search algorithm. It uses heuristics to guide the search, and therefore, reduce the number of nodes needed to be explored. Another advantage for using A* is that it can apply on both 2D and 3D space as long as the graph is connected. @cite_1 proposed an offline improved A* algorithm to deal with realistic constraints in UAV movement, including maximum moving angle, minimum route leg length, minimum flight height and maximum route length. Their algorithm can avoid collision with terrain while minimize the flight height. However, it only handles static graph, and can be computationally expensive. proposed fixes by trimming some less-permissble nodes, or imposing some hard nodes that the route must follows, but doing so will lose some potentially optimal solutions, and thus lose its completeness and optimality.