In many unmanned aerial vehicle (UAV) applications for surveillance and data collection, it is not possible to reach all requested locations due to the given maximum flight time. Hence, the requested locations must be prioritized and the problem of selecting the most important locations is modeled as an Orienteering Problem (OP). To fully exploit the kinematic properties of the UAV in such scenarios, we combine the OP with the generation of time-optimal trajectories with bounds on velocity and acceleration. We define the resulting problem as the Kinematic Orienteering Problem (KOP) and propose an exact mixed-integer formulation together with a Large Neighborhood Search (LNS) as a heuristic solution method. We demonstrate the effectiveness of our approach based on Orienteering instances from the literature and benchmark against optimal solutions of the Dubins Orienteering Problem (DOP) as the state-of-the-art. Additionally, we show by simulation \color{black} that the resulting solutions can be tracked precisely by a modern MPC-based flight controller. Since we demonstrate that the state-of-the-art in generating time-optimal trajectories in multiple dimensions is not generally correct, we further present an improved analytical method for time-optimal trajectory generation.
翻译:在许多无人驾驶飞行器用于监视和数据收集的应用程序中,由于飞行时间最长,不可能到达所有请求的地点。因此,必须优先处理所请求的地点,选择最重要的地点的问题必须作为 " 方向问题 " 的模式。要充分利用无人驾驶飞行器在此类情况下的动态特性,我们将《操作程序》与生成具有速度和加速度界限的时间最佳轨迹结合起来。我们把由此产生的问题定义为 " 虚拟东方问题 " (KOP),并提议将精确的混合网格配方与大型邻里搜索(LNS)一起作为一种超重的解决方案。我们从文献和基准中展示我们基于 " 方向性实例 " 的方法的有效性,以Dubins Orienteererer 问题(DOP)的最佳解决办法作为最佳解决办法。此外,我们通过模拟\cal{black}来显示,由此产生的解决办法可以由基于现代MPC的飞行控制器(KOP)精确地跟踪,并提议采用精确的混合网格配方配方,作为超重的解决方案。我们展示了我们当前分析轨迹模型的多轨制方法,因此,目前没有进行更精确地分析。