Mission planning for unmanned aerial vehicles

We formulate the mission planning problem for a meet of unmanned aerial vehicles (UAVs) as a mixed-integer nonlinear programming problem (MINLP). The problem asks for a selection of targets from a list to the UAVs, and trajectories that visit the chosen targets. To be feasible, a trajectory must pass each target at a desired maximal distance and within a certain time window, obstacles or regions of high risk must be avoided, and the fuel limitations must be obeyed. An optimal trajectory maximizes the sum of values of all targets that can be visited, and as a secondary goal, conducts the mission in the shortest possible time. In order to obtain numerical solutions to this model, we approximate the MINLP by a mixed-integer linear program (MILP), and apply a state-of-the-art solver (GUROBI) to the latter on a set of test instances.Das Missionsplanungsproblem für eine Flotte unbemannter Luftfahrzeuge (UAVs) formulieren wir als nichtlineares gemischt-ganzzahliges Optimierungsproblem (MINLP). Das Problem erfordert eine Auswahl von Zielen aus einer Liste von gegebenen UAVs und deren Flugbahnen, welche die ausgewählten Ziele besuchen. Um zulässig zu sein, muss eine Flugbahn jedes Ziel in einer vorgegebenen maximalen Entfernung und innerhalb eines bestimmten Zeitfensters passieren. Ferner müssen Hindernisse oder Bereiche mit hohem Risiko vermieden werden, und die Kraftstoffbeschränkungen müssen berücksichtigt werden. Eine optimale Mission maximiert die Summe der Werte aller Ziele, die besucht werden können, und führt als sekundäres Ziel die Mission in kürzester Zeit aus. Um numerische Lösungen für dieses Modell zu erhalten, approximieren wir das MINLP durch ein gemischt-ganzzahliges lineares Programm (MILP) und wenden auf Testinstanzen einen numerischen Löser (GUROBI) an