Learning-based Warm-Starting for Fast Sequential Convex Programming and Trajectory Optimization

Somrita Banerjee, Thomas Lew, Riccardo Bonalli, Abdulaziz Alfaadhel, Ibrahim A. Alomar, Hesham Shageer, Marco Pavone2020 · DOI

TL;DR

This paper tackles the computational cost of trajectory optimization for robots and spacecraft. They propose a novel approach that uses a neural network to predict a good initial guess (a "warm-start") for a theoretically guaranteed optimization algorithm called GuSTO. This significantly speeds up the optimization process while maintaining the algorithm's reliability.

What Problem Does This Paper Address?

Optimizing trajectories for robots and spacecraft is crucial for tasks like autonomous navigation and space missions. Sequential Convex Programming (SCP) methods, like GuSTO, are powerful because they can find locally optimal solutions and come with theoretical guarantees, even when starting from an unfeasible initial guess. However, SCP algorithms can still be computationally expensive, especially for complex systems with many dimensions and constraints. While machine learning methods can be fast, they often lack these crucial guarantees. This paper aims to bridge this gap by combining the speed of machine learning with the robustness of SCP.

Methods

The core of this paper is a hybrid approach that leverages a neural network to accelerate GuSTO. Here's how it works:

  1. Dataset Generation: They first generate a large dataset of "expert" trajectories by running GuSTO on many different trajectory optimization problems. These expert trajectories represent locally optimal solutions.
  2. Neural Network Training: A feedforward neural network is trained on this dataset. The network takes the desired initial and final states of a trajectory optimization problem as input and outputs a predicted state and control trajectory. This predicted trajectory is intended to be a good "warm-start" for GuSTO.
  3. Warm-Starting GuSTO: Instead of starting GuSTO from scratch (e.g., with a simple straight-line trajectory), the output of the neural network is used as the initial guess. This allows GuSTO to converge much faster.

The neural network predicts trajectories as polynomials, which simplifies the output representation. The authors specifically focus on the GuSTO algorithm, which is known for its theoretical guarantees and ability to handle non-convex problems.

Datasets

The paper describes the generation of a dataset for training and evaluation:

  • Training and Validation Dataset: This dataset consists of 11,297 instances of optimal control problems (OCPs) solved by GuSTO. These problems involve a 13D spacecraft model (Astrobee) with nonlinear dynamics and non-convex constraints (like obstacle avoidance). The initial and final states for these problems were sampled uniformly.
  • No New Benchmarks: The paper does not introduce new benchmark environments or datasets. Instead, it uses a simulated environment with static polygonal obstacles, representative of the International Space Station (ISS).

Key Insights and Ideas

  • Bridging the Gap: The paper successfully demonstrates that combining machine learning (for speed) with robust optimization algorithms (for guarantees) is a viable strategy for improving trajectory optimization.
  • Warm-Starting is Key: The quality of the initial guess significantly impacts the convergence speed of SCP algorithms. A well-predicted warm-start can drastically reduce computation time.
  • Neural Network as a "Smart Initializer": The neural network acts as an intelligent initializer, providing a much better starting point than naive methods, leading to faster convergence.
  • Robustness to Unseen Scenarios: Even when faced with obstacles not present in the training data, the neural network's prediction can still serve as a useful warm-start, demonstrating the framework's robustness.
  • Feasibility is Preserved: While the neural network's prediction might not be perfectly feasible, GuSTO can refine it to produce a feasible and locally optimal solution, maintaining its theoretical guarantees.

Key Results

  • Reduced Iterations: On average, using the neural network warm-start reduced the number of SCP iterations by 17% across all validation scenarios.
  • Significant Speedup in Challenging Cases: For more difficult problems requiring at least 10 iterations with a naive initialization, the warm-start led to an approximate 57% reduction in iterations.
  • Prediction Accuracy: The neural network achieved a mean trajectory prediction error of under 15% across various state and control dimensions.
  • Cost and Feasibility Maintained: The total cost of the optimized trajectory remained similar to that of a traditional straight-line initialization, and all constraints were satisfied in all tested scenarios.
  • Visualizations: Figures 4 and 5 show that the warm-started GuSTO solutions are nearly identical to the cold-started solutions, but achieved much faster.

Limitations and Future Work

  • Static Obstacles in Training: The neural network was trained on static obstacles. While the framework showed robustness to unseen obstacles, handling dynamic environments might require further advancements.
  • No Guarantee of Global Optimality: SCP methods, including GuSTO, provide locally optimal solutions. The paper does not claim to find globally optimal trajectories.
  • Future Research Directions:
    • Training the neural network to predict Lagrange multipliers for initial state constraints.
  • Using smoothing techniques on sampling-based planner outputs to generate more robust training data.
  • Incorporating environmental representations (like obstacle maps) into the neural network's input to improve generalization to different obstacle configurations.

Summary updated

Abstract

Sequential convex programming (SCP) has recently emerged as an effective tool to quickly compute locally optimal trajectories for robotic and aerospace systems alike, even when initialized with an unfeasible trajectory. In this paper, by focusing on the Guaranteed Sequential Trajectory Optimization (GuSTO) algorithm, we propose a methodology to accelerate SCP-based algorithms through warm-starting. Specifically, leveraging a dataset of expert trajectories from GuSTO, we devise a neural-network-based approach to predict a locally optimal state and control trajectory, which is used to warm-start the SCP algorithm. This approach allows one to retain all the theoretical guarantees of GuSTO while simultaneously taking advantage of the fast execution of the neural network and reducing the time and number of iterations required for GuSTO to converge. The result is a faster and theoretically guaranteed trajectory optimization algorithm.
BibTeX
@misc{banerjee2020learning,
  author = {Somrita Banerjee and Thomas Lew and Riccardo Bonalli and Abdulaziz Alfaadhel and Ibrahim A. Alomar and Hesham Shageer and Marco Pavone},
  title = {{Learning-based Warm-Starting for Fast Sequential Convex Programming and Trajectory Optimization}},
  year = {2020},
  doi = {10.1109/aero47225.2020.9172293},
}
Figure