Simultaneous Time Synchronization and Mutual Localization for Multi-robot System

Xiangyong Wen, Yingjian Wang, Xi Zheng, Kaiwei Wang, Chao Xu, Fei Gao

Abstract: Mutual localization stands as a foundational component within various domains of multi-robot systems. Nevertheless, in relative pose estimation, time synchronization is usually underappreciated and rarely addressed, although it significantly influences estimation accuracy. In this paper, we introduce time synchronization into mutual localization to recover the time offset and relative poses between robots simultaneously. Under a constant velocity assumption in a short time, we fuse time offset estimation with our previous bearing-based mutual localization by a novel error representation. Based on the error model, we formulate a joint optimization problem and utilize semi-definite relaxation (SDR) to furnish a lossless relaxation. By solving the relaxed problem, time synchronization and relative pose estimation can be achieved when time drift between robots is limited. To enhance the application range of time offset estimation, we further propose an iterative method to recover the time offset from coarse to fine. Comparisons between the proposed method and the existing ones through extensive simulation tests present prominent benefits of time synchronization on mutual localization. Moreover, real-world experiments are conducted to show the practicality and robustness.

Introduction

For a swarm of robots to coordinate effectively—whether mapping a building or performing search-and-rescue—they must determine their relative positions, a process known as "mutual localization." Most existing algorithms operate under the assumption that robot clocks are perfectly synchronized. In reality, hardware drift and network latencies mean that when Robot A records a measurement at its "12:00:01," Robot B might believe it is "12:00:04." This temporal mismatch leads to significant spatial inaccuracies because the robots were in different physical locations at those disparate times.

While network protocols like NTP or PTP exist, they often fail under high latency or require specialized hardware. This research treats the time offset not as a networking error to be externalized, but as a geometric variable to be solved alongside spatial position.

Methodology

The proposed framework utilizes a "tightly coupled" optimization approach built on several technical pillars:

  1. Constant Velocity Assumption: Over short intervals, a robot's velocity is assumed to be constant. This allows the position at a shifted time ($t + \Delta\tau$) to be expressed as the current position plus velocity multiplied by the time offset.
  2. Novel Error Representation: A new error model incorporates the time offset ($\Delta\tau$) directly into bearing-based localization equations.
  3. QCQP and SDR: The problem is formulated as a Quadratically Constrained Quadratic Problem (QCQP). To handle its non-convex nature, the researchers apply Semi-Definite Relaxation (SDR), transforming it into a convex problem solvable to global optimality.
  4. Iterative Time Optimization (ITO): Because linear assumptions only hold for small offsets, an iterative "coarse-to-fine" method was developed. This approach estimates a rough offset, shifts the data, and re-estimates until trajectories align.
The iterative process gradually aligns the estimated trajectory (blue) with the observer trajectory (orange), effectively recovering the correct shape from a jumbled initial state.

Experimental Results

The approach was validated through both synthetic simulations—using 4,000 poses and 200 bearing measurements with varying Gaussian noise—and real-world quadrotor experiments.

Breaking the 0.4s Barrier

A key finding is the limitation of standard non-iterative methods (NTO), which typically fail when the time offset exceeds 0.4 seconds. The proposed Iterative Time Optimization (ITO) successfully recovered trajectories even with offsets as large as 3 seconds. In quadrotor tests with a 1-second programmed offset, ITO achieved rotation errors as low as 1.53° and translation errors of 0.202m, whereas methods ignoring time sync produced egregiously large errors or failed to converge.

Quantitative assessment showing that ITO (blue) maintains near-zero error and low cost at much higher time offsets compared to the standard NTO (green) method.

Discussion and Conclusion

The core insight of this work is that time synchronization in robotics is essentially a trajectory alignment problem. By treating time as geometry, the system becomes robust to the temporal drifts inherent in multi-robot hardware.

While the SDR and iterative nature of the algorithm introduce higher computational overhead—making it better suited for periodic background execution rather than high-frequency real-time loops—it provides a mathematically grounded path to global optimality. Future work will focus on integrating this framework into complex multi-robot SLAM systems for GPS-denied environments.

Summary updated

Abstract

Mutual localization stands as a foundational component within various domains of multi-robot systems. Nevertheless, in relative pose estimation, time synchronization is usually underappreciated and rarely addressed, although it significantly influences estimation accuracy. In this paper, we introduce time synchronization into mutual localization to recover the time offset and relative poses between robots simultaneously. Under a constant velocity assumption in a short time, we fuse time offset estimation with our previous bearing-based mutual localization by a novel error representation. Based on the error model, we formulate a joint optimization problem and utilize semi-definite relaxation (SDR) to furnish a lossless relaxation. By solving the relaxed problem, time synchronization and relative pose estimation can be achieved when time drift between robots is limited. To enhance the application range of time offset estimation, we further propose an iterative method to recover the time offset from coarse to fine. Comparisons between the proposed method and the existing ones through extensive simulation tests present prominent benefits of time synchronization on mutual localization. Moreover, real-world experiments are conducted to show the practicality and robustness.
BibTeX
@inproceedings{wen2024simultaneous,
  author = {Xiangyong Wen and Yingjian Wang and Xi Zheng and Kaiwei Wang and Chao Xu and Fei Gao},
  title = {{Simultaneous Time Synchronization and Mutual Localization for Multi-robot System}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2024},
  url = {https://openreview.net/forum?id=0S3j8tEBWm},
}
Figure