⚡ electrical engineering

Semi-Decentralized Multi-Spacecraft Collision Avoidance under Communication Constraints

This paper proposes a semi-decentralized planning framework using a Recursive Small-Step Semi-Decentralized A* algorithm within a POMDP formulation to achieve near-centralized collision avoidance performance for multi-spacecraft systems while significantly reducing synchronization events under realistic intermittent ground-station communication constraints.

Original authors: Grace Ra Kim, Mahdi Al-Husseini, Duncan Eddy, Mykel J. Kochenderfer

Published 2026-07-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Grace Ra Kim, Mahdi Al-Husseini, Duncan Eddy, Mykel J. Kochenderfer

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 the sky above us is no longer just a quiet, empty canvas for stars, but a bustling, high-speed highway. In Low Earth Orbit (LEO), thousands of satellites are zooming around the planet, some carrying internet signals, others taking pictures of Earth. Just like cars on a busy road, these satellites sometimes find themselves on paths that might cross. When two satellites get too close, it's called a "conjunction," and if they don't move, they could crash. To prevent this, operators on the ground usually act like air traffic controllers: they watch the radar, calculate the risk, and tell the satellites to fire their engines to dodge. But here's the catch: these satellites aren't always talking to the ground. They only get updates when they fly over a specific radio tower, meaning the controllers often have to make decisions with old, delayed information.

This paper tackles a tricky question: How do we keep these satellites safe when they can't constantly talk to each other or the ground? The authors explore a middle ground between two extremes. On one side, you have "centralized" planning, where everyone knows everything instantly (like a perfect, super-fast internet connection). On the other, you have "decentralized" planning, where every satellite acts alone, guessing what the other might do (like two drivers trying to merge without ever waving or honking). The paper suggests a "semi-decentralized" approach, where satellites act mostly on their own but pause to sync up their data whenever they happen to fly over a ground station. They use a clever math trick called a "Semi-Decentralized Partially Observable Markov Decision Process" (SDec-POMDP) to plan these moves. Think of it as a game where players take turns making moves, but they only get to see the whole board when they land on specific "safe zones" (the ground stations). The goal is to see if this "check-in" method can be just as good as having constant communication, saving time and effort while keeping the satellites safe.

The researchers tested this idea using computer simulations of 52 different space scenarios, ranging from gentle near-misses to tight squeezes. They compared their new "semi-decentralized" planners against two other groups: the "perfect" planners who always know everything (centralized), and the "old-school" operators who follow simple, rigid rules like "if it looks close, move away as much as possible."

The results were quite promising. The paper found that the semi-decentralized approach recovered nearly the same quality of maneuver as the perfect, centralized planning. In fact, it achieved this high level of safety while requiring 28.5% fewer synchronization events than if the satellites were constantly coordinating. This means the satellites could spend more time just flying and less time stopping to chat, which is a huge efficiency boost.

Furthermore, when compared to the rule-based "old-school" operators, the new planning method was much smarter. The rule-based operators tended to overreact; they would often push the satellites far away to be safe, creating unnecessary detours that wasted fuel and messed up their orbits. The semi-decentralized planners, however, were precise. They consistently kept the satellites in the "Goldilocks zone"—far enough apart to be safe (specifically, within a desired miss-distance band of 4 to 7 km) but not so far that they had to make huge, wasteful corrections.

The study also figured out exactly when these check-ins mattered most. They found that you don't need to sync up every single time a satellite sees a ground station. By using a "greedy" method to cut out unnecessary check-ins, they discovered that syncing up specifically around the times when maneuvers are actually happening is enough to get the job done. This suggests that future satellite fleets could operate much more autonomously, only stopping to share critical data when absolutely necessary, rather than relying on constant, heavy-handed coordination.

In short, this paper doesn't claim to have solved space traffic forever, but it simulates a very practical way forward. It shows that by accepting that communication will be intermittent and planning around those gaps, we can keep our growing fleet of satellites safe without needing a perfect, always-on internet connection in the sky. It bridges the gap between the dream of perfect coordination and the reality of limited radio signals, offering a roadmap for a safer, more efficient orbital future.

Technical Summary: Semi-Decentralized Multi-Spacecraft Collision Avoidance Under Communication Constraints

Problem Statement
As Low Earth Orbit (LEO) becomes increasingly congested with mega-constellations, the frequency of spacecraft conjunctions has risen dramatically, placing a significant operational burden on satellite operators. Current collision avoidance (CA) operations are largely ground-driven, relying on intermittent contacts with ground stations. This results in delayed, asynchronously updated information and limited coordination between independent operators. While decision-theoretic approaches like Partially Observable Markov Decision Processes (POMDPs) effectively model the uncertainty of CA, existing multi-agent extensions typically assume either continuous information sharing or communication models that do not reflect the reality of ground-station constraints. Consequently, there is a gap between idealized centralized planning (which assumes perfect, continuous coordination) and fully decentralized planning (which ignores coordination opportunities), leaving a need for a framework that explicitly models intermittent information availability.

Methodology
The authors formulate the collaborative spacecraft conjunction avoidance problem as a Semi-Decentralized Partially Observable Markov Decision Process (SDec-POMDP). This formulation explicitly incorporates the intermittent nature of ground-station communication into the planning process.

State Representation: To ensure computational tractability, the six-dimensional relative state (Radial-Tangential-Normal frame) is reduced to a core planning state. This reduced state includes the signed along-track separation at Time of Closest Approach ( $\delta p_T$ ), accumulated along-track velocity deviations for each spacecraft ( $v_{dev}$ ), and the decision stage index ( $k$ ). The radial and cross-track components are treated as fixed constants for the planning horizon.
Communication Model: Synchronization opportunities are not optimized as decision variables but are derived a priori from predicted ground-station visibility windows. A synchronization stage occurs only when both spacecraft have completed their respective ground contacts, allowing operators to reconcile their local beliefs before the next action.
Action Space: Spacecraft execute impulsive along-track maneuvers of fixed magnitude ( $\pm 0.5$ m/s) or choose to wait. The joint action space considers the coupled effect of both spacecraft's maneuvers on the relative trajectory.
Reward Function: The objective function balances three goals: ensuring safe separation at TCA (penalizing miss distances $< 1$ km), minimizing unnecessary trajectory deviation (penalizing offsets $> 5$ km), and minimizing the number of maneuvers.
Solution Algorithm: The SDec-POMDP is solved using Approximate Recursive Small-Step Semi-Decentralized A (RS-SDA)**. This heuristic search algorithm computes near-optimal joint policies by incrementally expanding the policy space, explicitly reasoning over the changing availability of shared information.
Schedule Reduction: To identify the most valuable communication opportunities, the authors employ a greedy synchronization schedule reduction procedure. Starting from a full ground-station schedule, events are iteratively removed if the resulting policy performance remains within a tight tolerance of the fully centralized baseline.

Experimental Setup
The framework was evaluated on a suite of 52 synthetic conjunction scenarios representing near-circular LEO encounters with varying altitudes (550–1200 km), miss distances (1–10 km), and plane-crossing angles. The simulation utilized a six-station ground network to generate realistic, intermittent contact windows. Policies were computed offline using the discretized SDec-POMDP model but evaluated via closed-loop propagation in a high-fidelity continuous astrodynamics environment (Brahe library) with 200 Monte Carlo rollouts per scenario.

Key Results

Performance vs. Centralization: The semi-decentralized approach recovers near-centralized maneuver quality. Across the test suite, it required 28.5% fewer synchronization events than a continuous coordination model to achieve comparable performance.
Comparison with Heuristics: When compared to representative rule-based operator heuristics (e.g., threshold-based, selfish optimization, fixed-lead scheduling), the communication-aware semi-decentralized planning consistently achieved the desired operational miss-distance band (4–7 km). In contrast, heuristic approaches often satisfied safety by producing significantly larger-than-necessary miss distances (over-mitigation), leading to unnecessary mission trajectory deviations.
Value of Synchronization: The schedule reduction analysis demonstrated that not all ground-station contacts are equally valuable. Information exchange is most critical near maneuver execution epochs, and a locally minimal subset of synchronization events is sufficient to maintain high-quality coordination.

Significance and Claims
The paper establishes a practical planning framework for autonomous multi-operator collision avoidance under realistic intermittent communication constraints. By bridging the gap between fully centralized and fully decentralized planning, the proposed SDec-POMDP formulation allows operators to synchronize information only when ground-station contacts permit, while making independent maneuver decisions in between. The authors claim that this approach offers a scalable solution for the growing complexity of LEO traffic, demonstrating that high-fidelity coordination does not require continuous communication, but rather strategic synchronization aligned with operational ground-segment realities. The work validates that communication-aware optimization can consistently achieve safe separation while minimizing unnecessary trajectory disruption, a critical capability as satellite populations continue to expand.

Technical Summary: Semi-Decentralized Multi-Spacecraft Collision Avoidance Under Communication Constraints

More like this