🔢 mathematics

Time-Optimal Collision Avoidance Via a Greedy Polynomial Backward Sweep

This paper introduces a greedy time-optimal backward-sweep method that utilizes differential algebra to efficiently determine the latest possible maneuver initiation time for low-thrust spacecraft collision avoidance, achieving near-optimal safety with runtimes suitable for onboard implementation.

Original authors: Zeno Pavanello, Frank De Veld, Roberto Armellin

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zeno Pavanello, Frank De Veld, Roberto Armellin

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 driving a car on a highway, and suddenly, a massive truck ahead of you swerves into your lane. You have two choices: slam on the brakes immediately (which wastes fuel and might be unnecessary if the truck moves back), or wait as long as possible to see if the truck corrects itself, and then make a quick, sharp swerve at the very last second to avoid a crash.

This paper is about helping satellites do the "wait and swerve" strategy, but with a twist: they use low-thrust engines (like a gentle, continuous breeze rather than a rocket blast). Because these engines are weak, they need to start pushing early to move the satellite enough to miss a piece of space junk. The big question is: How late can we wait before we must start pushing?

Here is how the authors solved this puzzle, explained simply:

The Problem: The "Last Possible Moment"

Satellites orbit Earth at incredible speeds. Space is getting crowded with debris. When a satellite and a piece of junk are on a collision course, operators usually try to save fuel by maneuvering early. But sometimes, you get a warning very late, or you want to wait for better data to see if the collision is real.

The goal of this paper is to find the absolute latest moment a satellite can start its engine and still be safe. If you start any later, you crash. If you start earlier, you are safe, but you might have wasted fuel or time.

The Solution: The "Backward Sweep"

Most people solve problems by moving forward in time: "If I start now, where will I be? If I start later, where will I be?"

The authors used a clever trick called a Backward Sweep. Imagine you are walking backward from the moment of the potential crash (the "Time of Closest Approach") toward the present day.

Start at the crash: You stand at the point where the satellite and the junk would hit.
Step backward: You take a small step back in time.
Ask the question: "If I apply a tiny push right now (in this backward step), does it move the satellite enough to avoid the crash?"
Greedy Decision: The method is "greedy." It doesn't try to plan the perfect, fuel-saving route for the whole journey. It just asks, "What is the single best direction to push right now to get us out of trouble fastest?" It picks that direction, takes the step, and repeats.

It keeps stepping backward in time, stacking these "best immediate pushes" on top of each other, until it reaches a point where the satellite is finally safe. That point is the latest possible start time.

The Magic Tool: "Differential Algebra"

Doing this math for a satellite is incredibly hard because the satellite is moving fast, gravity is pulling it, and the "danger" changes constantly. If you calculate this step-by-step on a normal computer, it takes too long to be useful for a satellite in space.

The authors used a mathematical tool called Differential Algebra (DA).

The Analogy: Think of a normal calculator as a person who can only do one math problem at a time. Differential Algebra is like a super-chef who can prepare a whole banquet of related dishes at once. Instead of just calculating "where the satellite is," it calculates "where the satellite is, how fast it's changing, how that speed is changing, and how all those changes react to a push."
The Result: This allows the computer to predict the future (and the past) with extreme speed and accuracy. It can update the "Time of Closest Approach" on the fly. If a push moves the satellite, the moment of closest approach might shift by a fraction of a second. The DA tool tracks this instantly without needing to re-run the whole simulation.

The Results: Fast and Good Enough

The team tested this method on 2,170 different potential collisions using real data from the European Space Agency.

Speed: The computer solved every single problem in less than 80 milliseconds (faster than a human blink). This means a satellite could theoretically run this calculation on its own computer while flying.
Accuracy: The method was incredibly accurate, with less than a 0.15% error compared to a perfect, slow-motion simulation.
The Trade-off: Because the method is "greedy" (it just wants to be safe now), it isn't the most fuel-efficient way to fly. It uses about 33% to 41% more fuel than a perfectly planned, slow-and-steady maneuver.
- The Metaphor: It's like taking a taxi that drives aggressively to get you to the airport in 10 minutes, versus a bus that takes a scenic route and saves gas but takes 20 minutes. The taxi (this method) is great if you are late; the bus (fuel-optimal) is great if you have time.

Summary

This paper introduces a "panic button" algorithm for satellites. When time is running out, this method quickly figures out the very last second a satellite can start its engine to avoid a crash. It sacrifices a little bit of fuel to gain a massive amount of speed and safety, ensuring that even with late warnings, satellites can dodge space junk effectively.

Technical Summary: Time-Optimal Collision Avoidance Via a Greedy Polynomial Backward Sweep

Problem Statement
The paper addresses the challenge of designing collision avoidance maneuvers (CAMs) for low-thrust satellites operating in crowded orbital environments. While existing literature often focuses on fuel-optimal (FO) maneuvers that may require early initiation to minimize propellant, operational constraints frequently favor delaying maneuvers as long as possible. This delay allows operators to leverage updated tracking data to reduce positional uncertainty and avoid unnecessary maneuvers. The core problem is formulated as a time-optimal (TO) control problem: given a short warning time, determine the latest possible initiation time ( $t_0$ ) for a low-thrust maneuver that ensures the satellite remains safe at the time of closest approach (TCA). Safety is defined by exceeding a threshold for either the Miss Distance (MD) or the Probability of Collision (PoC), the latter being represented via the Squared Mahalanobis Distance (SMD) in the B-plane.

Methodology
The authors propose a Greedy Time-Optimal (GTO) backward-sweep method to solve this optimization problem without directly solving the complex continuous optimal control problem (OCP). The methodology relies on three main components:

Backward Sweep Strategy: Instead of forward integration, the algorithm starts at the nominal TCA and iteratively propagates the maneuver backward in time. At each discrete time step, it determines the thrust direction that locally maximizes the rate of change of the chosen danger metric (MD or SMD). The process continues until the safety threshold is met, identifying the latest possible start time.
Differential Algebra (DA): To efficiently handle the nonlinear dynamics and sensitivities required for the backward sweep, the authors utilize Differential Algebra. DA allows the system dynamics to be represented as high-order Taylor polynomial maps. This enables the propagation of state sensitivities and the calculation of how control actions at previous time steps affect the state at TCA without re-propagating the dynamics for every iteration.
Greedy Control and TCA Tracking: The control action at each step is computed by aligning the thrust vector with the gradient of the danger metric (a greedy approach). Crucially, the method accounts for the shift in TCA caused by the maneuver. Using DA, the orthogonality condition between relative position and velocity at TCA is solved via polynomial inversion to update the TCA shift ( $\delta t_{CA}$ ) online. This ensures the safety metric is evaluated at the correct, shifted time of closest approach.

Key Contributions

Formulation of a TO CAM Problem: The work shifts the focus from fuel-optimal to time-optimal formulations, specifically targeting the maximization of the warning time available before a maneuver must begin.
GTO Algorithm: A novel backward-sweep algorithm that combines a greedy control strategy with DA-based polynomial maps. This avoids the computational burden of solving the full OCP while maintaining high accuracy.
Online TCA Update: The integration of DA to automatically track and update the TCA shift due to low-thrust maneuvers, ensuring the safety metric is computed at the true geometric closest approach rather than a nominal time.
Computational Efficiency: The method achieves runtimes suitable for on-board implementation by avoiding iterative forward propagation and leveraging polynomial evaluations.

Results
The GTO method was validated using a dataset of 2,170 Low Earth Orbit (LEO) conjunctions from the ESA Collision Avoidance Challenge.

Accuracy: When compared against a forward-propagation validation, 99.7% of solutions exhibited a relative error below 0.15% for SMD and 0.04% for MD.
Optimality vs. OCP: Compared to a true optimal control solution (based on Pontryagin's Maximum Principle), the GTO method showed a median relative error in thrust initiation time of 2.96%, with 95th percentile errors under 11%. This indicates the greedy approach provides a close approximation to the true time-optimal solution.
Fuel Sub-optimality: As expected, the GTO method is less fuel-efficient than a dedicated fuel-optimal (FO) solution. The GTO approach required, on average, 33% to 41% more $\Delta v$ than the FO benchmark. This is attributed to the greedy strategy applying thrust continuously up to the threshold, whereas FO solutions often utilize coast arcs near TCA where control effort has diminishing returns.
Computation Time: The algorithm demonstrated high computational efficiency, with all runtimes remaining below 80 ms. Average runtimes were 23 ms for the SMD formulation and 56 ms for the MD formulation on standard hardware.

Significance and Claims
The paper claims that the GTO method offers a viable solution for on-board collision avoidance systems where warning time is the primary constraint. While the method accepts a trade-off in fuel efficiency compared to FO solutions, it provides a computationally lightweight way to determine the latest possible maneuver initiation time. The authors suggest that the GTO solution can serve as a robust initial guess for more complex FO solvers or be used in a pipeline where a time-optimal check is performed first to determine if a maneuver is strictly necessary before engaging in fuel-optimization routines. The ability to update the TCA shift online without re-propagation is highlighted as a critical enabler for the method's accuracy and speed.

The Problem: The "Last Possible Moment"

The Solution: The "Backward Sweep"

The Magic Tool: "Differential Algebra"

The Results: Fast and Good Enough

Summary

More like this