💻 computer science

Greedy Kalman-Swarm: Improving State Estimation in Robot Swarms in Harsh Environments

This paper introduces "Greedy Kalman-Swarm," a decentralized state estimation framework that enables robot swarms to achieve high-precision collective coordination in harsh, communication-constrained environments by leveraging localized, greedy integration of neighbor data rather than relying on centralized processing or global consensus.

Original authors: Phunyapa Suksomboon, Paulo Garcia

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Phunyapa Suksomboon, Paulo Garcia

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 you are leading a team of blindfolded explorers in a pitch-black, maze-like cave. Your goal is to draw a perfect map of the cave so you can find your way out or rescue someone.

Here is the problem: Each explorer has a pedometer (odometry) to count their steps and a compass (IMU) to know which way they are facing. But these tools are imperfect. The pedometer slips on the mud, and the compass gets a little dizzy. If an explorer walks alone for too long, they will eventually think they are in a different part of the cave than they actually are. Their internal map becomes a distorted, swirling mess. This is called drift.

Traditionally, to fix this, explorers would need to constantly radio their exact coordinates to a central command center (like a satellite), which then tells them, "No, you are actually here." But in a real disaster zone or deep space, radio signals are often blocked, weak, or non-existent. You can't rely on a constant connection.

The "Greedy Kalman-Swarm" Solution

This paper introduces a clever new way for these explorers to help each other without needing a central boss or constant radio chatter. They call it the "Greedy Kalman-Swarm."

Here is how it works, broken down into simple concepts:

1. The "Greedy" Mindset

Most smart algorithms are patient; they wait until they have all the data before making a decision. This new method is greedy. It means: "If I have any information right now, I will use it immediately to fix my map. I don't wait for the perfect moment."

2. The Two Modes of Operation

The explorers switch between two modes depending on who they can see:

Mode A: The Lonely Walk (IMU-Fuse)
When an explorer is alone, they can't fix their left/right position because they have no reference point. However, they can fix their direction. They use their internal compass (IMU) to make sure they know exactly which way is "North."
- Analogy: Imagine walking in a foggy field. You don't know exactly where you are, but you keep your compass steady so you don't start walking in circles. You stay oriented, even if you might be drifting slightly off-course.
Mode B: The "Greedy Reset" (Swarm Consensus)
Every few seconds, an explorer might bump into a teammate. In the real world, this is rare and unpredictable. But when they do meet, they don't just say "Hello." They instantly swap data.
- The Magic: The explorer who has been drifting says, "I think I'm here, but I'm not sure." The teammate says, "I know exactly where I am, and I see you right next to me."
- The "Greedy" Action: The drifting explorer immediately snaps their internal map to match reality. It's like a rubber band that was stretched out by errors suddenly snapping back to its original shape. They use this single moment of contact to correct all their accumulated mistakes.

3. Why This is a Big Deal

In the past, if you lost contact with the central command, your map would slowly become useless (catastrophic drift). If you tried to use complex math to agree with everyone else, you needed a lot of data and strong signals, which don't exist in harsh environments.

This new method says: "Don't wait for a perfect connection. Just grab any opportunity to check in with a neighbor, and use that moment to reset your entire understanding of the world."

The Results (The "Aha!" Moment)

The researchers tested this in a computer simulation of a robot swarm navigating a maze:

The Solo Robot: Walked for 10 minutes and ended up thinking it was in a completely different room. Its map was a blurry, twisted mess.
The Robot with a Compass: Stayed facing the right way, but still drifted sideways. Its map looked like a "ghost town" where the walls were slightly shifted or doubled.
The Greedy Swarm Robot: Even though it only checked in with a neighbor every 4 seconds (and had no internet connection), its map remained crystal clear. The walls were sharp, and the robot knew exactly where it was.

The Takeaway

This paper proves that you don't need a high-tech, always-connected internet to keep a group of robots working together. You just need them to be opportunistic.

If a robot sees a friend, it grabs that data and fixes its map instantly. This creates a system that is resilient. Even if the robots are in a cave, a forest, or on Mars where communication is spotty, they can still build a perfect map of the world together by being "greedy" for every little bit of help they can get.

In short: It's the difference between waiting for a phone call that might never come, versus just asking the person walking next to you for directions whenever you happen to pass them. It keeps the whole team on the same page, even in the darkest, most chaotic environments.

1. Problem Statement

In robotics, accurate state estimation (determining pose and velocity) is critical for stable operation. Traditional methods rely on Kalman Filters (KF) to balance predictive models with noisy sensor data. However, in robotic swarms, existing distributed estimation techniques face significant challenges:

Drift Accumulation: Standard odometry and Inertial Measurement Units (IMUs) suffer from cumulative errors (drift) over time, leading to catastrophic localization failure in long-duration missions.
Communication Constraints: Existing swarm solutions often require centralized processing or continuous, high-bandwidth communication to reach a global consensus. These are impractical in harsh, dynamic, or communication-denied environments (e.g., search-and-rescue, space exploration).
Data Availability: Many algorithms assume continuous data availability or stable network topologies, failing when peer-to-peer links are intermittent.

The core problem is how to achieve high-precision, global state awareness in a swarm without relying on constant communication or centralized control, while remaining robust to intermittent data loss.

2. Methodology: The Greedy Kalman-Swarm

The authors propose a decentralized algorithm called Greedy Kalman-Swarm, which utilizes a dynamically adaptable Greedy Extended Kalman Filter (EKF). The system operates on a "predict-update-map" cycle with a unique "opportunistic" logic.

Key Components:

State Prediction (Odometry): Robots use wheel encoders and differential drive kinematics to predict their state. This step inherently accumulates error due to process noise (wheel slip, friction).
Partial Update (IMU-Fuse): During periods of isolation (no peer contact), the robot performs a partial update. It fuses onboard IMU data to correct rotational drift ( $\theta$ ) but allows translational drift ( $x, y$ ) to accumulate. This stabilizes the map's orientation (keeping walls orthogonal) but not its position.
The "Greedy" Full-State Update:
- Trigger: When a robot detects a peer (simulated as occurring every 4.0 seconds in the study), it treats the peer's relative position data as a high-fidelity anchor.
- Logic: Instead of waiting for a global consensus or averaging data over time, the robot greedily expands its observation matrix to the identity matrix ( $I_{3\times3}$ ) and immediately incorporates the available peer data to correct all state variables ( $x, y, \theta$ ).
- Robustness: If data is missing, the robot continues with the partial IMU update. If data arrives, it performs a "Greedy Reset," collapsing the accumulated covariance and snapping the robot back to the correct global frame.
Environment Mapping: The system uses LiDAR data projected into a 2D occupancy grid. To ensure map quality, it employs:
- Temporal Lag Suppression: Pauses mapping during rapid turns to prevent rotational smearing.
- Confidence Thresholding: Only maps features observed repeatedly (confidence $\ge$ 30) to filter out transient sensor noise.

3. Key Contributions

Distributed Greedy Formulation: A novel Kalman state estimation formulation that integrates relative inter-robot measurements without requiring global consensus or full data availability.
Opportunistic Correction Strategy: Demonstrates that "greedy" updates—using all available neighbor data immediately upon contact—can effectively reset accumulated errors, even in sparse communication scenarios.
Resilience in Harsh Environments: The system is designed to function robustly in communication-constrained environments, striking a balance between the low overhead of independent estimation and the high accuracy of centralized systems.
Open-Source Implementation: The authors provide a reference implementation to facilitate further research.

4. Experimental Results

The algorithm was evaluated in a Webots R2025a simulation using a Pioneer 3-DX robot in a 15m $\times$ 15m maze with static obstacles. Three scenarios were compared over a 600-second trial:

Baseline (No Kalman): Raw odometry.
IMU-Fused EKF: Partial updates (orientation only).
Proposed Greedy Swarm: Full greedy updates upon peer detection.

Qualitative Results (Mapping):

Baseline: Suffered catastrophic rotational drift; the generated map was incoherent and unrecognizable.
IMU-Fused: Maintained correct orientation (orthogonal walls) but exhibited significant "ghosting" and translational drift, resulting in parallel line artifacts.
Greedy Swarm: Produced a sharp, high-fidelity occupancy grid. The intermittent 4-second peer resets successfully collapsed translational drift, resulting in single-pixel sharp walls.

Quantitative Results (Localization Error):

Baseline: Error diverged rapidly, peaking at >8.5 meters.
IMU-Fused: Reduced rotational error but translational error grew steadily to ~0.85 meters.
Greedy Swarm: Maintained a globally bounded error consistently below 0.05 meters.
Efficiency: The Greedy Swarm method achieved a 99.4% reduction in peak Euclidean error compared to the baseline.

5. Significance and Future Work

Significance:
This work proves that global state awareness can be emergent rather than enforced through heavy communication protocols. By prioritizing "high-impact" peer-to-peer covariance collapses over continuous data streaming, the Greedy Kalman-Swarm enables long-duration, high-precision autonomous exploration in environments where reliable, high-bandwidth communication cannot be guaranteed. This is particularly vital for search-and-rescue and space exploration missions.

Future Directions:

Scalability: Empirical validation is needed to ensure the approach scales effectively to larger swarms without creating communication bottlenecks.
Dynamical Stability: Further analysis is required from a dynamical systems perspective to understand if complex inter-robot interactions could induce instability in the estimation dynamics.

In conclusion, the Greedy Kalman-Swarm offers a scalable, resilient framework for maintaining swarm cohesion and mapping accuracy in unpredictable terrains, fundamentally shifting the paradigm from continuous consensus to opportunistic, greedy correction.