PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable LEO Conjunction Screening using Adaptive Synthetic-Covariance Thresholds

Vedant Srinivas, Grace Ra Kim, Duncan Eddy, Mykel J. Kochenderfer

arXiv:2610.11645v1cs.RO

TL;DR

Fixed apsis thresholds do not reflect object-to-object differences in orbit-prediction uncertainty. The method derives adaptive thresholds from propagated synthetic covariance and evaluates their intervals with a binary-search sweep. On a 33,791-object catalog, it reduced candidate pairs against fixed-threshold and brute-force baselines while retaining all close approaches in two reference sets.

  • Problem

    Fixed apsis thresholds ignore object-specific orbit-prediction uncertainty, potentially retaining unnecessary pairs for well-characterized objects while being too small for more uncertain ones.

    Source: §1 · p. 2

  • Method

    The method derives object-specific, time-dependent apsis thresholds from propagated synthetic covariance and evaluates interval overlaps with a binary-search altitude sweep.

    Source: §1 · p. 2

  • Results

    28.78% fewer candidate pairs than fixed 50 km screening and 71.48% fewer than brute-force screening were retained; both reference sets retained 100% of identified close approaches.

    Source: §6 · p. 7

  • Takeaways & Limitations

    Assigning screening intervals according to each object’s inferred uncertainty can reduce candidate pairs passed to downstream analysis.

    Source: §5 · p. 6

    The results support using public-ephemeris disagreement to size radial thresholds but do not establish a calibrated probability model for orbit uncertainty.

    Source: §5 · p. 6

Abstract

from arXiv · show

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.

1. INTRODUCTION

Growing orbital populations increase the number of conjunction pairs that screening systems must assess, while fixed apsis thresholds ignore differences in objects’ prediction uncertainty. This work introduces object-specific thresholds and a binary-search altitude sweep to reduce candidate pairs efficiently.

Motivation

  • Conjunction screening faces growing computational demands as orbital populations and potential close approaches increase.The introduction reports more than 130,000 conjunctions below 5 km in a single week and a projected rise in orbital population to over 100,000 satellites in 2030.Source: §1 · p. 1

Screening context

  • Apsis filtering is an early conservative sieve that removes pairs whose orbital altitude ranges cannot overlap before more costly downstream analysis.Because each removed pair avoids computation in later stages, the first-stage filter’s efficiency affects catalog-scale computational cost.Source: §1 · p. 2

Motivation

  • Fixed thresholds can retain unnecessary pairs for well-characterized objects yet be too small to remain conservative for objects with greater prediction uncertainty.The mismatch motivates adapting thresholds to orbit-prediction uncertainty.Source: §1 · p. 2

Uncertainty-aware thresholds

  • Object-specific, time-dependent apsis thresholds derived from propagated synthetic covariance tighten for well-characterized objects and widen when prediction uncertainty is greater.The covariance estimate uses recent GP element sets propagated to common epochs and their differences from the latest-set prediction.Source: §1 · p. 2

Scalable interval evaluation

  • A binary-search altitude sweep reduces interval-search complexity from O(N^2) to O(N log N) while preserving the apsis-screening condition.It sorts intervals and uses binary search to identify possible overlaps.Source: §1 · p. 2

Evaluation

  • 162.8 million candidates from 33,791 objects were retained, 28.78% fewer than with a fixed 50 km threshold and 71.48% fewer than with brute-force screening.The evaluation used a seven-day look-ahead horizon.Source: §1 · p. 2

2. METHODOLOGY

The methodology estimates object-specific prediction uncertainty from public ephemeris histories, propagates it into adaptive apsis thresholds, and evaluates interval overlap with a binary-search sweep. The sieve identifies candidates from radial-envelope overlap, a necessary but insufficient condition for conjunction.

Apsis Screening Formulation

  • The apsis sieve expands each object's minimum-perigee-to-maximum-apogee envelope by a nonnegative threshold; overlapping expanded intervals survive as candidates, but radial overlap alone does not establish spatial or temporal coincidence.Additional filters may reduce candidates before detailed miss-distance or collision-probability computation.Source: Apsis Screening Formulation · pp. 2–3

Synthetic Covariance Estimation from Public Ephemeris

  • Residuals are expressed in the reference trajectory's RTN frame, retaining position and velocity components so covariance propagation preserves their cross-correlations.Radial, transverse, and normal components measure disagreement in orbital radius, along the direction of motion, and perpendicular to the orbital plane.Source: Synthetic Covariance Estimation from… · p. 3
  • Recent public GP element histories provide propagated state differences for an object-specific covariance estimate, but this measures disagreement among public orbit estimates rather than operator-grade uncertainty.The method retains up to eight preceding ephemerides and forms residual samples at one-minute intervals over the first 0.3 days; at least seven finite samples are required for a full-rank mean-centered six-dimensional covariance.Source: Synthetic Covariance Estimation from… · p. 3

Covariance-Based Adaptive Thresholding

  • The method numerically propagates the full six-dimensional covariance with a force-model Jacobian that includes degree-and-order-6 gravity and atmospheric drag.The state and state-transition matrix propagation uses a GPU-accelerated implementation; adaptive thresholds are evaluated at look-ahead times through seven days.Source: Covariance-Based Adaptive Thresholding · p. 4
  • The threshold is scaled by two standard deviations of propagated radial uncertainty, widening for more uncertain objects and narrowing for well-characterized ones.Objects without sufficient ephemeris history use a fixed 50 km threshold.Source: Covariance-Based Adaptive Thresholding · p. 4

Apsis Envelope and Binary-Search Altitude Sweep

  • The binary-search altitude sweep sorts expanded intervals and reduces interval-search complexity from O(N^2) pairwise comparisons to O(N log N), returning the same candidates as exhaustive overlap evaluation.A fixed 5 km numerical padding is applied to both fixed and adaptive methods; the adaptive threshold varies with propagated radial uncertainty.Source: Apsis Envelope and Binary-Search… · p. 4

3. EXPERIMENTAL DESIGN

The experiments assess candidate reduction, close-approach retention, and the binary-search sweep’s scaling. They use public Space-Track GP history to estimate synthetic covariances and test the screening process against independent references and exhaustive interval evaluation.

3. EXPERIMENTAL DESIGN

  • The evaluation measures candidate-pair reduction, retention of independently identified close approaches, and the sweep’s scaling, with synthetic-covariance validation described in Appendix A.The screening comparisons include brute force and a fixed 50 km threshold.Source: §3 · p. 5

Catalog Data and Reference Configuration

  • The catalog experiment uses 33,791 valid objects and up to eight preceding GP records; 25,284 receive seven-day synthetic covariances, while 8,507 use the fixed 50 km fallback.Radial uncertainty is sampled at six look-ahead times from 0 to 7 days, with k = 2.Source: Catalog Data and Reference Configuration · p. 5

Primary Screening and Recall Experiments

  • Close-approach recall is measured against independently propagated pairs whose minimum sampled 3D separation is below 5 km during the seven-day horizon.The full-catalog comparison reports retained-pair counts and reductions against brute-force screening and the fixed-threshold sieve.Source: Primary Screening and Recall Experiments · p. 5
  • Binary-search correctness is tested by requiring exact agreement with exhaustive quadratic evaluation of the same apsis intervals.The comparison is evaluated separately from the screening experiments.Source: Primary Screening and Recall Experiments · p. 5
  • Three representative cases—a low-uncertainty payload, a rocket body, and debris—illustrate thresholds that can narrow below or widen beyond the fixed 50 km baseline.The debris case exceeds 50 km at the seven-day horizon.Source: Primary Screening and Recall Experiments · p. 5

Runtime Scaling

  • Runtime scaling is benchmarked on seven catalog sizes from 500 to 33,777 objects, using five random subsets per size and five timed repetitions after warm-up.The scaling tests are CPU-only and single-threaded; full-catalog covariance and state-transition-matrix propagation use one GPU.Source: Runtime Scaling · p. 5, §3 · p. 5

4. RESULTS

The adaptive sieve reduces the seven-day catalog candidate set relative to fixed-threshold and brute-force screening while retaining all close approaches in both reference sets. Its thresholds vary with object uncertainty, and the binary-search sweep preserves the candidate set while scaling faster than exhaustive interval evaluation.

Screening Recall and Candidate Reduction

  • Both the fixed and adaptive sieves retain every reference pair, giving 100% recall across SGP4 and numerical-propagation sets of 98 and 1,768 pairs.The reference pairs have sampled three-dimensional separation below 5 km over seven days.Source: Screening Recall and Candidate Reduction · p. 5
  • The binary-search sweep returns the exhaustive interval-evaluation candidate set; one-vs-catalog queries show 26.00% median and 59.63% 95th-percentile candidate reduction.Median query latency is 50.46 µs, with 81.92 µs at the 95th percentile; 4.87% of objects return more candidates than fixed screening.Source: Screening Recall and Candidate Reduction · p. 5
  • 162,819,449 pairs are retained at seven days, 28.78% fewer than the fixed 50 km sieve and 71.48% fewer than brute force.The result covers a catalog of 33,791 objects; Table 1 reports the seven-day all-vs-all screening results.Source: Screening Recall and Candidate Reduction · p. 5, Table 1 · p. 6

Object-Specific Screening Conservatism

Screening Scaling

  • At 33,777 objects, the sweep takes 0.009 16 s versus 0.247 s for exhaustive evaluation, a 27× speedup; the adaptive sieve retains fewer candidates than the fixed sieve at every tested catalog size.The timing comparison uses the CPU-only benchmark; Figure 3’s theoretical curves are scaling references.Source: Screening Scaling · p. 6

5. DISCUSSION

The discussion presents uncertainty-specific thresholds and an indexed sweep as a way to reduce screening work while retaining observed close approaches. Its evidence is bounded to the evaluated reference sets and LEO seven-day screening, and does not establish calibrated orbit-uncertainty probabilities.

5. DISCUSSION

  • Object-specific radial uncertainty narrows intervals for well-characterized objects and can widen them beyond the fixed 50 km baseline for uncertain debris.The candidate-pair reduction arises from assigning each screening interval according to inferred object uncertainty.Source: §5 · p. 6
  • Both independently propagated reference sets retained all identified close approaches under the adaptive sieve.The authors report reduced downstream candidate load without losing close approaches observed in those evaluated sets.Source: §5 · p. 6
  • At the largest tested catalog, the binary-search sweep matched exhaustive interval evaluation and achieved a 27.0× speedup.The comparison concerns screening intervals; orbit propagation and covariance generation are excluded from Figure 3’s scaling analysis.Source: §5 · p. 6, Figure 3 · p. 7
  • The method does not establish a calibrated probability model for orbit uncertainty, and its reported regime is LEO over a seven-day horizon.The chosen k = 2 and nrecent = 8 are implementation screening parameters, not universal uncertainty calibrations.Source: §5 · pp. 6–7

6. CONCLUSIONS

The conclusions report lower candidate counts, full recall of observed close approaches in two reference sets, and a faster sweep on the evaluated catalog. They frame public-ephemeris disagreement as useful for selective first-stage screening while identifying calibration and scope boundaries.

6. CONCLUSIONS

  • The method derives object-specific thresholds from propagated synthetic covariance estimated using public-ephemeris disagreement.The binary-search altitude sweep evaluates heterogeneous intervals while preserving the candidate set from exhaustive evaluation.Source: §6 · p. 7
  • On 33,791 objects, the sieve retained 162.8 million pairs (28.78% fewer than fixed 50 km; 71.48% fewer than brute force), retained all reference close approaches, and reached a 27-times speedup.The speedup is for the sweep at the largest tested catalog size, with the same candidate set as exhaustive interval evaluation.Source: §6 · p. 7
  • Public ephemeris history can support more selective first-stage screening without applying equal conservatism to every catalog object.The authors state that reducing pairs passed to higher-fidelity propagation and collision-risk analysis can lower catalog-scale computational burden.Source: §6 · p. 7
  • The evaluation is limited to LEO and a seven-day horizon, and future work should calibrate thresholds with independent close-approach data and additional regimes.The authors also identify multiple catalog epochs and variation in history length and threshold scaling as future evaluation questions.Source: §6 · p. 7

BIOGRAPHY[

The biographies describe the authors’ Stanford affiliations and professional, academic, and research backgrounds.

BIOGRAPHY[

  • Vedant Srinivas is an undergraduate in Stanford’s Intelligent Systems Laboratory and has experience in AI software and wildlife-monitoring systems.His listed research interests include optimization and decision-making for autonomous systems.Source: BIOGRAPHY[ · p. 8
  • Grace Ra Kim is a Stanford PhD candidate whose research interests span space traffic management, safe autonomous systems in space, and space policy.Her biography also lists a Cambridge M.Phil. and prior study at Harvard.Source: BIOGRAPHY[ · p. 8
  • Duncan Eddy is a Stanford staff research fellow and Center for AI Safety executive director whose work includes safety-critical, climate, and space systems.He previously led space operations at Capella Space and founded Amazon Project Kuiper’s Constellation Management and Space Safety Organization.Source: BIOGRAPHY[ · p. 9
  • Mykel J. Kochenderfer is a Stanford associate professor who directs the Stanford Intelligent Systems Laboratory and studies robust decision-making algorithms.His prior work includes airspace modeling and aircraft collision avoidance at MIT Lincoln Laboratory.Source: BIOGRAPHY[ · p. 9

A. SYNTHETIC COVARIANCE VALIDATION

The appendix describes three validation analyses for the synthetic covariance model: comparison with NASA CARA covariance, sensitivity to ephemeris-history length, and representative RTN uncertainty propagation.

A. SYNTHETIC COVARIANCE VALIDATION

  • The validation compares propagated synthetic covariance with independently reported NASA CARA covariance.The passage identifies this as the first of the appendix’s supporting validation analyses.Source: A. SYNTHETIC COVARIANCE VALIDATION · p. 9
  • The validation examines sensitivity to the number of preceding ephemeris records used in the estimator.The passage does not report the outcome of this sensitivity analysis.Source: A. SYNTHETIC COVARIANCE VALIDATION · p. 9
  • The validation also examines representative RTN uncertainty propagation over the seven-day screening horizon.The passage identifies the scope of this analysis but gives no numerical result.Source: A. SYNTHETIC COVARIANCE VALIDATION · p. 9

Comparison with NASA CARA Covariance

The comparison assesses propagated synthetic covariance against NASA CARA-reported covariance at TCA, focusing on radial variance because it determines the adaptive apsis threshold. Agreement varies across cases and RTN components.

Comparison with NASA CARA Covariance

  • The primary comparison uses propagated synthetic and reported CARA radial variance at TCA, because radial uncertainty determines the adaptive apsis threshold.The CARA covariance data come from conjunction data messages, and cases outside LEO or without sufficient public ephemeris history are excluded.Source: Comparison with NASA CARA Covariance · p. 9
  • The median synthetic-to-reported radial variance ratio is 5.95; among 97 finite cases, 12.4% are within a factor of two, 48.5% within a factor of ten, and 91.8% within a factor of one hundred.The comparison uses 98 usable LEO object-cases, of which 97 have finite positive radial-variance ratios.Source: Comparison with NASA CARA Covariance · p. 9
  • Along-track variance is underpredicted in 70.1% of cases, while radial and cross-track variances are overpredicted on median.This directional variation motivates using radial variance directly for the apsis threshold rather than treating the synthetic covariance as uniformly calibrated across the full state.Source: Comparison with NASA CARA Covariance · p. 9

Ephemeris-History Sensitivity

The seven-day adaptive threshold becomes approximately stable after using several preceding ephemeris records, though stabilization differs by object. Propagated uncertainty also varies across RTN components and objects.

Ephemeris-History Sensitivity

  • Thresholds approach stable values after approximately 5–10 preceding records, with stabilization rates differing across three representative objects.The debris case plateaus after about five records, the well-tracked payload stabilizes near nrecent = 8, and the median-object case increases modestly beyond eight before flattening; eight is selected as a common configuration.Source: Ephemeris-History Sensitivity · p. 9, Figure 5 · p. 10

Representative RTN Uncertainty Propagation

  • Across three representative objects, along-track uncertainty grows most strongly over seven days, while radial uncertainty remains smaller and varies more slowly; uncertainty magnitude also differs considerably across objects.Figure 6 shows radial, along-track, and cross-track standard deviations with orbital-period minimum–maximum envelopes; Figure 4 compares synthetic and reported radial variance for 97 LEO cases, and Table 2 covers covariance diagonal entries.Source: Representative RTN Uncertainty… · p. 9, Figure 4 · p. 10, Table 2 · p. 10
Loading 2610.11645v1…