Kerbal Space Program Trajectory Optimization Tool

[Arrowstar]

Hi everyone!

Those of you from Orbiter-Forum may recognize me as the author of the Trajectory Optimization Tool (TOT), a software application designed to make finding optimal interplanetary trajectories in the Earth's solar system easy. Given that I've taken TOT as far as I could for Orbiter, I've decided that I'd like to do the same for Kerbal Space Program. The aim of this software tool, then, is to provide the KSP community with an easy-to-use application that can find optimal arbitrary trajectories to and from any body in the KSP solar system.

How does this differ from the other "orbit calculator" tools that are out there, you ask? It's really quite straight forward. Those only compute particular types of orbits, such as Hohmann transfer orbits, Bi-elliptical transfer orbits, etc. In doing so, these tools make a number of important assumptions about the layout of the solar system and the trajectory that you, as the user, may want to take. The most important underlying assumption of these programs is is this: that the lowest energy transfer is usually the one with the lowest delta-V. However, in real life, this is usually quite wrong, and even simple Earth-Mars trajectories typically have transfer angles less than 180 degrees (Hohmann). On the other hand, KSP TOT uses a sophisticated algorithm known as a Lambert solver to compute two-body trajectories between any two planets/moons/etc. This algorithm will ultimately be passed to an optimizer, which will find the optimal trajectory between where you are and where you want to go. In TOT, I use a genetic algorithm for this work and I'm heavily leaning towards that again here in KSP TOT.

KSP TOT is currently being written in Java. To demonstrate that this isn't vaporware, I'd like to show you how my tool compares to analysis that JPL did for the 2005 Earth-Mars transfer. Their "porkchop plot" (a graph that shows how much energy is required to depart Earth and arrive at Mars) is shown here (credit: Wikipedia):

The minimum C3 energy is about 16 km^2/sec^2.

Now, consider the same analysis I've done with KSP TOT. My version of the porkchop plot is show here:

As you can see, they are basically identical. I use this to validate the underlying transfer orbit analysis software that I've written for KSP TOT. From here on out, it's really just a matter of passing that algorithm to an optimizer, building a GUI, and finding out what you folks, the users, want from such a tool. In that case, I urge anyone with thoughtful suggestions or questions to post here and I'll try to get back to you.

So as I said, comments, questions, and concerns are more than welcome. Thanks everyone, and happy orbiting!

Edited August 11, 2012 by Arrowstar

[togfox]

Nice. Yet another realism tool. I'll watch this thread closely.

[pina_coladas]

Very cool and just in time for the expanded solar system in 0.17! I'm curious about the genetic algorithm though. How long did it take to compute that earth-mars transfer in your graph? Can a typical desktop computer spit these things out relatively quickly or do they have to chug along for a bit? Do they use genetic algorithms for this stuff at JPL too?

[silent_prtoagonist]

I considered doing something like this for my final project in the optimization course I took last spring (although I ended up doing a different project); I'll be very interested to follow your development.

I'm also curious about the choice of a genetic algorithm. It seems like this wouldn't be a difficult problem for the more efficient algorithms, as long as you don't mind loosing the capacity to find multiple minima...

[Arrowstar]

For simple trajectories, a genetic algorithm is not efficient. In that, both of you are correct. However, consider the case where you are trying to find optimal departure and arrival times for four or five different bodies on an interplanetary tour. A genetic algorithm works quite well here because it searches a large portion of the design space (which, for this example, is very large) in parallel.

As for the question about computing speed, it is "fast enough." Yes, a solution will take a minute or two to converge in all likelihood. In the TOT for Orbiter, I wrote my code in MATLAB and typically was able to find trajectories in under 5 minutes. The more complicated the trajectory (or, the more design variables) and the bigger the population you use to search the design space, the slower the computations will be. I'm really not too concerned about speed, though. Prior experience has shown that it will be fine in most cases.

Also, I should point out that the graph that I showed up there is just a simple search across the design space, picking N departure times and M arrival times. I just evaluated the C3 energy cost for each of those points to generate the contour. In general, the genetic algorithm would not have to do this, and will be far more efficient... Pina, it took about 20 seconds to generate the graph in this way.

Do they use GAs at JPL? Honestly, I don't know. I know that a number of universities have used GAs for advanced trajectory optimization work and papers have been published, some of which I have read. It seems like a promising field of study.

---------------

Anyway, an update: yesterday I did some GUI work on the Flight Plan designer and today I'm going to be working on the related computations. As I've said, I've already done a bunch of this before with Orbiter TOT, so it shouldn't be too terrible.

[TheCardinal]

Beautiful plots, Arrowstar, if only i knew how to read them (or use them). Could you explain what kind of information is in them and how someone can use them?

[Arrowstar]

Sure. I'm just going to discuss mine, since the JPL plot is a bit more advanced and shows more information. C3 energy is the term we use to describe how much kinetic energy the spacecraft must provide to reach a destination in space beyond that required to leave its current gravity well. In my example, it's the amount of kinetic energy needed to get to Mars from Earth. We use this as a metric because presumably it takes the same amount of kinetic energy to get up to escape speed regardless of the direction in which you apply it to leave. (Keep in mind that this assumes that Earth and its gravity well is infinitely small and that the spacecraft is in solar orbit at the same place the Earth is.)

The color bar on the right of the plot shows which contours correspond to higher or lower C3 energy. The bluer you get, the less energy needed to get to Mars. The redder you get, the more energy needed.

The reason there are two minimum points (two sets of "porkchops") is that there are two different ways to get to Mars. You can find trajectories that are "short way" (transfer angle around the Sun less than 180 degrees) and you can find "long way" trajectories that have transfer angles greater than 180 degrees around the Sun. Transfer angle is kind of like the change in true anomaly needed to get to where you're going. In my plot, it turns out that the upper porkchop is the "long way" (or Type 2) transfer, and the lower porkchop is the "short way" (or Type I) transfer.

The labels on the x and y axis are Earth departure and Mars arrival times, given in Julian Date. So, if you want to leave Earth on a particular day and arrive at Mars on a particular day, just find that point on the grid and look up the C3 energy on the color bar. Viola: you know how much energy is required to get you to Mars for those dates.

I think that's about it... did I lose you (or anyone else)? Any questions?

[domox]

That is super handy.

[silent_prtoagonist]

Ah, that makes sense about the GAs, I wasn't thinking about multiple-encounter missions.

[TheCardinal]

The explanation was very clear and understandable. The only thing i still don't get is the julian date in the x and y-axis. In the x-axis i see five times 2.4536 and two times 2.4537 (times 10^6), in the Y-axis there are also multiple occurences of the same value. Why is that and what julian date is 2453600?

[domox]

http://www.wolframalpha.com/input/?i=2.4536+to+julian+date

Wolfram is indispensable with this game (and math in general)...

[Arrowstar]

TheCardinal: The reason that you see the date repeating on the axis is because of truncation of the numbers. Julian dates are long strings and there wasn't enough room on the axis to fit all the digits, hence why you see the "same" date repeating. In reality, they are different dates, I promise! Had I elected to use a shorter date format, such as modified Julian date (MJD), you'd be able to read the numbers better. Sorry for the confusion!

[Arrowstar]

I did a bit of work on KSP TOT yesterday and today, and I have something to show for it. Presenting version 1 of the user interface...

What do you guys think? Keep in mind this is very heavily Work in Progress...

[togfox]

Nice. Happy to discretely test it under a NDA (<-- NDA part is a joke, testing part is not).

[Arrowstar]

I will need testers, and will happily take you up on your offer when the application actually gets to the point where there's something to test. Right now I still need to implement all the delta-V calculation code, though I have the theory all figured out right now.

By the way, are the any particular feature requests while I'm thinking of it? What would make life easier as an interplanetary Kerbonaut?

[Arrowstar]

So tonight I finished up the calculation segment of the code so far as will be necessary for a 0.1 release. I added functions that compute departure C3 energy, delta-V for powered gravity assist maneuvers, and hyperbolic arrival delta-V (basically the Sun-relative difference between the spacecraft velocity and the planet velocity). For the 0.2 release I'll add functions for computing delta-V directly from your initial orbit around Kerbin or whatever and for your desired final orbit around whatever body you've selected as a destination. That'll provide for a bit more accuracy in the analysis, but the 0.1 release will have calculations that will be almost just as good for trajectory optimization.

I also worked on the GUI a bit more. The gravity assist flight plan segment interface is 90% done now.

That's it for now. As usual, comments and feedback welcome...

[pina_coladas]

Are you planning on presenting some kind of instrumentation or data in-game? Maybe eventually mechjeb integration? Is it too soon to ask?...

[TheCardinal]

Are you planning on presenting some kind of instrumentation or data in-game? Maybe eventually mechjeb integration? Is it too soon to ask?...

I've been thinking the same thing. In my opinion the gravity assist will become quite important as soon as more planets and moons are added to KSP, especially for the distant ones. The autom8te option in Mechjeb probably can be used for setting the trajectory.

[togfox]

Id offer improvements but i cant till ive seen the first version.

Pm me when its ready and ill give it and the formulas a good bashing.

[Arrowstar]

Are you planning on presenting some kind of instrumentation or data in-game? Maybe eventually mechjeb integration? Is it too soon to ask?...

I would LOVE to have MechJeb integration. I've actually been thinking about this a fair amount and I think I could pull it off. Of course, I would need R4m0n's help as he would have to parse the data coming out of KSP TOT, be it either a data stream from the application or some type of flat file with the trajectory information in it or something.

Can I assume this is something a lot of people want to see?

Togfox: Sounds good. Shoot me a PM and I'll ship you a copy of v0.1 when I've got it ready. Might even be this weekend if I can get things cleaned up enough. Keep in mind that it will be very WIP....

[jeff_9219]

What are the chances of a version for us dreaded mac users? eventually closer to release at least?

[TheCardinal]

Can I assume this is something a lot of people want to see?

I certainly would like to see this integrated. The further the planet/moon will be, the more use it will be to KSP users. Of course those will be reachable with a lot of fuel and boosters but with a gravity assist the craft doesn't need to be humongeous. And it will add an extra element to the game.

[Arrowstar]

What are the chances of a version for us dreaded mac users? eventually closer to release at least?

Since it's written in Java, as long as you can obtain version 7 of the Java Runtime Environment, you should be able to use it. Since I'm using the native theme for the GUI, it should even sort of resemble a normal Mac application. If you want to volunteer to test it on Mac, I'd be happy to give it to you whenever I finish v0.1.

I certainly would like to see this integrated. The further the planet/moon will be, the more use it will be to KSP users. Of course those will be reachable with a lot of fuel and boosters but with a gravity assist the craft doesn't need to be humongeous. And it will add an extra element to the game.

Alrighty then! Whenever I get to a good point, I'll try to get in touch with R4m0n and see what he says. No promises, obviously, since it'll be on him to do a good chunk of the work involved in any integration effort.

[pina_coladas]

Here's a question for you: does your system assume instantaneous impulse to the desired trajectory? I only ask because in the Kerbal universe celestial bodies are so tiny that a low thrust to weight ratio craft can get pretty far from apoapsis during an insertion burn, which I imagine would throw off the accuracy of some of the more delicate slingshot maneuvers. Is this a dumb question? Am I asking something outside the scope of this project?

[Arrowstar]

Here's a question for you: does your system assume instantaneous impulse to the desired trajectory? I only ask because in the Kerbal universe celestial bodies are so tiny that a low thrust to weight ratio craft can get pretty far from apoapsis during an insertion burn, which I imagine would throw off the accuracy of some of the more delicate slingshot maneuvers. Is this a dumb question? Am I asking something outside the scope of this project?

Not a dumb question at all! You are correct, KSP TOT does assume impulsive maneuvers. If i wanted to do finite duration maneuvers, the whole problem becomes a lot more complicated to compute. I would have to write the equations of motion of the spacecraft and then integrate those numerically while somehow enforcing the end conditions of arrival and departure at the correct bodies. It would be a nightmare.

KSP TOT isn't designed to be perfectly accurate, though for most interplanetary situations it should be good enough as to not be noticeable. Instead, it's designed to basically tell you when to leave home and what your transfer orbits should approximately look like. Of course, since KSP uses a two-body model of motion, it should actually be possible to follow the computed trajectory perfectly after the initial burn, assuming you hit your gravity assist maneuvers perfectly. But I'll leave that little problem to the pilots.