1This tiny robot mouse can finish this maze in just six seconds.
2...
3Every year, around the world, people compete in the oldest robotics race.
4The goal is simple: get to the end of the maze as fast as possible.
5But competition has grown fierce.
6When somebody saw my design, they said, "You're crazy!"
7Why is there so much tension? What's riding on it?
8Honor? - Honor!
9In 1952, mathematician Claude Shannon constructed an electronic mouse named Theseus that could solve a maze.
10The trick to making the mouse intelligent was hidden in a computer built into the maze itself,
11made of telephone relay switches.
12The mouse was just a magnet on wheels, essentially,
13following an electromagnet controlled by the position of the relay switches.
14He is now exploring the maze using a rather involved strategy of trial and error.
15As he finds the correct path, he registers the information in his memory.
16Later, I can put him down in any part of the maze that he's already explored,
17and he'll be able to go directly to the goal without making a single false turn.
18Theseus is often referred to as one of the first examples of machine learning.
19A director at Google recently said that it inspired the whole field of AI.
2025 years later, editors at the Institute of Electrical and Electronics Engineers, or IEEE,
21caught wind of a contest for electronic mice, or le mouse electronique, as they had heard.
22They were ecstatic.
23Were these the successors to Theseus?
24But something had been lost in translation.
25These mice were just batteries in cases, not robots capable of intelligent behavior.
26But the misunderstanding stuck with them, and they wondered,
27"Why couldn't we hold that competition ourselves?"
28In 1977, the announcement for IEEE's Amazing Micro-Mouse Maze Contest attracted over 6,000 entrants,
29but the number of successful competitors dwindled rapidly.
30Eventually, just 15 entrants reached the finals in 1979.
31But by this point, the contest had garnered enough public interest to be broadcast nationwide on the evening news.
32And just like the rumor that inspired the competition,
33Micromouse began to spread across the world.
34Just like a real mouse, a Micromouse has to be fully autonomous.
35No internet connection, no GPS or remote control
36and no nudging it to help it get unstuck.
37It has to fit all its computing, motors, sensors, and power supply in a frame no longer or wider than 25 centimeters.
38There isn't a limit on the height of the mouse,
39but the rules don't allow climbing, flight, or any forms of combustion,
40so rocket propulsion, for example, is out of the equation.
41The maze itself is a square about three meters on each side,
42subdivided by walls into corridors only 18 centimeters across.
43And in 2009, the half-size Micromouse category was introduced,
44with mice smaller than 12.5 centimeters per side,
45and paths just nine centimeters across.
46The final layout of the maze is only revealed at the start of each competition,
47after which competitors are not allowed to change the code in their mice.
48The big three competitions, All Japan, Taiwan, and USA's APEC,
49usually limit the time mice get in the maze to seven or 10 minutes,
50and mice are only allowed five runs from the start to the goal.
51So if you spend a lot of time searching, that's a penalty.
52So the strategy for most Micromice is to spend their first run carefully learning the maze and looking for the best path to the goal,
53while not wasting too much time.
54Then they use their remaining tries to sprint down that path for the fastest run time possible.
55...
56Solving a maze may sound simple enough,
57though it's important to remember that, with only a few infrared sensors for eyes,
58the view from inside the maze is a lot less clear than what we see from above.
59Still, you can solve a maze with your eyes closed.
60If you just put one hand along one wall, you will eventually reach the end of most common mazes.
61And that's exactly what some initial Micromouse competitors realized, too.
62And after a simple wall-following mouse took home gold in the first finals,
63the goal of the maze was moved away from the edges, and free-standing walls were added,
64which would leave a simple wall-following mouse searching forever.
65Your next instinct might be to run through the maze, taking note of every fork in the road.
66Whenever you reach a dead end or a loop,
67you can go back to the last intersection and try a different path.
68If your last left turn got you nowhere,
69you'd come back to that intersection and go right instead.
70You can think of this strategy as the one a headstrong mouse might use,
71running as deep into the maze as it can, and turning back only when it can't go any further.
72This search strategy, known as depth-first search,
73will eventually get the mouse to the goal.
74The problem is, it might not be the shortest route,
75because the mouse only turns back when it needs to,
76so it may have missed a shortcut that it never tried.
77The sibling to this search algorithm, breadth-first search, would find the shortest path.
78With this strategy, the mouse runs down one branch of an intersection, until it reaches the next one,
79and then it goes back to check the path it skipped, before moving on to the next layer of intersections.
80So the mouse checks every option it reaches,
81but all that backtracking means that it's rerunning paths dozens of times.
82At this point, even searching the whole maze often takes less time.
83So why not just do that?
84A meticulous mouse could search all 256 cells of the maze,
85testing every turn and corner to ensure it has definitely found the shortest path.
86But searching so thoroughly isn't necessary, either.
87Instead, the most popular Micromouse strategy is different from all of these techniques.
88It's a search algorithm known as flood fill.
89This mouse's plan is to make optimistic journeys through the maze,
90so optimistic, in fact, that on their first journey, their map of the maze doesn't have any walls at all.
91They simply draw the shortest path to the goal and go.
92When their optimistic plan inevitably hits a wall that wasn't on their map,
93they simply mark it down and update their new shortest path to the goal.
94Running, updating, running, updating,
95always beelining for the goal.
96Under the hood of the algorithm,
97what the Micromouse is marking on their map is the distance from every square in the maze to the goal.
98To travel optimistically, the mouse follows the trail of decreasing numbers down to zero.
99Whenever they hit a wall, they update the numbers on their map to reflect the new shortest distance to the goal.
100This strategy of following the numerical path of least resistance gives the flood fill algorithm its name.
101The process resembles flooding the maze with water and updating values based on the flow.
102Once the mouse reaches the goal,
103it can smooth out the path it took and get a solution to the maze.
104However, it may look back and imagine an even shorter, uncharted path it could've taken.
105The mouse might not be satisfied that it's found the shortest path just yet.
106While this algorithm isn't guaranteed to find the best path on first pass,
107it takes advantage of the fact that Micromice need to return to the start to begin their next run.
108So if the mouse treats its return as a new journey,
109it can use the return trip to search the maze as well.
110Between these two attempts, both optimized to find the shortest path from start to finish,
111it's extremely likely that the mouse will discover it,
112and the mouse will have done it efficiently,
113often leaving irrelevant areas of the maze entirely untouched.
114Flood fill offers both an intelligent and practical way for Micromice to find the shortest path through the maze.
115Once there was a clear strategy to find the shortest path,
116and once the microcontrollers and sensors required to implement it became common,
117some people believed Micromouse had run its course.
118As a paper published in IEEE put it,
119"At the end of the 1980s, the Micromouse Contest had outlived itself."
120"The problem was solved, and did not provide any new challenges."
121In the 2017, All Japan Micromouse Competition,
122both the bronze-and silver-placing mice found the shortest path to the goal,
123and once they did, they were able to zip along it as quick as 7.4 seconds.
124But Masakazu Utsunomiya's winning mouse, Red Comet, did something entirely different.
125This is the shortest path to the goal, the one that everyone took.
126This is the path that Red Comet took.
127It's a full 5.5 meters longer.
128That's because Micromice aren't actually searching for the shortest path,
129they're searching for the fastest path.
130And Red Comet's search algorithm figured out that this path had fewer turns to slow it down.
131So even though the path was longer, it could end up being faster.
132So it took that risk.
133...
134It won by 131 milliseconds.
135Differing routes at competition are now more common than not,
136and even just getting to the goal remains difficult,
137whether due to a mysterious algorithm or a quirk of the physical maze.
138Micromice don't always behave as you'd expect.
139Micromouse is far from solved,
140because it's not just a software problem or a hardware problem,
141it's both.
142It's a robotics problem.
143Red Comet didn't win because it had a better search algorithm or because it had faster motors.
144Its cleverness came from how the brains and body of the mouse interacted together.
145So it turns out solving the maze is not the problem, right? It never was the problem, right?
146But it's actually about navigation, and it's about going fast.
147Every year, the robots get smaller, faster, lighter.
148There is still plenty of innovation left.
149And there's a small group of devotees in Japan busy building quarter-size Micromouse
150which would sit on a quarter.
151Nearly 50 years on, Micromouse is bigger than ever.
152Competitions have appeared solved at first glance before.
153The high jump was an Olympic sport since 1896,
154with competitors refining their jumps using variations like the scissor, the western roll, and the straddle over the decades, with diminishing returns.
155But once foam padding became standard in competition,
156Dick Fosbury rewrote the sport in 1968
157by becoming the first Olympian to jump over the pole backwards.
158Now almost every high jumper does what's known as the Fosbury flop.
159If Micromouse had indeed stopped in the 1980s,
160the competition would've missed its own Fosbury flops,
161two innovations that completely changed how Micromice ran.
162After all, a lot can change in a sport where competitors can solder on any upgrade they can imagine.
163The first Fosbury flop was one of the earliest innovations in Micromouse,
164and had nothing to do with technology.
165It was simply a way of thinking outside the box,
166or rather, cutting through the box.
167Every mouse used to turn corners like this.
168But everything changed with the mouse Mitee 3.
169So Mitee Mouse 3 implemented diagonals for the first time.
170And that turned out to be a much better idea than we really thought.
171And because it's cool,
172you know, maze designers often put diagonals into the maze now.
173So, you know, you could end up with a maze where it never comes up,
174but most of the time it's actually a benefit.
175In order to pull off diagonals,
176the chassis of the mouse had to be reduced to less than 11 centimeters wide,
177or just five centimeters for half-size Micromouse.
178The sensors and software of the mouse had to change, too.
179When you're running between parallel walls,
180all you have to do is maintain an equal distance between your left and right infrared readings.
181But a diagonal requires an entirely new algorithm,
182one that essentially guides the mouse as if it had blinders on.
183Normally, if you're going along the side of a wall, or something like that,
184most of the time you can see the wall all the time.
185And so that helps you to guide yourself, and you know when you're getting off.
186But in the diagonal situation, you just see these walls coming at you.
187And if you veer even a tiny bit off course,
188snagging a corner is a lot less forgiving than sliding against a wall.
189Diagonals are still one of the biggest sources of crashes in competition today.
190But in exchange, a jagged path of turns transforms into one narrow straightaway.
191...
192These days, nearly every competitive Micromouse is designed to take this risk.
193Cutting diagonals opened up room for even more ideas.
194Around the same time, mice were applying similar strategies to turning.
195Instead of stopping and pivoting through two right turns,
196a mouse could sweep around in a single U-turn motion.
197And once the possibility of diagonals were added,
198the total number of possible turns opened up exponentially.
199The maze was no longer just a grid of square hallways.
200With so many more options to weigh,
201figuring out the best path became more complex than ever.
202But the payoff was dramatic.
203What was once a series of stops and starts could now be a single, fluid, snaking motion.
204How Micromice imagined and moved through the maze had changed completely.
205Available technology was getting upgrades over the years as well.
206Tall and unwieldy arms that were used to find walls were replaced by a smaller array of infrared sensors on board the mouse.
207Precise stepper motors were traded in for continuous DC motors and encoders.
208Gyroscopes added an extra sense of orientation.
209But even with all the mechanical upgrades,
210the biggest physical issue for Micromice went unaddressed for decades.
211One thing you'll see almost every competitor holding is a roll of tape.
212Once you know to look for it, you'll see it everywhere.
213This tape isn't for repairs or reattaching fallen parts.
214It's to gather specs of dust off the wheels in between rounds.
215At the speed and precision these robots are operating,
216that tiny change in friction is enough to ruin a run.
217If you wanna turn while driving fast,
218you need centripetal force to accelerate you into the turn.
219And the faster you're moving, the more force you need to keep you on the track.
220The only centripetal force for a car turning on flat ground is friction,
221which is determined by two things,
222the road pushing up the weight of the car, or the normal force,
223multiplied by the static coefficient of friction,
224which is the friction of the interface between the tire and road surface.
225This is why racetracks have banked turns.
226The steep angles help cars turn with less friction,
227because part of the normal force itself now points in to contribute to the centripetal force required.
228If the banked turn is steep enough, cars can actually make the turn without any friction at all.
229The inward component of the normal force alone is enough to provide the centripetal force required to stay on track.
230Micromice are no different, and they don't have banked turns to help.
231As they got faster and faster, by the early 2000s,
232their limiting factor was no longer speed, but control of that speed.
233They had to set their center of gravity low,
234and slow down during turns to avoid slipping into a wall or flipping over.
235But unlike race cars, there wasn't anything in the rules to stop Micromouse competitors from solving this problem
236by engineering an entirely new mechanism.
237Micromouse's second Fosbury flop was almost considered a gimmick
238when the mouse Mokomo08 first used it in competition.
239You might be staring at the video to try to see it, but you won't.
240Instead, it's something you'll hear.
241That isn't the mouse revving its engines. It's spinning up a propeller.
242And while flying over the walls is against the rules,
243there's nothing in the rules against a mouse vacuuming itself to the ground to prevent slipping.
244At the scale of Micromouse, a vacuum fan, often just built from handheld drone parts,
245is enough to generate a downward force five times the mouse's weight.
246With that much friction, Micromice today can turn corners with a centripetal acceleration approaching six Gs.
247That's the same as F1 cars.
248Once nearly everyone equipped fans, the added control allowed builders to push the speed limit on Micromice.
249When it's allowed to, it will out-accelerate a Tesla Roadster,
250but not for very far.
251And they can zip along at up to seven meters per second,
252faster than most people can run.
253Every one of the features now standard on the modern Micromouse was once an experiment,
254and the next Fosbury flop might not be far off.
255The first four wheeled Micromouse to win the All Japan competition did so in 1988,
256but it would take another 22 years of the winning mouse growing and losing appendages
257before four-wheeled mice became the norm.
258With Micromice still experimenting in six- and eight wheel designs,
259omnidirectional movement, and even computer vision,
260who knows what the next paradigm shift will be?
261But if you wanna get started with Micromouse,
262you don't need to worry about wheel count or vacuum fans, or even diagonals.
263At its core, Micromouse is just about a mouse trying to solve a maze.
264Though, nearly 50 years later, it's a simple problem that's a good reminder,
265there is no such thing as a simple problem.