Dr. Zsolnai walks through an AI system that solves interlocking puzzles by finding collision-free moves. It tackles three puzzles of increasing difficulty, using techniques like tunnel discovery and shortest-path planning to untangle rigid bodies that seem impossibly locked together.
Dear fellow scholars, this is Two Minute Papers with Dr. Zsolnai. Today we are going to immerse ourselves into the wonderful art of rigid body disentanglement. Or in simpler words, we are going to solve these puzzles to be more exact. We'll sit and enjoy our time while a learning based algorithm is going to miraculously solve some really challenging puzzles. Yes, this is going to be a spicy paper. Now these puzzles are roughly ordered by difficulty, where the easier ones are on the left, and as we traverse to the right, things get more and more difficult. And get this, this new technique is able to algorithmically solve all of them. If you are like me and you don't believe a word of what's been said, let's see if it lives up to its promise by solving three of them in increasing difficulty. Let's start with an easy one. Example number one. Here the algorithm recognizes that we need to pull the circular part of the red piece through the blue one and apply the appropriate rotations to make sure that we don't get stuck during this process while we finish this sequence. Please note that this video contains spoilers for some well known puzzles. If you wish to experience them yourself, pause this video and I guess buy and try them. This one was good enough to warm ourselves up, so let's hop on to the next one. Example number two, the duet puzzle. Well, that was quite a bit of a jump in difficulty because we seem stuck right at the start. Hmm. This seems flat out impossible until the algorithm recognizes that there are these small notches in the puzzle. And if we rotate the red piece correctly, we may go from one cell to the next one. Great. So now it's not impossible anymore. It is more like a maze that we have to climb through. But the challenges are still not over. Where is the end point? How do we finish this puzzle? There has to be a notch on the side. Yes, there is. This one or this one. So we ultimately have to end up in one of these places. And there we go. Bravo. Experiment number three, my favorite, the enigma. Hmm. This is exactly the opposite of the previous one. It looks so easy. Just get the tiny opening on the red piece onto this part of the blue one and we are done. Uh oh. The curved part is in the way. Something that seems so easy now suddenly seems absolutely impossible. But fortunately, this learning algorithm does not get discouraged and and does not know what impossible is. And it finds this tricky series of rotations to go around the entirety of the blue piece and then finish the puzzle. Glorious. What a roller coaster. A hallmark of an expertly designed puzzle. And to experience more of these puzzles, make sure to have a look at the paper and its website with a super fun interactive app. If you do, you will also learn really cool new things. For instance, if you get back home in the middle of the night and after a long day and two of your keys are stuck together, you will know exactly how to handle it. And all this can be done through the power of machine learning and computer graphics research. What a time to be alive. So how does this wizardry work exactly? The key techniques here are tunnel discovery and path planning. First, a neural network looks at the puzzles and identifies where the gaps and notches are and specifies the starting position and the goal position that we need to achieve to finish the puzzle. Then a set of collision free key configurations are identified after which the blooming step can commence. So what does that do? Well, the goal is to be able to go through these narrow tunnels that represent tricky steps in the puzzles that typically require some unintuitive rotations. These are typically the most challenging parts of the puzzles and and the blooming step starts from these narrow tunnels and helps us reach the bigger bubbles of the puzzle. But as you see, not all roads connect, or at least not easily. The Forest Connect step tries to connect these roads through collision free paths. And now finally all we have to do is find the shortest path from the start to the end point to solve the puzzle. And also according to my internal numbering System, this is Two Minute Papers episode number 478. And to every single one of you fellow scholars who are watching this, thank you so much to all of you for being with us for so long on this incredible journey. Man, I love my job and I jump out of bed full of energy and joy knowing that I get to read research papers and flip out together with many of you fellow scholars on a regular basis. Thank you. This episode has been supported by weights and biases. In this post they show you how to visualize your scikit, learn models with just a few lines of code. Look at all those beautiful visualizations. So good you can even try an example in an interactive notebook through the link in the video Description during my PhD studies I trained a ton of neural networks which were used in our experiments. However over time they there was just too much data in our repositories and what I am looking for is not data but insight. And that's exactly how weights and biases helps you by organizing your experiments. It is used by more than 200 companies and research institutions including OpenAI, Toyota, Research, GitHub and more. And get this Weights and Biases is free for all individuals, academics and open source projects. Make sure to visit them through wnb. Com papers or just click the link in the video description and you can get a free demo today. Our thanks to Weightsand Biases for their long standing support and for helping us make better videos for you. Thanks for watching and for your generous support and I'll see you next time.
