Marc Toussaint, Christian Goerick (2010): A Bayesian view on motor control and planning. In Olivier Sigaud, Jan Peters (Eds.): From motor to interaction learning in robots, Springer, print expected in 2010.
Comments on the relationship between linearized belief propagation and covariant gradient descent
Earlier we derived an algorithm that used belief propagation to efficiently compute the covariant gradient for trajectory optimization under a kinetic energy metric. A special case of the kinetic energy term, in which we assume all of the robot’s mass is concentrated at the end-effector, reduces to
where and is the forward kinematics function. Covariant gradient descent under the kinetic energy metric (for this special case) is extremely closely related to a the algorithm proposed in this paper, particularly the variant discussed in Section 4.4 which additionally incorporates collision constraints. There are four stages to the algorithm (I’ve grouped them slightly differently from the paper):
- Forward-backward in workspace with cost integration.
- Propagate down to the configuration space.
- Forward-backwith in configuration space.
- Propagate up to workspace.
The analogy under covariant gradient descent is
- Compute the workspace cost gradient. The arc-length parameterization CHOMP uses for the cost functional produces a workspace gradient that is in a sense qualitatively related to smoothing the gradient across the workspace trajectory (although the two operations are quantitatively different). This point is the biggest difference between the two algorithms and I have yet to completely reconcile it.
- Backpropagate the gradient down to the configuration space using the chain rule.
- Compute the covariant gradient by solving the linear system.
- Push the new configurations up to the workspace using the forward kinematics.
Verifying the details of these points mathematically by showing that the updates are equivalent is tedious and dependent on the correct choice of cost function and metric (e.g. Toussaint’s cost function cares only about the end-effector currently, although the extension is straightforward), so my question is whether there is a higher level way to relate the algorithms to one another.
Writing out the equivalent objective is straightforward, but behavior of belief propagation is not well understood. Optimization, on the other hand, has a strong history and recent results on optimization over Riemannian manifolds (see the literature listed in the reading group post) have made strides toward a formal understanding within this generalized context. My belief is that linearized belief propagation, such as the algorithm proposed in this paper, has general connections to covariant gradient descent on a Riemannian manifold. (Additionally, it’s well known that even for Gaussian graphical models with loops, the estimates of covariance matrices are not accurate under loopy belief propagation, so this algorithm may be more accurately viewed as primarily an optimization procedure.) Formalizing this connection may provide tools for analyzing the convergence and convergence rate of continuous belief propagation algorithms, and on the flip side, may give us more computationally efficient ways of exploiting structure in covariant gradient descent.