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_3: This article describes the use of predictive control for the decentralized cooperative control of unmanned aerial vehicles in an unfamiliar three-dimensional environment. It is assumed that each vehicle is equipped with an autopilot and a trajectory control unit. The autopilot insures the stability of the vehicle. The setpoints of the autopilot are calculated by the trajectory control unit, thus forming a cascade control structure. The trajectory control unit relies on a predictive control algorithm to calculate the optimal commands (autopilot setpoints) such that the vehicle will reach fixed targets at known positions while avoiding static obstacles that are detected en route. The advantage in using predictive control is that it offers great flexibility in the objective function to optimize while respecting constraints such as command limits, limits on the displacement that a vehicle can carry out, and the constraints that allow obstacle avoidance. The principle proposed in order to avoid static obstacles (that are assumed ellipsoid) is to verify that the predicted vehicle trajectory does not intersect these obstacles. With the objective to increase performance, cooperation between vehicles must also be privileged. Thus, if some vehicles are within the communication range, they can share the position and shape of the obstacles they have detected. Simulations illustrate the method and higlight the benefits of cooperation.
  @cite_6: The path planning is a core technology to autonomous flight of the unmanned aerial vehicle (UAV). The most important part of the UAV path planning is its algorithms. In this paper the path planning methods are sorted into two categories: off-line path planning and online path planning. Because of real-time obstacle avoidance, online path planning algorithms are widely used. Three online path algorithms are introduced, including their fundamental theories, advantages and disadvantages and potential improvements. Finally, the development trends of online path planning algorithm are given.
summary: Online path finding algorithms is designed to deal with uncertainties and emergencies during the flight. @cite_6 presents some common online algorithms, including potential field approach and particle swarm optimization (PSO). They have advantages and disadvantages: potential field approach are simple and straightforward to understand, but may easily fall into local optimum should no adjustment to algorithm is done. PSO is also intuitive, but it can also be too computationally expensive to reroute in real-time. @cite_3 proposed a predictive control scheme that use shared knowledge between nearby UAVs to find collision-free route, meanwhile considering the dynamics of UAV itself.