Authors:  Suhan Shetty, Teguh Lembono, Tobias Löw, Sylvain Calinon

The convergence of many numerical optimization techniques is highly dependent on the initial guess given to the solver. To address this issue, we propose a novel approach that utilizes tensor methods to initialize existing optimization solvers near global optima. Our method does not require access to a database of good solutions. We first transform the cost function, which depends on both task parameters and optimization variables, into a probability density function. The joint probability distribution of the task parameters and optimization variables is approximated using the Tensor Train model which enables efficient conditioning and sampling.  Unlike existing methods, we treat the task parameters as random variables and for a given task we generate samples for decision variables from the conditional distribution to initialize the optimization solver. Our method can produce multiple solutions for a given task from different modes when they exist. We evaluate the approach on benchmark functions for numerical optimization that are hard to solve using gradient-based optimization solvers with naive initialization. The proposed method can generate samples close to global optima and from multiple modes. We demonstrate the generality and relevance of our framework to robotics by applying it to inverse kinematics with obstacles and motion planning problems with a 7-DoF manipulator.

Paper: https://arxiv.org/pdf/2206.05077.pdf (Published version at IJRR)

Software: https://github.com/idiap/ttgo

Summary of the Approach:

1. 1. 1. [Offline Phase] The cost function is treated as a function of task parameters and optimization variables

         • The task parameters correspond to the various tasks the robot will encounter in the online phase

      2. [Offline Phase] We  transform the cost function into an unnormalized probability density function (pdf)

         • Thus, the optimal solutions for a given task are the peaks of the pdf when conditioned with the corresponding task parameter 

      3. [Offline Phase] We approximate the pdf using Tensor Train (TT) model, which allows:

         • Conditioning w.r.t the task parameters

         • Fast procedures to sample from the high-density regions in a controlled manner

      4. [Online Phase] Use the samples from the conditioned TT model as an approximation to the optima 

         • Given a task, condition the TT model w.r.t. the corresponding task parameter

         • Collect samples from the conditioned TT model in the high-density regions 

         • Choose the best samples (ones with the highest density or lowest cost) as the approximation to the optima

      5. [Online Phase] Fine-tune the approximate solution using local search methods  

Note: Our approach allows the distribution of computation into offline and online phases. For the problems considered in this paper, the offline phase (steps [1] to [3]) takes a couple of seconds to several minutes. It models the solution for a diverse set of tasks (specified by the task parameter) that could be encountered in the online phase. On the other hand, the online phase (steps [4] and [5]) is fast to compute. It is often accomplished in a few milliseconds. 

What is a Tensor Train (TT) model?

• It is a particular type of sum-of-product of univariate  function representation (separation of variable format) which is often very efficient in terms of storage  

• Any function (the variables could be continuous or discrete) can be represented as a TT model 

• There is a technique called TT-Cross which can directly take the function to be approximated as the input and models the function in TT format in an unsupervised manner. It is also a non-parametric approach as the number of parameters can grow or shrink depending on the complexity of the function being modeled 

• In addition, TT model is highly interpretable and allows efficient algebraic operations over it. For example, you can add two TT models, do element-wise product, compute the mean, etc  

But why approximate a known function in another format?

• This is the key insight behind this paper. 

• For example, consider a probability density function (pdf) corresponding to a cost function (e.g. $$pdf(x) = exp(-cost(x))$$ ). 

• Even if we have access to the actual pdf it might be very difficult to efficiently sample from it. 

• Representing a function in another format ( such as TT format as done in this paper, or alternatively GMM), allows fast procedures to sample from the distribution and find the modes of the function. This in turn allows efficient procedures for numerical optimization.

Why use TT model for pdf approximation? Why not GMM or a Neural Network (NN)?

• Traditional function approximation techniques such as GMM or NN are not suitable to accurately model a pdf (or any function). 

  • GMM has nice sampling properties but suffers from the curse of dimensionality

  • NN is good for fitting data for classification and regression purposes. However, techniques to find GMM (e.g., EM algorithm) and NN (e.g., gradient-based approach) do not fully exploit the information when the function to be modeled is known. 

  • Since the function is known, we have unlimited access to the data about the function to be approximated using GMM or NN. However, the amount of data needed to train the GMM or NN to accurately model the function scales exponentially w.r.t the dimensionality. Thus, it will be very slow and becomes impractical.

  • Even if we model a pdf using NN, what do with it? It is still hard to sample from it efficiently. 

• On the other hand, there exists  a powerful technique called TT-Cross that can directly take the function as the input and  efficiently represent it in TT format in an unsupervised manner.

  • Check this jupyter-notebook for a comparison of TT vs NN for function approximation of known functions

 Below we demonstrate the benefits of TT for numerical optimization in robotics:

Applications in Robotics:

Motion Planning with TTGO

Real Robot Experiments: