The Fastest Maze-Solving Competition On Earth

- This little robot mouse can finish this

maze

in just six seconds. (dramatic music) Every year, around the world, people compete in the oldest robotics race. The goal is simple: get to the end of the

maze

as quickly as possible. - The person who came in second place (announcer chattering) (people applauding) lost by 20 milliseconds. - But the

competition

has become fierce. -When someone saw my design, he said: "You're crazy!" - Why is there so much tension? What is in game? Honor? - Honor (audience applauding) (audience applauding) - This video is sponsored by Onshape. In 1952, mathematician Claude Shannon built an electronic mouse called Theseus that could solve a maze.

The trick to making the mouse smart was hidden in a computer built into the maze itself, made of telephone relay switches. The mouse was simply a magnet on wheels, essentially following an electromagnet controlled by the position of relay switches. - You are now exploring the maze using a rather complicated trial and error strategy. As you find the right path, you record the information in your memory. Then I'll be able to drop him off at any part of the maze he's already explored and he'll be able to go straight to the goal without making a single wrong turn. - Theseus is often referred to as one of the first examples of machine learning.

A Google director recently said that it inspired the entire field of AI. Twenty-five years later, editors at the Institute of Electrical and Electronics Engineers, or IEEE, learned of an electronic mouse contest, or le mouse electronicique, as they had heard. They were ecstatic. Were these the successors of Theseus? But something had been lost in translation. These mice were just batteries in boxes, not robots capable of intelligent behavior. But the misunderstanding persisted and they asked themselves: "Why couldn't we organize that

competition

ourselves?" In 1977, the announcement of the IEEE Amazing Micro-Mouse Maze contest attracted more than 6,000 entrants, but the number of successful competitors rapidly declined.

Ultimately, only 15 contestants made it to the finals in 1979. But by that time, the contest had generated enough public interest to be broadcast nationally on the evening news. And just like the rumor that inspired the competition, Micromouse began to spread throughout the world. ♪ Micromouse, it's here for the taking ♪ ♪ Micromouse, it's here and now ♪ ♪ Take the opportunity and start creating ♪ (upbeat music) (reporter speaking Japanese) - A Micromouse? - Micromouse! (audience applauds) - Even the people in the top two or three places, you can see them trying to set up their mice, and they can barely find the buttons to press, because it's absolutely stressful. (suspense music) It doesn't matter what it is, it could be horse racing, it could be car racing, it could be mouse racing.

If you have an ounce of competitiveness in you, you would want to win, right? - Just like a real mouse, a Micromouse must be completely autonomous. No internet connection, no GPS or remote control and no need to push it to take it off. You have to fit all your computers, motors, sensors and power supply in a frame that is no larger than 25 centimeters in length or width. There is no limit on mouse height, but the rules do not allow climbing, flying, or any form of combustion, so rocket propulsion, for example, is out of the equation. (audience applauding) (announcer chattering) The maze itself is a square about three meters on each side, subdivided by walls into corridors only 18 centimeters wide.

And in 2009, the mid-size Micromouse category was introduced, with mice less than 12 1/2 centimeters on a side and paths just nine centimeters wide. The final layout of the maze is only revealed at the beginning of each competition, after which competitors cannot change the code on their mice. (announcer speaking in Japanese) (audience applauding) The three big competitions, the APEC in Japan, Taiwan and the US, typically limit the time the mice spend in the maze to seven or 10 minutes, and the mice are only allowed They allow five races from start to finish. - So if you spend a lot of time searching, that's a penalty. - Makes sense.

So the strategy for most Micromice is to spend their first race carefully learning the maze and finding the best path to the goal, without wasting too much time. They then use the remaining attempts to run along that path and achieve the shortest running time possible. (audience applauds) Solving a maze may seem simple enough, although it is important to remember that, with only a few infrared eye sensors, the view from inside the maze is much less clear than what we see from above. Still, you can solve a maze with your eyes closed. If you simply place a hand along a wall, you will eventually reach the end of the most common mazes.

And that's exactly what some of Micromouse's initial competitors realized as well. And after a simple wall-following mouse took home the gold in the first final, the maze goal was moved away from the edges and free-standing walls were added, which would leave a simple wall-following mouse searching for always. Your next instinct might be to run through the maze, taking note of each fork in the road. Whenever you reach a dead end or loop, you can go back to the last intersection and try a different path. If your last left turn took you nowhere, you would return to that intersection and turn right instead.

You can think of this strategy as one a stubborn mouse might use: run as deep as it can into the maze and return only when it can go no further. This search strategy, known as depth-first search, will eventually lead the mouse to the goal. The problem is that it may not be the shortest path, because the mouse only returns when necessary, so you may have missed a shortcut you never tried. The brother of this search algorithm, breadth-first search, would find the shortest path. With this strategy, the mouse travels along a branch of an intersection until it reaches the next, and then returns to check the path it missed, before moving to the next layer of intersections.

So the mouse checks every option it reaches, but all that backtracking means you re-execute routes dozens of times. At this point, even searching the entire maze usually takes less time. So why not just do that? A meticulous mouse could search all 256 cells of the maze, testing every bend and corner to make sure it had definitely found the shortest path. But it is not necessary to search so thoroughly. Instead, the most popular Micromouse strategy is different from all of these techniques. It is a search algorithm known as flood filling. This mouse's plan is to make optimistic trips through the maze—so optimistic, in fact, that on his first trip, his map of the maze has no walls at all.

They simply plot the shortest path to the goal and leave. When their optimistic plan inevitably hits a wall that wasn't on their map, they simply mark it and update their new shortest path to the goal. Running, updating, running, updating, always in a straight line towards the goal. Under the hood of the algorithm, what the Micromouse marks on its map is the distance from each square of the maze to the goal. To travel with optimism, the mouse follows the trail of decreasing numbers until it reaches zero. Every time they hit a wall, they update the numbers on their map to reflect the new shorter distance to the finish line.

This strategy of following the numerical path of least resistance gives the flood filling algorithm its name. The process is similar to flooding the maze with water and updating the values ​​based on the flow. Once the mouse reaches the goal, it can pave the path it took and find a solution to the maze. However, you can look back and imagine an even shorter, unexplored path you could have taken. The mouse may not be satisfied that it has found the shortest path yet. While this algorithm is not guaranteed to find the best path on the first pass, it takes advantage of the fact that Micromices need to return to the beginning to begin their next run.

So, if the mouse considers its return as a new trip, it can also use the return trip to search the maze. Between these two attempts, both optimized to find the shortest path from start to finish, the mouse will most likely figure it out, and will have done so efficiently, often leaving irrelevant areas of the maze completely untouched. Flood filling offers a clever and practical way for Micromice to find the shortest path through the maze. Once there was a clear strategy for finding the shortest path, and once the microcontrollers and sensors needed to implement it became common, some people believed that Micromouse had run its course.

As an article published in IEEE put it: "By the late 1980s, the Micromouse contest had survived. The problem was solved and presented no new challenges." (people chatting) At the 2017 Japan Micromouse Competition, the bronze and silver mice found the shortest path to the finish line, and once they did, they were able to travel it in just 7.4 seconds. (Audience applauds) But Masakazu Utsunomiya's winning mouse, Red Comet, did something completely different. This is the shortest path to the goal, the one that everyone took. This is the path the Red Comet took. It is 5 1/2 meters longer. This is because Micromice don't actually look for the shortest path, but rather the

fastest

path.

And Red Comet's search algorithm discovered that this path had fewer turns to slow it down. So even if the path was longer, it could end up being faster. So he took that risk. (announcer speaking in Japanese) (audience applauding) - He won by 131 milliseconds. (upbeat music) Different routes in the competition are now more common than not, and even reaching the finish line remains difficult, whether due to a mysterious algorithm or a quirk of the physical maze. (audience laughing) - The corner, it's a bit like a... Wow! (commentator speaking in Japanese) - Micromice don't always behave as you would expect. (competitor speaking in Japanese) (upbeat music) 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 engines. Their intelligence came from how the mouse's brain and body interacted. - It turns out that

solving

the maze is not the problem. It was never the problem, was it? But it's really about navigation and going fast. - Every year, robots become smaller, faster and lighter. There is still a lot of innovation left. And there's a small group of devotees in Japan busy building a quarter-sized Micromouse that would fit on a quarter. (commentator speaking in Japanese) - Almost 50 years later, Micromouse is bigger than ever. (commentator speaking in Japanese) (audience applauding) - The competitions before seemed resolved at first glance.

The high jump was an Olympic sport since 1896, and competitors perfected their jumps using variations such as the scissors, western twist, and straddle over decades, with diminishing returns. But once foam padding became standard in competition, Dick Fosbury rewrote the sport in 1968 by becoming the first Olympic athlete to vault the pole backwards. Now almost all high jumpers do what is known as the Fosbury flop. If Micromouse had really stopped in the 1980s, the competition would have missed out on its own Fosbury flops, two innovations that completely changed the way Micromice worked. After all, a lot can change in a sport where competitors can work on any improvements they can imagine.

Fosbury's first failure was one of the first innovations at Micromouse and had nothing to do with technology. It was simply a way of thinking outside the box, or rather, breaking out of the box. All the mice used to turn corners like this. (micromouse hum) But everything changed with the Mitee 3 mouse. - So Mitee Mouse 3 implemented diagonals for the first time. (people chatting) And it turned out to be a much better idea than we actually thought. And because it's cool, maze designers now often put diagonals in the maze. So, you know, you might end up with a maze where it never appears, but most of the time it's actually a benefit. - To achieve diagonals, the mouse chassis had to be reduced to less than 11 centimeters wide, or only five centimeters for a medium-sized Micromouse.

The mouse sensors and software also had to be changed. When running between parallel walls, all you have to do is keep the same distance between the left and right infrared readings. But a diagonal requiresa completely new algorithm, one that essentially guides the mouse as if it had blinders on. - Normally, if you go along the side of a wall, or something, most of the time you can see the wall all the time. And that helps guide you and know when you're getting off. But in the diagonal situation, you just see these walls coming towards you. - And if you veer even slightly off course, snagging a corner is much less forgiving than sliding into a wall.

Diagonals continue to be one of the biggest sources of accidents in today's competition. But in exchange, an irregular road of curves transforms into a narrow straight. - Oh! Oh! (audience applauding) (audience applauding) (audience applauding) - Today, almost all competitive Micromouses are designed to take this risk. Cutting diagonals opened up space for even more ideas. At almost the same time, the mice applied similar turning strategies. Instead of stopping and turning right twice, a mouse could move with a single U-turn motion. And once the possibility of diagonals was added, the total number of possible turns opened up exponentially.

The maze was no longer just a network of square hallways. With so many options to weigh, figuring out the best path became more complex than ever. But the reward was dramatic. What was once a series of stops and starts could now be a single, fluid, meandering movement. The way Micromice imagined and moved through the maze had completely changed. (audience applause) The technology available has also improved over the years. The tall, unwieldy arms used to find walls were replaced by a smaller array of infrared sensors on board the mouse. Precise stepper motors were replaced with continuous DC motors and encoders. - DC motors offer more power with less size and weight, and that's why we were interested in doing it.

Then you have to have a servo. It is actually necessary to have feedback on the motor for it to function properly. - Gyroscopes added an extra sense of orientation. It's like a compass, if you had this with you. - They emerged thanks to mobile phones, actually. So technology provides people with things that didn't exist before. All turning is done based on the gyroscope rather than counting wheel pulses, because it is much more reliable. - But even with all the mechanical improvements, the Micromice's biggest physical problem was not solved for decades. One thing you'll see almost every competitor have in their hand is a roll of duct tape.

Once you know how to look for it, you'll see it everywhere. This tape is not for repairs or reattaching dropped parts. It is to collect dust particles from the wheels between rounds. With the speed and precision with which these robots operate, that small change in friction is enough to ruin a race. If you want to turn while driving fast, you need centripetal force to accelerate you through the turn. And the faster you move, the more strength you'll need to stay 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 interface friction between the tire and the road surface.

That's why the circuits have inclined curves. Steep angles help cars turn with less friction, because some of the normal force now aims to contribute to the required centripetal force. If the banked turn is steep enough, cars can make the turn without any friction. The internal component of the normal force alone is sufficient to provide the centripetal force necessary to maintain heading. (upbeat music) Micromice are no different and don't have stacked turns to help. As they became faster and faster, in 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 sliding into a wall or tipping over.

But unlike racing cars, there was nothing in the rules to prevent Micromouse's competitors from

solving

this problem by designing an entirely new mechanism. Micromouse's second failure at Fosbury was almost considered a trick when mouse Mokomo08 used it for the first time in competition. You may be watching the video to try to see it, but you won't. Instead, it's something you'll hear. (Micromouse whirring) That's not the mouse revving its motors. It's spinning a propeller. And while flying over walls is against the rules, there's nothing in the rules that prevents a mouse from hoovering itself to the floor to avoid slipping. -Dave Otten was the first person I saw put a fan on a mouse, but he used a ducted fan, and I think he was really looking for some kind of reaction force, you know, knocking the thing down.

It had a skirt around it, but it wasn't very effective. But forgive me for saying this. The idea is to let in as little air as possible. And just like your vacuum cleaner, when you block it, the motor discharges and speeds up, so the current drops. But if you let too much air in, the current is too high. And these are just quadcopter motors and they draw a lot of current. - On the Micromouse scale, a vacuum fan, often simply constructed from portable drone parts, is enough to generate a downward force five times the weight of the mouse.

Wow. Well. That is amazing. So how much does the car really weigh? - About 130 grams. And if you listen, I don't know if you'll hear it on your microphone, but- (engine whirring) - Oh, yeah. - you can hear the engines slow down and load. - With so much friction, Micromice today can turn corners with a centripetal acceleration close to six G. That's the same as F1 cars. (engines revving) Once almost everyone equipped fans, the added control allowed builders to exceed the speed limit in Micromice. - When allowed, it will out-accelerate a Tesla Roadster, but not by much. (Derek laughs) - And they can move at up to seven meters per second, faster than most people can run. (audience laughing) (micromouse whirring) (audience applauding) Every feature that is now standard on the modern Micromouse was once an experiment, and Fosbury's next flop might not be far away.

The first four-wheeled Micromouse to win the All Japan competition did so in 1988, but it took another 22 years for the winning mouse to grow larger and lose appendages before four-wheeled mice became the norm. As Micromice continues to experiment with six- and eight-wheel designs, omnidirectional movement, and even computer vision, who knows what the next paradigm shift will be? - Your time in the maze actually begins only when you leave the starting square, so you are not penalized for any of this time. - But if you want to start with Micromouse, you don't need to worry about the number of wheels or the aspiration fans, or even the diagonals. - In my opinion, it's the perfect combination of all the major disciplines you need for robotics, engineering and programming, embedded systems, all in one accessible package that you can do in your living room, and you don't need a lab to run it.

You come because you're curious and then you think, "I could do that. It doesn't seem that hard." And then you're doomed, really. If it absorbs you, it becomes quite a journey. (commentator speaking in Japanese) (audience applauding) - At its core, Micromouse is simply about a mouse trying to solve a maze. However, almost 50 years later, it is a simple problem that is a good reminder that there are no such things as simple problems. ♪ Micromouse, it's for the taking ♪ ♪ Micromouse, it's here and now ♪ ♪ Take the opportunity and start creating ♪ ♪ Micromouse, it'll show you how ♪ (logo beeps) - If you want to build your own Micromouse, you probably need to design parts using a 3D CAD program like Onshape, the sponsor of this video.

Onshape is a modern CAD plus PDM system designed for businesses and completely free for manufacturers and hobbyists to use. Any serious hardware product needs precise design to be successfully manufactured in the real world, from a Micromouse model like this to a professional V2 engine model like this. Unlike traditional CAD programs, which are installed locally, Onshape was built entirely in the cloud, allowing engineering and design teams to collaborate like never before. Onshape allows you to work together in real time on the same design with multiple users, just like Google Docs. This completely eliminates the need to send and receive large files via email and trying to keep track of who has the latest version, whether V2 or V22.

With Onshape, agile methodologies that are common in software development are now being adopted in hardware development to enable companies to create better products faster. Onshape is not only great for businesses, but also for open source projects or just working on designs with your friends. Again, it's completely free for hobbyists, so you can try it out as much as you want at onshape.pro/veritasium. You can take Onshape with you wherever you go. You don't need a powerful desktop or a specific operating system to run it. Whether you're on a Mac or PC, or even just on your phone, you can easily use Onshape.

So to get started, register for free at onshape.pro/veritasium. I want to thank Onshape for sponsoring this video and I want to thank you for watching it.