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
- 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) - Distributed Solution of the Inverse Rig Problem in Blendshape Facial
Animation [0.0]
Rig inversion is central in facial animation as it allows for a realistic and appealing performance of avatars.
A possible approach towards a faster solution is clustering, which exploits the spacial nature of the face.
In this paper, we go a step further, involving cluster coupling to get more confident estimates of the overlapping components.
arXiv Detail & Related papers (2023-03-11T10:34:07Z) - Probabilistic Bilevel Coreset Selection [24.874967723659022]
We propose a continuous probabilistic bilevel formulation of coreset selection by learning a probablistic weight for each training sample.
We develop an efficient solver to the bilevel optimization problem via unbiased policy gradient without trouble of implicit differentiation.
arXiv Detail & Related papers (2023-01-24T09:37:00Z) - 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.