🔥🔥🔥 Download app DailyDictation on AppStore DailyDictation on Google Play

The Fastest Maze-Solving Competition On Earth

Vocab level: C1
Loading...

This tiny robot mouse can finish this maze in just six seconds.
...
Every year, around the world, people compete in the oldest robotics race.
The goal is simple: get to the end of the maze as fast as possible.
But competition has grown fierce.
When somebody saw my design, they said, "You're crazy!"
Why is there so much tension? What's riding on it?
Honor? - Honor!
In 1952, mathematician Claude Shannon constructed an electronic mouse named Theseus that could solve a maze.
The trick to making the mouse intelligent was hidden in a computer built into the maze itself,
made of telephone relay switches.
The mouse was just a magnet on wheels, essentially,
following an electromagnet controlled by the position of the relay switches.
He is now exploring the maze using a rather involved strategy of trial and error.
As he finds the correct path, he registers the information in his memory.
Later, I can put him down in any part of the maze that he's already explored,
and he'll be able to go directly to the goal without making a single false turn.
Theseus is often referred to as one of the first examples of machine learning.
A director at Google recently said that it inspired the whole field of AI.
25 years later, editors at the Institute of Electrical and Electronics Engineers, or IEEE,
caught wind of a contest for electronic mice, or le mouse electronique, as they had heard.
They were ecstatic.
Were these the successors to Theseus?
But something had been lost in translation.
These mice were just batteries in cases, not robots capable of intelligent behavior.
But the misunderstanding stuck with them, and they wondered,
"Why couldn't we hold that competition ourselves?"
In 1977, the announcement for IEEE's Amazing Micro-Mouse Maze Contest attracted over 6,000 entrants,
but the number of successful competitors dwindled rapidly.
Eventually, just 15 entrants reached the finals in 1979.
But by this point, the contest had garnered enough public interest to be broadcast nationwide on the evening news.
And just like the rumor that inspired the competition,
Micromouse began to spread across the world.
Just like a real mouse, a Micromouse has to be fully autonomous.
No internet connection, no GPS or remote control
and no nudging it to help it get unstuck.
It has to fit all its computing, motors, sensors, and power supply in a frame no longer or wider than 25 centimeters.
There isn't a limit on the height of the mouse,
but the rules don't allow climbing, flight, or any forms of combustion,
so rocket propulsion, for example, is out of the equation.
The maze itself is a square about three meters on each side,
subdivided by walls into corridors only 18 centimeters across.
And in 2009, the half-size Micromouse category was introduced,
with mice smaller than 12.5 centimeters per side,
and paths just nine centimeters across.
The final layout of the maze is only revealed at the start of each competition,
after which competitors are not allowed to change the code in their mice.
The big three competitions, All Japan, Taiwan, and USA's APEC,
usually limit the time mice get in the maze to seven or 10 minutes,
and mice are only allowed five runs from the start to the goal.
So if you spend a lot of time searching, that's a penalty.
So the strategy for most Micromice is to spend their first run carefully learning the maze and looking for the best path to the goal,
while not wasting too much time.
Then they use their remaining tries to sprint down that path for the fastest run time possible.
...
Solving a maze may sound simple enough,
though it's important to remember that, with only a few infrared sensors for eyes,
the view from inside the maze is a lot less clear than what we see from above.
Still, you can solve a maze with your eyes closed.
If you just put one hand along one wall, you will eventually reach the end of most common mazes.
And that's exactly what some initial Micromouse competitors realized, too.
And after a simple wall-following mouse took home gold in the first finals,
the goal of the maze was moved away from the edges, and free-standing walls were added,
which would leave a simple wall-following mouse searching forever.
Your next instinct might be to run through the maze, taking note of every fork in the road.
Whenever you reach a dead end or a loop,
you can go back to the last intersection and try a different path.
If your last left turn got you nowhere,
you'd come back to that intersection and go right instead.
You can think of this strategy as the one a headstrong mouse might use,
running as deep into the maze as it can, and turning back only when it can't go any further.
This search strategy, known as depth-first search,
will eventually get the mouse to the goal.
The problem is, it might not be the shortest route,
because the mouse only turns back when it needs to,
so it may have missed a shortcut that it never tried.
The sibling to this search algorithm, breadth-first search, would find the shortest path.
With this strategy, the mouse runs down one branch of an intersection, until it reaches the next one,
and then it goes back to check the path it skipped, before moving on to the next layer of intersections.
So the mouse checks every option it reaches,
but all that backtracking means that it's rerunning paths dozens of times.
At this point, even searching the whole maze often takes less time.
So why not just do that?
A meticulous mouse could search all 256 cells of the maze,
testing every turn and corner to ensure it has definitely found the shortest path.
But searching so thoroughly isn't necessary, either.
Instead, the most popular Micromouse strategy is different from all of these techniques.
It's a search algorithm known as flood fill.
This mouse's plan is to make optimistic journeys through the maze,
so optimistic, in fact, that on their first journey, their map of the maze doesn't have any walls at all.
They simply draw the shortest path to the goal and go.
When their optimistic plan inevitably hits a wall that wasn't on their map,
they simply mark it down and update their new shortest path to the goal.
Running, updating, running, updating,
always beelining for the goal.
Under the hood of the algorithm,
what the Micromouse is marking on their map is the distance from every square in the maze to the goal.
To travel optimistically, the mouse follows the trail of decreasing numbers down to zero.
Whenever they hit a wall, they update the numbers on their map to reflect the new shortest distance to the goal.
This strategy of following the numerical path of least resistance gives the flood fill algorithm its name.
The process resembles flooding the maze with water and updating values based on the flow.
Once the mouse reaches the goal,
it can smooth out the path it took and get a solution to the maze.
However, it may look back and imagine an even shorter, uncharted path it could've taken.
The mouse might not be satisfied that it's found the shortest path just yet.
While this algorithm isn't guaranteed to find the best path on first pass,
it takes advantage of the fact that Micromice need to return to the start to begin their next run.
So if the mouse treats its return as a new journey,
it can use the return trip to search the maze as well.
Between these two attempts, both optimized to find the shortest path from start to finish,
it's extremely likely that the mouse will discover it,
and the mouse will have done it efficiently,
often leaving irrelevant areas of the maze entirely untouched.
Flood fill offers both an intelligent and practical way for Micromice to find the shortest path through the maze.
Once there was a clear strategy to find the shortest path,
and once the microcontrollers and sensors required to implement it became common,
some people believed Micromouse had run its course.
As a paper published in IEEE put it,
"At the end of the 1980s, the Micromouse Contest had outlived itself."
"The problem was solved, and did not provide any new challenges."
In the 2017, All Japan Micromouse Competition,
both the bronze-and silver-placing mice found the shortest path to the goal,
and once they did, they were able to zip along it as quick as 7.4 seconds.
But Masakazu Utsunomiya's winning mouse, Red Comet, did something entirely different.
This is the shortest path to the goal, the one that everyone took.
This is the path that Red Comet took.
It's a full 5.5 meters longer.
That's because Micromice aren't actually searching for the shortest path,
they're searching for the fastest path.
And Red Comet's search algorithm figured out that this path had fewer turns to slow it down.
So even though the path was longer, it could end up being faster.
So it took that risk.
...
It won by 131 milliseconds.
Differing routes at competition are now more common than not,
and even just getting to the goal remains difficult,
whether due to a mysterious algorithm or a quirk of the physical maze.
Micromice don't always behave as you'd expect.
Micromouse is far from solved,
because it's not just a software problem or a hardware problem,
it's both.
It's a robotics problem.
Red Comet didn't win because it had a better search algorithm or because it had faster motors.
Its cleverness came from how the brains and body of the mouse interacted together.
So it turns out solving the maze is not the problem, right? It never was the problem, right?
But it's actually about navigation, and it's about going fast.
Every year, the robots get smaller, faster, lighter.
There is still plenty of innovation left.
And there's a small group of devotees in Japan busy building quarter-size Micromouse
which would sit on a quarter.
Nearly 50 years on, Micromouse is bigger than ever.
Competitions have appeared solved at first glance before.
The high jump was an Olympic sport since 1896,
with competitors refining their jumps using variations like the scissor, the western roll, and the straddle over the decades, with diminishing returns.
But once foam padding became standard in competition,
Dick Fosbury rewrote the sport in 1968
by becoming the first Olympian to jump over the pole backwards.
Now almost every high jumper does what's known as the Fosbury flop.
If Micromouse had indeed stopped in the 1980s,
the competition would've missed its own Fosbury flops,
two innovations that completely changed how Micromice ran.
After all, a lot can change in a sport where competitors can solder on any upgrade they can imagine.
The first Fosbury flop was one of the earliest innovations in Micromouse,
and had nothing to do with technology.
It was simply a way of thinking outside the box,
or rather, cutting through the box.
Every mouse used to turn corners like this.
But everything changed with the mouse Mitee 3.
So Mitee Mouse 3 implemented diagonals for the first time.
And that turned out to be a much better idea than we really thought.
And because it's cool,
you know, maze designers often put diagonals into the maze now.
So, you know, you could end up with a maze where it never comes up,
but most of the time it's actually a benefit.
In order to pull off diagonals,
the chassis of the mouse had to be reduced to less than 11 centimeters wide,
or just five centimeters for half-size Micromouse.
The sensors and software of the mouse had to change, too.
When you're running between parallel walls,
all you have to do is maintain an equal distance between your left and right infrared readings.
But a diagonal requires an entirely new algorithm,
one that essentially guides the mouse as if it had blinders on.
Normally, if you're going along the side of a wall, or something like that,
most of the time you can see the wall all the time.
And so that helps you to guide yourself, and you know when you're getting off.
But in the diagonal situation, you just see these walls coming at you.
And if you veer even a tiny bit off course,
snagging a corner is a lot less forgiving than sliding against a wall.
Diagonals are still one of the biggest sources of crashes in competition today.
But in exchange, a jagged path of turns transforms into one narrow straightaway.
...
These days, nearly every competitive Micromouse is designed to take this risk.
Cutting diagonals opened up room for even more ideas.
Around the same time, mice were applying similar strategies to turning.
Instead of stopping and pivoting through two right turns,
a mouse could sweep around in a single U-turn motion.
And once the possibility of diagonals were added,
the total number of possible turns opened up exponentially.
The maze was no longer just a grid of square hallways.
With so many more options to weigh,
figuring out the best path became more complex than ever.
But the payoff was dramatic.
What was once a series of stops and starts could now be a single, fluid, snaking motion.
How Micromice imagined and moved through the maze had changed completely.
Available technology was getting upgrades over the years as well.
Tall and unwieldy arms that were used to find walls were replaced by a smaller array of infrared sensors on board the mouse.
Precise stepper motors were traded in for continuous DC motors and encoders.
Gyroscopes added an extra sense of orientation.
But even with all the mechanical upgrades,
the biggest physical issue for Micromice went unaddressed for decades.
One thing you'll see almost every competitor holding is a roll of tape.
Once you know to look for it, you'll see it everywhere.
This tape isn't for repairs or reattaching fallen parts.
It's to gather specs of dust off the wheels in between rounds.
At the speed and precision these robots are operating,
that tiny change in friction is enough to ruin a run.
If you wanna turn while driving fast,
you need centripetal force to accelerate you into the turn.
And the faster you're moving, the more force you need to keep you on the track.
The only centripetal force for a car turning on flat ground is friction,
which is determined by two things,
the road pushing up the weight of the car, or the normal force,
multiplied by the static coefficient of friction,
which is the friction of the interface between the tire and road surface.
This is why racetracks have banked turns.
The steep angles help cars turn with less friction,
because part of the normal force itself now points in to contribute to the centripetal force required.
If the banked turn is steep enough, cars can actually make the turn without any friction at all.
The inward component of the normal force alone is enough to provide the centripetal force required to stay on track.
Micromice are no different, and they don't have banked turns to help.
As they got faster and faster, by the early 2000s,
their limiting factor was no longer speed, but control of that speed.
They had to set their center of gravity low,
and slow down during turns to avoid slipping into a wall or flipping over.
But unlike race cars, there wasn't anything in the rules to stop Micromouse competitors from solving this problem
by engineering an entirely new mechanism.
Micromouse's second Fosbury flop was almost considered a gimmick
when the mouse Mokomo08 first used it in competition.
You might be staring at the video to try to see it, but you won't.
Instead, it's something you'll hear.
That isn't the mouse revving its engines. It's spinning up a propeller.
And while flying over the walls is against the rules,
there's nothing in the rules against a mouse vacuuming itself to the ground to prevent slipping.
At the scale of Micromouse, a vacuum fan, often just built from handheld drone parts,
is enough to generate a downward force five times the mouse's weight.
With that much friction, Micromice today can turn corners with a centripetal acceleration approaching six Gs.
That's the same as F1 cars.
Once nearly everyone equipped fans, the added control allowed builders to push the speed limit on Micromice.
When it's allowed to, it will out-accelerate a Tesla Roadster,
but not for very far.
And they can zip along at up to seven meters per second,
faster than most people can run.
Every one of the features now standard on the modern Micromouse was once an experiment,
and the next Fosbury flop might not be far off.
The first four wheeled Micromouse to win the All Japan competition did so in 1988,
but it would take another 22 years of the winning mouse growing and losing appendages
before four-wheeled mice became the norm.
With Micromice still experimenting in six- and eight wheel designs,
omnidirectional movement, and even computer vision,
who knows what the next paradigm shift will be?
But if you wanna get started with Micromouse,
you don't need to worry about wheel count or vacuum fans, or even diagonals.
At its core, Micromouse is just about a mouse trying to solve a maze.
Though, nearly 50 years later, it's a simple problem that's a good reminder,
there is no such thing as a simple problem.