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.

How to use the published solutions to improve your GTOCX score

avatar

DietmarW

GTOCX is the first GTOC competition were submitted solutions were published.
I opened this thread to discuss how these solutions can be utilized. May be others
can add their ideas, we definitely can achieve better results by joining forces.

Published solutions may be used to:

a) Achieve speedups by implementing a fast approximation for star to star transfers:

Fast approximation of valid star to star transfers speed up your algorithm. You may use
elliptical approximations of your transfers using the Lambert algorithm based on the
assumption that there is a central body as source of gravitation. For a galaxy this
is not the case, but for short transfer times (< 20 Myr) Lambert approximations are quite
accurate. The gravitational parameter of the central body can be derived from R and the
mean motion. Since R is different at start and arrival we have to somehow approximate the
gravitational parameter.
This approximation can be verified using an existing GTOCX solution as follows:
One term of the merit function is dVmax/dVused. Compute dVmax/dVused for good GTOCX solutions
using your Lambert approximation and compare with the real value.

b) Achieve speedups by implementing filters for valid star to star transfers:

A filter can further improve performance by sorting out infeasible transfers based on
the positions of the stars and the time of flight. You may verify such a filter by checking
if valid transfers of good GTOCX solutions are not filtered out.

c) Finetune the parameters of your algorithm

To explain this topic we need an example algorithm. Lets choose the simplest one I know
which is able to generate a reasonable (> 3000) score:

Prerequisites
-------------

You need an efficient incremental implementation of the merit function, both without and
with the dVmax/dVused part. Which means you have to maintain the sums for a given star/transfer
set to be able to compute the merit function fast if a star/transfer is added.

Base Algorithm
--------------

The base algorithm is based on star sets, it abstracts from the problem how to get from star A
to star B:
Given a set of settled stars setA, determine a disjoined set setB so that merit(setA + setB) is maximized.
We use the merit function without the dVmax/dVused part here. The incremental
algorithm works as follows:

a) Randomly choose a star S not in setA.
If merit(setA + S) + 0.2 > merit(setA) then add S to setA
b) Repeat a) until setA no longer grows
c) Randomly choose a star S added to setA by a),b),
randomly choose a star S2 not in setA.
If merit(setA + S2) > merit(setA + S)
then add S2 to setA and remove S from setA
d) Repeat c) until merit(setA) no longer grows
e) Repeat a), b), c) d) until merit(setA) no longer grows

avatar

DietmarW

With "randomly choose" we mean choose and retry for a configurable number of times until the condition
is met. In practice you can set hard limits to the number of repetitions in each step. Since the algorithm
is stochastic it can easily be parallelized: Distribute different instances of the algorithm
to your available CPU cores and choose the best result.

Interesting test star sets to be extended derived from a submitted solution can be:
a) the set of stars reached by mother/fast ships.
b) the set of stars reached before Myr=90

Considering valid transfers
---------------------------

In practice you cannot simply add a star S to your set of visited stars, you have to fulfill two
constraints:
a) Branching factor <= 3: Only 3 settler ships may start from a star
b) Valid transfer: There has to be a valid transfer between a star in treeA to S.
We always choose the earliest possible departure time = arrival time + 2 Myr. The targeted arrival time is
a parameter of the algorithm. Now we also need the full merit function using dVmax/dVused which
we name meritDV here.

The goal is now:
Given a tree of settled stars treeA, determine a disjoined tree treeB so that meritDV(treeA + treeB) is maximized,
treeB nodes are rooted in treeA nodes using valid transfers and the resulting tree
treeA + treeB fulfills the branching factor <= 3 constraint.

These valid transfer contraints are added to the merit constaints above. Only if the merit constraints
of the basic algorithm are fulfilled we need to check transfer constraints. Keep in mind, that the timings
of the transfers are fixed for now: departure time = arrival time + 2 Myr, arrival time at next star
is a parameter of the algorithm.

a) Iterate over stars S0 in treeA with less than 3 outgoing transfers.
b) Randomly choose a star S not in treeA. If merit(treeA + S) + 0.2 > merit(treeA)
and if there is a valid transfer from S0 to S
and if meritDV(treeA + S) + 0.2*dVmax/dVused > meritDV(treeA) add S to treeA.
c) Repeat a), b) until treeA no longer grows
d) Iterate over stars S0 in treeA with less than 3 outgoing transfers.
e) Randomly choose a star S added to treeA by a),b),c),
randomly choose a star S2 not in treeA. If merit(treeA + S2) > merit(treeA + S)
and if there is a valid transfer from S0 to S2
and if meritDV(treeA + S2) > meritDV(treeA + S) then add S2 to treeA and remove S from treeA
f) Repeat d), e) until meritDV(treeA) no longer grows
g) Repeat a), b), c), d), e), f) until merit(treeA) no longer grows

The order of the iteration in a) and d) needs to be optimized to cope with the branching factor <= 3 limit.
We maintain the sum of the number of added outgoing transfers for each of the stars we iterate over and
sort these stars according to this sum. This way stars which have less chance to be root of new settlements will
get higher priority.

avatar

DietmarW

Finetune the parameters of your algorithm
-----------------------------------------

As a first step take the subtree of a good solution including all stars reached before Myr=90.
Then apply the algorithm with a fixed arrival time of Myr=90. If you take for instance the
NUDT subtree you should reach a score > 3000 by adding Myr=90 nodes to the tree using the algorithm
above. If not your parameters need some tweaking.

How to compute a solution based on a root tree generated using only mother ships and fast ships
----------------------------------------------------------------------------------------------

If you start from a root tree you can use the algorithm with fixed arrival time of Myr=90
removing the branching factor <= 3 constraint to quickly evaluate the "quality" of the root tree.

But to compute a real solution, we cannot directly head for Myr=90, we need intermediate nodes to
grow the tree. We simply iterate over multiple invocations of the algorithm above incrementally
increasing the targeted arrival time. Something like

Tree treeA = baseTree;
double dt = 2.3;
for (double maxTime = 7; maxTime < 90; maxTime += dt) {
treeA = callAlgorithm(treeA, maxTime);
dt += 0.9;
}
callAlgorithm(treeA, 90);

which incrementally increases the step size dt. We used maxTime as an upper limit
randomly choosing the the arrival time between maxTime-0.5*dt and maxTime. Only
for maxTime=90 we always took arrivalTime=90. We used parallelization inside
callAlgorithm choosing the best result using all cores of a single NUMA node,
and at the level of the outer loop assigning full NUMA-Nodes to loop executions.

avatar

alessandro.zavoli@uniroma1.it

Dear Wolz,
Your idea seems very intriguing.
Concerning the point "b) Achieve speedups by implementing filters for valid star to star transfers", I would suggest you to check the simple solution we "developed" in Rome, that is essentially based on the solution of a linear impulsive rendzevous problem. Further details are provided in the conference paper.
Error in DV estimate are usually about 1-5 km/s. You may send me an email need further details.
Alessandro Zavoli

avatar

DietmarW

Dear Alessandro,
thanks for your reply,.
will check your paper and contact you via mail in case of questions.

Did some more experiments and noticed the scores above a a bit inflated:
a) Without further optimization the simple method above reaches about score 2800 when started from the NUDT tree
without the Myr=90 nodes and about 1500 when started from the NUDT Mothership/Fast ship root tree.
You need further optimizations as described in the papers from NUDT / ESA to proceed from here.
b) Instead of a fixed arrival time a fixed time of flight (incremented in subsequent applications of the algorithm) can be advantageous.
c) You may increase the number of reached stars (and decrease the dv ratio) by lowering the
time of flight if the dv is low. This may generate a better basis for further optimizations.
d) The algorithm may be further simplified by removing d) to g), the exchange of target stars, specially
if you plan to apply another optimization phase.

avatar

DietmarW

Dear Alessandro,
after checking your conference paper I noticed that our approach is very similar to yours.
You can approximate the non-keplerian multi-impulse spaceship transfer by two impulses and

a) a line
b) a circle
c) an ellipse

We thought although the stars itself travel on circular orbits, transfers can better be approximated using ellipses.
But I agree that probably circular transfers are accurate enough and easier/faster to compute. But thanks to Darios fast
open source Lambert transfer code, elliptical approximations are also quite efficient.
We handle the problem of single impulses exceeding the 175kms limit by adding a penalty value to the sum of the impulses.

Here is the reformulation of the algorithm using maximal time of flight instead of arrival time as parameter:

algoV2 ( maxTOF) =
a) Iterate over stars S0 in treeA with less than 3 outgoing transfers.
b) Randomly choose a star S not in treeA.
If merit(treeA + S) > merit(treeA) - 0.2
and if there is a valid transfer from S0 to S
and if meritDV(treeA + S) > meritDV(treeA) + 0.1 add S to treeA.
c) Repeat a), b) until treeA no longer grows
d) Iterate over stars S added to treeA by a),b),c) via a transfer from star S0
e) Randomly choose a star S2 not in treeA.
If merit(treeA - S + S2) > merit(treeA)
and if there is a valid transfer from S0 to S2.
and if meritDV(treeA - S2 + S0) > meritDV(treeA + S)
then remove S from treeA and add S2 to treeA
f) Repeat d), e) until meritDV(treeA) no longer grows
g) Repeat a), b), c), d), e), f) until merit(treeA) no longer grows

A transfer is valid if with tof (time of flight) = maxTOF and approximated dv < 400 kms.
If dv < 400 kms with tof = maxTOF also try tof = maxTOF * (dv / 400)^0.8 to reduce time of flight.
Adjust tof so that arrival time never exceeds 90 Myr.

You may use a loop to iteratively increase maxTOF like:

for (double maxTOF = 2.3; maxTOF < 60; maxTOF += 0.9)
algoV2 ( maxTOF)

Is there another basic algorithm as simple as this achieving a score around J = 1500?
ESAs concurrent search without refinement (which is quite similar) reaches J = 1177, a separate result for
NUDTs ACO for the CMSTDC problem is not given in their paper, Tsinghuas GA looks more complex
(but is quite successful). Our approach doesn't limit the number of available stars as NUDTs first GA step
does. NUDTs final result suggests this is a good idea. I am not sure about this.
Dietmar

avatar

DietmarW

small correction, should be:
and if meritDV(treeA - S2 + S0) > meritDV(treeA)

Please log in to leave a comment.