Dodging space debris with algorithms

Researchers from TU Darmstadt and ESA present a new method.

More and more artificial objects are orbiting the Earth. Apart from satellites essential for communication, research, or navigation, most others are unwelcome and pose an operational risk because they increase the probability of collisions. Preventing these requires efficient algorithms to identify objects that are getting dangerously close to each other, researchers at TU Darmstadt and the European Space Agency (ESA) now present two new approaches.

In 1957, the first satellite was sent into orbit. Many more have followed since – a total of around 16,000 to date. What sounds like only a few in the vastness of space has significant implications. With each satellite launched, the number of objects orbiting the Earth continues to increase, not only from the satellites themselves but also from a wide variety of debris, known as space junk: parts of launch vehicles and retired satellites or other mission-related items, such as clamps, sleeves or bolts, that were released in Earth orbit.

All these objects move in orbits at very high speeds, which has already frequently resulted in collisions. There is the threat of a chain reaction: when objects collide with satellites or other debris, many new pieces of debris are created. These, in turn, increase the probability of further collisions. Even tiny parts can cause considerable damage to satellites and spacecraft because of their high velocity, making space travel’s safety and the use of space in general increasingly challenging.

Space surveillance sensors now track more than 30,000 objects in Earth orbit. Some 8,000 of these objects are operational satellites, of which about 2,400 were launched in 2022 alone. New methods that will be used in the coming years should soon make tracking more than one million objects possible. Additionally, it is estimated that there are over 100 million other objects in orbits in near-Earth space that are too small to be located at present.

How can satellites be prevented from colliding with each other or with other objects? The researchers from the Technical University of Darmstadt and ESA worked on this problem – and to do this, they first needed (position) data. “Satellites and space debris are monitored from the ground with powerful radars and optical telescopes,” explains Reinhold Bertrand, responsible for research and development in the Space Safety Programme of the European Space Agency ESA and a cooperation professor at TU Darmstadt. “Functional satellites usually have on-board sensors for positioning and can therefore provide even more precise position data to Earth. This allows the current orbit to be determined for each object from the observation data.”

From this, in turn, forecasts for the position one to two weeks into the future can be derived mathematically. The system checks whether two objects come too close to each other at any time and determines their collision risk. This can be calculated more precisely the more imminent the collision is. If a satellite is on a collision course with another satellite or object, a collision warning is sent to the satellite operator, who can then initiate an evasive manoeuvre. The lead time is approximately one to two days, sometimes only a few hours. However: if two pieces of debris are on a collision course, a collision cannot be avoided.

Due to the increasing number of objects in Earth orbit, current collision detection algorithms and procedures are reaching their limits. The number of objects to be monitored is already high and increasing rapidly as both the amount of debris and the number of satellites continue to grow. Additionally, improved detection methods will make significantly more objects visible in the future than is the case now, which the calculation will then all have to take into account.

This is where the Laboratory for Parallel Programming at TU Darmstadt comes into play, which develops programs for complex computing tasks. “We faced two challenges,” says Professor Felix Wolf, head of the laboratory. “For one thing, we wanted to simulate the positions of the objects for a much longer period of time, not just one or two weeks as before. Secondly, we wanted to consider a larger number of objects. This required a new and efficient algorithm.”

At present, the calculations on the orbits of all objects in space are carried out pairwise (“all-on-all”), resulting in a quadratic number of satellite pairs whose collision risk must be excluded one after the other. These calculations take longer the more objects need to be checked and the faster they move.
To avoid the quadratic number of comparisons and thus a quadratic amount of work and computation, the researchers used spatial data structures and parallelisation methods to identify possible collisions (“grid-based variant”), which means that the collision risk is now no longer calculated sequentially for each pair of objects, but the objects are sorted into “cells”, each representing a small part of near-Earth space. This makes it possible to have to compare only the objects within the cells and their directly adjacent cells. In a second step, the scientists investigated a hybrid method, combining the grid-based variant with the classical one.

Data from real satellites were used for the simulation. The researchers were able to perform the necessary computations on TU Darmstadt’s Lichtenberg computer, which is specifically designed for complex computations of this kind. It contains special processors and graphics cards (GPUs) that are far more powerful than their standard end-user counterparts. Although this does not speed up the algorithm from a theoretical point of view, the actual computation still only takes a fraction of the time.

The researchers showed that predicting impending collisions can be significantly accelerated with the new method. Furthermore, it can simulate and, thus, help monitor the movement of more than one million objects in Earth orbit. The limiting factor for the number of objects to be examined is the memory consumption for the computations. However, using several graphics processors could compensate for this to a certain extent.

“Our computation methods make it possible to examine all objects in space that can be tracked in the near future for possible collisions,” Wolf sums up the results. “The new algorithm is already being used as a model in an ESA study,” adds Bertrand. The two professors agree: “It will increase safety in space.”

Wissenschaftliche Ansprechpartner:

Prof. Dr. Felix Wolf
Department of Computer Science
– Parallel Programming –
E-Mail: felix.wolf@tu-darmstadt.de
Tel.: +49 6151/16-21635

Originalpublikation:

Christian Hellwig, Fabian Czappa, Martin Michel, Reinhold Bertrand, Felix Wolf: “Satellite Collision Detection using Spatial Data Structures.” In Proc. of the 37th IEEE International Parallel and Distributed Processing Symposium (IPDPS), St. Petersburg, Florida, USA, pages 724–735, May 2023.

https://www.tu-darmstadt.de/universitaet/aktuelles_meldungen/einzelansicht_417856.en.jsp