Optimal Path Computation for Autonomous Aerial Vehicles

In this paper, a path planning approach is developed and demonstrated for an unmanned aerial vehicle (UAV); the algorithm is applicable for autonomous robot path planning also. The main contribution of the paper is the development of an extension to the Bellman–Ford algorithm that enables incorporation of constraints directly into the algorithm during run-time. This, therefore, provides a framework for path planning, which does not cause violation of the dynamical constraints of the vehicle (or robot), such as its angle of turn. Furthermore, a procedure for computing a number of sub-optimal paths is developed so that a range of options is available for selection; the optimality of the paths is also proved. These sub-optimal paths are generated in an order of priority (optimality). An objective function is developed that models different conflicting objectives in a unified framework; these objectives can be assigned different weights. The objectives may include minimizing the length of the path, keeping the path as straight as possible, visiting areas of interest, avoiding obstacles, approaching the terminal point from a given direction, etc. The algorithm is tested for complex mission objectives, and results are discussed.