  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.
