Every year, around the world, people compete in the oldest robotics race: the Micromouse Maze Contest. The goal is simple: to get to the end of the maze as fast as possible. In 1952, mathematician Claude Shannon constructed an electronic mouse, named Theseus, that could solve a maze. This mouse was just a magnet on wheels, essentially, following an electromagnet controlled by the position of the relay switches. This inspired the whole field of AI and 25 years later, editors at the Institute of Electrical and Electronics Engineers (IEEE) announced a contest for electronic mice.
The competition has grown fierce, with participants having to fit all their computing, motors, sensors, and power supply in a frame no longer or wider than 25 centimeters. The maze itself is a square about three meters on each side, subdivided by walls into corridors only 18 centimeters across. In 2009, a half-size Micromouse category was introduced, with mice smaller than 12 1/2 centimeters per side, and paths just nine centimeters across.
The tension is high, as 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. Honor is riding on it, and the person who came second lost by just 20 milliseconds. The competition for the fastest tiny robot mouse is on, and it has become a global phenomenon. The goal of the Micromouse competition is to find that shortest path.
The big three competitions – All Japan, Taiwan, and USA’s APEC – usually limit the time mice get in the maze to seven or ten minutes, and they are only allowed five runs from the start to the goal. Understanding the maze is the key to success, 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, but 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. This is what some initial Micromouse competitors realized, so 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. 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.
The most popular Micromouse strategy, however, is 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. 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 goal of the Micromouse competition is to find that shortest path. The mouse may not be satisfied with its initial attempt to find the shortest path in the maze. This algorithm takes advantage of the fact that Micromice need to return to the start, and so the mouse can use the return trip to search the maze as well. By optimizing both attempts to find the shortest path, the mouse is likely to discover it efficiently, without exploring irrelevant areas of the maze. Flood fill is an intelligent and practical way for Micromice to find the shortest path.
In the past, some people thought that Micromouse had run its course, as the problem was solved and there were no new challenges. However, the 2017 All Japan Micromouse Competition saw bronze- and silver-placing mice find the shortest path to the goal, and Masakazu Utsunomiya’s winning mouse, Red Comet, did something entirely different. Red Comet’s search algorithm figured out that a path with fewer turns was actually faster, even though it was longer.
The problem of Micromouse has not been solved, as it is not just a software or hardware problem, but a robotics problem. Competitors now take different routes to the goal, and even getting to the goal is difficult due to mysterious algorithms or quirks of the physical maze. Furthermore, robots are getting smaller, faster, and lighter, leaving plenty of room for innovation. As a result, Micromouse is far from solved and competitions have seen their own version of the Fosbury flop. That force is generated by the wheels pushing against the ground.But if the wheels don’t have enough grip, the mouse will just skid out and crash into a wall.
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. (Micromouse whirring) But everything changed with the mouse Mitee 3, which implemented diagonals for the first time. (people chattering) And that turned out to be a much better idea than originally thought. Maze designers often put diagonals into the maze now as 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. In order to turn while driving fast, centripetal force is needed to accelerate into the turn. This force is generated by the wheels pushing against the ground. However, if the wheels don’t have enough grip, the mouse will just skid out and crash into a wall. To prevent this, competitors use a roll of tape to gather specs of dust off the wheels in between rounds. Tall and unwieldy arms were replaced by a smaller array of infrared sensors on board the mouse, and precise stepper motors were replaced by continuous DC motors and encoders. Gyroscopes were added to provide an extra sense of orientation, and with the possibility of diagonals, 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. The faster a car is moving, the more force is needed to keep it on the track. This force is known as the centripetal force and is usually provided by friction between the tire and the road surface. To reduce the friction, racetracks have banked turns, which use the steep angles to help cars turn with less friction. In some cases, the inward component of the normal force is enough to provide the centripetal force required to stay on track.
In the case of Micromice, they don’t have banked turns to help them. As they got faster and faster, they had to set their center of gravity low and slow down during turns to prevent slipping into a wall or flipping over. To solve this problem, engineers came up with the idea of a vacuum fan, which is enough to generate a downward force five times the mouse’s weight. This allows Micromice to turn corners with a centripetal acceleration approaching six Gs, faster than most people can run.
Every feature now standard on the modern Micromouse was once an experiment and the next Fosbury flop might not be far off. 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? At its core, Micromouse is just about a mouse trying to solve a maze. If you’re interested in getting started with Micromouse, you don’t need to worry about wheel count, vacuum fans, or diagonals. It is a perfect combination of robotics, engineering, programming, and embedded systems, all wrapped up in one accessible bundle that you can do in your living room. However, it’s important to remember that there is no such thing as a simple problem.
If you want to build your own Micromouse, you’ll need to design parts using a 3D CAD program like Onshape. Onshape is a modern CAD plus PDM system designed for businesses, and is completely free for makers and hobbyists to use. It allows engineering and design teams to collaborate in real time on the same design, just like Google Docs. This eliminates the need for emailing large files back and forth and trying to keep track of who has the most recent version. Onshape is not only great for businesses, but also for open source projects, or just working on designs with your friends.
Sign up for free at onshape.pro/veritasium to try it out for yourself. I want to thank Onshape for sponsoring this video, and I want to thank you for watching.