  Estimating the orientations of nodes in a pose graph from relative angular
measurements is challenging because the variables live on a manifold product
with nontrivial topology and the maximum-likelihood objective function is
non-convex and has multiple local minima; these issues prevent iterative
solvers to be robust for large amounts of noise. This paper presents an
approach that allows working around the problem of multiple minima, and is
based on the insight that the original estimation problem on orientations is
equivalent to an unconstrained quadratic optimization problem on integer
vectors. This equivalence provides a viable way to compute the maximum
likelihood estimate and allows guaranteeing that such estimate is almost surely
unique. A deeper consequence of the derivation is that the maximum likelihood
solution does not necessarily lead to an estimate that is "close" to the actual
nodes orientations, hence it is not necessarily the best choice for the problem
at hand. To alleviate this issue, our algorithm computes a set of estimates,
for which we can derive precise probabilistic guarantees. Experiments show that
the method is able to tolerate extreme amounts of noise (e.g., {\sigma} =
30{\deg} on each measurement) that are above all noise levels of sensors
commonly used in mapping. For most range-finder-based scenarios, the
multi-hypothesis estimator returns only a single hypothesis, because the
problem is very well constrained. Finally, using the orientations estimate
provided by our method to bootstrap the initial guess of pose graph
optimization methods improves their robustness and makes them avoid local
minima even for high levels of noise.
