The Fastest Maze-Solving Competition On Earth

0:00 [Derek] This tiny robot mouse can finish this maze in just six seconds.

0:05 (dramatic music) Every year, around the world,

0:13 people compete in the oldest robotics race.

0:16 The goal is simple: get to the end of the maze as fast as possible.

0:20 The person who came second (announcer

0:22 chattering) (people cheering) lost by 20 milliseconds.

0:26 [Derek] But competition has grown fierce.

0:29 When somebody saw my design, they said,

0:32 "You're crazy!"- [Derek] Why is there so much tension?

0:36 What's riding on it?

0:37 Honor?

0:39 Honor (audience applauding) (audience cheering)- [Derek]

0:45 This video is sponsored by Onshape.

0:48 In 1952, mathematician Claude Shannon constructed an electronic

0:52 mouse named Theseus that could solve a maze.

0:55 The trick to making the mouse intelligent was

0:58 hidden in a computer built into the maze itself,

1:02 made of telephone relay switches.

1:04 The mouse was just a magnet on wheels, essentially,

1:07 following an electromagnet controlled by the position of the relay switches.

1:11 [Claude] He is now exploring the maze using

1:13 a rather involved strategy of trial and error.

1:16 As he finds the correct path, he registers the information in his memory.

1:21 Later, I can put him down in any part of the maze that he's already explored,

1:24 and he'll be able to go directly to the goal without making a single false turn.

1:29 [Derek] Theseus is often referred to as one

1:31 of the first examples of machine learning.

1:33 A director at Google recently said that it inspired the whole field of AI.

1:39 25 years later, editors at the Institute

1:42 of Electrical and Electronics Engineers, or IEEE,

1:45 caught wind of a contest for electronic mice,

1:48 or le mouse electronique, as they had heard.

1:51 They were ecstatic.

1:52 Were these the successors to Theseus?

1:55 But something had been lost in translation.

1:57 These mice were just batteries in cases,

2:00 not robots capable of intelligent behavior.

2:03 But the misunderstanding stuck with them, and they wondered,

2:06 "Why couldn't we hold that competition ourselves?" In 1977,

2:11 the announcement for IEEE's Amazing Micro-Mouse

2:14 Maze Contest attracted over 6,000 entrants,

2:18 but the number of successful competitors dwindled rapidly.

2:22 Eventually, just 15 entrants reached the finals in 1979.

2:27 But by this point, the contest had garnered enough

2:30 public interest to be broadcast nationwide on the evening news.

2:34 And just like the rumor that inspired the competition,

2:37 Micromouse began to spread across the world.

2:40 Micromouse, is for the taking♪♪ Micromouse, is here and now♪♪ Take a chance,

2:49 and start creating♪ (upbeat music) (reporter speaking Japanese)- A Micromouse?

2:59 [Group] Micromouse!

3:06 (audience applauding)- Even people in the top two or three,

3:34 you can see them trying to set their mice up,

3:35 and they can barely find the buttons to press,

3:38 because it's absolutely nerve-racking.

3:42 (suspenseful music) It doesn't matter what it was,

3:47 it could be horse racing, it could be motor racing, it could be mouse racing,

3:54 If you have a shred of competitiveness in you, you'd wanna win, right?

4:03 [Derek] Just like a real mouse, a Micromouse has to be fully autonomous.

4:06 No internet connection,

4:08 no GPS or remote control and no nudging it to help it get unstuck.

4:13 It has to fit all its computing, motors, sensors,

4:15 and power supply in a frame no longer or wider than 25 centimeters.

4:21 There isn't a limit on the height of the mouse,

4:24 but the rules don't allow climbing,

4:26 flight, or any forms of combustion, so rocket propulsion,

4:29 for example, is out of the equation.

4:31 (audience cheering) (announcer chattering) The maze itself is

4:42 a square about three meters on each side,

4:44 subdivided by walls into corridors only 18 centimeters across.

4:49 And in 2009, the half-size Micromouse category was introduced,

4:53 with mice smaller than 12 1/2 centimeters per side,

4:56 and paths just nine centimeters across.

4:59 The final layout of the maze is only revealed at the start of each competition,

5:03 after which competitors are not allowed to change the code in their mice.

5:09 (announcer speaking in Japanese) (audience cheering) The big three competitions,

5:21 All Japan, Taiwan, and USA's APEC,

5:25 usually limit the time mice get in the maze to seven or 10 minutes,

5:29 and mice are only allowed five runs from the start to the goal.

5:33 So if you spend a lot of time searching, that's a penalty.

5:38 Makes sense.

5:39 So the strategy for most Micromice is to spend their first run

5:43 carefully learning the maze and looking for the best path to the goal,

5:46 while not wasting too much time.

5:49 Then they use their remaining tries to sprint

5:51 down that path for the fastest run time possible.

5:57 (audience applauding) Solving a maze may sound simple enough,

6:02 though it's important to remember that, with only

6:04 a few infrared sensors for eyes,

6:06 the view from inside the maze is a lot less clear than what we see from above.

6:10 Still, you can solve a maze with your eyes closed.

6:13 If you just put one hand along one wall,

6:16 you will eventually reach the end of most common mazes.

6:19 And that's exactly what some initial Micromouse competitors realized, too.

6:24 And after a simple wall-following mouse took home gold in the first finals,

6:28 the goal of the maze was moved away from the edges,

6:30 and free-standing walls were added,

6:33 which would leave a simple wall-following mouse searching forever.

6:39 Your next instinct might be to run through the maze,

6:41 taking note of every fork in the road.

6:44 Whenever you reach a dead end or a loop,

6:46 you can go back to the last intersection and try a different path.

6:49 If your last left turn got you nowhere,

6:51 you'd come back to that intersection and go right instead.

6:55 You can think of this strategy as the one a headstrong mouse might use,

6:58 running as deep into the maze as it can,

7:00 and turning back only when it can't go any further.

7:04 This search strategy, known as depth-first search,

7:07 will eventually get the mouse to the goal.

7:09 The problem is, it might not be the shortest route,

7:12 because the mouse only turns back when it needs to, so

7:15 it may have missed a shortcut that it never tried.

7:19 The sibling to this search algorithm,

7:22 breadth-first search, would find the shortest path.

7:25 With this strategy, the mouse runs down one branch of an intersection,

7:28 until it reaches the next one,

7:30 and then it goes back to check the path it skipped,

7:32 before moving on to the next layer of intersections.

7:35 So the mouse checks every option it reaches,

7:37 but all that backtracking means that it's rerunning paths dozens of times.

7:42 At this point, even searching the whole maze often takes less time.

7:47 So why not just do that?

7:48 A meticulous mouse could search all 256 cells of the maze,

7:52 testing every turn and corner to ensure

7:55 it has definitely found the shortest path.

7:58 But searching so thoroughly isn't necessary, either.

8:03 Instead, the most popular Micromouse strategy

8:05 is different from all of these techniques.

8:07 It's a search algorithm known as flood fill.

8:11 This mouse's plan is to make optimistic journeys through the maze,

8:15 so optimistic, in fact, that on their first journey,

8:17 their map of the maze doesn't have any walls at all.

8:20 They simply draw the shortest path to the goal and go.

8:24 When their optimistic plan inevitably hits a wall that wasn't on their map,

8:28 they simply mark it down and update their new shortest path to the goal.

8:33 Running, updating, running, updating, always beelining for the goal.

8:39 Under the hood of the algorithm, what the Micromouse is marking on their map is

8:43 the distance from every square in the maze to the goal.

8:46 To travel optimistically,

8:47 the mouse follows the trail of decreasing numbers down to zero.

8:51 Whenever they hit a wall, they update the numbers on their map

8:54 to reflect the new shortest distance to the goal.

8:58 This strategy of following the numerical path of least

9:01 resistance gives the flood fill algorithm its name.

9:04 The process resembles flooding the maze with water

9:06 and updating values based on the flow.

9:10 Once the mouse reaches the goal,

9:12 it can smooth out the path it took and get a solution to the maze.

9:16 However, it may look back and imagine an even shorter,

9:19 uncharted path it could've taken.

9:22 The mouse might not be satisfied that it's found the shortest path just yet.

9:26 While this algorithm isn't guaranteed to find the best path on first pass,

9:30 it takes advantage of the fact that Micromice need

9:32 to return to the start to begin their next run.

9:35 So if the mouse treats its return as a new journey,

9:38 it can use the return trip to search the maze as well.

9:43 Between these two attempts,

9:44 both optimized to find the shortest path from start to finish,

9:47 it's extremely likely that the mouse will discover it,

9:50 and the mouse will have done it efficiently,

9:52 often leaving irrelevant areas of the maze entirely untouched.

9:56 Flood fill offers both an intelligent and practical way

10:00 for Micromice to find the shortest path through the maze.

10:03 Once there was a clear strategy to find the shortest path,

10:06 and once the microcontrollers and sensors

10:08 required to implement it became common,

10:11 some people believed Micromouse had run its course.

10:14 As a paper published in IEEE put it,

10:16 "At the end of the 1980s, the Micromouse Contest had outlived itself.

10:20 The problem was solved, and did not provide any new challenges." (people

10:26 chattering) In the 2017 All Japan Micromouse Competition,

10:30 both the bronze-and silver-placing mice found the shortest path to the goal,

10:34 and once they did, they were able to zip along it as quick as 7.4 seconds.

10:40 (audience applauding) But Masakazu Utsunomiya's winning mouse,

10:43 Red Comet, did something entirely different.

10:47 This is the shortest path to the goal, the one that everyone took.

10:51 This is the path that Red Comet took.

10:54 It's a full 5 1/2 meters longer.

10:57 That's because Micromice aren't actually searching for the shortest path,

11:00 they're searching for the fastest path.

11:02 And Red Comet's search algorithm figured out

11:05 that this path had fewer turns to slow it down.

11:07 So even though the path was longer, it could end up being faster.

11:12 So it took that risk.

11:14 (announcer speaking in Japanese) (audience applauding)-

11:24 [Derek] It won by 131 milliseconds.

11:27 (upbeat music) Differing routes at competition are now more common than not,

11:32 and even just getting to the goal remains difficult,

11:35 whether due to a mysterious algorithm or a quirk of the physical maze.

11:39 (audience laughing)- [Commentator] The corner, it's a little bit like a...

11:42 Whoa!

11:43 (commentator speaking in Japanese)- [Derek] Micromice

11:49 don't always behave as you'd expect.

11:52 (competitor speaking in Japanese) (upbeat music) Micromouse is far from solved,

12:08 because it's not just a software problem or a hardware problem, it's both.

12:12 It's a robotics problem.

12:14 Red Comet didn't win because it had a better

12:16 search algorithm or because it had faster motors.

12:19 Its cleverness came from how the brains

12:21 and body of the mouse interacted together.

12:24 So it turns out solving the maze is not the problem.

12:26 It never was the problem, right?

12:27 But it's actually about navigation, and it's about going fast.

12:31 Every year, the robots get smaller, faster, lighter.

12:34 There is still plenty of innovation left.

12:37 And there's a small group of devotees in Japan

12:41 busy building quarter-size Micromouse which would sit on a quarter.

12:46 (commentator speaking in Japanese)- [Derek] Nearly 50

12:51 years on, Micromouse is bigger than ever.

12:56 (commentator speaking in Japanese) (audience cheering)- [Derek]

13:06 Competitions have appeared solved at first glance before.

13:09 The high jump was an Olympic sport since 1896,

13:12 with competitors refining their jumps using variations like the scissor,

13:16 the western roll, and the straddle over the decades, with diminishing returns.

13:20 But once foam padding became standard in competition,

13:23 Dick Fosbury rewrote the sport in 1968 by becoming

13:27 the first Olympian to jump over the pole backwards.

13:30 Now almost every high jumper does what's known as the Fosbury flop.

13:36 If Micromouse had indeed stopped in the 1980s,

13:39 the competition would've missed its own Fosbury flops,

13:42 two innovations that completely changed how Micromice ran.

13:46 After all, a lot can change in a sport

13:48 where competitors can solder on any upgrade they can imagine.

13:52 The first Fosbury flop was one of the earliest innovations in Micromouse,

13:56 and had nothing to do with technology.

13:59 It was simply a way of thinking outside the box,

14:01 or rather, cutting through the box.

14:04 Every mouse used to turn corners like this.

14:08 (Micromouse whirring) But everything changed with the mouse Mitee 3.

14:13 So Mitee Mouse 3 implemented diagonals for the first time.

14:18 (people chattering) And that turned out to be

14:24 a much better idea than we really thought.

14:26 And because it's cool, you know,

14:28 maze designers often put diagonals into the maze now.

14:31 So, you know, you could end up with a maze where it never comes up,

14:35 but most of the time it's actually a benefit.

14:38 [Derek] In order to pull off diagonals,

14:39 the chassis of the mouse had to be reduced to less than 11 centimeters wide,

14:43 or just five centimeters for half-size Micromouse.

14:46 The sensors and software of the mouse had to change, too.

14:49 When you're running between parallel walls,

14:51 all you have to do is maintain an equal

14:53 distance between your left and right infrared readings.

14:56 But a diagonal requires an entirely new algorithm,

14:59 one that essentially guides the mouse as if it had blinders on.

15:03 Normally, if you're going along the side of a wall,

15:05 or something like that, most of the time you can see the wall all the time.

15:09 And so that helps you to guide yourself, and you know when you're getting off.

15:14 But in the diagonal situation, you just see these walls coming at you.

15:18 [Derek] And if you veer even a tiny bit off course,

15:21 snagging a corner is a lot less forgiving than sliding against a wall.

15:25 Diagonals are still one of the biggest sources of crashes in competition today.

15:30 But in exchange, a jagged path of turns transforms into one narrow straightaway.

15:36 [Commentator] Oh!

15:37 Whoa!

15:38 (audience applauding) (audience applauding)

15:42 (audience cheering)- [Derek] These days,

15:45 nearly every competitive Micromouse is designed to take this risk.

15:50 Cutting diagonals opened up room for even more ideas.

15:53 Around the same time, mice were applying similar strategies to turning.

15:57 Instead of stopping and pivoting through two right turns,

16:00 a mouse could sweep around in a single U-turn motion.

16:04 And once the possibility of diagonals were added,

16:06 the total number of possible turns opened up exponentially.

16:10 The maze was no longer just a grid of square hallways.

16:14 With so many more options to weigh,

16:16 figuring out the best path became more complex than ever.

16:20 But the payoff was dramatic.

16:22 What was once a series of stops and starts could now be a single,

16:26 fluid, snaking motion.

16:27 How Micromice imagined and moved through the maze had changed completely.

16:31 (audience cheering) Available technology was getting

16:37 upgrades over the years as well.

16:39 Tall and unwieldy arms that were used to find walls were

16:42 replaced by a smaller array of infrared sensors on board the mouse.

16:46 Precise stepper motors were traded in for continuous DC motors and encoders.

16:51 The DC motors give you more power for less size and weight,

16:54 and so we were interested in doing that.

16:56 So then you have to have a servo.

16:58 You have to actually have feedback on the motor to make it do the right thing.

17:02 [Derek] Gyroscopes added an extra sense of orientation.

17:06 It's like a compass, if you had this thing with you.

17:09 They came about cause of mobile phones, really.

17:11 so the technology provides people with things which weren't there before.

17:15 All of the turning is done based off

17:18 the gyro rather than counting pulses off the wheels,

17:21 because it's much more reliable.

17:23 [Derek] But even with all the mechanical upgrades,

17:25 the biggest physical issue for Micromice went unaddressed for decades.

17:29 One thing you'll see almost every competitor holding is a roll of tape.

17:33 Once you know to look for it, you'll see it everywhere.

17:36 This tape isn't for repairs or reattaching fallen parts.

17:40 It's to gather specs of dust off the wheels in between rounds.

17:44 At the speed and precision these robots are operating,

17:47 that tiny change in friction is enough to ruin a run.

17:53 If you wanna turn while driving fast,

17:55 you need centripetal force to accelerate you into the turn.

17:59 And the faster you're moving, the more force you need to keep you on the track.

18:03 The only centripetal force for a car turning on flat ground is friction,

18:08 which is determined by two things, the road pushing up the weight of the car,

18:12 or the normal force, multiplied by the static coefficient of friction,

18:16 which is the friction of the interface between the tire and road surface.

18:19 This is why racetracks have banked turns.

18:22 The steep angles help cars turn with less friction,

18:25 because part of the normal force itself now

18:28 points in to contribute to the centripetal force required.

18:32 If the banked turn is steep enough,

18:33 cars can actually make the turn without any friction at all.

18:37 The inward component of the normal force alone is enough

18:39 to provide the centripetal force required to stay on track.

18:43 (upbeat music) Micromice are no different,

18:46 and they don't have banked turns to help.

18:49 As they got faster and faster, by the early 2000s,

18:52 their limiting factor was no longer speed, but control of that speed.

18:56 They had to set their center of gravity low,

18:59 and slow down during turns to avoid slipping into a wall or flipping over.

19:04 But unlike race cars,

19:05 there wasn't anything in the rules to stop Micromouse competitors

19:08 from solving this problem by engineering an entirely new mechanism.

19:14 Micromouse's second Fosbury flop was almost considered a gimmick

19:18 when the mouse Mokomo08 first used it in competition.

19:22 You might be staring at the video to try to see it, but you won't.

19:25 Instead, it's something you'll hear.

19:27 (Micromouse whirring) That isn't the mouse revving its engines.

19:32 It's spinning up a propeller.

19:35 And while flying over the walls is against the rules,

19:38 there's nothing in the rules against a mouse

19:39 vacuuming itself to the ground to prevent slipping.

19:42 Dave Otten was the first person I saw put a fan on a mouse,

19:46 but he used a ducted fan,

19:48 and I think he was really looking at kind of reaction force,

19:51 you know, blowing the thing down.

19:53 He had a skirt around, but it was not terribly effective.

19:58 Forgive me for saying this, though.

20:00 The idea is to let as little air in as possible.

20:04 And like your vacuum cleaner, when you block your vacuum cleaner,

20:07 right, the motor unloads and speeds up, and so the current drops.

20:11 But if you let too much air in, the current's very high.

20:14 And these are just quadcopter motors, and they draw a lot of current.

20:18 [Derek] At the scale of Micromouse, a vacuum fan,

20:20 often just built from handheld drone parts,

20:24 is enough to generate a downward force five times the mouse's weight.

20:29 Wow.

20:30 Okay.

20:31 That's impressive.

20:32 So how much does the car actually weigh?

20:35 About 130 grams.

20:36 And if you listen, I don't know if you'll get it on your microphone,

20:39 but- (motor whirring)- Oh yeah.

20:41 you can hear the motors slow down, and it loads up.

20:45 [Derek] With that much friction, Micromice today can turn corners

20:48 with a centripetal acceleration approaching six Gs.

20:52 That's the same as F1 cars.

20:55 (engines revving) Once nearly everyone equipped fans,

21:00 the added control allowed builders to push the speed limit on Micromice.

21:04 When it's allowed to, it will out-accelerate a Tesla Roadster,

21:08 but not for very far.

21:09 (Derek laughs)- [Derek] And they can zip along at up to seven meters per second,

21:13 faster than most people can run.

21:15 (audience laughing) (Micromouse whirring) (audience

21:31 cheering) Every one of the features

21:37 now standard on the modern Micromouse was once an experiment,

21:40 and the next Fosbury flop might not be far off.

21:43 The first four-wheeled Micromouse to win

21:46 the All Japan competition did so in 1988,

21:49 but it would take another 22 years of the winning

21:52 mouse growing and losing appendages before four-wheeled mice became the norm.

21:57 With Micromice still experimenting in six- and eight-wheel designs,

22:01 omnidirectional movement,

22:02 and even computer vision, who knows what the next paradigm shift will be?

22:07 [Commentator] Your time on the maze actually

22:08 begins only when you leave the start square,

22:11 so he's not penalized for any of this time.

22:17 [Derek] But if you wanna get started with Micromouse,

22:19 you don't need to worry about wheel count or vacuum fans, or even diagonals.

22:24 It is, to my mind, the perfect combination of all the major

22:28 disciplines that you need for robotics

22:31 and engineering and programming, embedded systems,

22:35 all wrapped up in one accessible bundle that you can do in your living room,

22:40 and you don't need a laboratory to run it.

22:45 You come along because you're curious, and then you think, "I could do that.

22:50 That doesn't look so hard." And then you're doomed, really.

22:53 If it sucks you in, it turns into quite the journey.

22:57 (commentator speaking in Japanese) (audience cheering)- [Derek] At its core,

23:15 Micromouse is just about a mouse trying to solve a maze.

23:19 Though, nearly 50 years later, it's a simple problem that's a good reminder,

23:23 there is no such thing as a simple problem.

23:28 Micromouse, is for the taking♪♪ Micromouse, is here and now♪♪ Take a chance,

23:36 and start creating♪♪ Micromouse,

23:39 will show you how♪ (logo beeping)- If you wanna build your own Micromouse,

23:47 you'll likely need to design parts using a 3D CAD program like Onshape,

23:52 the sponsor of this video.

23:54 Onshape is a modern CAD plus PDM system designed for businesses,

23:58 and completely free for makers and hobbyists to use.

24:02 Any serious hardware product needs a precise design

24:05 in order to be successfully made in the real world,

24:07 from a Micromouse model like this one

24:10 to a professional V2 engine model like this one.

24:13 Unlike traditional CAD programs, which are installed on premises,

24:17 Onshape was built entirely in the cloud,

24:19 which allows engineering and design teams to collaborate like never before.

24:23 Onshape allows you to work together in real

24:25 time on the same design with multiple users, just like Google Docs.

24:29 This completely eliminates the need for emailing large files back and forth

24:33 and trying to keep track of who has the most recent version,

24:36 whether it's V2 or V22.

24:39 With Onshape, Agile methodologies that are

24:41 common in software development are now

24:43 being adopted in hardware development to allow

24:46 companies to build better products faster.

24:48 Onshape's not only great for businesses, but also for open source projects,

24:52 or just working on designs with your friends.

24:54 Again, it's totally free for hobbyists, so you can try it out for yourself

24:58 as much as you like at onshape.pro/veritasium.

25:02 You can take Onshape with you wherever you go.

25:04 You don't need a powerful desktop or a specific operating system to run it.

25:08 Whether you're on a Mac or PC,

25:10 or even just on your phone, you can easily use Onshape.

25:13 So to get started, sign up for free at onshape.pro/veritasium.

25:17 I wanna thank Onshape for sponsoring this video,

25:19 and I wanna thank you for watching.