nasa caltech_jpl
GTOC X
10th Global Trajectory Optimisation Competition

May 21, 2019, 8 p.m. UTC

June 12, 2019, 8 p.m. UTC

Timeline

The competition is over.

Did anyone beat J=4000 yet?

avatar

DietmarW

NUDT-XSC state in their paper:
"However, the performance must be discounted by going around the time-dependent problem, so it is confidently expected that there is still considerable improved room for the current best solution"

How much room for improvement is actually there? Did anyone beat J=4000 yet?

We tried to implement a new settler-ship algorithm (see below) keeping the mother ship and fast ship transfers as submitted by the teams, but failed to reach J=4000.

NUDT-XSC J = 3889, 4033 stars
ESA-ACT J = 3159, 3859 stars
Aerospace J = 3117, 3686 stars
Tsinghua J = 2922, 3767 stars
TeamKata J = 2558, 3707 stars
HIT_BACC J = 2529, 3795 stars
MSU-RAS J = 1713, 2781 stars
1-2-B-num1 J = 1469, 2512 stars
CSU J = 1391, 2199 stars
worhp2orb J = 1211, 2160 stars

Then, keeping NUDTs mothership transfers we slightly shifted NUDTs fast ship targets just a bit further, we choose star 26758 at Myr=26.28 and star 55401 at Myr=35.93. Now finally we were able to reach our goal:

NUDT-XSC-Jena J = 4023, 4216 stars

avatar

DietmarW

How did we do it?

We apply the whole list of operations:

- adding stars / nodes
- deleting stars / nodes
- replacing stars
- shifting transfer timing

in a loop both during tree construction - where we limit the maximal settling time, and during final optimization - were we have a fixed settling time at 90 Myr. The maximal settling time is incremented in 5 Myr steps. During tree construction we individually try to reduce the settling time preserving the approximated DV limit and allow timing
shifts only if they reduce arrival time.

Before final optimization we shift all leaves to Myr=90 and perform the tree restructuring described in Figure 7 in the ESA paper.

We apply the operations on nodes starting with the ones with the lowest time of flight from the settling root (mother ship or fast ship). Candidate stars for adding / replacements are reverse ordered according to their distance to the star we come from / we are replacing. We were surprised that reverse ordering works better here. We applied
a distance limit of Kpc=4.5 for all replacements.

We terminate the loop if the score doesn't improve any more. For each (maximal) settling time we run the loop twice. The second time adding and deleting is performed if the score increases. The first time we add more cautiously only if the score after adding a star increases more than J = 0.2 and delete more aggressively if the score after deletion increases more than J = -0.3 - so it may actually decrease a bit. This way the score/set of stars oscillates between adding / deleting which helps to compensate for the lack of "memory". We store only one settling tree which is greedily improved. Algorithms like beam search or genetic algorithms store many individuals which would require a lot of memory because we optimize a whole tree.

After the loop ran twice for the final settling time 90 Myr, we replace the approximated transfers (elliptical 2-impulse approximation) by the required model (n-impulses using the given differential equations). This is easy since the merit function already favors low DV transfers.

avatar

DietmarW

Evolution of the best solution so far:

Expansion phase:

- two impulse elliptic approximation
- result after both loops terminated

max arrival time = 15.7 Myr, J = 16.9, 21 stars
max arrival time = 20.7 Myr, J = 20.0, 30 stars
max arrival time = 25.7 Myr, J = 24.4, 46 stars
max arrival time = 30.7 Myr, J = 31.3, 66 stars
max arrival time = 35.7 Myr, J = 43.6, 94 stars
max arrival time = 40.7 Myr, J = 59.5, 119 stars
max arrival time = 45.7 Myr, J = 87.0, 176 stars
max arrival time = 50.7 Myr, J = 133.8, 273 stars
max arrival time = 55.7 Myr, J = 201.2, 431 stars
max arrival time = 60.7 Myr, J = 300.7, 627 stars
max arrival time = 65.7 Myr, J = 456.3, 942 stars
max arrival time = 70.7 Myr, J = 702.3, 1404 stars
max arrival time = 75.7 Myr, J = 977.5, 1979 stars
max arrival time = 80.7 Myr, J = 1456.1, 2846 stars
max arrival time = 85.7 Myr, J = 2019.4, 3586 stars
max arrival time = 90 Myr, J = 2763.6, 4283 stars

Tree transformation, see Figure 7 in the ESA paper.

Final optimization phase:

arrival time = 90 Myr, J = 3972.2, 4216 stars

- multi impulse model using the differential equations:

arrival time = 90 Myr, J = 4023.2, 4216 stars

avatar

DietmarW

Further details of the method are given in relation to the NUDT-XSC paper:

NUDT-XSC: "A latest research of the authors using Monte Carlo tree search algorithm was conducted in the context of GTOC X suggesting that its use may be competitive to the current state of the art technique."

In game theory tree search is applied to branches representing the state after n moves. Optimization target are branches, not trees. GTOCX requires optimization of large trees which renders the Monte Carlo tree as a "tree of trees". This is the reason we prefer a simple greedy algorithm storing only a single state / tree at a time. Which doesn't mean Monte Carlo tree search couldn't lead to improvements.

NUDT-XSC: "Actually, body-to-body optimization should be contained in the overall optimization if we want to achieve the global optimal total velocity increments. However, it is too time consuming and computationally difficult to determine the best departure and arrival times while calculating the optimal velocity increments of each transfer when there are tens or even hundreds of stars in a tree."

You don't need to determine the best arrival time, just an approximation. In our inner loop we perform the following fast optimization:

num = 300;
dtmax = 0.1; // Myr
double fac = 1.0 - (1.0 / num);
for (int i = 0; i < num; i++) {
ddv += optimizeTransfers(dtmax);
dtmax *= fac;
}

where optimizeTransfers shifts the arrival time of all nodes with children starting near the leaves by (dtmax * random(0,1))^2 if a) the arriving transfer and its children are valid and b) the overall score improves. fac represents a cool down factor of the arrival time movement over time. This optimization is fast enough to be applied in our inner loop at every stage.

NUDT-XSC: "At the early stage of the competition, we increased the fuel coefficient significantly by optimizing the maneuver time".

During expansion you should only increase the score by shifting the arrival time down. Shifting up is reserved for the final phase, otherwise you reduce the number of stars visited which hurts the score.

avatar

DietmarW

It follows a comparison of the NUDT-Algorithms described in their paper with our approach. Each step is aimed at maximizing the real performance index, which is different to many approaches other teams applied, but is exactly what we do.

NUDT-XSC: "Algorithm 3 ACO for the CMSTDC problem"

This algorithm is replaced by applying the other algorithms in a nested loop incrementally increasing the maximal arrival time in an outer loop.

NUDT-XSC: "Algorithm 4 Reconstruction nodes"

There is no equivalent of this algorithm in our approach. Instead
we only use adding, deleting and replacing and the tree transformation from Figure 7 in the ESA paper.

NUDT-XSC: "Algorithm 5 Adding nodes"

Similar to our method, but
a) we sort the candidate parents, we try all candidate parents.
b) we sort the candidate new stars (max dist <= 4.5 kpc to brother or parent), we try all candidates fulfilling this property
c) we require a J-jump in the first loop - but not in the second.
d) applied in all loops in all stages
e) we first try linear approximation at the maximal arrival time, then elliptical approximation at the maximal arrival time, then we reduce time of flight at most 2 times: tof_new = tof_old * (dv / 400)^0.711. If after tof reduction dv > 400 we take the last valid tof.
f) in the final optimization phase we instead use always a fixed arrival time = 90 Myr

Purpose of sorting is to increase the average branching factor. Nodes near the root get a better chance to be extended.

NUDT-XSC: "Algorithm 6 Deleting nodes"

Similar to our method, but
a) we sort the candidates for deletion (inverse to the sorting of parents used for adding nodes), we try all candidates.
b) we allow the J value to decrease slightly in the first loop - but not in the second.
c) applied in all loops in all stages

NUDT-XSC: "Algorithm 7 Replacing nodes"

Similar to our method, but
a) we sort the candidates for replacements (as parents for adding nodes)
b) we sort the candidate replacement stars (max dist <= 4.5 kpc to replaced node) as we did for
candidate new stars for adding nodes.
c) we don't use the existing arrival time but use the method e),f) in "adding nodes" to
determine an optimal arrival time for the replacement star.
d) we accept a replacement only if the arrival time for the replacement star decreases or is equal to the existing arrival time.
Note that in the final optimization phase this condition holds always because we use a fixed arrival time = 90 Myr.

Beside adding, deleting and replacement we apply our arrival time shifting optimization in each inner loop.

avatar

DietmarW

Here are youtube video links so that you can compare the after competition improvements with the original submissions:

After competition improvements:

NUDT XCC improved fast ships https://youtu.be/L4z-QlWlOhE
NUDT XCC https://youtu.be/rheyEOvp2i8
TsinghuaLAD-XINGYI https://youtu.be/yIMMJkifOeg
ESA-ACT https://youtu.be/ipTcEzExark
Aerospace https://youtu.be/zrxiL9Rb0zQ
HIT_BACC https://youtu.be/LhCy-ZK3dzo
TeamKataskopoi https://youtu.be/71KJksexJ0Y

Original submissions:

NUDT&XSCC: https://youtu.be/5jJwgmFygcg
Tsinghua LAD - XINGYI: https://youtu.be/3HyaczvnxeA
ESA ACT: https://youtu.be/s8mD9UvJlXc
The Aerospace Corporation: https://youtu.be/e2ZmWM_UFBA
HIT_BACC: https://youtu.be/OUgb4AuQC6U
Team Kataskopoi: https://youtu.be/J5vtNZ-Uu1M

avatar

DietmarW

In the meantime I improved my own verification method and found small constraint violations. Initially I thought these can be fixed by shifting the timings, but at that level (> 3800) these are already very tight. So the results shown above are mainly interesting to compare the mothership/fastship routes of the different teams, verifiable results are probably about 3-4% lower. The best verified solution has J = 3847 using 3677 stars, so the J = 4000 goal is still open. If anyone is interested to verify the J = 3847 solution please send me an email.

avatar

DietmarW

I got some questions about the approach used, so I will try to clarify further:

Q: You must get your preliminary trees, so that the preliminary trees could be improved by reconstruction, yes?

A: That is how all other approaches work, but not this one. We start directly with the mothership / fast ship root tree and apply the following nested loops keeping only one single instance of the settler tree which is improved in all operations:

for (arrival_time = 15; arrival_time <= 90; arrival_time += 5.0) {
do {
improve_timing();
replace_nearby_1(arrival_time);
delete_leaves(0.3);
add_nearby_1(arrival_time, 0.2);
} until no score improvement
do {
improve_timing();
replace_nearby_1(arrival_time);
delete_leaves(0.0);
add_nearby_1(arrival_time, 0.0);
} until no score improvement
}
reorganize_transfers;
shift_leaves_to_90();
do {
improve_timing();
replace_nearby_2(90);
delete_leaves(0.3);
add_nearby_2(90, 0.2);
} until no score improvement
do {
improve_timing();
replace_nearby_1(90);
delete_leaves(0.0);
add_nearby_2(90, 0.0);
} until no score improvement

- the operations marked "_2" in the final phase don't try to reduce the arrival time as the
"_1" operations do.
- delete_leaves(0.3) means a delete is performed if the score doesn't drop more than J = 0.3.
- add_nearby(arrival_time, 0.2) means a node is added if the score increases more than J = 0.2

Q: How are the transfers approximated?

A: We use
- 2 impulse linear approximation to filter out bad transfers, then a
- 2 impulse elliptical approximation (Lambert algorithm).
- if one impulse > 175 we switch to a 3 impulse elliptical approximation,
- if both are > 175 we use a 4 impulse elliptical approximation.
We apply the Lambert impulse capped to 175 km/s, do a keplerian propagation for 1 Myr
(mu is approximated from R and the mean motion of the star)
and then apply the Lambert algorithm again to determine the impulses.

avatar

DietmarW

Q: How do you deal with the Curse of Dimensionality?

Lets assume we use a simple greedy algorithm by discreting transfer time by step 5 Myr. Means we aim at arrival time t = 15, 20, 25, ..., 90 using only the "add star/child node" operation if the score increases.

What would be the result? You would end up with a quite small number of nodes, since

a) tof would be higher than necessary

b) branching factor would be quite low, since we waste the "good stars" for high time of flight transfers, which are better used for low tof transfers.

c) score added by the given stars is low, since we greedily chose stars which later turn out to be suboptimal.

Each of these issues is addressed:

a1) Instead of taking the discrete arrival time we try to lower it even if the score is reduced. From discrete tof and dv we could guess which tof would result in dv = 400. Instead we aim lower (lets say at dv = 350) and apply the method a second time if successful. Aiming directly at dv=400 would result in too many failures. The decision if the operation (adding/replacing) is finally performed is based on the final tof/dv (which is no longer discrete) based on the score using this final tof/dv.

a2) The improve_timing optimization is performed in the inner loops. In the build phase there are two restrictions: Arrival time is shifted only down, it is applied only if the score increases. Looks contradicting, but not for nodes which have already children, since we adapt the start time for the children accordingly.

b1) We sort the candidate (parent-)nodes for addition, replacement and deletion according to their arrival time (of the parent in case of addition). This way we make sure nodes with low arrival time have the highest chance to be extended.

b2) We sort the nearby nodes to be added / replaced according to their distance to the parent / replaced existing node. Why this works needs to be further investigated, I just found out that it improves the result when we prioritize far stars. It seems it helps to better distribute the stars of the tree.

c1) Replacement of stars (if the score increases and the arrival time is lowered) helps to undo bad choices. This is the reason we perform replacement in the inner loop during construction of the preliminary tree.

c2) Oscillating score: The inner loops adding/deleting/replacing stars increases the number of stars when adding and decreases it when deleting.
This inner loop - with a specific discrete initial arrival time - is performed twice. The second time we allow only operations increasing the score, but the first time we parameterize adding/deletion in a way which leads not only to an oscillating number of stars, but also to an oscillating score. By allowing deletions here even if they decrease the score we enhance the chance to revert "bad decisions". The loops are terminated if the score after adding no longer increases (ignoring the score after deletion).

Please log in to leave a comment.