💻 computer science

Technical Report: Asynchronous Distributed Trajectory Estimation of Multi-Robot Systems

This paper proposes an asynchronous block coordinate descent algorithm for distributed trajectory estimation in multi-robot systems that significantly reduces communication overhead, guarantees exponential convergence, and outperforms state-of-the-art methods in both accuracy and robustness to delays.

Original authors: Adam Pooley, Matthew Hale

Published 2026-07-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Adam Pooley, Matthew Hale

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a team of detectives trying to figure out where a group of lost hikers (the "robots") have been over the last hour. Each detective (an "agent") has a walkie-talkie and a notebook. They all see different parts of the hikers' path and need to combine their notes to build one perfect map of the journey.

This paper presents a new way for these detectives to work together, specifically designed for a messy, real-world environment where things don't happen at the exact same time.

Here is the breakdown of the problem and their solution, using simple analogies:

The Problem: The "Wait for the Slowest" Trap

In many existing systems, all detectives must stop and wait for the slowest person to finish their notes before anyone can write anything new.

The Issue: If Detective A is fast but Detective B is slow (maybe their walkie-talkie has a bad signal, or they are tired), the whole team sits idle waiting for B.
The Result: The team moves slowly, and if the hikers are moving fast, the map becomes outdated before it's even finished.
The "All-to-All" Nightmare: To get a perfect map, the old methods required every detective to call every other detective constantly to share every single detail. With 100 detectives, this creates a chaotic, crowded phone line where everyone is shouting over each other.

The Solution: The "Asynchronous Block" Method

The authors propose a new system where detectives don't wait for each other. They work at their own speed and only talk to the specific people they need to.

1. Working at Your Own Pace (Asynchrony)
Imagine a relay race where runners don't wait for a baton hand-off signal. Instead, as soon as a runner finishes their lap, they immediately start the next one, even if the person next to them is still running.

In this paper, if a detective finishes their calculation, they immediately update their notebook and share it. They don't wait for the slowest teammate. This keeps the team moving even if some members have "bad connections" or slow computers.

2. Only Talking to Neighbors (Sparse Communication)
The authors realized that to solve the puzzle, Detective A doesn't actually need to hear from Detective Z. They only need to hear from Detective B and C.

The Analogy: Think of a long line of people passing a bucket of water. Person 1 only needs to talk to Person 2. Person 2 talks to 1 and 3. They don't need to shout across the whole line.
The Result: By figuring out exactly who needs to talk to whom, the team cuts down the number of phone calls by up to 96.9%. The phone lines are no longer jammed.

3. The "Approximation" Trick
To make this "neighbor-only" talking work, the team uses a clever shortcut.

The Analogy: Imagine trying to calculate the exact weight of a giant cake by weighing every single crumb. It's accurate but takes forever. The authors' method is like weighing the cake in big slices. It's not perfectly precise down to the milligram, but the error is so tiny (negligible) that nobody notices.
The Payoff: This tiny, invisible trade-off in precision allows them to skip the massive, slow "all-to-all" phone calls.

The Results: Faster and More Accurate

The team tested this new method in two ways:

Computer Simulations: They created a virtual world with up to 128 detectives. The new method was 64% more accurate than the current best method (which forces everyone to wait and talk to everyone).
Real Robots: They put 4 real robots on a test track (the Robotarium). Even when they introduced huge delays in the robots' communication (simulating bad signals or slow computers), the new method kept working perfectly. It handled delays that were 1,000 times longer than normal without breaking a sweat.

The Bottom Line

This paper introduces a smarter way for robot teams to track their own movements. Instead of forcing everyone to wait in line and shout to everyone else, they let everyone work at their own speed and only whisper to their immediate neighbors. The result is a system that is faster, uses way less communication, and is more accurate, even when the robots are dealing with messy, delayed connections.

Technical Summary: Asynchronous Distributed Trajectory Estimation of Multi-Robot Systems

Problem Statement

The paper addresses the challenge of Distributed State Estimation (DSE) for multi-robot systems. In this setting, a team of $N$ agents observes a "target system" (a team of robots) and collaboratively estimates the target's state trajectory over a sliding time window.

While DSE is fundamental to autonomy, existing literature typically assumes that agents compute and communicate synchronously. However, real-world systems face inevitable delays due to physical barriers, adversarial jamming, bandwidth saturation, and heterogeneous hardware speeds. Synchronizing agents to overcome these delays often induces a "straggler effect," where the entire system operates at the speed of the slowest agent, significantly slowing convergence.

The specific problem formulated is to solve a Maximum A Posteriori (MAP) estimation problem for a sliding window of states in a partially asynchronous environment. In this environment, computation and communication delays are bounded but arbitrary, and agents do not operate on a global clock. A critical challenge identified is that standard distributed optimization approaches for this problem often require all-to-all communication among agents to maintain accuracy, which is inefficient and prone to bottlenecks.

Methodology

1. Problem Formulation and Initial Analysis

The authors model the target system dynamics and agent measurements using standard linear Gaussian assumptions. The goal is to minimize a cost function $J$ representing the negative log-posterior probability of the state trajectory over a sliding window $\{t-T_t, \dots, t\}$ .

Initial analysis of the Block Coordinate Descent (BCD) algorithm applied to the exact MAP formulation reveals a significant communication bottleneck. The dependency structure of the exact solution requires agents to exchange information with all other agents (all-to-all communication) because the information matrix becomes dense over time. This is demonstrated in Example 1, where a system with 10 agents requires 400 non-zero communication links after just 6 time steps.

2. Approximate Objective Formulation

To mitigate the communication burden, the paper proposes an approximation of the MAP problem.

Instead of propagating the full covariance matrix (which leads to dense dependencies), the algorithm propagates a submatrix of the information matrix (the inverse of the covariance).
This approximation, denoted as $\tilde{J}$ , is derived to maintain high accuracy while inducing sparsity in the communication requirements.
Lemma 2 proves that this update law is mathematically equivalent to the exact update regarding the prior information matrix, ensuring the approximation does not degrade the theoretical foundation of the estimator.
As shown in Example 2, this approximation reduces the communication topology from a dense graph ( $O(N^2)$ edges) to a sparse line graph ( $O(N)$ edges), where agents only communicate with immediate neighbors in the dependency chain.

3. Asynchronous Algorithm

Building on the sparse communication structure, the authors present Algorithm 1, an asynchronous BCD algorithm:

Local Storage: Each agent $i$ maintains local copies of the trajectory estimate, measurements, and prior estimates.
Asynchronous Updates: Agents compute updates to their local state blocks independently. They utilize potentially outdated information from neighbors (bounded by a delay $B$ ) without waiting for synchronization.
Communication: Agents only exchange data with neighbors defined by the sparse dependency sets derived from the approximate objective.
Convergence Analysis: The paper assumes "partial asynchrony," where every agent computes at least once every $B$ iterations, and information is at most $B$ iterations stale. Theorem 1 proves that under these conditions, the sequence of estimates converges exponentially fast to the unique minimizer of the approximate objective.

Key Contributions

The paper explicitly lists four main contributions:

Derivation of an Approximated Update Law: A method that maintains high estimation accuracy while promoting sparsity in inter-agent communications (Lemma 3).
Convergence Proof: A proof that the algorithm converges to the solution of the approximated MAP problem with an exponential convergence rate, even under both asynchronous computations and asynchronous communications (Theorem 1).
Simulation Results: Comparisons against a state-of-the-art synchronous algorithm (DRWT from [2]), demonstrating up to a 64% reduction in estimation error for the proposed method.
Hardware Validation: Experimental results on mobile robots demonstrating the algorithm's robustness to communication delays spanning three orders of magnitude (from 25 to 5000 time steps).

Results

Simulation

Simulations were conducted with $N \in \{4, \dots, 128\}$ agents.

Error Reduction: The proposed asynchronous BCD algorithm achieved up to 64% lower error compared to the synchronous DRWT algorithm.
Scalability: While the error of the synchronous DRWT algorithm increased rapidly as the number of agents grew, the proposed algorithm maintained low sub-optimality.
Approximation Accuracy: The Root Mean Square Error (RMSE) between the centralized MAP estimate and the proposed approximate MAP estimate was upper-bounded by $4.4 \times 10^{-4}$ , confirming the approximation introduces negligible error.

Hardware Experiments

The algorithm was implemented on the Robotarium with 4 agents estimating the trajectories of 4 robots.

Robustness: The system was tested with communication delays ( $B$ ) ranging from 25 to 5000.
Performance: The results showed that the BCD estimates converged to the approximate MAP solution. Smaller delays resulted in faster convergence, but the system remained stable and functional even with very large delays.
Error Behavior: The error exhibited characteristic spikes when the sliding window advanced (reinitializing the problem), followed by exponential decay as BCD iterations proceeded.

Significance and Claims

The paper claims to advance the field of distributed robotics by addressing the practical limitations of synchronous algorithms. The authors emphasize that:

Asynchrony is necessary: Real-world systems cannot rely on synchronized operations due to hardware heterogeneity and environmental constraints.
Communication efficiency is critical: By reducing the communication requirement from all-to-all to a sparse topology (up to 96.9% reduction in communication edges), the algorithm enables scalable multi-robot systems.
Robustness: The approach is robust to significant delays, making it suitable for environments with unreliable or saturated communication channels.
Accuracy: The proposed approximation introduces negligible errors while providing superior performance compared to existing synchronous methods in terms of both error magnitude and communication efficiency.

The authors conclude that their work provides a novel application of block coordinate descent for sliding window trajectory estimation under partially asynchronous conditions, offering a practical solution for decentralized autonomy. Future work is noted to potentially involve independently selected step sizes to further improve convergence speed.