2 ms·

The original paper can be found here: https://arxiv.org/abs/1910.07291 https://arxiv.org/abs/1910.07291 Abstract: > Since its formulation by Sir Isaac Newton,

by EndXA 7y ago

The original paper can be found here: https://arxiv.org/abs/1910.07291 https://arxiv.org/abs/1910.07291 Abstract: > Since its formulation by Sir Isaac Newton, the problem of solving the equations of motion for three bodies under their own gravitational force has remained practically unsolved. Currently, the solution for a given initialization can only be found by performing laborious iterative calculations that have unpredictable and potentially infinite computational cost, due to the system's chaotic nature. We show that an ensemble of solutions obtained using an arbitrarily precise numerical integrator can be used to train a deep artificial neural network (ANN) that, over a bounded time interval, provides accurate solutions at fixed computational cost and up to 100 million times faster than a state-of-the-art solver. Our results provide evidence that, for computationally challenging regions of phase-space, a trained ANN can replace existing numerical solvers, enabling fast and scalable simulations of many-body systems to shed light on outstanding phenomena such as the formation of black-hole binary systems or the origin of the core collapse in dense star clusters.

xgbi 7y ago
I expect KSP will finally get a real N-body simulator! My mun orbit insertion will be even harder!
- Sanzig 7y ago
  There already is a pretty good one available as a mod: https://github.com/mockingbirdnest/Principia https://github.com/mockingbirdnest/Principia
- perl4ever 7y ago
  When I read that KSP didn't use "real" N-body physics, I lost interest in trying it. Maybe it doesn't make a big difference, but I don't understand how it would save any noticeable amount of cpu cycles. I mean, there aren't that many objects in the game, are there? It's not like it involves galaxies or star clusters.
  - antepodius 7y ago
    I can think of a few reasons why it was a pain to add at any given point, (and then you just have to imagine some dev inertia/laziness/other priorities to ge tthe rest of the way): The game started off with only on body, Kerbin (earth knockoff), with the sun going around it. They then added the Mun and put in spheres of influence. As they added more planets, if, at any point, they had changed from the simple model to the true one, it would have broken all tutorials, delta-v calculations, extant saves, etc. It would also have required more changes to make the game properly playable. In KSP, players will often leave vessels in orbits on timewarp while focusing on something else- they'll have 10 missions ongoing at once. This works well when orbits aren't being perturbed, but in real life/real physics, you can't just leave a vessel in orbit around the moon for a year without course correction- it'll crash. The problem is, the game has no way to automate course correction/stationholding, and that would be far less trivial to add than merely changing the gravity model from one system to another. I'm not apologising for the devs not having done it right, really. KSP didn't really live up to all its promises, though it is pretty good.
  - wcoenen 7y ago
    That's because N-body physics implies unstable orbits. For the planet scale objects, the game designers would have to make sure that the orbits don't go crazy (over times that can be explored at maximum time warp). But then if the goal is to keep those orbits stable, why not just save all the dev effort and just keep them on Keplerian rails? For the smaller objects launched by the player, unstable orbits aren't necessarily desirable either. Imagine going on a multi-decade mission and returning home to find your favorite space station missing. Game devs aren't going to spend effort on complicated features that will just piss off most players.
semi-extrinsic 7y ago
As long as you're focusing on a bounded time interval, I believe a fair comparison would be comparing to interpolation between precomputed solutions obtained with the same computing power as used for training the network. If there is not any improvement over that, then it's not interesting. Look-up tables for rapidly solving such problems in a limited region have also existed since Newton's time.
- marmaduke 7y ago
  > Look-up tables don't work well on GPU because threads don't access the same memory location based on the argument to teh lut. Some nonlinear basis or projection doesn't have the same problem.
prmph 7y ago
Is this approach provably guaranteed to come up with an accurate solution?
- Enginerrrd 7y ago
  You can come up with a probablistic notion of accuracy, but I'm not sure proving guaranteed accuracy on a deep ANN is possible even in principle. Am I misunderstanding the question?
raverbashing 7y ago
> be found by performing laborious iterative calculations that have unpredictable and potentially infinite computational cost, due to the system's chaotic nature This is an exaggeration. This is an undergraduate level problem. It's not difficult to integrate the movement of 3 bodies under the influence of gravity. Sure, it can be tricky sometimes, or you need a small step size, but it's not rocket science. > provides accurate solutions at fixed computational cost and up to 100 million times faster than a state-of-the-art solver 100Mi times faster is a bit of a stretch. > Our results provide evidence that, for computationally challenging regions of phase-space, a trained ANN can replace existing numerical solvers, enabling fast and scalable simulations of many-body systems Yes but extrapolating from 3 to several is exactly where this technique is bound to break.
- perl4ever 7y ago
  There's already a much faster method for solving many-body systems than calculating the influence of every one on every other one. Basically, you divide your space into pieces depending on the location of the masses, and you build a tree, where far away areas are treated as if they were point masses at the center of gravity. This converts an N^2 computation into an N log N one. I'm not clear whether this neural net does better than the well known fast approximate method.

by EndXA 7y ago

xgbi 7y ago

I expect KSP will finally get a real N-body simulator! My mun orbit insertion will be even harder!

Sanzig 7y ago
There already is a pretty good one available as a mod: https://github.com/mockingbirdnest/Principia https://github.com/mockingbirdnest/Principia
perl4ever 7y ago
When I read that KSP didn't use "real" N-body physics, I lost interest in trying it. Maybe it doesn't make a big difference, but I don't understand how it would save any noticeable amount of cpu cycles. I mean, there aren't that many objects in the game, are there? It's not like it involves galaxies or star clusters.
- antepodius 7y ago
  I can think of a few reasons why it was a pain to add at any given point, (and then you just have to imagine some dev inertia/laziness/other priorities to ge tthe rest of the way): The game started off with only on body, Kerbin (earth knockoff), with the sun going around it. They then added the Mun and put in spheres of influence. As they added more planets, if, at any point, they had changed from the simple model to the true one, it would have broken all tutorials, delta-v calculations, extant saves, etc. It would also have required more changes to make the game properly playable. In KSP, players will often leave vessels in orbits on timewarp while focusing on something else- they'll have 10 missions ongoing at once. This works well when orbits aren't being perturbed, but in real life/real physics, you can't just leave a vessel in orbit around the moon for a year without course correction- it'll crash. The problem is, the game has no way to automate course correction/stationholding, and that would be far less trivial to add than merely changing the gravity model from one system to another. I'm not apologising for the devs not having done it right, really. KSP didn't really live up to all its promises, though it is pretty good.
- wcoenen 7y ago
  That's because N-body physics implies unstable orbits. For the planet scale objects, the game designers would have to make sure that the orbits don't go crazy (over times that can be explored at maximum time warp). But then if the goal is to keep those orbits stable, why not just save all the dev effort and just keep them on Keplerian rails? For the smaller objects launched by the player, unstable orbits aren't necessarily desirable either. Imagine going on a multi-decade mission and returning home to find your favorite space station missing. Game devs aren't going to spend effort on complicated features that will just piss off most players.

semi-extrinsic 7y ago

As long as you're focusing on a bounded time interval, I believe a fair comparison would be comparing to interpolation between precomputed solutions obtained with the same computing power as used for training the network. If there is not any improvement over that, then it's not interesting. Look-up tables for rapidly solving such problems in a limited region have also existed since Newton's time.

marmaduke 7y ago
> Look-up tables don't work well on GPU because threads don't access the same memory location based on the argument to teh lut. Some nonlinear basis or projection doesn't have the same problem.

prmph 7y ago

Is this approach provably guaranteed to come up with an accurate solution?

Enginerrrd 7y ago
You can come up with a probablistic notion of accuracy, but I'm not sure proving guaranteed accuracy on a deep ANN is possible even in principle. Am I misunderstanding the question?

raverbashing 7y ago

> be found by performing laborious iterative calculations that have unpredictable and potentially infinite computational cost, due to the system's chaotic nature This is an exaggeration. This is an undergraduate level problem. It's not difficult to integrate the movement of 3 bodies under the influence of gravity. Sure, it can be tricky sometimes, or you need a small step size, but it's not rocket science. > provides accurate solutions at fixed computational cost and up to 100 million times faster than a state-of-the-art solver 100Mi times faster is a bit of a stretch. > Our results provide evidence that, for computationally challenging regions of phase-space, a trained ANN can replace existing numerical solvers, enabling fast and scalable simulations of many-body systems Yes but extrapolating from 3 to several is exactly where this technique is bound to break.

perl4ever 7y ago
There's already a much faster method for solving many-body systems than calculating the influence of every one on every other one. Basically, you divide your space into pieces depending on the location of the masses, and you build a tree, where far away areas are treated as if they were point masses at the center of gravity. This converts an N^2 computation into an N log N one. I'm not clear whether this neural net does better than the well known fast approximate method.