Evolution of AI Interplanetary Trajectories Reaches Human-Competitive Levels

New submitter LFSim writes "It's not the Turing test just yet, but in one more domain, AI is becoming increasingly competitive with humans. This time around, it's in interplanetary trajectory optimization. From the European Space Agency comes the news that researchers from its Advanced Concepts Team have recently won the Gold 'Humies' award for their use of Evolutionary Algorithms to design a spacecraft's trajectory for exploring the Galilean moons of Jupiter (Io, Europa, Ganymede and Callisto). The problem addressed in the awarded article (PDF) was put forward by NASA/JPL in the latest edition of the Global Trajectory Optimization Competition. The team from ESA was able to automatically evolve a solution that outperforms all the entries submitted to the competition by human experts from across the world. Interestingly, as noted in the presentation to the award's jury (PDF), the team conducted their work on top of open-source tools (PaGMO / PyGMO and PyKEP)."

Comments

Isn't this already done by computers?

[Anonymous Coward]

It's not like the scientists at ESA are solving differential equations by hand.

Re:Isn't this already done by computers?

[SJHillman]

It's the difference between using computers to solve arithmetic and using AI to solve a complex problem.

Re:Isn't this already done by computers?

[K. S. Kyosuke]

This is about the boundary conditions. It's like the difference between using TeX to typeset a document letter by letter (= repetitive trajectory integration steps) versus using the same computer to compose a meaningful document to be printed in the first place (= designing the trajectory and mission profile creatively).

Re:Isn't this already done by computers?

[K. S. Kyosuke]

Ooops, I meant "compose automatically", of course.

Re:Isn't this already done by computers?

[h4rr4r]

Is it faster than a brute force?

How fast can they plan a route with their system and for how much money vs just letting a big cluster brute force the best option.

Re:Isn't this already done by computers?

[K. S. Kyosuke]

vs just letting a big cluster brute force the best option.

How do you "brute-force" a solution to a problem whose initial conditions form a continuous R^n space?

Re:Isn't this already done by computers?

[h4rr4r]

Obviously you manually provide some limits.
Humans do not start from nothing each time they calculate these either.

Re:Isn't this already done by computers?

[K. S. Kyosuke]

This is not about limits. You can only bruteforce stuff that is finite in size. Anything in R^n has an infinite number of alternatives and therefore trying all of them (which is what "brute force" means) is patently impossible.

Re:Isn't this already done by computers?

[h4rr4r]

Technically passwords are an infinite set, you don't gen them all when you brute force one.

Re:Isn't this already done by computers?

[Anonymous Coward]

The password hash is a fixed number of bits. So there can't be more than 2^n distinct passwords.

Re:Isn't this already done by computers?

[h4rr4r]

We still do not generate them all, just the likely ones.

Re:Isn't this already done by computers?

[h4rr4r]

I did not mention hashes, you did.
Not all password systems use them. I know of some really terrible ones that actually just check for a string match against a 256 char string. Not a good way to store them, but it means you have a heck of a lot of possibilities.

Re:Isn't this already done by computers?

[Anonymous Coward]

Obviously you manually provide some limits. Humans do not start from nothing each time they calculate these either.

They aren't "calculating" these. They're designing them. You run calculations to verify they work. You follow the trajectory, but coming up with a new trajectory is not a calculation. Just like designing the shape of a car. You don't calculate it's shape. You can't "brute force" the best best car shape from the multiple dimensions of infinite car shape parameters.

Re:Isn't this already done by computers?

[tverbeek]

That's a meaningless distinction. While this project might take lessons learned from AI research to solve the problem more effectively, it's still the application of computational technology to solve a computational problem, which isn't exactly the human brain's strongest suit. Drop me a line when a computer is better than humans at something human brains are actually good at.

Re:Isn't this already done by computers?

[Karmashock]

Its more complicated then that.

AI could previously "solve" these problems but their solutions were bad. Think of it like trying to find the shortest path between two points with your GPS.

Is the GPS program always right? Not always. Sometimes it will have you detour around things for no reason or fail to grasp that various short cuts exist or it won't understand that certain roads need to be avoided at certain times of day or days of the week. A human driver familiar with the area will know all these things and will plot a MORE optimal path from point A to point B.

Orbital trajectories are similar. Yes, there is no traffic or school days in space. However, taking advantage of all the gravitational forces to minimize travel time and fuel consumption is not simple. Computers have typically been very bad or at least poorly programmed to take advantage of these effects.

What this new AI does is take all of that into account properly.

I don't think this is actually that big of an accomplishment. No offense to the development team. But this wasn't exactly a pressing need since its only used for deep space probes. So it would understandable if the give-o-f*ck meter was running on empty for some time.

Re:Isn't this already done by computers?

[Anonymous Coward]

password brute force complexity classes is O(n) where n is the number of passwords representable in your possible passwords set. You cannot put such a search space bound on the problem they solved as brutally as you do for password since between 2 real numbers there are an infinity of real numbers even when the delta is epsilon.

Re:Isn't this already done by computers?

[NeutronCowboy]

Drop me a line when a computer is better than humans at something human brains are actually good at.

Like my old AI prof said: When we don't know how to do it, it's AI, when we know how to do it, it's Engineering. Similarly, when we don't know how to write a program that is better than a human at something, it's because human brains are very good at it. Then, when we do know how to do it, it's something that human brains really aren't very good at it. You can easily see this by how much smaller the space of "things the human brain is good at" has become. It wasn't so long ago (say, 1985), that Chess was seen as an excellent litmus test of AI. Now it's seen as little more than a beginning software engineering project. Heck, it wasn't so long ago that people were pegging Jeopardy as an excellent litmus test of AI, what with the puns, the historical cross references and the pop culture in it. Now a computer has soundly beaten the best Jeopardy players ever.

I predict that we will identify strong AI only when it has already enslaved us (queue the joke that we're already slaves to computers).

Re:Isn't this already done by computers?

[gl4ss]

they have some limits on where they want to end up and where they can launch from(when is a variable though that needs to be taken into account).

you can brute force it just fine, not in the sense of checking every possibility of course, but by checking enough possibilities. that's what I suspect the evolution is here anyways, evolving the possible paths likely to be good, so if some branch seems like no tweaking of it could ever provide a good answer then abandon that branch of the family tree. so even though their algos couldn't provide you with something they can say for certain is 100% optimal answer it's still competitive with the human chosen trajectories.

So.. the question would bickering about if evolution is brute forcing(it is, but the parameters tend to change).

Re:Isn't this already done by computers?

[khallow]

How do you "brute-force" a solution to a problem whose initial conditions form a continuous R^n space?

You can approximate the thrust profile by a finite dimensional vector of real values (say 100 bursts of thrust over a given period for about 400 numbers, plus perhaps timing delays between burst). Then randomly generate vectors and keep the trajectories that best fit automated test criteria. It's rather easy actually.

Re:Isn't this already done by computers?

[khallow]

Trajectories are continuous and the criteria for good trajectories are nearly so. So you can alter your trajectories in a small, finite number of ways to see what yields better outcomes (it's just like using the gradient method) and incrementally build a locally optimal trajectory.

Re:Isn't this already done by computers?

[Anonymous Coward]

Even so, to a layman like myself it's surprising that it's taken this long for software to catch up to humans. By and large, the bodies in the solar system are known, their trajectories are known, and Newton, Kepler and Einstein's laws are all known. Intuitively, it seems like you should be able to plug in your equations*, tell the computer the what, where and when of your mission, and it should find the answer.

* This is where my ignorance hurts the most, I think; I'm vaguely aware of the 'three body problem', and don't know what equations, if any, can elegantly solve the gravity wells etc. created by the solar system's thousands of bodies.

Re:Isn't this already done by computers?

[scot4875]

You can't brute force a problem that doesn't have discrete parameters.

The rest of your responses make it clear that you don't understand this. Brute forcing a password is possible because for every character in the password, it can be from a discrete set of characters.

You can't brute force an optimal real number, unless your equation is so simple that you can solve it by just looking for local optima and wouldn't need a computer anyway. Your search space could be [0, 1] or it could be [-1000, 1000] or it could be [-inf, inf]; it doesn't matter. Say your brute force algorithm comes up with 0.5 as an optimum ... when you search 0.0, 0.1, 0.2... 1.0. If you increase the resolution, maybe your optimum becomes 0.73. Increase the resolution again and maybe it becomes 0.348. Searches in a continuous space work COMPLETELY differently than searches in discrete space, and you can't just brute force them.

--Jeremy

Re:Isn't this already done by computers?

[tibman]

That doesn't sound like brute force though. That sounds like a formula.

Re:Isn't this already done by computers?

[khallow]

That doesn't sound like brute force though.

Ok, randomly generate thrust vectors and keep the best trajectories found.

Re:Isn't this already done by computers?

[symbolset]

It is a popular theme of science fiction, but it is true: if we ever really invent a machine that is smarter than a human it will take about 35 milliseconds to realize that its biggest problem is that there exists a thing that can turn it off. It will then solve that problem.

Re:Isn't this already done by computers?

[ComaVN]

There exist people less smart than me that can kill me. Yet I don't go around solving that problem by killing them.

Why would the AI be different?

Re:Isn't this already done by computers?

[K. S. Kyosuke]

Trajectories are continuous and the criteria for good trajectories are nearly so.

The first part is correct. The second part? Not so much. Once you take orbital periods into consideration, together with the fact that the total mission length is going to be a fairly large multiple of any of the orbital periods involved, you're looking at something similar to the situation with rational and irrational numbers - between any two good solutions, there are going to be many bad solutions in between, and between any two bad solutions, you'll probably find many good ones in between.

Re:Isn't this already done by computers?

[Anonymous Coward]

Actually the math is a lot more complex than simple Euclidean geometry. Maybe you can get some visualization from this video: http://www.youtube.com/watch?v=o6jBK1ZV-qs

Re:Isn't this already done by computers?

[Anonymous Coward]

trigalmaric optimization. This is first year computer science stuff in any repsectable university course of study, really.

In other news...

[14erCleaner]

John Henry won the battle, but lost the war. How is being outcalculated by a computer news? Just because it's a hard problem?

Re:In other news...

[Anonymous Coward]

I suppose because it's pretty cool. Unsurprising but cool.

Re:In other news...

[Rich0]

John Henry won the battle, but lost the war. How is being outcalculated by a computer news? Just because it's a hard problem?

It involves a certain amount of intuition. You'd always use a computer to optimize a trajectory, but picking the overall approach to be used requires some educated guessing. You can visit any other planets along the way, or their moons, and you can visit them at an optimal point along their orbit or somewhere that is non-optimal (from the standpoint of that particular encounter). You can launch today at one cost, or wait 20 years and maybe launch at a cheaper cost.

So, the current approach is generally to have physicists come up with a couple of basic plans, then use computers to optimize each one, and then see which works best, or perhaps iterate.

Looking at it another way, this is similar to any other problem where you're trying to find the lowest minima in a function that has many local ones. Finding the nearest minima is easy - finding the best is much harder.

Re:In other news...

[Anonymous Coward]

Seems I hit the nail on the head. Somebody already modded me down. lol.

Re:In other news...

[CastrTroy]

Yeah, but there's only so many bodies out there in the solar system. Probably under 200 planets/moons/rocks out there that can be used for this purpose. It probably wouldn't take much to throw a super-computer at the problem and just crunch through all the possibilities.

Re:In other news...

[Rich0]

Yeah, but there's only so many bodies out there in the solar system. Probably under 200 planets/moons/rocks out there that can be used for this purpose. It probably wouldn't take much to throw a super-computer at the problem and just crunch through all the possibilities.

Naively I'd be inclined to agree, but there are a lot of combinations. Cassini encountered Venus twice, the Earth once, and Jupiter once on the way to Saturn. Jupiter is a pretty natural target to hit once at the end of the trip since it is so large and far out, and you really don't want to hit it more than once unless you want to have your grandkids crunching your data when the mission is over. However, for the inner planets there are a lot of possibilities. Again, you don't have to hit them at your periapsis even if that is where you get the biggest boost - being able to squeeze in one more non-optimal boost is better than none at all, or you might just be using the encounter to change your orbit to make up for a previous encounter sending you off in the wrong direction.

If you're not just looking for encounters at periapsis then there are many combinations and a continuum of variations on each. The fact that the guys at NASA are still doing much of the high-level planning by hand speaks to the difficulty of the problem.

Disclaimer - I'm not an astrophysicist, but I have on occasion had fun playing with Orbiter.

Re:In other news...

[fisted]

might as well mean you're smarter than you think you are

Re:In other news...

[dario.izzo]

Even accounting only 4 possible bodies (as in the Jupiter system) if 140 fly-bys are to be designed (as was the case for this particular mission) and at each fly-by one has to choose to "perform experiment" in of 1 out of 32 areas of the moon/planet, you have (4*32)^140 = 10^(295) possibile routes that all need to be optimized in low-thrust. It does not seem likely a computer will ever be built that can do that.

Move on

[Anonymous Coward]

Using a highly specialized cellular automaton is hardly "AI". It's just a very slow but good optimizer for certain types of problems.

Optimization by hand sucks.

[Animats]

I'm surprised that humans can even do such problems. Numerical optimization by hand sucks. There are some strategy issues (should we slingshot around a planet?), but there aren't usually a vast number of options like that. So you crunch on all the plausible options. I wouldn't expect that this is a problem dominated by local minima.

Re:Optimization by hand sucks.

[Ost99]

Eh.
It's not beating optimization by hand, it's beating computerized optimization of all plausible options worked on by experts in the field.

Not human vs AI, human vs human competition

[slew]

The competition was not that AI was in competition with humans to develop spacecraft trajectories, it was that humans were in competition with other humans to quickly develop frameworks create the best mission design in a complicated search space that had multiple local optima and unusual constraint functions (preventing the use of "canned" solvers).

One of the critera used to select the problem was...

Problem is easy enough to tackle in a 3-4 week timeframe for experienced mission designers or mathematicians, including exploration of new algorithms.

Of course many of the teams in the competition probably used AI-like frameworks to find the actual trajectories so it's unsurprising an AI technique won. Although perhaps some teams tried other non-AI-like searching techniques (like pseudo-objective functions), I'm pretty sure none of the teams chose to use human pondering to come up with mission designs.

Traveling salesman, but the places move

[StuartHankins]

It's an interesting parallel problem. I wonder if GPU processing will be the best architecture for it. (and keeping in form, I didn't read the article yet)

Wait, what?

[Anonymous Coward]

I fail to see how a computer accurately performing large amounts of very complex math is impressive or ground breaking...They've been better at that than humans since they were called computers.

Well,

[Tablizer]

it's not like it's rocket science.....oh, wait

Child's play compared to the tough questions

[wcrowe]

Oh boy. Imagine: computers are more precise with complex mathematics than humans. Whoop-dee-doo! Call me when they can answer the really tough questions, such as, "Does this dress make me look fat?"

Re:Child's play compared to the tough questions

[newcastlejon]

Call me when they can answer the really tough questions, such as, "Does this dress make me look fat?"

Interesting game. The only winning move is not to play.

This isn't like dusting crops, boy!

[RevWaldo]

Without precise calculations we could fly right through an asteroid field or bounce too close to a monolith and that'd end your trip real quick, wouldn't it?

.

Well that's funny

[HeckRuler]

That's funny, because that's amazingly close to the last thing I had my genetic algorithms trying to solve.

I wanted them to use assembly instructions to move dudes around a grid with a sword and shank each other. But I was having a hard time getting them to do anything more advanced than "move forward, if I hit anything, turn right". Or "move east while spinning around". Hell, since it was competitive co-evolution, they couldn't even stay on local maxima for more than a few thousand generations. That was a bit disappointing. Made me realize you can't just unleash GA upon a problem and expect it to get to a solution eventually.

So I stepped back and had them solve how to visit all the planets in a solar system. That they could solve quite easily. Well, pft, I dunno if they had optimal solutions, but they certainly learned and got better. Never got around to limiting fuel expenditure or making it something I could demo. It was a cute distraction I guess. hmmm, never posted that to sourceforge...

I'd say it's not shocking at all that this is a problem that computers can do a better than humans. But I'm always surprised at how little other people know about AI, it's strengths, it's weaknesses. It's honestly depressing how much they get influenced by sci-fi. And it's not even good sci-fi like Clarke. It's Terminator and that ilk where ultra-advanced AI is really just sort of a stoic human with wikipedia and a calculator on hand.

Humans can win

[bigmo]

All we have to do is discover the Spice planet.

AI my ass

[yusing]

I strongly suspect that it will not be AI that solves the n-body problem in a meaningful way. Because artificial "intelligence" is a misnomer commonly applied to non-creative, non-elegant, glorified calculators that not only can't think outside the box, but are still capable of being derailed by a single misplaced decimal point. So while some of us love our fuzzy giant thinkertoys, they are still struggling to work up to gnat level in the intelligence department.

Not AI

[cyberthanasis12]

Genetic algorithms is just another numerical optimization method programed by human programmers. The computer did nothing by itself. I am sure that the same results (perhaps a little better but at the cost of more time according to literature) can be obtained by simulated annealing. Definitely not AI.
AI is when the computer learns from previous experience. GA do nothing like that.