Scalable LEO Conjunction Screening using Adaptive Synthetic-Covariance Thresholds

The gist The adaptive sieve replaces a fixed catalog-wide threshold with object-specific thresholds derived from propagated synthetic covariance to enhance LEO conjunction screening efficiency.

Methodology Overview

The proposed method consists of three main stages: estimating object-specific prediction uncertainty from past ephemeris data, propagating that uncertainty and using it to construct adaptive apsis filtering thresholds, and evaluating the resulting radial threshold intervals with a binary-search algorithm. The core idea is to replace a single fixed apsis threshold with object-specific thresholds derived from propagated radial uncertainty The resulting thresholds vary across both objects and prediction time, becoming narrower when propagated uncertainty is small and wider when uncertainty grows.

Synthetic Covariance Estimation

To generate the object-specific threshold, the method estimates object-specific synthetic covariances from histories of publicly available General Perturbations (GP) element sets. This involves retaining the reference ephemeris and up to nrecent=8 preceding ephemeris states, propagating each with SGP4 over the common prediction interval [t0, tf], and constructing a six-dimensional covariance. The initial synthetic covariance is constructed from M finite residual samples uniformly at one-minute intervals over [t0, t0 + 0.3 days), where the initial synthetic covariance is P RTN i,0 = 1/(M − 1) Σ p=1 δx RTN p - x¯ RTN δx RTN p / (M − 1). This resulting covariance measures local disagreement among recent public orbit estimates rather than operator-grade orbit uncertainty.

Covariance-Based Adaptive Thresholding

The propagated covariance is numerically propagated using the state transition matrix (STM) integrated with the reference trajectory according to Φ˙i(t) = Ai(t)Φi(t), Φi(0) = I. The radial standard deviation is σR,i(t) = sqrt P RTN i(t), where P RTN i(t) is the upper-left entry of the RTN covariance matrix and represents the radial position variance. The adaptive threshold Ti(t) is defined as Ti(t) = k σenv R,i (t), where k = 2 corresponds to a two-standard-deviation scaling of the propagated radial uncertainty. This allows the adaptive threshold to tighten or widen according to each object’s predicted uncertainty.

Binary-Search Altitude Sweep

To evaluate the resulting radial threshold intervals computationally efficiently at catalog scale, a binary-search based altitude sweep is used instead of exhaustive pairwise comparison. This algorithm sorts the expanded intervals by their lower bounds and uses binary search to reduce the interval-search complexity from O(N 2) pairwise comparisons to O(N log N). The sweep returns the same candidate set as exhaustive evaluation of the apsis-overlap condition in Eq. 3, and it achieves a 27 times speedup at the largest tested catalog size.

Experimental Results

On a 33,791-object Space-Track catalog, the adaptive sieve retains 162.8 million candidate pairs over a seven-day horizon, reducing the candidate set by 28.78% relative to the fixed 50 km baseline and by 71.48% relative to brute force. Both independently propagated reference sets retain 100% of identified close approaches, showing that the adaptive sieve reduces the candidate set substantially while preserving all close approaches in both reference sets. The median conjunction-screening query latency is 50.46 µs, with a 95th-percentile latency of 81.92 µs over 1,000 sampled queries.

Conclusion

The present results support the use of public-ephemeris history to size radial screening thresholds, suggesting that public ephemeris history can support more selective first-stage conjunction screening without applying the same conservatism to every catalog object. The adaptive sieve retains 28.78% fewer candidates than fixed screening and 71.48% fewer than brute force. Both independently propagated reference sets retain 100% of identified close approaches. The binary-search sweep keeps this additional flexibility computationally tractable, achieving a 27 times speedup at the largest tested catalog size. Future work should calibrate the threshold scale against additional independent close-approach data.

How it works

The adaptive sieve uses an object-specific screening interval defined by Ii(τ) = [qi(τ) − Ti(τ), Qi(τ) + Ti(τ)] where the threshold is determined by the propagated radial uncertainty. The method estimates object-specific synthetic covariances from histories of publicly available General Perturbations (GP) element sets.

Apsis Screening Formulation

Objects i and j survive the apsis sieve if and only if their expanded radial intervals overlap, defined by Ii(τ) ∩ Ij (τ) ≠ ∅. The method evaluates the overlap condition for all N(N − 1)/2 object pairs, but uses a binary-search altitude sweep to reduce the interval-search complexity from O(N 2) pairwise comparisons to O(N log N).

Synthetic Covariance Estimation from Public Ephemeris

The synthetic covariance is constructed by comparing propagated historical solutions, where the inertial state difference is δx RTN(t) = R(t) 0 0 R(t) δx(t). This initial synthetic covariance P RTN i,0 is then propagated over the screening horizon using the state transition matrix (STM) integrated with the reference trajectory according to Φ˙i(t) = Ai(t)Φi(t), Φi(0) = I.

Covariance-Based Adaptive Thresholding

The radial standard deviation is σR,i(t) = sqrt P RTN i (t), and the adaptive threshold Ti(t) is defined as Ti(t) = k σenv R,i (t), with k = 2. This mechanism allows the adaptive threshold to tighten or widen according to each object’s predicted uncertainty.

Apsis Envelope and Binary-Search Altitude Sweep

The expanded interval bounds for object i are defined as li(t) = qi − δapsis − Ti(t), hi(t) = Qi + δapsis + Ti(t), where δapsis = 5 km is the fixed numerical padding applied to the nominal apsis envelope. The binary-search altitude sweep returns exactly the same candidate set as exhaustive evaluation of the same expanded apsis intervals.

Object-Specific Screening Conservatism

The reduction in candidate pairs arises from object-specific differences in the adaptive threshold, illustrating that well-characterized objects can be screened with substantially narrower intervals while uncertain debris objects can receive a threshold wider than the fixed 50 km baseline. The runtime advantage of the altitude sweep increases with catalog size, reaching a 27× speedup at the largest tested catalog.

Appendix A: Synthetic Covariance Validation

The comparison with NASA CARA covariance data shows that the median synthetic-to-reported radial variance ratio is 5.95, indicating that the synthetic covariance provides an object-specific screening scale. The axis-specific results in Table 2 show that alongtrack variance is underpredicted in 70.

1. Bold header: Adaptive Conjunction Screening Integration

This improvement allows AI systems to replace fixed, catalog-wide thresholds with object-specific thresholds derived from propagated synthetic covariance, meaning The resulting thresholds vary across both objects and prediction time, becoming narrower when propagated uncertainty is small and wider when uncertainty grows. This enables the system to allocate screening conservatism according to object-specific uncertainty rather than uniformly across the catalog.

2. Bold header: Efficient Catalog Scale Searching

The system can utilize a binary-search altitude sweep that makes the resulting heterogeneous intervals efficient to evaluate at catalog scale with log-linear search complexity, which is described as replacing O(N 2) pairwise interval testing with an O(N log N) search while preserving the same apsis-screening condition. This directly addresses the computational bottleneck of all-vs-all screening by achieving a 27 times speedup at the largest catalog size.

3. Bold header: Uncertainty Quantification from Historical Data

The AI can estimate object-specific uncertainty using historical GP element sets by constructing an object-specific six-dimensional covariance that is subsequently propagated over the screening horizon. This allows the system to use public ephemeris disagreement to size radial screening thresholds, enabling more selective first-stage conjunction screening.

4. Bold header: Preserving Recall in Screening

The system can ensure that filtering does not compromise safety by confirming that Both independently propagated reference sets retain 100% of identified close approaches after applying the adaptive sieve, thus supporting using the adaptive threshold as a first-stage screening criterion: it reduces the number of pairs passed downstream without losing any of the close approaches observed in the evaluated reference sets.

5. Bold header: Dynamic Threshold Adaptation

The AI can dynamically adjust its conservatism based on object characteristics, as illustrated by how thresholds can tighten or widen according to each object’s predicted uncertainty. This means "well-characterized objects receive tighter thresholds, allowing more infeasible pairs to be removed before downstream analysis, while objects with larger prediction uncertainty receive wider thresholds to preserve conservative screening."

As orbital populations grow, conjunction screening must search more object pairs for potential collision risks. Existing pipelines use early-stage filters, such as an apsis filter, to eliminate pairs whose orbital altitude ranges cannot produce a close approach. However, these filters apply the same fixed threshold to every object, making the screening unnecessarily conservative for well-constrained objects while potentially insufficient for objects with greater orbit-prediction uncertainty. In this work, we present an uncertainty-aware conjunction screening method that replaces a single fixed apsis threshold with object-specific thresholds derived from propagated radial uncertainty. The resulting thresholds vary across both objects and prediction time, becoming narrower when propagated uncertainty is small and wider when uncertainty grows. We pair this adaptive screening rule with a binary-search altitude sweep that makes resulting heterogeneous intervals efficient to evaluate at catalog scale with log-linear search complexity. We evaluate the method on 33,791 objects from the Space-Track General Perturbations (GP) catalog using the preceding eight public ephemeris snapshots and a seven-day prediction horizon. The adaptive sieve retains 162.8 million candidate pairs, reducing the candidate set by 28.78% relative to a fixed 50 km apsis threshold and by 71.48% relative to brute-force all-pairs screening. It retains all close approaches identified in two independently propagated reference sets. At the largest tested catalog size, the binary-search sweep is 27 times faster than exhaustive interval evaluation while returning the same candidate set. These results demonstrate that uncertainty-aware screening can substantially reduce the candidate burden passed to downstream conjunction analysis, providing a scalable path toward managing increasingly large and heterogeneous orbital populations.