Overlapping Domain Decomposition for Distributed Pose Graph Optimization

Aneesa Sonawalla; Yulun Tian; Jonathan P. How

cs.ROMar 3, 2026

Overlapping Domain Decomposition for Distributed Pose Graph Optimization

Authors: Aneesa Sonawalla, Yulun Tian, Jonathan P. How

Organizations: MIT Department of Aeronautics and Astronautics. · Draper Scholar, The Charles Stark Draper Laboratory, Cambridge, MA. · University of Michigan Robotics Department.

Abstract

We present ROBO (Riemannian Overlapping Block Optimization), a distributed and parallel approach to multi-robot pose graph optimization (PGO) based on the idea of overlapping domain decomposition. ROBO offers a middle ground between centralized and fully distributed solvers, where the amount of pose information shared between robots at each optimization iteration can be set according to the available communication resources. Sharing additional pose information between neighboring robots effectively creates overlapping optimization blocks in the underlying pose graph, which substantially reduces the number of iterations required to converge. Through extensive experiments on benchmark PGO datasets, we demonstrate the applicability and feasibility of ROBO in different initialization scenarios, using various cost functions, and under different communication regimes. We also analyze the tradeoff between the increased communication and local computation required by ROBO's overlapping blocks and the resulting faster convergence. We show that overlaps with an average inter-robot data cost of only 36 Kb per iteration can converge 3.1 $\times$ faster in terms of iterations than state-of-the-art distributed PGO approaches. Furthermore, we develop an asynchronous variant of ROBO that is robust to network delays and suitable for real-world robotic applications.

Figures & tables

Panel of Figure 1 — Fig. 1: Example three-robot pose and communication graphs. (a) Nodes correspond to poses; node color indicates “ownership” of that pose. Solid lines denote odometry measurements, dashed lines are inter-robot loop closures. Overlapping blocks with $\omega=1,3,4$ highlighted for robot $\alpha$ . Robot subgraphs summarized in (b) and (c) to form the communication graph, $G_{C}^{\omega}(\mathcal{B},\mathcal{E})$ . (b) $G_{C}^{\omega}(\mathcal{B},\mathcal{E})$ for $\omega=1$ . (c) $\omega=3$ or $4$ changes $G_{C}^{\omega}(\mathcal{B},\mathcal{E})$ due to inter-robot measurements, such that all robots are connected.

Method	% Problems Solved at Iteration ( $\Delta_{rel}\leq 0.1\%$ )
	Dist. Chordal			Spanning Tree			Odometry
	100	500	1000	100	500	1000	100	500	1000
RBCD ++	45.5	45.5	59.1	13.6	27.3	31.8	0.00	9.1	22.7
AMM-PGO #	40.9	81.8	90.9	18.2	54.5	63.6	0.00	22.7	54.5
ROBO-1	45.5	72.7	81.8	9.1	40.9	45.5	9.1	18.2	27.3
ROBO-2	63.6	81.8	86.4	13.6	54.5	72.7	13.6	40.9	63.6

TABLE I: Synchronous ROBO and baseline methods on benchmark datasets with varied initialization. Percentage of problems solved shown after 100, 500, 1000 iterations. Colors show best (green) and second-best (yellow) results.

Fig. 2: Performance profile comparing AMM-PGO # , RBCD ++ , and ROBO with varying overlap levels when using block-wise spanning tree initialization. From left to right, the relative suboptimality thresholds used to determine convergence are 1%, 0.1%, and 0.01%.

Dataset	Opt.	Init.	Objective after 100 iterations
Dataset	Opt.	Init.	AMM-PGO #	ROBO-2	ROBO-3
ais2klinik (2D)	188.5	2.6e8	488	1742	3.4e4
city (2D)	638.6	1.1e7	717.8	638.6	638.6
cubicle (3D)	717.1	2.5e6	852.9	717.1	717.1
grid (3D)	84319.01	4.9e5	84319.10	84319.01	84319.01
rim (3D)	5460.9	3.8e7	8702.3	5461.7	5460.9

TABLE II: Cost after 100 iterations of ROBO and best-performing baseline in synchronous setting.

Panel of Figure 5 — Fig. 3: (a) Local solve time as $\omega$ increases. Each curve shown is one dataset. For all but 4 of 22 datasets, local solve times are $\geq 20$ Hz (dashed line) for $\omega\leq 3$ . (b) Datasets with longest solve times (decreasing order).

	AMM-PGO #	ROBO-2	ROBO-3
Avg. poses per iteration	50	130	159
Max. poses per iteration	481	1010	1153
Avg. data per iteration (Kb)	11	29	36
Max. data per iteration (Kb)	108	226	258
Avg. speedup over AMM-PGO #	-	2.6	3.1

TABLE III: Speedup and robot-to-robot communication load of ROBO-

\omega

vs. AMM-PGO # across all benchmarks.

	Method	% Problems Solved at Iteration
		$\Delta_{rel}$ $\leq 0.1\%$			RMSE APE $\leq 0.1$
		100	500	1000	100	500	1000
Sync.	MESA-parallel	13.6	27.3	27.3	31.8	31.8	31.8
	ROBO-1	45.5	59.1	72.7	45.5	54.5	59.1
	ROBO-2	50.0	68.2	77.3	54.5	63.6	72.7
	ROBO-3	59.1	72.7	81.8	59.1	68.2	72.7

TABLE IV: ROBO (geodesic cost) vs MESA-parallel and MESA

Dataset	Opt.	Init.	ROBO- $\omega$ objective after 30 s
Dataset	Opt.	Init.	$\omega=1$	2	3	4	5
ais2klinik (2D)	188.5	322	196.9	195.5	194.3	193.8	192.6
city (2D)	638.6	711	650.3	642.6	640.1	639.3	638.8
cubicle (3D)	717.1	835	720.2	719.0	718.0	749.5	717.2
grid (3D)	84319	87265	84319	84334	84324	84324	84436
rim (3D)	5460.9	8084	5890.2	5535.2	5469.3	5467.1	5464.6

TABLE V: Asynchronous ROBO cost (1s delay,

\lambda=10

Hz)

Panel of Figure 9 — Fig. 4: Fraction of problems solved with $\Delta_{rel}$ $\leq 0.1\%$ after 30 s with increasing delay and overlap ( $\lambda=10$ Hz). (a) Shorter delays, excluding 4 datasets with longest local solve times. (b) Longer delays, all datasets.

Pose Graph Optimization

Pose graph optimization estimates globally consistent positions and orientations by reconciling relative-pose measurements in a graph.

See all 28 papers

Distributed Pose Graph Optimization via Continuous Riemannian Dynamics
May 11, 2026Jaeho Shin, Maani Ghaffari, Yulun TianRiemannian Optimization Multi-Robot Systems
University of Michigan Ann Arbor, MI 48109, USA
Decentralized Pose Graph Riemannian Optimization for Object-based Multi-Robot SLAM
Jun 23, 2026Yixian Zhao, Yan Huang, Yang Xu +2Simultaneous Localization and Mapping Riemannian Optimization
College of Control Science and Engineering, Zhejiang University, Hangzhou, 310027, China · Division of Decision and Control Systems, School of EECS, KTH Royal Institute of Technology, Stockholm, SE-100 44, Sweden · Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University, Shanghai, 201210, China
Learning Adaptive Solvers for Distributed Factor Graph Optimization on Matrix Lie Groups
Jul 9, 2026Jaeho Shin, Maani Ghaffari, Yulun TianFactor Graph Optimization Riemannian Optimization
University of Michigan

May 11, 2026J/K move · Enter open · S save

Distributed Pose Graph Optimization via Continuous Riemannian Dynamics

Jaeho Shin, Maani Ghaffari, Yulun Tian

University of Michigan Ann Arbor, MI 48109, USA

Riemannian Optimization Multi-Robot Systems Distributed Optimization Pose Graph Optimization

Open paper AskPDF arXiv

We present a framework for distributed Pose Graph Optimization (PGO) by formulating the problem as a second-order continuous-time dynamical system evolving on Lie groups. By modeling pose variables as massive particles subject to damping, the equilibrium points of the resulting Riemannian dynamics coincide with first-order critical points of the original PGO problem. Using the governing damped Euler--Poincaré equations and a semi-implicit geometric integrator, we design an optimization algorithm that generalizes existing algorithms such as Riemannian gradient descent and Gauss--Newton. In multi-robot settings, we present a fully distributed and parallel method based on block-diagonal mass and damping matrices, where each robot solves an ordinary differential equation for its own poses with minimal communication overhead. Moreover, modeling both state and velocity enables principled neighbor prediction that significantly improves convergence under delayed communication. Theoretically, we present an analysis and establish sufficient condition that ensures energy dissipation under the employed geometric discretization scheme. Experiments on benchmark PGO datasets demonstrate that the proposed solver achieves superior performance compared to state-of-the-art distributed baselines in both synchronous and asynchronous regimes.

Abstract

Pose Graph Optimization

Explore similar work

Distributed Pose Graph Optimization via Continuous Riemannian Dynamics

Decentralized Pose Graph Riemannian Optimization for Object-based Multi-Robot SLAM

Learning Adaptive Solvers for Distributed Factor Graph Optimization on Matrix Lie Groups