Exploiting structures of trajectory optimization for efficient optimal motion planning

Tang, Gao

Permalink

https://hdl.handle.net/2142/110483 Copy

Description

Title

Exploiting structures of trajectory optimization for efficient optimal motion planning

Author(s)

Tang, Gao

Issue Date

2021-04-16

Director of Research (if dissertation) or Advisor (if thesis)

Hauser, Kris

Doctoral Committee Chair(s)

Hauser, Kris

Committee Member(s)

• Forsyth, David
• Gupta, Saurabh
• Chowdhary, Girish
• Righetti, Ludovic

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Trajectory Optimization
• Motion Planning
• Machine Learning

Abstract

Trajectory optimization is an important tool for optimal motion planning due to its flexibility in cost design, capability to handle complex constraints, and optimality certification. It has been widely used in robotic applications such as autonomous vehicles, unmanned aerial vehicles, humanoid robots, and highly agile robots. However, practical robotic applications often possess nonlinear dynamics and non-convex constraints and cost functions, which makes the trajectory optimization problem usually difficult to be efficiently solved to global optimum. The long computation time, possibility of non-convergence, and existence of local optima impose significant challenges to applying trajectory optimization in reactive tasks with requirements of real-time replanning. In this thesis, two structures of optimization problems are exploited to significantly improve the efficiency, i.e. computation time, reliability, i.e. success rate, and optimality, i.e. quality of the solution. The first structure is the existence of a convex sub-problem, i.e. the problem becomes convex if a subset of optimization variables is fixed and removed from the optimization. This structure exists in a wide variety of problems, especially where decomposition of spatial and temporal variables may result in convex sub-problem. A bilevel optimization framework is proposed that optimizes the subset and its complement hierarchically where the upper level optimizes the subset with convex constraints and the lower level uses convex optimization to solve its complement. The key is to use the solution of the lower level problem to compute analytic gradients for the upper-level problem. The bilevel framework is reliable due to its convex lower problem, efficient due to its simple upper problem, and yields better solutions than alternatives, although the existing requirement of convex sub-problem is generally too strict for many applications. The second structure is the local continuity of the argmin function for parametric optimization problems which map from problem parameters to the corresponding optimal solutions. The argmin function can be approximated from data which is collected offline by sampling the problem parameters and solving them to optima. Three approaches are proposed to learn the argmin from data each suited best for distinct applications. The nearest-neighbor optimal control searches problems with similar parameters and uses their solution to initialize nonlinear optimization. For problems with globally continuous argmin, neural networks can be used to learn from data and a few steps of convex optimization can further improve their predictions. As for problems with discontinuous argmin, mixture of experts (MoE) models are used. The MoE contains several experts and a classifier and is trained by splitting the data first according to discontinuity of argmin and then training each expert independently. Both empirical $k$-Means and theoretical topological data analysis approaches are explored for discontinuity identification and finding suitable data splits. Both methods result in data splits that help train MoE models that outperform the discontinuity-agnostic learning pipeline using standard neural networks. The trajectory learning approach is efficient since it only requires model evaluation to compute a trajectory, reliable since the MoE model is accurate after correctly handling discontinuity, and optimal since the data are collected offline and solved to optimal. Moreover, this local continuity structure is less restrictive and exists for a wide range of non-degenerate problems. The exploitation of these two structures helps build an efficient optimal motion planner with high reliability.

Graduation Semester

2021-05

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/110483

Copyright and License Information

Copyright 2021 Gao Tang

Owning Collections