Enhancing Bilevel Optimization for UAV Time-Optimal Trajectory using a Duality Gap Approach
Enhancing Bilevel Optimization for UAV Time-Optimal Trajectory using a Duality Gap Approach
复制标题
DOI：
10.1109/icra40945.2020.9196789
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Gao Tang;Weidong Sun;Kris K. Hauser
中科院分区：
文献类型：
--
作者：
Gao Tang;Weidong Sun;Kris K. Hauser
动态机器人车辆的时间最优轨迹由于其非线性和bang-bang控制结构，即使使用最先进的非线性规划（NLP）求解器也难以计算。本文提出了一个双层优化框架，通过将空间和时间变量分解为层次优化来解决这些问题。具体来说，原始问题分为内层和外层，内层计算沿给定几何路径的时间最优速度剖面，外层采用准牛顿方法对几何路径进行细化。内部优化是凸的，用内点法有效地求解。利用参数优化问题的灵敏度分析，可以解析得到外层的梯度。一个新颖的贡献是在内部优化中引入对偶间隙，而不是将其求解为最优性；这使得优化器实现了内点法的热启动，避免了主动不等式约束切换引起的外代价函数的非光滑性。与先前的双层框架一样，该方法保证在任何时候都能返回可行的解，但收敛速度比无间隙双层优化快。在具有速度和加速度限制的无人机模型上进行的数值实验表明，该方法比无间隙双层优化和一般NLP求解方法具有更快和更强的鲁棒性。
Time-optimal trajectories for dynamic robotic vehicles are difficult to compute even for state-of-the-art nonlinear programming (NLP) solvers, due to nonlinearity and bang-bang control structure. This paper presents a bilevel optimization framework that addresses these problems by decomposing the spatial and temporal variables into a hierarchical optimization. Specifically, the original problem is divided into an inner layer, which computes a time-optimal velocity profile along a given geometric path, and an outer layer, which refines the geometric path by a Quasi-Newton method. The inner optimization is convex and efficiently solved by interior-point methods. The gradients of the outer layer can be analytically obtained using sensitivity analysis of parametric optimization problems. A novel contribution is to introduce a duality gap in the inner optimization rather than solving it to optimality; this lets the optimizer realize warm-starting of the interior-point method, avoids non-smoothness of the outer cost function caused by active inequality constraint switching. Like prior bilevel frameworks, this method is guaranteed to return a feasible solution at any time, but converges faster than gap-free bilevel optimization. Numerical experiments on a drone model with velocity and acceleration limits show that the proposed method performs faster and more robustly than gap-free bilevel optimization and general NLP solvers.