Dear Fellow Scholars, this is Two Minute Papers with Dr. Károly Zsolnai-Fehér.
Today we are going to immerse ourselves into a 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 endpoint?
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 of 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 seemed so easy now suddenly seems absolutely impossible!
But fortunately, this learning algorithm does not get discouraged, 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 rollercoaster!
A hallmark of an expertly designed puzzle.
And to experience more of these puzzles, make sure to have a look 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 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 puzzle 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 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 endpoint 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.
Thanks for watching and for your generous support, and I'll see you next time!