6. September 2023

Making outer space safer with algorithms

Burned-out rocket stages, broken satellites, lost screwdrivers, chipped paint particles: There is so much space debris flying around the world that dangerous accidents are becoming increasingly common. Researchers at TU Darmstadt want to prevent this. Their mission: They want to make outer space safer.

space debris_copyright-ESA
Debris objects, mostly debris in low Earth orbit LEO, view over the equator pillars. Note: Artist’s impression; size of debris exaggerated as compared to the Earth. Copyright: European Space Agency, ESA

Since 1957, when the first satellite Sputnik was launched, more and more objects have been flying around the Earth. Today, there are about 16,000 satellites and many millions of pieces of debris, which are dangerous for these satellites. Because even small pieces of debris can cause great damage in a collision, setting off a chain reaction. New debris particles are created, which can collide with satellites again. This can take an avalanche-like development. Under certain circumstances, space travel could cease in certain areas in the future.

The European Space Agency (ESA) in Darmstadt constantly checks whether satellites could collide and, if necessary, lets them avoid them. The experts must intervene every two weeks.

“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 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.”

Predicting when accidents will occur is elementary. But this is becoming increasingly difficult because the number of satellites is growing rapidly.

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 and member of our CSG Parallelism and Performance in NHR4CES. “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 parallelization 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.

Computations on Lichtenberg high performance computer
Data from real satellites were used for the simulation. The researchers performed 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. Currently, the experts are monitoring around 30,000 objects in Earth orbit.

When the new method comes into use in a few years, ESA will be able to prevent many more serious satellite accidents and make outer space a little safer.

space debris_copyright-ESA