[WIN/MAC/LINUX] KSP Trajectory Optimization Tool v1.6.10 [Major LVD Improvements!]

[Arrowstar]

It'll be able to figure out the soonest departure time from Duna to Kerbin, with the mass and fuel available, leaving enough fuel to slow down at Kerbin?

In a manner of speaking, yes. Perhaps not the soonest departure, but definitely the fastest transfer. If you specify propulsion residual constraints (that is, how much prop you have left over), you can force it to keep some fuel in reserve, as well. Is this what you meant?

Update on MA progress. Tonight I have a standalone script running a very basic optimization on a simple Kerbin/Mun transfer. Actually, we can hardly call it an optimization. All I'm doing is asking the optimizer to find is the delta-v of a vector that, in an unconstrained fashion, minimizes mass usage. Without constraints, it should result in a 0 m/s delta-v burn. Still working out quirks in the system, but everything looks good so far!

[Galane]

Without constraints, it should result in a 0 m/s delta-v burn. Still working out quirks in the system, but everything looks good so far!

The only way to not use any fuel, is not to play? (Apologies to "War Games".)

[bk2w]

My "injection burn" do you mean the "insertion burn"?

Yep, I mean insertion burn, or arrival burn.

Do you already have enough information to calculate the orbital velocity of the spacecraft and of the target body at the interception? Then we could calculate the difference between the two and have a rough approximation of what the actual insertion burn would need to be.

-Brian

[Arrowstar]

Yep, I mean insertion burn, or arrival burn.

Do you already have enough information to calculate the orbital velocity of the spacecraft and of the target body at the interception? Then we could calculate the difference between the two and have a rough approximation of what the actual insertion burn would need to be.

-Brian

So yes, that information exists. But honestly, it's not very good at estimating the delta-v needed to insert into orbit, as what it's actually measuring is delta-v needed to stop at the planet, just outside it's SoI. It's how you enter orbit is critical and will dictate the amount of delta-v needed for the mission.

That all said, the porkchop plot can be made to optimize on arrival+departure C3 energy, which is more along the lines of what you're talking about. See the options on the main GUI menu bar for more details. Let me know if you have any questions, I'm having to type this real fast this morning, so not a lot of time for detailed explanation.

[Frederf]

One thing I forsee taking a great deal of manual computation burden off is a wide array of generic events in the mission architect. For example rendezvousing with a probe or similar will have an event-based mass change that isn't maneuver related. Munar landers in an Apollo style profile for example has dead weight added and subtracted in mission. Joining for adding modules of fuel/supplies in orbit for interplanetary travel is another example.

[Arrowstar]

One thing I forsee taking a great deal of manual computation burden off is a wide array of generic events in the mission architect. For example rendezvousing with a probe or similar will have an event-based mass change that isn't maneuver related. Munar landers in an Apollo style profile for example has dead weight added and subtracted in mission. Joining for adding modules of fuel/supplies in orbit for interplanetary travel is another example.

This is very much how things are already working. I only have four different types of events: coasting, dv maneuver, set state, and mass dump, each with their own set of multiple implementations that all work the same way. The last one is what you're talking about: it gives the analyst the ability to add/subtract mass from the current stage. Typically you'd use it when staging or when accounting for contingency prop you might want to take along, but there's no reason why you couldn't enter in negative values to "subtract" and make the s/c heavier. This is allowed.

[Arrowstar]

So good news. Tonight I got the optimizer code mostly working. It's not hooked up to the GUI yet, but I've got it running nicely in an external script. I developed a new objective function that really helped a lot. Instead of minimizing fuel usage, it attempts to minimize the distance to a particular target body. This works great if you seed it with a good initial guess (which will basically be a requirement for Mission Architect). Where do those "initial guesses" come from? Well, luckily, the rest of KSP TOT has an entire suite of analysis tools designed to find optimum maneuvers!

So what I did was find a Kerbin-Duna window using the KSP TOT porkchop plot, plug that burn into Mission Architect, add a coast to Duna SoI, and a circularization burn. Then Mission Architect modified the coast to the burn true anomaly and the departure burn vector and got this:

Look at the final spacecraft state there. I was aiming for a ~100 km altitude circular, equatorial orbit. It did pretty well.

What do you guys think?

[diomedea]

What do you guys think?

That is quite impressive, really good result. Though, I hope that by "minimizing distance to a target body" instead of "minimizing fuel usage", doesn't mean in the end we can't choose the destination orbit radius, nor have the plan cost more fuel than strictly needed.

BTW, I like these updates of how the tool coding proceeds.

Also, what strategy this tool is going to use to achieve a desired orbit inclination? In your example, it looks like the inclination was achieved by means of burning DV while entering the final orbit (step 6). I most often try to set initial periapsis from the transfer orbit so that the inclination with the final orbit is already given. If the desired inclination is not possible from the transfer orbit, I would burn retrograde at periapsis enough to lower eccentricity, but still keeping apoapsis high enough; then change the inclination at apoapsis and circularize at the next periapsis. Those are generally the strategies costing me less fuel when it comes to inclination.

[Arrowstar]

That is quite impressive, really good result. Though, I hope that by "minimizing distance to a target body" instead of "minimizing fuel usage", doesn't mean in the end we can't choose the destination orbit radius, nor have the plan cost more fuel than strictly needed.

You will be able to set a constraint on the minimum/maximum distance to target that the optimizer should hit. The whole optimization process is likely going to be a three part thing the user will have to do: minimize the distance to target unconstrained, just to get in the SoI; minimize distance to target, but constrain the radius; and then minimize fuel usage. The first two are needed to direct the optimizer towards the correct solution. Once you are close, then constrain the optimizer more (with orbital parameters and the like) and tell it to minimize fuel usage. This "walking in" of the solution will likely be necessary for complex missions, and it's also what we do in the "real world".

BTW, I like these updates of how the tool coding proceeds.

Cool, I'll keep doing them.

Also, what strategy this tool is going to use to achieve a desired orbit inclination? In your example, it looks like the inclination was achieved by means of burning DV while entering the final orbit (step 6). I most often try to set initial periapsis from the transfer orbit so that the inclination with the final orbit is already given. If the desired inclination is not possible from the transfer orbit, I would burn retrograde at periapsis enough to lower eccentricity, but still keeping apoapsis high enough; then change the inclination at apoapsis and circularize at the next periapsis. Those are generally the strategies costing me less fuel when it comes to inclination.

The strategy is whatever you design it to be. In my picture, the inclination is actually targeted all the way from Kerbin. I know it doesn't look like it, but the final maneuver is really just a circularization burn (set SMA = desired, ecc = 0). No inclination was changed in the Duna SoI at all.

If you want to change the inclination more, you can set constraints on the final orbit to have a high apogee and low perigee. Then go ahead and place a maneuver at apogee to do the inclination change, and add it to the things that the optimizer solves for. Should work out well enough.

Does that answer your questions?

[diomedea]

Does that answer your questions?

Yes, perfectly. And I really like how this tool will work.

[Kurtvw]

A quick question, Arrowstar..

Right now I'm using version 11.2 (if you have a more recent one, please do tell), and I'm noticing that a lot of times the orbit it plots in KSP is not what it looks like in the KSPTOT. And I'm confused about the selection for use Mean Anom, and Epoch, Could you explain why I might check or uncheck that? Under what circumstances there would be an advantage?

Anyhow, as it relates to the variations, Is it because it often puts the maneuver marker days in advance of the current time? Or should the transfer orbit look exactly as shown? It seems to me that since I'm having it import direct from KSP and output direct to KSP I should be getting exact results. I'm often able to tweak the manuver to get it right, but sometimes its off by quite a long distance, in one case from Duna to Kerbin it shot me into a much higher Apoapsis out near Jool, and with periapsis still near Duna.

[Arrowstar]

Kurt, I'm in the middle of running to work, and your question has a bit of a long answer, so I'll get to it tonight.

Anyway, quick update on the Mission Architect development. Yesterday I finished up the major part of the Optimizer GUI and integrated it with the rest of Mission Architect. Using it, I was able to plan a mission from low Kerbin orbit to low Duna orbit, directly inserting into a 100x100x3 deg inclination orbit using only two burns. This is similar to what I showed before, the difference being that the optimizer code is now running in MA and not in a stand alone script. Anyway, the take away here is that Mission Architect works!

Unfortunately, it works kinda slowly. The various optimizer runs take about 4 minutes for ten iterations of the optimizer, and you could see anywhere from 10-50 iterations per optimization run. Given that, yesterday I spent a long time optimizing code and pursuing means to get things running faster. Right now I'm vectorizing the code that coverts between orbital elements position/velocity. This means that, ultimately, I will be able to remove the for loop I've got in the main propagator ("go to this time step, then this, then this") and just pass in a vector of time steps in one command and I'll get out all the orbits in one command. This should greatly increase run time speed. Other ideas I'm pursuing are parallelization of the optimizer code (very easy as MATLAB can do this for you), and experiments show a 2-fold decrease in run time when computing objection function gradients in parallel; and compiling some basic MATLAB code into MEX files that execute at about 100 times the speed of the function they replace. Unfortunately, you can only compile a subset of MATLAB functions into MEX files, so you have to pick what you pull out for compilation carefully.

My goal is to get optimization down to 3 seconds per iteration on average. Right now, best I've ever seen is 6.4 seconds per iteration, but that's without massive parallelization. I think once I couple those two with whatever compiling I can pull off, I will make it, easy.

In any event, progress has been made and things are happening, but the past few days have been more about putting the pieces together and making sure they work well than developing new features, hence there being nothing to share.

Oh, nice side effect of all this optimization: since the code I'm working on is low level stuff used everywhere in TOT, all tools/functions should see an increase in speed. Yay!

[diomedea]

Unfortunately, it works kinda slowly. The various optimizer runs take about 4 minutes for ten iterations of the optimizer, and you could see anywhere from 10-50 iterations per optimization run. ....

My goal is to get optimization down to 3 seconds per iteration on average. Right now, best I've ever seen is 6.4 seconds per iteration, but that's without massive parallelization. I think once I couple those two with whatever compiling I can pull off, I will make it, easy.

Happy to know about your progress, this is fast becoming a usable feature (and joy, everything would be run faster in TOT after compiling and parallel optimizer code are done). Actually, 24 seconds for each iteration don't seem too much, believe in reality space mission parameters took much longer to be computed.

[Kurtvw]

Kurt, I'm in the middle of running to work, and your question has a bit of a long answer, so I'll get to it tonight.

Cool, looking forward to it, thanks!

[Galane]

NASA or some corporate space company might come calling. Have you tried using real solar system orbit info instead of KSP data? Having a planner like this that can run on cheap PC systems would save a lot of money.

[Arrowstar]

A quick question, Arrowstar..

Right now I'm using version 11.2 (if you have a more recent one, please do tell), and I'm noticing that a lot of times the orbit it plots in KSP is not what it looks like in the KSPTOT. And I'm confused about the selection for use Mean Anom, and Epoch, Could you explain why I might check or uncheck that? Under what circumstances there would be an advantage?

Anyhow, as it relates to the variations, Is it because it often puts the maneuver marker days in advance of the current time? Or should the transfer orbit look exactly as shown? It seems to me that since I'm having it import direct from KSP and output direct to KSP I should be getting exact results. I'm often able to tweak the manuver to get it right, but sometimes its off by quite a long distance, in one case from Duna to Kerbin it shot me into a much higher Apoapsis out near Jool, and with periapsis still near Duna.

Okay, so, KSP and KSP TOT both work off two fundamental principles of motion: the two body gravity assumption and the patched conics approximation. The former says that only one planet/moon can affect your spacecraft at a time, and the latter dictates how you move between the influence of gravity sources. So far so good. Where KSP TOT differs from KSP is that the I'm using a patched conics approximation in which the sphere of influence has radius of zero. That is, the SoI size is always assumed to be small as compared to the next largest SoI up the celestial body hierarchy. In the real world, this is actually an okay assumption. But in KSP, where the game is scaled, some of the differences do start to show through, as you've found.

So what about the solutions KSP TOT gives you? They're excellent for the zero-sized SoI problem. For the KSP simulation, the non-zero SoI size problem, they are good approximations. However, as you've found, you will have to adjust the solution to find the real solution. It's not too hard, so I'm not too concerned with people needing to do this.

Luckily, Mission Architect does not have this same zero-sized SoI limitation: I'm building it from the ground up to act just like KSP. So far it's worked well, and the solutions you get from the maneuver planning codes in KSP TOT will make good first guesses for maneuvers in Mission Architect, just like they are good first guesses in KSP proper.

Hope that helps.

On that front, I didn't get all that much accomplished today in MA. I had hoped to vectorize a lot of my math... and I did. But it turns out that the overhead from doing that was actually worse than just running the for-loops I was avoiding with compiled code. Also, the resulting vectorized code was horrible. Though it worked, it was not elegant in any way, shape, or form. I'm happy that I'm ultimately abandoning that approach, because it wasn't pretty to work with or maintain.

So I'm stuck at about 6.2 seconds per optimization iteration, and the average mission optimization seems to be about 15-20 iterations. Call it about two minutes per optimization. This'll have to do for now, though there is some additional disk read/write that I'm going to try to eliminate in the future, and that will help some.

Tomorrow's tasks are to fix up a few bugs with the Mission Optimizer window and get started on the Optimizer display. This latter feature will show, in real time, the result of the optimization and will hopefully let users cancel it cleanly if needed.

Hope that sounds good.

[tavert]

So how much of that time per iteration is computing the objective function and constraints, versus the gradients and Jacobian? Are you relying on Matlab to do finite differences for you, or can you compute gradients analytically? Are the optimization variables the orbital elements and maneuver components for each phase?

If vectorizing is adding overhead, either you're doing it wrong or your problems just aren't very big. For loops should be avoided like the plague in Matlab for sizes beyond about 5-10.

[Kurtvw]

Okay, so, KSP and KSP TOT both work off two fundamental principles of motion: the two body gravity assumption and the patched conics approximation. The former says that only one planet/moon can affect your spacecraft at a time, and the latter dictates how you move between the influence of gravity sources. So far so good. Where KSP TOT differs from KSP is that the I'm using a patched conics approximation in which the sphere of influence has radius of zero. That is, the SoI size is always assumed to be small as compared to the next largest SoI up the celestial body hierarchy. In the real world, this is actually an okay assumption. But in KSP, where the game is scaled, some of the differences do start to show through, as you've found.

So what about the solutions KSP TOT gives you? They're excellent for the zero-sized SoI problem. For the KSP simulation, the non-zero SoI size problem, they are good approximations. However, as you've found, you will have to adjust the solution to find the real solution. It's not too hard, so I'm not too concerned with people needing to do this.

thanks for taking the time to explain... I'd actually figured this was probably the case, but its good to have you clarify. I've had some of the best luck with KSP TOT for getting me ballpark dialed in on my manuver (as compared with other similar mods). But I wasn't sure if the errors were real or not. Sounds like its working as best it can and as long as it dials me into orbits I can afford, it's all good.

For those you you reading along though, I'll tell you there is more profit in adjusting the maneuver time than there is in adjusting the maneuver velocities...

[PlonioFludrasco]

Downloading!

I want to see how much can help me with interplanetary transfers.

[Arrowstar]

So how much of that time per iteration is computing the objective function and constraints, versus the gradients and Jacobian? Are you relying on Matlab to do finite differences for you, or can you compute gradients analytically? Are the optimization variables the orbital elements and maneuver components for each phase?

If vectorizing is adding overhead, either you're doing it wrong or your problems just aren't very big. For loops should be avoided like the plague in Matlab for sizes beyond about 5-10.

Would need to look at the time break down, but MATLAB is doing the gradients in parallel. MATLAB is doing finite differencing; there is no analytical gradient for this problem. Optimization variables for this run is a true anomaly for departure burn and the right ascension, declination, and magnitude of the burn (better than three rectilinear components for optimization).

I agree that I probably just screwed it up somewhere. I vectorized the functions that convert to and from Keplerian orbital elements to position/velocity vectors. These are fairly complex functions with a fair bit of logic in them, plenty of room for error. If you'd like to take a look, shoot me a PM and I'll send you what I've got.

[Arrowstar]

Downloading!

I want to see how much can help me with interplanetary transfers.

Thanks! Let me know if I can help with any questions.

[Arrowstar]

I made some good progress today on the Mission Architect tool. I managed to squash a (serious) bug that was preventing some SoI transitions to be found. I stumbled across it while planning a direct Kerbin-Ike misson. In any event, everything works great now. I also have plans for additional speed improvements across the MA application in general. It involves a bit of rework with the way data is stored, but the code should be much faster afterwards.

My goal for tomorrow is to get this speed improvement implemented (the current data storage technique is pretty slow guys). After that, I'll get the GUI for the Optimizer progress page (let's you watch the mission optimizer work) going. Hopefully will finish this last item this weekend. Might be ready for a test pre-release next week.

Here's a nice picture of my trip to Ike:

[diomedea]

... Where KSP TOT differs from KSP is that the I'm using a patched conics approximation in which the sphere of influence has radius of zero. That is, the SoI size is always assumed to be small as compared to the next largest SoI up the celestial body hierarchy. ...

... I managed to squash a (serious) bug that was preventing some SoI transitions to be found. ...

Just out of curiosity, are the two facts with SoI radius related? I got some doubts () while reading the first sentence, that some issues may come from that assumption. While I am certain the correct SoI is used with the main bodies at the extremes of a transfer, eventual other bodies along the trajectory, whose SoI is intersected, would not be considered having influence. Of course that would prevent accidental slingshots to be found and computed (I believe planned slingshot are, by setting the relevant body in both the incoming and outgoing parts of the slingshot trajectory).

[Arrowstar]

Just out of curiosity, are the two facts with SoI radius related? I got some doubts () while reading the first sentence, that some issues may come from that assumption. While I am certain the correct SoI is used with the main bodies at the extremes of a transfer, eventual other bodies along the trajectory, whose SoI is intersected, would not be considered having influence. Of course that would prevent accidental slingshots to be found and computed (I believe planned slingshot are, by setting the relevant body in both the incoming and outgoing parts of the slingshot trajectory).

Oh, apologies for the confusion. No, Mission Architect uses the same SoI radii that KSP uses. There was a bug in the way the intersects were being calculated (particularly when the s/c orbit was hyperbolic), and I fixed that. It's the rest of KSPTOT that uses the infinitesimal SoI radius assumption.

I should note, for the record, that this idea of a zero-sized SoI is not my own idea. It's how orbital mechanics is taught in classrooms, and for good reason. Dealing with spheres of influence is a royal pain in the neck. Not worrying about them simplifies your problem, and the math/logic behind your problem, considerably.

[diomedea]

Oh, apologies for the confusion. No, Mission Architect uses the same SoI radii that KSP uses. There was a bug in the way the intersects were being calculated (particularly when the s/c orbit was hyperbolic), and I fixed that. It's the rest of KSPTOT that uses the infinitesimal SoI radius assumption.

I should note, for the record, that this idea of a zero-sized SoI is not my own idea. It's how orbital mechanics is taught in classrooms, and for good reason. Dealing with spheres of influence is a royal pain in the neck. Not worrying about them simplifies your problem, and the math/logic behind your problem, considerably.

Yep, thanks for explaining that. Very interesting as always.

About SoI radius, agreed. I know they are just an assumption, if true multi-body gravitational fields computing was feasible, we would treat SoI just as an indicator of the relative gravitation force. That was the approach with the Orbiter Space Sim, at least that had 3-body computing and SoI was given with a percentage of the relative strength. With the limit of 2-body computing that KSP has, a SoI is really an artificial boundary, suddenly the gravity a craft is subject to wholly changes from one to another center of mass. But then, you mean KSPTOT, instead of using SoI to switch to a different center of gravity, is using true newtonian gravity with all the centers of mass along a trajectory?