A method performing distributed iterative probabilistic inference or state estimation on a graph of relations between variables by means of message passing.

E.g. estimating position of various agents by communicating relative positions between each.

We construct a factor graph where the factors are the measurements received by the robots, and the variables are the locations of each robot. Our factors can have either one or two variables and our states are 2D vectors.

GBP has three steps:

• factor-to-variable-message or $m_{f\rightarrow x}$
• variable-to-factor-message or $m_{x\rightarrow f}$
• belief update or $b(x)$

The schedule of operations can be entirely arbitrary, but does affect convergence time. Damping messages can also improve convergence as shown in On Convergence Conditions of Gaussian Belief Propagation.

Belief update

A variable $x_i$ has its belief updated as the product of messages from all connected factors.

Variable-to-factor message

The message to a connected factor is the product of the incoming messages from all other connected factors.

Factor-to-variable message

For a single-variable factor, this is simply the factor. For a two-variable factor this is the product of the factor and the message from the other variable.