SpaceTree

• 

  Spatial octree constructed by our implementation of the Barnes-Hut algorithm.

• 

  Our blackboard full of the brainstorming/debugging work for the project.

• 

  Our visualization of a sample data point showing the post collision state of two bodies from the dataset.

• 

  Figure from one of the papers that inspired this project that shows a 2d view of sample planetary collision states from the dataset,

Inspiration

N-body simulations - which simulate the gravitational interactions between N bodies of mass - are an algorithmically hard problem, and thus by nature their modeling of the nuances of physics is limited. For example, properly simulating a collision between two planets would itself require a separately expensive simulation, and so most N-body simulations operate on simplistic blobs of dark matter that instantly combine. Recent literature has focused on the possibility of efficiently estimating baryonic interactions in these simulations using machine learning. By running many collision simulations and recording the before and after states, one can train a simple ML model to do a decent job of predicting post-collision properties. However, they fall a bit short of the ideal: most recent models only predict the number of large planetary remnants rather than a complete description of where the debris is and its velocity. Moreover, these have all been largely theoretical endeavors and none of the models have been actually integrated into a real N-body simulation.

What it does

SpaceTree is an n-body simulation that incorporates this novel ML approach into its design. It uses the classic Barnes-Hut algorithm that reduces the time complexity of force computation down from O(n^2) to O(n log n) by dividing the space into an octree and using the center of mass of regions of space far away from a body to approximate the net gravitational force from that area.

SpaceTree's other component is where the primary novelty comes into play: our ML model is designed such that it gives a complete enough description of the end state such that it is usable by a simulation. We trained a model on an existing large dataset of the position and masses of planetary fragments before and after collision to predict a probability distribution for the presence of planetary fragments along each direction from a body of mass as well as a velocity distribution. This enables the simulation to sample said distribution and accurately place planetary remnants with positions and velocities that are reasonably sound given the collision.

These components combined enable a simulation that provides more accuracy without compromising on performance.

How we built it

We used C++ (with industry standard libraries like Eigen) to build the simulation framework and used pybind11 to generate Python bindings for visualization purposes. Our simulation provides a debug view using PyVista, a wrapper around VTK.

We used Python to perform a good deal of post processing of an existing dataset of planetary collisions (https://phaidra.univie.ac.at/detail/o:1206181) so that our ML model was possible as well as prototype the machine learning model.

Challenges we ran into

Existing literature provided models that were generally unhelpful for full use in a simulation and so we had to spend lots of time at the blackboard brainstorming how to retrofit their data to a harder task. The dataset was also large and slow internet speed meant we only got to see it for the first time about 4 hours into the project.

We were tragically plagued by strange segmentation faults that arose from a mix of strange Python binding semantics and sometimes confusing recursive tree algorithms.

Accomplishments that we're proud of

Our Barnes-Hut implementation produced a correct octree on our first successful compilation! We're also proud of our overhauled design of the machine learning model that enables proper usage in a simulation: it was challenging figuring out the task given the unusual input and output space.

What we learned

We learned a lot about computational astronomy, parallelization of complicated systems, cutting-edge research in applied machine learning, adaptive problem solving in confusing domains, and more. We also learned how to effectively work together on two parallel subprojects and brainstorm effectively!

What's next for SpaceTree

Now that the bulk of the work (in the form of somewhat heavy data processing and simulation implementation) is largely done, the ML model needs to rounded off and combined with the simulation. There's plenty of room for more complexity: other kinds of baryonic interactions can be approximated with similar methods and our simulation can get even faster either by thorough parallelization or by using TreePM and handling some of the force computation in Fourier space.

Built With

• c++
• eigen
• python
• pytorch
• pyvista