 |
|
2021 Vol. 26, #3 - Flight Planning for Unmanned Aerial Vehicles
The following flight planning problem was posed by the German Federal Armed Forces: How to select a subset of targets from a given list, assign them to a fleet of unmanned aerial vehicles (UAVs), and compute feasible trajectories for each UAV that visit the chosen tar-gets. To be feasible, the trajectory must pass each of its targets within a certain range and time window. Geographical obstacles, regions of high risk, and other UAVs must be avoided, and fuel limitations must be obeyed. An optimal solution to this problem maximizes the sum of values of all targets that are visited, and as a secondary goal, conducts the mission in the shortest possible time. It turns out that this problem can be formulated as a mixed-integer non-linear programming problem (MINLP) with ordinary differential equation (ODE) constraints. The authors’ solution approach is to discretize the ODEs and approximate the nonlinear constraints, so that a mixed-integer linear program (MILP) is obtained. Using state-of-the-art numerical solvers for the latter problem class (such as CPLEX, XPRESS, and GUROBI), proven global optimal solutions can be obtained on a standard PC or laptop within a one hour time limit for instances with up to 15 targets and two UAVs. For larger instances, it is still possible to compute near-optimal solutions (within 25% of optimality for two UAVs and up to 30 targets) with this approach.
Member Fee:$0.00
Non-Member Fee:$15.00
Availability: In stock
|
|
|