Optimal Rocket Generator

[MathigNihilcehk]

Quick background: I am a physics major, and math enthusiast. I found a web app on the forums (http://forum.kerbalspaceprogram.com/threads/65011-WEB-0-25-KSP-Optimal-Rocket-Calculator-v1-15) that generates rocket designs. However, it requires enormous amounts of processor power and seems to miss some ideal solutions for generating rockets. (I tested 4500 2-stage, and 2 2250 stages (mass of 1st stage as payload of 2nd stage) and got different results) So, I am going to do an analysis of the problem "How do I create a rocket generator". I believe my solution may be significantly superior to the existing app's solution(I love the app, but think I may have found a better solution), and I wanted to know what the community thought about it. My analysis will consider three engine types, and one type of fuel, but simple expansion can adapt to any number of engine types. Spoilers hide the derivation, and variable names.

dv= actual change in velocity

g = force of gravity on kerbin surface

ISP_i = ISP value of engine i

ISP = Overall ISP value

P = payload mass

E_i = engine i's mass(with coupler/branches factored in for simplicity)

E = total mass for engines

F = total mass of fuel

C = total mass of empty fuel canisters

f = mass of smallest unit of fuel

c = mass of smallest unit of empty fuel canister

T_i = Thrust of engine i

T = total engine thrust

TWR = actual thrust per weight ratio

M = mass of entire rocket with fuel

m = mass of entire rocket without fuel

k = number of fuel canisters

x,y,z = number of engines x,y, or z respectively

_x,_y,_z = indicating "of engine x, y, or z" respectively

L = some finite lower limit for P/M we know ahead of time

D = desired change in velocity

TPR = desired thrust to weight ratio

x*E_x+y*E_y+z*E_z = E

x*T_x+y*T_y+z*T_z = T

T/((x*T_x/ISP_x)+(y*T_y/ISP_y)+(z*T_z/ISP_z)) = ISP

dv < g*ISP*ln(M/m)

T/(g*M) = TWR

k*f=F

k*c=C

M=P+E+C+F

m=P+E+C

L < P/M (defined such that TPR = TWR is reasonable)

TPR < TWR

D < dv

In this system, I want to generate every reasonable "guess" for an engine configuration, and then filter out every "guess" that doesn't satisfy our desired thrust to weight and change in velocity conditions. I also want to sort for lowest mass, part count, and cost, so every "guess" whose mass, part count, and cost are all higher than another engine should be eliminated as quickly as possible. This is what our lower limit is for. If some engine's payload/mass is lower than our limit, we can avoid guessing it. This turns out to be the case for all engine configurations with a specific engine count above a certain value. We then want to check against some equation that satisfies both TPR < TWR and D < dv. If an equation satisfies both of these, then we can finally check it's mass, part count, and cost to determine the best one.

M < P/L

T/(g*TWR) = M

T/(g*TWR) < P/L

T < g*TWR*P/L

T < g*TPR*P/L (because we picked a low enough L)

x*T_x+y*T_y+z*T_z < g*TPR*P/L

0 <= x < g*TPR*P/(L*T_x)

0 <= y < g*TPR*P/(L*T_y)

0 <= z < g*TPR*P/(L*T_z)

Since x, y, and z are all integers, we now have a limited number of guesses to check. This number is x*y*z or...

(g*TPR*P/L)^3*(1/T_x+1/T_y+1/T_z)

So the number of guesses increases exponentially as the payload, desired thrust to weight ratio, and number of engines increases and as thee limit decreases.

D < dv

D < g*ISP*ln(M/m)

D < g*ISP*ln((P+E+C+F)/(P+E+C))

D < g*ISP*ln((P+E+k*c+k*f)/(P+E+k*c))

D/(g*ISP) < ln((P+E+k*c+k*f)/(P+E+k*c))

e^(D/(g*ISP)) < (P+E+k*c+k*f)/(P+E+k*c)

e^(D/(g*ISP))*(P+E+k*c) < (P+E+k*c+k*f)

(P+E)*e^(D/(g*ISP))+k*c*e^(D/(g*ISP)) < (P+E+k*c+k*f)

(P+E)*e^(D/(g*ISP)) < (P+E+k*c+k*f) - k*c*e^(D/(g*ISP))

(P+E)*e^(D/(g*ISP))-(P+E) < k*(c+f) - k*c*e^(D/(g*ISP))

(P+E)*e^(D/(g*ISP))-(P+E) < k*((c+f) - c*e^(D/(g*ISP)))

(P+E)*(e^(D/(g*ISP))-1) < k*((c+f) - c*e^(D/(g*ISP)))

(P+E)*(e^(D/(g*ISP))-1)/((c+f) - c*e^(D/(g*ISP))) < k

TPR < TWR

TPR < T/(g*M)

TPR < T/(g*(P+E+C+F))

TPR < T/(g*(P+E+k*(c+f)))

(g*(P+E+k*(c+f))) < T/TPR

(P+E)+k*(c+f) < T/(TPR*g)

k*(c+f) < (T/(TPR*g)-(P+E))

k < (T/(TPR*g)-(P+E))/(c+f)

(P+E)*(e^(D/(g*ISP))-1)/((c+f) - c*e^(D/(g*ISP))) < k < (T/(TPR*g)-(P+E))/(c+f)

(P+E)*(e^(D/(g*ISP))-1)/((c+f) - c*e^(D/(g*ISP))) < (T/(TPR*g)-(P+E))/(c+f)

-((c+f)-(c+f)*e^(D/(g*ISP)))/((c+f) - c*e^(D/(g*ISP))) < (T/(TPR*g)-(P+E))/(P+E)

-((c+f)-c*e^(D/(g*ISP))-f*e^(D/(g*ISP)))/((c+f) - c*e^(D/(g*ISP))) < (T/(TPR*g)-(P+E))/(P+E)

-1-(-f*e^(D/(g*ISP)))/((c+f) - c*e^(D/(g*ISP))) < (T/(TPR*g)-(P+E))/(P+E)

(f*e^(D/(g*ISP)))/((c+f) - c*e^(D/(g*ISP))) < (T/(TPR*g)-(P+E))/(P+E)+1

(f*e^(D/(g*ISP)))/((c+f) - c*e^(D/(g*ISP))) < (T/(TPR*g)-(P+E)+(P+E))/(P+E)

(f*e^(D/(g*ISP)))/((c+f) - c*e^(D/(g*ISP))) < (T/(TPR*g))/(P+E)

(f*e^(D/(g*ISP)))/((c+f) - c*e^(D/(g*ISP))) < T/(TPR*g*(P+E))

f/((c+f)*e^(-D/(g*ISP))-c)<T/(TPR*g*(P+E))

We can sort part count by adding up the parts, costs by adding up each part multiplied by it's cost, and mass similarly to cost. I will solve for mass, and skip the others for brevity. Since we want low mass, part count, and cost, we will want k to be minimal for each engine configuration. Thus, we can round up the k value for our k > ... expression.

(P+E)*(e^(D/(g*ISP))-1)/((c+f) - c*e^(D/(g*ISP))) < k

k optimal = roundup((P+E)*(e^(D/(g*ISP))-1)/((c+f) - c*e^(D/(g*ISP))))

M=P+E+C+F

M=P+E+k*(c+f)

M=P+E+roundup((P+E)*(e^(D/(g*ISP))-1)/((c+f) - c*e^(D/(g*ISP))))*(c+f)

So, assume we now have 2 stages. By guessing, dividing the delta V equally between the stages will give an optimal rocket. Then, we will calculate the first stage and plug in it's mass into our payload for the second stage. Since we are only calculating 1 equation for every set of engine configurations, and one more equation for each valid configuration, we can save time on displaying the actual rocket configurations until the scan is complete. Once complete, we can calculate the delta V, mass, etc. for the top few operations, as desired.

Final Solution:

Consider every possible set of x, y, and z(except 0,0,0) that satisfy

0 <= x < g*TPR*P/(L*T_x)

0 <= y < g*TPR*P/(L*T_y)

0 <= z < g*TPR*P/(L*T_z)

and test if they satisfy f/((c+f)*e^(-D/(g*ISP))-c)<T/(TPR*g*(P+E)). If so, sort by M=P+E+roundup((P+E)*(e^(D/(g*ISP))-1)/((c+f) - c*e^(D/(g*ISP))))*(c+f) (for mass, cost and part count can be done similarly) and display the final solutions with the values for x, y, and z. Optionally calculate change in velocity, mass, and thrust to weight ratio and display for final solutions.

Conclusion: While I have yet to calculate the time per guess, I am assuming this would be a better method for generating rockets. At the very least it is one to consider, because the calculation time is not exponentially related to the stage count, but instead is proportional to it.

Questions: How do I find the time for testing each guess? Are there any errors in my calculations or reasoning? Did you enjoy reading this? Should I continue to pursue developing this method into a web-app or a download-able app? Should I move this to a new thread or location? Any other thoughts?

Thanks for reading!

[Pds314]

I guess I could probably write some simple mock-up Java code to do it. I'm not sure I wanna try to maintain such an app, especially because manually entering in the Isps, thrusts, and masses of all those rockets, and the masses and sizes of all those tanks sounds difficult.

The main issue with your method is I have no clue what the maximal time complexity would be, but it looks pretty nasty if some of the numbers get very big. Is this sorting for each instance or just at the end, because if it is, remember that sorts are O(n*log(n)) complexity, at best.

I do agree that the Optimal rocket calculator we have could use some work. Sometimes I've had it run for half an hour and find something not even as good as I could make up out of thin air.

[MathigNihilcehk]

The main issue with your method is I have no clue what the maximal time complexity would be, but it looks pretty nasty if some of the numbers get very big. Is this sorting for each instance or just at the end, because if it is, remember that sorts are O(n*log(n)) complexity, at best.

It would sort only rockets which meet the dV and TWR constraints. However, like the app, I'd imagine limiting it to the top 20 or 10 working rockets would quicken the sorting process.

A bigger concern might be the guess range as your number of rocket engines increases. The guess range I have is rather gross. I'd imagine some sort of lower bound could be found(with another "impossible" upper bound, maybe?), and first order corrections on the upper bound.

[madlemur]

What about thrust plates and using multiple small engines with larger tanks? That really opens up some new permutations...

[MathigNihilcehk]

What about thrust plates and using multiple small engines with larger tanks? That really opens up some new permutations...

Thrust plates are methods for stability, not for increasing thrust or change in velocity. This system would include any combination of allowed engines and tanks, but it would not handle large numbers of allowed engines easily.

Edited November 12, 2014 by MathigNihilcehk

[Dilir]

I am working on something with matlab. Here is how i proceeded:

- Build a 1 stage evaluation function. Imputs : minimum TWR (and later some engine size limitation). Output: optimization variable (IE mass or funds (currently mass), optimal engine as function of (dv, payload).

The function evaluates the best couple of "engine + fuel " that match the required dv and twr.

- Set global criteria for mission : total dv, payload mass, specific requirement (dead weight winglets for the first 2000m/s, twr >1.2 at launch, etc).

- Create a random set of rocket (a rocket is a sucession of dvi, sum(dvi)=total dv). Compute with previous function total mass

- Use genetic algorythm to find near optimal values.

I am testing this in a new career. Works pretty well so far (i can save a few kg but that's due to algo rounding). I have done mostly 2-stages rockets for now, but the algorythm was designed for more. Right now, with a very coarse time consuming programation, i have rougthly 1min computation time. (2min if i add all the engines from KW, Novapunch, AIES)

Concerning thrust plats and multiple engine, i guess that if you want to incorporate them, you should just define that as a new engine. Oh, you can also eliminate some dominated engine (for example, LV-T45 is dominated by LV-T30 if you don't use gimbaling).

Edited November 12, 2014 by Dilir

[MathigNihilcehk]

- Create a random set of rocket (a rocket is a sucession of dvi, sum(dvi)=total dv). Compute with previous function total mass

- Use genetic algorythm to find near optimal values.

LOL... with those two lines you summarized your entire attempt at the solution. Care to elaborate a bit?

[Dilir]

Genetic, not generic :-).

I am neither a programmer nor a specialist in optimization problem (my field is material science), so don't be too judging.

The idea is to create a random dv repartition for a population of rockets. They would be the parents. Then with the previous function you compute what is the mass of each of them. You then use genetic algorithm techniques (selection, crossing, mutation) to generate a child population. After a given number of generation, you look for the best individual in your population.

Oh, i also did an exhaustive search algorithm for 2 stages rocket, and the two give matching result. If you only have 2 or 3 stage, i would however suggest exhaustive over genetics, which is more suited to 3+ stages rockets.

Edited November 12, 2014 by Dilir

[madlemur]

Genetic, not generic :-).

I am neither a programmer nor a specialist in optimization problem (my field is material science), so don't be too judging.

The idea is to create a random dv repartition for a population of rockets. They would be the parents. Then with the previous function you compute what is the mass of each of them. You then use genetic algorithm techniques (selection, crossing, mutation) to generate a child population. After a given number of generation, you look for the best individual in your population.

Heh... In Computer Science, genetic algorithms are self-rewriting algorithms, or more generally, the algorithms mutate, not the input/output (well, not directly). What you're doing is applying genetic theory in an iterative optimization algorithm.

Interesting idea, though. Are you determining some ideal "child" engine specs, then finding the closest match in the set of available engines?

[Dilir]

Well, we are talking optimization genetic algorythm, i don't know what computer scientist are calling genetic ^^. I can't take credit for the idea, it's well documented.

I am not determining ideal child specs. I use my first function (only once per differents twr required, that's the trick) to generate two matrix. First give mass as a function of delta v and payload for single stage rocket, second give related optimal engine from those available.

Then, a rocket is just defined by how you break your total DV. Each subset engine can be easily extracted from the matrix previously computed. This is still under testing and improvement and I will give more precise info when it will be a bit more polished.

Edited November 12, 2014 by Dilir

[MathigNihilcehk]

Well, we are talking optimization genetic algorythm, i don't know what computer scientist are calling genetic ^^. I can't take credit for the idea, it's well documented.

I am not determining ideal child specs. I use my first function (only once per differents twr required, that's the trick) to generate two matrix. First give mass as a function of delta v and payload for single stage rocket, second give related optimal engine from those available.

Then, a rocket is just defined by how you break your total DV. Each subset engine can be easily extracted from the matrix previously computed. This is still under testing and improvement and I will give more precise info when it will be a bit more polished.

Still having trouble figuring out what you are doing... So, you generate a matrix that will look like

[table=width: 500, class: grid]

[tr]

[td]m(dV,P)_x_1y_1z_1[/td]

[td]x_1[/td]

[td]y_1[/td]

[td]z_1[/td]

[/tr]

[tr]

[td]m(dV,P)_x_2y_2z_2[/td]

[td]x_2[/td]

[td]y_2[/td]

[td]z_2[/td]

[/tr]

[tr]

[td]m(dV,P)_x_iy_iz_i[/td]

[td]x_i[/td]

[td]y_i[/td]

[td]z_i[/td]

[/tr]

[/table]

Then you search for the minimum mass given a certain P and dV and display the appropriate x, y, and z?

On another note entirely, I found a way to optimize my guesses. I just plug in my limit condition into a for-loop to scan for valid guesses, then immediately test the dv and TWR followed by comparing with the optimal set and resorting it, if needed.

And... since someone replied fairly quickly, I'll set up a working model in Matlab, before transporting to C# (I'm thinking Unity for GUI would work best, unless anyone has a better idea). After-all, who can say what the best model is, until the model is put to the test.

Edited November 12, 2014 by MathigNihilcehk

[Dilir]

Ok, here is what i do

Function 1 (1 stage optimization)

Imputs : required TWR, required size

Harcoded : all engine specs (for now, i only use vacuum isp).

Code

Step 1: discretize dv and payload to n and m values

Step 2: create two n*m matrix. First will contain best engine for each (dv,m) couple, second required fuel for that engine.

Step 3: for each (dv,m), for each engine, compute the required mass to get dv. Store best (engine, mass) into dv,m point of storages matrix.

Retrun the two n*m matrix.

Obviously, this function is quite time consuming. But, as we hard store the result for a large number of dv and mass, it only need to be run once per required TWR in rocket design.

Function 2: main algo

Step 1: create N rockets (a rocket is a partition of dV).

Step 2: evalutate mass of rockets using function 1.

Step 3: select (with mass), cross and mutate the rockets. This is the genetic part. The idea is to use "good' parents to produce next generation. Good but not necessarely best allows better coverage of the optimization space and to avoid local minimas.

Step 4: iterate until convergence.

Step 5: keep best individual. Dv of each stage is given by definition of my rocket, corresponding engines are computed using function 1.

I am going to bed now, but could discuss that furthermore tomorrow.

Edited November 12, 2014 by Dilir

[madlemur]

OK... Tell me more about Function 2, Step 3... How are you crossing and mutating the rockets? What variables (chromosomes) are you using?

[Dilir]

You got the tricky part right. I am really open to new ideas here, as it's my first go at theses algos.

Mutating is for most of the case transfering some dv from one stage to the next or previous one. Sometimes, it's adding or removing an engine. Crossing is chosing a cutoff delta-v and take the upper part of rocket 1 and lower part of rocket 2.

I got the idea of using these algo from 1 phd and 1 paper found here:

https://etd.auburn.edu/bitstream/handle/10415/837/BAYLEY_DOUGLAS_5.pdf?sequence=1

and here

http://strategic.mit.edu/spacelogistics/pdf/AIAA-2006-1720-231.pdf

And now i'm really going to sleep!

[MathigNihilcehk]

Regarding the Genetic Algorithm paper(I'll have to read more into it, in the future, it is quite interesting), I've learned that it basically takes a number of random valid inputs, and then breeds them together and checks the offspring for better or worse engine design. It takes the best sets and continually breeds them until one solution is found. However, this solution is not guaranteed to be the global maximum or minimum as stated in the paper "However, finding this global optimum is not guaranteed." page 11, paragraph 2. IE: some rocket components could be lost for reasons completely unrelated to their value (ie, the rocket they were in failed as a whole). This is avoided if a large enough sample size is used, but the larger the sample size, the more generations will need to be checked, and computational time is exponentially related to sample size. As the second paper explains, the optimization is partly random, as in page 9 paragraph 2 "This is a result of the randomness inherent in a heuristic optimization algorithm, and suggests that more computation is necessary to give confidence with the results."

While this may lead to an optimization function that generates good rockets that qualify our constraints in a short period of time, it may either miss better rockets, or eat up more computational time than desired. In contrast, my method takes more of a thorough approach and scans every rocket within a range of valid rockets. A finite range can be picked to include the most optimal rocket, and thus the best rocket can be found given enough time.

[Dilir]

The global idea is good.

However, keeping only the best set for offspring, while it allows faster convergence, often causes to fal into a local minimal. By keeping some "less good" individual, you ensure better genetics diversity at the price of computation time.

I am not sure of the complexity of my algo. It's roughly number of individuals * number of generation to convergence, but i don't know how the latter relates to the former.

I agree with you that for high complexity (3+ stages) rocket, if you limit the numer of generation, you might only get "goods rockets" and not the absolute minima.

This is a tradoff, because for n stage, exhaustive search is, assuming you divide your rocket in 1000 dv units, (n-1) among 1000 which is roughly 1000^(n-1)/(n-1)!

Anyway, genetic search was something fun i wanted to try out (because i never used it before) and seemed to be interesting for the problem i am trying to adress. I do not say it is the best solution, and I would be happy to discuss with you about other algos.