Bringing Network Coding into Multi-Robot Systems: Interplay Study for Autonomous Systems over Wireless Communications

1. Problem Statement

Multi-Robot Systems (MRS) rely heavily on wireless communication for state exchange, coordination, and safety. However, existing autonomy algorithms often assume ideal, timely, and reliable message delivery. In reality, wireless channels introduce packet loss, delays, and out-of-order delivery, which can degrade estimation accuracy and compromise safety-critical decisions.

The core problem identified is the misalignment between standard transport protocols and MRS requirements:

• Retransmission-based protocols (e.g., SR-ARQ): While reliable, they suffer from "Head-of-Line" (HoL) blocking and Round-Trip Time (RTT) delays when packets are lost. This causes long stalls in in-order delivery, rendering data stale or irrelevant by the time it arrives.
• Best-effort protocols (e.g., UDP): Lack reliability, leading to missing data that corrupts estimators.
• The Gap: Current research often treats communication as a separate layer, failing to co-design communication mechanisms with autonomy algorithms (estimators and controllers).

2. Methodology

The authors propose a co-design framework that integrates communication behavior directly into the autonomy loop. They compare three transport mechanisms across two distinct case studies:

A. Transport Protocols Evaluated

1. UDP (Unreliable Baseline): No retransmission or ordering; minimal delay but high packet loss.
2. SR-ARQ (Reliable Baseline): Selective Repeat Automatic Repeat Request. Retransmits missing packets but enforces strict in-order delivery, causing stalls if early packets are lost.
3. AC-RLNC (Proposed Solution): Adaptive Causal Random Linear Network Coding.
   • Instead of waiting for specific missing packets, it proactively injects coded redundancy.
   • The receiver decodes data once it accumulates enough linearly independent coded packets (degrees of freedom), regardless of which specific packets were received.
   • It adapts the coding rate based on channel conditions to balance delay and throughput.

B. Case Study 1: Cooperative Localization

• Scenario: A group of robots estimates their positions using GPS-like self-measurements and inter-robot measurements (LiDAR) exchanged over a lossy, delayed channel.
• Estimation Strategies:
  • Naive Approach: Updates the Extended Kalman Filter (EKF) immediately upon packet arrival, ignoring delays (leads to out-of-sequence updates).
  • I-ReE (Iterative Re-Estimation): A delay-aware method that buffers measurements and replays the EKF prediction/update steps in chronological order when delayed data arrives.
• Goal: Quantify how different transport protocols affect trajectory estimation error under varying packet erasure probabilities ($\epsilon$).

C. Case Study 2: Safety-Critical Overtaking

• Scenario: An ego vehicle (A) attempts to overtake a truck (T) while an oncoming vehicle (B) approaches in the same lane. Vehicle A cannot see B due to T; it must rely on V2V messages from B to decide whether to abort.
• Constraint: The vehicle must receive a specific threshold of packets ($N_{req}$) before a calculated abort deadline to avoid a collision.
• Goal: Measure the probability of meeting the deadline (reliability) under different transport protocols.

3. Key Contributions

1. Demonstration of Protocol Impact: The paper provides empirical evidence that the choice of transport protocol fundamentally alters the performance of autonomy algorithms. Specifically, it shows that in-order delivery stalls caused by retransmissions are more detrimental to MRS than simple packet loss.
2. Advocacy for Network Coding: It positions AC-RLNC not just as a throughput enhancer, but as a critical mechanism for maintaining estimation consistency and safety deadlines. By decoupling recovery from specific packet identities, it eliminates HoL blocking.
3. Delay-Aware Estimation: The introduction of the I-ReE method demonstrates that autonomy algorithms must be designed to handle delayed data chronologically to maintain accuracy, rather than discarding late data or applying it out of order.
4. Co-Design Framework: The study argues for a unified design where communication mechanisms (coding rates, redundancy) are tuned specifically to the timeliness and reliability needs of the robotic task.

4. Experimental Results

Cooperative Localization Results

• Impact of Delay: In the absence of packet loss, I-ReE significantly outperforms the naive approach when delays exist, restoring estimation accuracy to near-ideal levels.
• Protocol Comparison:
  • UDP: Estimation error increases monotonically with packet loss ($\epsilon$) because data is never recovered.
  • SR-ARQ: Performs well at low loss but degrades sharply at high loss ($\epsilon > 0.4$). The retransmission stalls cause packets to arrive too late to be useful within the estimation window.
  • AC-RLNC: Maintains near-ideal performance even at high erasure probabilities (up to $\epsilon = 0.8$). The adaptive coding ensures a steady stream of decodable information, preventing the estimation error from spiking.

Safety-Critical Overtaking Results

• Deadline Reliability: The study measured the probability of receiving the required 25 packets before the abort deadline ($t=110$).
  • AC-RLNC: Achieved a success probability of ~80%. The reliability curve rose rapidly, indicating packets arrived well before the deadline.
  • SR-ARQ: Achieved only ~60% success. The reliability curve had a "long tail," meaning retransmission stalls frequently pushed the arrival of the final required packet past the safety deadline.
• Conclusion: In safety-critical scenarios, the latency variance introduced by retransmission protocols is a major safety risk, whereas network coding provides the deterministic timeliness required for safe aborts.

5. Significance and Future Directions

This paper fundamentally shifts the perspective on MRS communication from a "background utility" to a core component of the autonomy pipeline.

• Safety Implications: It proves that relying on conventional TCP-like retransmission strategies can lead to catastrophic failures in safety-critical maneuvers due to latency jitter.
• Design Paradigm: It advocates for joint optimization of autonomy algorithms and communication protocols. Future systems should not just react to network conditions but proactively adapt coding strategies to meet task-specific deadlines (e.g., urgency, freshness).
• Future Work: The authors suggest formalizing task-level requirements (deadlines, relevance) to drive the development of new streaming coding algorithms that dynamically allocate redundancy based on the criticality of the data.

In summary, the paper establishes that Network Coding (specifically AC-RLNC) is a superior mechanism for MRS compared to traditional retransmission protocols, as it preserves the timeliness and consistency of information required for both accurate state estimation and life-saving safety decisions.