Slashdot Mirror
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)."
John Henry won the battle, but lost the war. How is being outcalculated by a computer news? Just because it's a hard problem?
Have you read my blog lately?
It's the difference between using computers to solve arithmetic and using AI to solve a complex problem.
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).
Ezekiel 23:20
Ooops, I meant "compose automatically", of course.
Ezekiel 23:20
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?
Ezekiel 23:20
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.
Obviously you manually provide some limits.
Humans do not start from nothing each time they calculate these either.
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.
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)
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.
Ezekiel 23:20
Technically passwords are an infinite set, you don't gen them all when you brute force one.
We still do not generate them all, just the likely ones.
it's not like it's rocket science.....oh, wait
Table-ized A.I.
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?"
Proverbs 21:19
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.
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.
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?
.
Prisencolinensinainciusol. Ol Rait!
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.
http://alternatives.rzero.com/
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.
I've decided to stop wasting my time responding to AC trolls/sockpuppets... so if you want a response from me... login.
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.
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).
Those who can, do. Those who can't, sue.
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).
world was created 5 seconds before this post as it is.
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.
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.
All we have to do is discover the Spice planet.
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
Jesus was a liberal
That doesn't sound like brute force though. That sounds like a formula.
http://soylentnews.org/~tibman
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.
"You must try to forget all you have learned. You must begin to dream." -- Sherwood Anderson
That doesn't sound like brute force though.
Ok, randomly generate thrust vectors and keep the best trajectories found.
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.
Help stamp out iliturcy.
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?
Be wary of any facts that confirm your opinion.
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.
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.
Ezekiel 23:20