Nonlinear Multiobjective Time-Dependent TF/TA Trajectory Planning Using a Network Flow–Based Algorithm

Abstract

This paper studies the problem of finding the optimum time-dependent trajectory for an unmanned aerial vehicle (UAV) or any aerial robot flying on a low-altitude terrain following/threat avoidance (TF/TA) mission. Using a grid-based discrete scheme, a modified minimum cost network flow (MCNF) algorithm over a large-scale network is proposed. Using the Digital Terrain Elevation Data (DTED) and discrete dynamic equations of motion, the four-dimensional (4D) trajectory (three spatial and one time dimensions) from a source to a destination is obtained exactly through minimization of a cost functional subject to the nonlinear dynamics and mission constraints of the UAV. Several objectives (including the arc length, fuel consumption, flight time, and risk of threat regions) may be assigned to each arc in the network. The algorithm uses scalarization, by which a multiobjective problem can be tackled by repeatedly solving a single-objective subproblem. An attempt is made to reduce the time order of the algorithm using innovative techniques to construct a polynomial-time algorithm. Moreover, owing to the increasing deviation of the inertial navigation system (INS) in terms of time, flying safely and avoding a collision with terrain at low altitudes is a significant problem in the trajectory design of this type of vehicle. An attempt is made to add this constraint to the algorithm to produce a practical and safe trajectory with no evident increase in the complexity and execution time. Numerical results are presented to verify the capability of the proposed approach to generate an admissible trajectory in the minimum possible time compared to previous approaches.