7
$\begingroup$

I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks?

More formally, given two points $a$ and $b$, and energy functional $E(C)$, where $C$ is a curve such that $C(0)=a$ and $C(T)=b$, I want: $$ C^*=\arg\min_C E[C]=\arg\min_C \int_0^T E_p(C(t))\,dt $$

Essentially, I'd like a solution to a variational curve problem.

I have looked at path-planning, but these tend to be looking at graphs or other paths in discrete spaces.

Another idea is to place points, construct a spline between them, and integrate the energy measure over the spline. But how can I do gradient descent on the points' positions to iteratively improve them?

Edit (081517): just to clarify some things, thanks to the comments. I am looking for techniques for curve construction, where I am given an energy functional $E$ (computed by integrating a point-wise energy $E_p$ over the curve) and two endpoints $a,b$ in a space $M$. It could be a Riemannian manifold, but for now $\mathbb{R}^n$ is sufficient. $E_p$ may depend on derivatives of $C$, as in standard calculus of variations.

In other words, I want an algorithm that does the following:

$$\text{Input: } a,b,E \;\rightarrow\; \text{Output: a curve } C \text{ that minimizes } E(C)$$

For example, let $M=\mathbb{R}^{n}$, $n=10$, $v:\mathbb{R}^{n} \rightarrow\mathbb{R}^{n} $ be a vector field, $f_i:\mathbb{R}\rightarrow\mathbb{R}$ be a function, $C(t)\in\mathbb{R}^n$, and $\gamma_i,\eta_i,\alpha\in\mathbb{R}$, with point-wise energy: $$ E_p[C(t)]=\alpha\,\text{div}(v(C(t))) + \sum_i\gamma_i[ C'(t)_i - \eta_if_i(C(t)) ]^2 $$ where $C'(t)_i = \partial_t C_i(t)$ is the derivative of the $i$th component.

My guess is that $C$ should be given in some kind of spline form, i.e. a set of points $P$ with some associated spline parameters $S$. Then we can optimize over $P$ and $S$ to optimize $E$.

Edit (081517)$^2$: based on the comments below, I'm going to look at the ODE defined by the Euler-Lagrange equations of my example function. I get: \begin{align} \frac{\partial E_p}{\partial C_k} &= \alpha\sum_j \frac{\partial^2 v_j}{\partial C_j^2} - 2\sum_i \gamma_i\eta_i\frac{\partial f_i}{\partial C_k}[\dot{C}(t)_i - \eta_if_i(C(t))]\\ \frac{d}{dt}\frac{\partial E_p}{\partial \dot{C}_k} &= 2\gamma_k[\ddot{C}(t)_k - \eta_k\sum_j \frac{\partial f_k}{\partial C_j}\dot{C}(t)_j \end{align} So I get a system of $n$ second-order (coupled implicit) ODEs: $$ \frac{\partial E_p}{\partial C_k} - \frac{d}{dt}\frac{\partial E_p}{\partial \dot{C}_k} =0 $$

Questions:

  • How do I solve this for $C$?
  • Is there no other standard approach for doing this? (E.g. via optimization)
$\endgroup$
  • 2
    $\begingroup$ This reduces to solving a partial differential equation en.m.wikipedia.org/wiki/Euler–Lagrange_equation $\endgroup$ – Ariel Aug 14 '17 at 4:46
  • 1
    $\begingroup$ If E is arbitrary, wouldn't this be basically all of machine learning? $\endgroup$ – BlueRaja - Danny Pflughoeft Aug 14 '17 at 6:01
  • $\begingroup$ I am having exactly the same problem with the only difference that instead of using a measure of energy related to the value of curvature along the path I would like using something related to a sort of precomputed distance field in order to prefer paths which avoid obstacles. I was thinking to use B spline or NURBS but the issue remain the same...how to generate control points in the right position to create the best path? I was trying to understand this paper but still don't know if it's actually useful dmg.tuwien.ac.at/geom/ig/papers/sig04.pdf if you agree we can speak about it .. d $\endgroup$ – Marlene Pinzi Aug 14 '17 at 13:22
  • $\begingroup$ @BlueRaja-DannyPflughoeft They are both forms of function approximation/construction, but that's where the similarities end :) If you can solve this with machine learning, let me know. $\endgroup$ – user3658307 Aug 14 '17 at 15:16
  • $\begingroup$ @Ariel Thanks for your comment. I am aware of the underlying variational problem. The problem with a PDE-based approach is that I am in high dimensions (and sometimes on a manifold)... solving complex PDEs in high dimensions is too computationally expensive (and, I think, unnecessary since I should be able to do some kind of gradient descent on a curve). $\endgroup$ – user3658307 Aug 14 '17 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.