Fast UAV Trajectory Optimization using Bilevel Optimization with Analytical Gradients

Weidong Sun, Gao Tang, Kris Hauser

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present an efficient optimization framework that solves trajectory optimization problems by decoupling state variables from timing variables, thereby decomposing a challenging nonlinear programming (NLP) problem into two easier subproblems. With timing fixed, the state variables can be optimized efficiently using convex optimization, and the timing variables can be optimized in a separate NLP, which forms a bilevel optimization problem. The challenge is to obtain the gradient of the objective function which itself needs an optimization to compute. Whereas finite differences must solve many optimization problems to compute the gradient, our method is based on sensitivity analysis of parametric programming: the dual solution (Lagrange multipliers) of the lower-level optimization is used to compute analytical gradients. Since the dual solution is a by-product of the optimization, the exact gradients can be obtained "for free". The framework is demonstrated on generating trajectories in safe corridors for an unmanned aerial vehicle. Experiments demonstrate that bilevel optimization converges significantly more reliably than a standard NLP solver, and analytical gradients outperform finite differences in terms of computation speed and accuracy. With a 25ms cutoff time, our approach achieves over 8 times better suboptimality than the current state-of-the-art.

Original languageEnglish (US)
Title of host publication2020 American Control Conference, ACC 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages82-87
Number of pages6
ISBN (Electronic)9781538682661
DOIs
StatePublished - Jul 2020
Event2020 American Control Conference, ACC 2020 - Denver, United States
Duration: Jul 1 2020Jul 3 2020

Publication series

NameProceedings of the American Control Conference
Volume2020-July
ISSN (Print)0743-1619

Conference

Conference2020 American Control Conference, ACC 2020
Country/TerritoryUnited States
CityDenver
Period7/1/207/3/20

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Fast UAV Trajectory Optimization using Bilevel Optimization with Analytical Gradients'. Together they form a unique fingerprint.

Cite this