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)
E
is arbitrary, wouldn't this be basically all of machine learning? $\endgroup$ – BlueRaja - Danny Pflughoeft Aug 14 '17 at 6:01