Memory Clustering using Persistent Homology for Multimodality- and Discontinuity-Sensitive Learning of Optimal Control Warm-starts

• URL: http://arxiv.org/abs/2010.01024v3
• Date: Wed, 24 Mar 2021 14:18:29 GMT
• Title: Memory Clustering using Persistent Homology for Multimodality- and Discontinuity-Sensitive Learning of Optimal Control Warm-starts
• Authors: Wolfgang Merkt, Vladimir Ivan, Traiko Dinev, Ioannis Havoutis, Sethu Vijayakumar
• Abstract summary: Shooting methods are an efficient approach to solving nonlinear optimal control problems. Recent work has focused on providing an initial guess from a learned model trained on samples generated during an offline exploration of the problem space. In this work, we apply tools from algebraic topology to extract information on the underlying structure of the solution space.
• Score: 24.576214898129823
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shooting methods are an efficient approach to solving nonlinear optimal control problems. As they use local optimization, they exhibit favorable convergence when initialized with a good warm-start but may not converge at all if provided with a poor initial guess. Recent work has focused on providing an initial guess from a learned model trained on samples generated during an offline exploration of the problem space. However, in practice the solutions contain discontinuities introduced by system dynamics or the environment. Additionally, in many cases multiple equally suitable, i.e., multi-modal, solutions exist to solve a problem. Classic learning approaches smooth across the boundary of these discontinuities and thus generalize poorly. In this work, we apply tools from algebraic topology to extract information on the underlying structure of the solution space. In particular, we introduce a method based on persistent homology to automatically cluster the dataset of precomputed solutions to obtain different candidate initial guesses. We then train a Mixture-of-Experts within each cluster to predict state and control trajectories to warm-start the optimal control solver and provide a comparison with modality-agnostic learning. We demonstrate our method on a cart-pole toy problem and a quadrotor avoiding obstacles, and show that clustering samples based on inherent structure improves the warm-start quality.

Related papers

• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA) Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers.
  arXiv  Detail & Related papers  (2024-09-02T12:55:27Z)
• Outer Approximation and Super-modular Cuts for Constrained Assortment Optimization under Mixed-Logit Model [6.123324869194196]
  We study the assortment optimization problem under the mixed-logit customer choice model. Existing exact methods have primarily relied on mixed-integer linear programming (MILP) or second-order cone (CONIC) reformulations. Our work addresses the problem by focusing on components of the objective function that can be proven to be monotonically super-modular and convex.
  arXiv  Detail & Related papers  (2024-07-26T06:27:11Z)
• What to Do When Your Discrete Optimization Is the Size of a Neural Network? [24.546550334179486]
  Machine learning applications using neural networks involve solving discrete optimization problems. classical approaches used in discrete settings do not scale well to large neural networks. We take continuation path (CP) methods to represent using purely the former and Monte Carlo (MC) methods to represent the latter.
  arXiv  Detail & Related papers  (2024-02-15T21:57:43Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• Deep Magnification-Flexible Upsampling over 3D Point Clouds [103.09504572409449]
  We propose a novel end-to-end learning-based framework to generate dense point clouds. We first formulate the problem explicitly, which boils down to determining the weights and high-order approximation errors. Then, we design a lightweight neural network to adaptively learn unified and sorted weights as well as the high-order refinements.
  arXiv  Detail & Related papers  (2020-11-25T14:00:18Z)
• Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
  We use a Noise Contrastive approach to motivate a family of surrogate loss functions. We address a major bottleneck of all predict-and-optimize approaches. We show that even a very slow growth rate is enough to match the quality of state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-11-10T19:09:12Z)
• Physarum Powered Differentiable Linear Programming Layers and Applications [48.77235931652611]
  We propose an efficient and differentiable solver for general linear programming problems. We show the use of our solver in a video segmentation task and meta-learning for few-shot learning.
  arXiv  Detail & Related papers  (2020-04-30T01:50:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.