A Two-time-level Model for Mission and Flight Planning of an Inhomogeneous Fleet of Unmanned Aerial Vehicles

We consider the mission and flight planning problem for an inhomogeneous fleet of unmanned aerial vehicles (UAVs). Therein, the mission planning problem of assigning targets to a fleet of UAVs and the flight planning problem of finding optimal flight trajectories between a given set of waypoints are combined into one model and solved simultaneously. Thus, trajectories of an inhomogeneous fleet of UAVs have to be specified such that the sum of waypoint-related scores is maximized, considering technical and environmental constraints. Several aspects of an existing basic model are expanded to achieve a more detailed solution. A two-level time grid approach is presented to smooth the computed trajectories. The three-dimensional mission area can contain convex-shaped restricted airspaces and convex subareas where wind affects the flight trajectories. Furthermore, the flight dynamics are related to the mass change, due to fuel consumption, and the operating range of every UAV is altitude-dependent. A class of benchmark instances for collision avoidance is adapted and expanded to fit our model and we prove an upper bound on its objective value. Finally, the presented features and results are tested and discussed on several test instances using GUROBI as a state-of-the-art numerical solver.本文针对非均质无人驾驶飞行器（unmanned aerial vehicles，以下简称UAV）机群的任务规划与航迹规划问题展开研究。其中，将为UAV机群分配任务目标的任务规划问题，与在给定航点集中求解最优飞行航迹的航迹规划问题整合为单一模型并同步求解。据此，需为非均质UAV机群规划航迹，在满足技术与环境约束的前提下，最大化所有航点相关得分的总和。本文对现有基础模型的多个维度进行拓展，以获得更精细化的求解结果。提出双层时间网格方法，用于平滑求解得到的飞行航迹。三维任务空域可包含凸形限制空域，以及风场会对飞行航迹产生影响的凸形子区域。此外，飞行动力学与燃油消耗导致的质量变化相关，且每架UAV的续航航程均与飞行高度相关。针对避障问题的一类基准测试实例进行适配与拓展，以适配本文所提模型，并证明了该模型目标值的上界。最后，采用当前主流数值求解器GUROBI，在多个测试实例上对本文提出的模型特性与求解结果进行测试与分析讨论。