2
$\begingroup$

I'm a PhD student in an unrelated field. It's been a very long time since I've done physics, and I've run into a problem in my research which I think is actually a physics problem.

Basically, I have N 3-dimensional points attached to a rigid body. At each of the points, I have a 3-dimensional gradient of an objective function defined over 3D space. I want to find, given these N point gradients, a small transformation which will move the entire rigid body in the direction of the gradient (the "direction of steepest descent" in optimization terms).

I think this problem is the same as finding the net force and torque on an object around its center of mass assuming a uniform mass distribution, but I'm not sure about that. Any thoughts?

Edit More clarification: I have a cost function in 3D space. For all points, its cost is defined, as well as the gradient of the cost function. I want to find a local minimum of the cost function defined on the points attached to a rigid body by gradient descent.

For example, if I have a cube with 8 points, and a cost function that is just 1 over distance from the origin, then descending the gradient of the cost function should push the cube away from the origin. I should be able to somehow compute the way that the cube moves from the point gradients defined at its corners. Translation is easy. I just add up all the point gradients. But what about rotation?

Hope that makes it clearer.

Some math: We have some cost function C. $$ \text{objective:}~~C(x) : \mathbf{R}^3 \to \mathbf{R} $$ $$ \text{gradient:}~~ \nabla C(x) : \mathbf{R}^3 \to \mathbf{R}^3 $$ We can additionally define a gradient over a set of N points, which are rigidly attached to one another. $$ \text{point-set objective:}~~C(\{x_1, \ldots, x_N\}) = \Sigma_i C(x_i)$$ We want to find: $$ \text{goal: }~~ T^* = \text{arg}~\text{min}_{T} C(\{T x_1, \ldots, T x_N\}) $$ Where T is a rigid transformation. We can find a local minimum by descending the gradient with respect to T, which should decompose into a translation part, and a rotation part. $$ \text{translation part: }~~ \nabla_{\text{trans}} C(\{x_1, \ldots x_N\}) = \Sigma_i \nabla C(x_i)$$ $$ \text{rotation part: }~~ \nabla_{\text{rot}} C = ??$$

EDIT: I found the answer to my question in section 4.2 of this paper:

http://www.geometrie.tuwien.ac.at/ig/papers/tr117.pdf

The key is to represent the problem using plucker coordinates, and indeed treat the problem as calculating the net wrench from a bunch of point forces.

$\endgroup$
  • $\begingroup$ I added a link for the term objective function. Is this the correct idea I linked to? $\endgroup$ – BMS Jul 3 '14 at 0:44
  • $\begingroup$ Yes, sorry. An objective function is just a "cost" associated with each point in space. The goal is to minimize the cost over all the points on the rigid body by moving the body around. $\endgroup$ – user52676 Jul 3 '14 at 0:48
  • $\begingroup$ Did you take into account the fact that one might end up in a local minimum of the cost function, rather than the global one? $\endgroup$ – Danu Jul 3 '14 at 0:50
  • $\begingroup$ Yes. I want to find a local minimum using gradient descent. $\endgroup$ – user52676 Jul 3 '14 at 0:51
  • $\begingroup$ Cool problem... I was going to suggest using screw theory, but you found the answer already. $\endgroup$ – John Alexiou Jul 8 '14 at 17:02
1
$\begingroup$

I think the study of dynamical systems and control is more relevant for you than physics. Force and torque are concerned with 2nd-order systems (momentum and angular momentum become states), but it looks like in your case you just have to follow 1st-order dynamics (momentum and angular momentum become output signals).

Your system consists $N$ points. The cost function generates a scalar and a gradient for each point. So we write:

$$f: (N \text{ points} \in \mathbb{R}^3) \mapsto (N \text{ costs} \in \mathbb{R}, N \text{ gradients} \in \mathbb{R}^3).$$

Owing to rigidity you really only have 6 degrees of freedom: 3 for translation and 3 for rotation. It would simplify your optimization problem if you define the "state" of the system in this 6-dimensional space.

Concretely, you should choose an "initial configuration" for all your points. You can then choose a reference origin (e.g. the first point?) and a reference orientation (e.g., the $+x$ axis and the $+y$ axis). From here, each point is assigned a fixed $\textbf{relative coordinate}$ to your 6-dimensional states. Now you can map from state to absolute point coords:

$$p: (6\text{-dim translation and rotation}) \mapsto (N \text{ points} \in \mathbb{R}^3).$$

(Edit 1: this part is fishy) Now, for each of the $N$ points you have the 3D gradient vector. Summing (possibly weighted) the vectors gives you a "momentum" on the rigid body. Summing (possibly weighted) the cross product of these vectors against the relative coordinates of the respective point gives you the "angular momentum" of the rigid body (axis of rotation with magnitude), so you have:

$$q: (N \text{ costs} \in \mathbb{R}, N \text{ gradients} \in \mathbb{R}^3) \mapsto (6\text{-dim momentum and angular momentum}).$$

Composing the above yields $g = q \circ f \circ p$, which maps from a 6D state to a 6D "momentum" output. You can then divide by mass and moment of inertia to get the desired "speed", which is needed for gradient descent. Once you use $g$'s output to alter state, you form a feedback loop for the gradient descent / ascent. Equilibrium is reached when the output of $g$ is 0, and this depends on the weights you choose.

For concrete implementation, I'd recommend representing the translation and rotation using homogeneous 3D transform matrices, commonly used in computer graphics. So the state is a $4 \times 4$ matrix given by:

$$X = \begin{bmatrix} R & t \\ 0^T & 1\end{bmatrix} \in \mathbb{R}^4,$$

where $R \in SO(3)$ is the rotation state, $t \in \mathbb{R}^3$ is the translation state. Each reference point $p_i$ is $$p_i = \begin{bmatrix} x_i \\ y_i \\ z_i \\ 1 \end{bmatrix}.$$ So $X \times p_i$ gives you translation and rotation in one fell swoop. Next, let the output "speeds" be $(dx, dy, dz)$ for translation and $(dr_x, dr_y, dr_z)$ for rotation (here I abused notation; should have $\frac{1}{dt}$ for completeness). You can form:

$$\Delta X = \begin{bmatrix} 0 & -dr_z & dr_y & dx \\ dr_z & 0 & -dr_x & dy \\ -dr_y & dr_x & 0 & dz \\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

Finally, you start with $X[0] = I$. To time-step, you can proceed by $X[k+1] := X[k] - \Delta X[k] \Delta t$ for some time step parameter $\Delta t$ (tuning required, possibly adaptive), followed by orthogonalizing the rotation part.

A more clever approach is to evolve the system by operating within the Lie group:

$$X[k + 1] := e^{-\Delta X[k] \Delta t} X[k].$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oh wait, I made mistake in computing $q$, by not observing multi-variable chain rule. Meanwhile, it might be easier to just compute the final gradient numerically by perturbing each of the 6 inputs. $\endgroup$ – arccosh Jul 3 '14 at 2:32
  • $\begingroup$ Thank you; this is very similar to my original idea, which was to compute the dx, dy, and dz just by summing all the point gradients, however for the rotation part you cleverly just directly compute the partial derivatives of each element of the rotation matrix rather than first computing a torque using euler angles, as was my original plan. I think going in this direction will be much more fruitful. $\endgroup$ – user52676 Jul 3 '14 at 4:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.