Combinatorial Space Trajectories
to Comets and Asteroids

Ingo Althöfer (Jena University)
Latest Update: March 05, 2019


In principle, the design of optimal space trajectories is a continuous optimization problem. However, if the task involves several objects (planets, asteroids, comets, space junk) it has also facets of combinatorial optimization. When I learned about the "Global Trajectory Optimization Competitions" in 2009, my old and almost forgotten interest in space missions reawakened. I looked for a creative colleague and programmer - and found him in Dietmar Wolz.

New: In 80 Years through the Solar System

Dietmar Wolz designed a very interesting "Total Tour" through the solar system: Starting at Earth with modest speed, making flybys at all planets (from Mercury to Neptune) and having a smooth accounter with Pluto in the end. Most of the energy is taken from gravity assists.

Entry in Dietmar's blog
Video: In 80 years through the solar system


Jena Missions to
Comet Churyumov-Gerasimenko

One of the "recent" highlights in space research was and is the Rosetta mission by ESA. Started from earth in 2004, the probe made high-speed flybys at two asteroids (Steins and Lutetia), and in 2014 arrived at comet Churyumov-Gerasimenko.

We were motivated to find other interesting tours: also with this comet as the final target, but before with slow flybys at many main belt asteroids. By "slow" a relative speed of 5 km/s or less is meant. At this speed more data and photos can be taken, and at this speed it is also possible to make the flybys more narrow: for instance with minimum distance 1,000 km instead of 2,500 km.

Using modified techniques from the GTOC-competitions and the list of 16,000+ asteroids from GTOC-7, we constructed several interesting low-thrust tours with computer help. Here are some of them.

Double Probe Mission with 27 + 24 Flybys

A highlight is the following double mission: Two probes start from earth and have the comet Churyumov-Gerasimenko as their final destination. The first probe is intended to make a highspeed crash into the comet. The other probe will arrive two months later for a soft landing and possible investigation of the impact place. During their trajectories, both probes will make slow flybys (with delta-v below 5 km/s in most cases) at many main belt asteroids. The "crash probe" meets 24 asteroids, and her soft sister has even 27 encounters. All the asteroids visited are different, so a total of 51 minor bodies and the comet at the end are inspected. Arrivals at the comet will be, when the comet is relatively near to earth - and also in an active phase.

The probes start from earth in January 2022, and arrive at the comet in 2035.

Video: The Jena double mission to comet "Chury" with 27+24 slow flybys

Comet Sample Return Mission with 19 + 23 Flybys

A single probe starts from earth and will go to comet Churyumov-Gerasimenko. There it will land, collect samples and brings them back to earth. Both in the first and the second leg, the low-thrust probe will make slows flybys at many mainbelt asteroids (again taken from the 16,000+ list of GTOC-7).

The probe starts from earth in December 2021, arrives at the comet in 2035, and is back at earth in the year 2048.

Video: Jena return mission to comet "Chury" and back to Earth with 19 + 23 slow flybys


Flyby at Asteroid VishyAnand and Dust Collection at Comet Churyumov-Gerasimenko

This mission is rather different from the previous ones. It is relatively short: slightly longer than five years. Start from Earth in 2025, narrow slow flyby at asteroid VishyAnand in 2026, narrow fast flyby at comet Churyumov-Gerasimenko in 2028 (including the collection of comet dust), return of the dust to Earth in April 2030.

Video: Jena mission with flyby at VishyAnand and dust return from comet Churyumov-Gerasimenko

Vishy Anand is (still today) one of the very strongest chess players in the world. He was 6-fold World Champion (between 2001 and 2013) and the best Asian chess player so far. The idea for this space tour came up, when the international chess press reported that an asteroid had gotten the name of Vishy Anand. By chance, he is also interested in astronomy, including observation "campaigns" with modern telescopes.

On demand more details of the mission can be given: mass bounds, time tables, flyby and reentry speeds, propulsion strategy ... Perhaps India, a nation with high ambitions in space reasearch and smart engineers (see the Indian mission to Mars from 2014), might be interested to fly such a tour. For this mission - as well as for the other missions mentioned on this site - of course also later starting dates are possible.


Global Trajectory Optimization Competitions


In a Global Trajectory Optimization Competition strong engineers and scientists from all over the world try to solve a difficult and futuristic trajectory task under realtime conditions. The task is published, and registered teams have exactly 28 days to submit the best solutions they "find". A second serious point is: It is not known ahead what the overall optimal solution is - and how far other participants have come. Even the team (the winner of the previous competition) who provides the task typically does not know what is achievable.

During the competitions, more and more teams participated. It started in GTOC-1 with 17 participants and grew to 38 at GTOC-7. One thing has to be seen: Not each registered team will submit a solution. For instance, in GTOC-7, only 27 of the 38 teams submitted. Participants come from almost all nations with engagement in space activities: USA, Canada, Western Europe (national and international teams), Russia, Japan, China. (And it is only a question of time that also teams from India and Iran will compete.) Three times, a team from the Jet Propulsion Laboratories in Pasadena (California) won the competition. But also West Europeans were successfull, and also a group from Moscow State University.


Here we present space trajectories designed by my team at Jena University and Dietmar Wolz. Some are from the GTOC competitions. Others are from tasks he worked on by his own interest. In each case, we visualized and published the trajectories in a Youtube video. Of course, in all these missions fuel was limited and also the maximum duration of the mission.

Essential for the design of our trajectories are three algorithms by Dario Izzo (Lambert solver), Nikolaus Hansen (CMA-ES), and M.J.D. Powell (BOBYQA). We give some links for descriptions and sources at the end of this site.


Our Best: 49+1 at GTOC-4

A list of about 1,300 near earth asteroids (with their Kepler orbits) was given and a 15-year time window for the start from earth. The task was to design a low-thrust trajectory with as many flybys as possible, including a soft final landing on one of the asteroids. The whole tour had to last no longer than 10 years from earth start to final asteroid landing. The problem statement in detail can be found here: GTOC-4.

Winner of the GTOC-4 became a team from Moscow State University, with 44+1 asteroids.
Video of the winning Moscow tour for GTOC-4


Video of the 45+1-"Johnson Tour, University of Texas at Austin" for GTOC-4


Video of the 46+1-"Jena Tour" for GTOC-4, found in 2015
Asteroid list of our 46+1 tour:

In September 2017, Dietmar Wolz was able to compute a GTOC-4 tour with 47+1 asteroids. Video of the 47+1-Tour for GTOC-4

In April 2018, Dietmar Wolz made another big step forward. He computed - by sort of a miracle - a GTOC-4 tour with 49+1 asteroids.

Youtube movie of our 49+1-Tour for GTOC-4

More details of this tour on request. Send email to
gtoc4.ingo.althoefer@gtoc4.uni-jena.de
In doing so, delete all gtoc4. parts from the address.

Are there 50+1 tours around for the GTOC-4 problem?


GTOC-5

A list of about 7,000 asteroids was given and a 15-year time window for the start from earth. The task was to design a trajectory where the probe softlanded on asteroids and installed seismographs. Later the probe shot a "heavy bullet" into such asteroids (and the seismograph should record the impact). For each soft landing the mission got 0.2 score points, and for each heavy bullet another 0.8 points. The task was to get as high a score as possible within mission length 10 years or less. The problem statement in detail can be found here: GTOC-5.

The winning team (from JPL, Pasadena) achieved 18 points. During the competition, we "found" a tour with 12 points. Later - with improved techniques - Dietmar Wolz got another tour with 17 points.

Video of our tour with score 17 for GTOC-5


GTOC-6

Planet Jupiter with her four main moons (Io, Europa, Ganymede, Callisto; innermost mentioned first) was given. For each moon, the surface was subdivided in 32 areas/faces; and each face had some value between 1 and 3. A probe should take photos of the faces, during a 4-year tour with multiple gravity assists at the moons. The task was to maximise the total score (324 being the theoretical upper bound). The problem statement in detail can be found here: GTOC-6.

The winning team (from Roma and Torino) achieved 311 points. Our best solution - constructed in early 2015 - has 275 points.

Video of our 275-tour; view from above
Video of our 275-tour; view from the side


GTOC-7

A list of about 16,000 main belt asteroids was given. The task was to design a trajectory for one mothership and three smaller probes. Each probe would leave the mothership to softland on as many as possible asteroids during a 6 year span, then return to the mothership. Score was the total number of asteroids visited. The problem statement in detail can be found here: GTOC-7.

During the competition, we found a solution with 24 points - and were optimistic that these 24 points were a strong score. But after evaluation it turned out that the JPL team had achieved a 36-solution; so we had missed our target to get at least 80 percent of the winner score. At least, the 24 points made us the best German scorer. Rather quickly after the competition we found a 29-solution, and even later one with 34 points.

Video: A Jena tour with score 29 for GTOC-7


Video: A strong Jena tour with score 34 for GTOC-7



Computing time was not for free. The power bill for Winter 2014/2015 showed more than 700 Euro extra, only for the trajectory computations.


In Summer 2018 we had a look at the first three editions of GTOC. For each one, we produced a video for our best solutions so far.

Video of our best tour for GTOC-1

Video of our best tour for GTOC-2

Video of our best tour for GTOC-3


History: Pioneer 10
Through the Main Asteroid Belt

The sequence of planets is well known. Starting at the sun and going outwards we have Mercury, Venus, Earth, Mars, Jupiter, ... Between Mars and Jupiter, many smaller bodies "reside": the asteroids in their main belt. For a long time it was not clear how densely this belt was filled with really "small" pieces. In particular it was an open question if a probe from earth would have good chances to survive a treck throught the main belt. It definitely has!

The first trecker was the US-probe Pioneer 10. It was launched in March 1972, reached the inner shore of the belt in July 1972, had passed the belt healthy in February 1973, and reached Jupiter successfully in December 1973.

The different steps of the Pioneer 10 and 11 tours were celebrated by special postal letters. We are proud to own some of them:






Our Toolbox

Our search algorithm for designing space trajectories is implemented in Java. It is based on three C++ algorithms called via JNI:

* The new Lambert problem solver by Dario Izzo
described here, implemented as part of the PyKEP C++ library. Here is the source code. This algorithm performs significantly faster than any alternative we tested. We also use the Taylor propagator for the continuous thrust conversion.

* CMA-ES by Nikolaus Hansen
CMA-ES is used for continuous thrust conversion and the global optimization of trajectories approximated by Lambert transfers after search. We use the active CMA variant with Hansen's mirrored sampling. We developed our CMA-ES C++ code from our contribution to Apache Commons Math.

* BOBYQA by M.J.D. Powell
BOBYQA is used for local optimization of trajectory legs during search. Here, we use the code from the dlib C++ Library.

As a starting point for our development we used the OREKIT library which is currently mainly used for verification purposes.

* Blogspot
More technical stuff can be found at Dietmar's new Scientific Computation Blog.



Outlook and Dreams

* Our Missions in Reality

It is our dream that one day an agency will really fly one of our trajectories; for instance a state agency or a private company (asteroid miners?!).

* Missions for Directed Panspermia

Maybe, life came to our solar system and to earth via directed panspermia. I am looking for the design of 10,000-year missions who bring (elementary) terrestrial life to other stars and exo-planets.

See also my website on Directed Panspermia and Titius-Bode Law

* PhD Studies at Jena University

At Jena University I lead a group in Discrete Optimization and Applied Mathematics. For smart young people with algorithmic background and creativity, there are PhD positions available. Feel free to apply.




Dr. Dietmar Wolz

Dietmar Wolz holds a PhD in Theoretical Computer Science. In the years 2000-2002 he programmed very nice and fast algorithmic procedures for solving the "Eternity Puzzle". On a standard single core PC, his program constructed several new Eternity solutions, one by one every five days or so - not bad for a problem called Eternity. Wolz was also successful in other discrete optimization problems, for instance in the design of cellular automata with extreme properties.




Back to the main site - Zurück zur Hauptseite