Evolution of AI Interplanetary Trajectories Reaches Human-Competitive Levels 52
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)."
Re: (Score:2)
It's the difference between using computers to solve arithmetic and using AI to solve a complex problem.
Re: (Score:1)
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: (Score:2)
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: (Score:3)
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? (Score:4, Interesting)
Re: (Score:2)
Technically passwords are an infinite set, you don't gen them all when you brute force one.
Re: (Score:2)
We still do not generate them all, just the likely ones.
Re: (Score:2)
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: (Score:2)
Re: (Score:2)
That doesn't sound like brute force though. That sounds like a formula.
Re: (Score:2)
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: (Score:2)
That doesn't sound like brute force though.
Ok, randomly generate thrust vectors and keep the best trajectories found.
Re: (Score:3)
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 thou
Re: (Score:1)
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: (Score:2)
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: (Score:2)
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
Re: (Score:1)
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
Re: (Score:2)
Re: (Score:3)
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 se
Re: (Score:2)
Re: (Score:2)
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: (Score:3)
Re: (Score:2)
This isn't like dusting crops, boy! (Score:2)
.
In other news... (Score:4, Insightful)
Re: (Score:2)
Re:In other news... (Score:5, Informative)
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: (Score:2)
Re: (Score:3)
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 pe
Re: (Score:1)
Optimization by hand sucks. (Score:2)
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: (Score:2)
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 (Score:3)
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 (Score:2)
Well, (Score:1)
it's not like it's rocket science.....oh, wait
Child's play compared to the tough questions (Score:2)
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: (Score:3)
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.
Well that's funny (Score:2)
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
Humans can win (Score:2)
All we have to do is discover the Spice planet.
AI my ass (Score:2)
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 (Score:2)
AI is when the computer learns from previous experience. GA do nothing like that.