论文标题
误差范围，用于离散最短路径问题，以及用于免费飞行轨迹优化的应用程序
Error Bounds for Discrete-Continuous Shortest Path Problems with Application to Free Flight Trajectory Optimization
论文作者
论文摘要
解决连续最短路径问题的两阶段方法从空间图中的离散最短路径开始局部最小化。这种混合方法与全局最小化器的收敛性通过将离散的全局优化限制为图所引起的离散误差取决于对图的离散误差，对选择适当的图形密度的含义相应。一个典型的例子是飞行计划，即根据给定天气条件下的飞行时间和燃油消耗的最佳路线计算。存在高效的离散最短路径算法，可直接用于计算局部收敛最佳控制方法的起点。根据图密度和给定的风场，我们在离散路径的飞行时间中得出了离散路径的飞行时间的先验和局部误差界限。这些边界允许设计具有最佳局部连接结构的图形。在一组基准问题上说明了边界的属性。事实证明，本地化改善了四个数量级的误差，但仍留出足够的机会，可以通过后验估计器限制更严格的误差范围。
Two-stage methods addressing continuous shortest path problems start local minimization from discrete shortest paths in a spatial graph. The convergence of such hybrid methods to global minimizers hinges on the discretization error induced by restricting the discrete global optimization to the graph, with corresponding implications on choosing an appropriate graph density. A prime example is flight planning, i.e., the computation of optimal routes in view of flight time and fuel consumption under given weather conditions. Highly efficient discrete shortest path algorithms exist and can be used directly for computing starting points for locally convergent optimal control methods. We derive a priori and localized error bounds for the flight time of discrete paths relative to the optimal continuous trajectory, in terms of the graph density and the given wind field. These bounds allow designing graphs with an optimal local connectivity structure. The properties of the bounds are illustrated on a set of benchmark problems. It turns out that localization improves the error bound by four orders of magnitude, but still leaves ample opportunities for tighter error bounds by a posteriori estimators.
