From: veritasium
Maze-solving robots have a rich history, beginning with early mechanical and electronic predecessors and evolving into sophisticated autonomous systems. The competition surrounding these robots has continuously pushed the boundaries of their design and algorithms, leading to ongoing innovation.
Historical Inspiration
The concept of intelligent machines solving mazes dates back to 1952, when mathematician Claude Shannon constructed an electronic mouse named Theseus [00:00:48]. The intelligence of Theseus was derived from a computer built directly into the maze itself, composed of telephone relay switches [00:00:58]. The mouse, essentially a magnet on wheels, followed an electromagnet controlled by these switches [00:01:04].
Theseus explored the maze using a “trial and error” strategy and registered information in its memory as it found the correct path [00:01:11]. This allowed it to return to any explored part of the maze and go directly to the goal without false turns [00:01:21]. Theseus is often regarded as one of the earliest examples of machine learning and is credited with inspiring the entire field of AI [00:01:29].
Twenty-five years later, in 1977, a misunderstanding about a Japanese contest for “le mouse electronique” led the Institute of Electrical and Electronics Engineers (IEEE) to launch their own “Amazing Micro-Mouse Maze Contest” [00:01:39]. Although the initial “electronic mice” they heard about were merely batteries in cases, not intelligent robots [00:01:57], the IEEE decided to create a competition for actual intelligent, autonomous maze-solving robots [00:02:03]. This contest attracted over 6,000 entrants [00:02:15] and quickly gained public interest, being broadcast nationwide by 1979 [00:02:27]. This marked the birth of the Micromouse competition, which subsequently spread globally [00:02:36].
Current State and Challenges
Micromouse robots must be fully autonomous, without external connections like internet, GPS, or remote control [00:04:03]. They must contain all their computing, motors, sensors, and power supply within a 25-centimeter frame (or 12.5cm for half-size mice) [00:04:13]. The maze layout is revealed only at the start of each competition, with no code changes allowed afterwards [00:04:59].
Evolution of Mazesolving Algorithms
The evolution of mazesolving algorithms in robotics has seen several stages:
- Wall-Following: Early mice used a simple wall-following strategy [00:06:10]. This was rendered ineffective by moving the goal away from edges and adding free-standing walls [00:06:28].
- Depth-First Search: This strategy involves running deep into the maze, noting forks, and turning back only at dead ends or loops [00:06:55]. While it eventually finds a path, it may not be the shortest [00:07:09].
- Breadth-First Search: This algorithm finds the shortest path by checking every option at each layer of intersections [00:07:19]. However, extensive backtracking means it often takes longer than simply searching the entire maze [00:07:37].
- Flood Fill: The most popular Micromouse strategy, it involves optimistic journeys through the maze, updating a map of distances to the goal as walls are encountered [00:08:03]. The mouse follows decreasing numbers to zero, akin to flooding the maze with water [00:08:46]. This method is efficient and often leaves irrelevant areas untouched [00:09:50].
Despite these advancements, the goal is not always the shortest path, but the fastest. In 2017, the winning Micromouse, Red Comet, took a path 5.5 meters longer than the shortest route but won by 131 milliseconds because it had fewer turns to slow it down [00:10:41]. This highlights that Micromouse is a robotics problem, where the interaction between software (brain) and hardware (body) is key [00:12:08].
Technological Innovations
Significant “Fosbury flops”—innovations that completely changed how Micromice ran—have occurred:
- Diagonals: The mouse Mitee 3 first implemented diagonal movement, which transformed jagged paths into straightaways [00:14:10]. This required smaller chassis designs (less than 11cm wide) and new algorithms to navigate without constant wall feedback [00:14:37]. Today, nearly every competitive Micromouse uses diagonals [00:15:44].
- Sweeping Turns: Instead of stopping and pivoting, mice began using single U-turn motions, contributing to a more fluid, snaking motion through the maze [00:15:57].
- Hardware Upgrades:
- Early tall arms for wall finding were replaced by arrays of infrared sensors [00:16:39].
- Precise stepper motors were exchanged for continuous DC motors with encoders, offering more power in a smaller, lighter package [00:16:46].
- Gyroscopes, thanks to mobile phone technology, provide crucial orientation sensing, making turns more reliable than wheel pulse counting [00:17:02].
- Vacuum Fans: A key innovation for control at high speeds, vacuum fans, often built from handheld drone parts, generate a downward force up to five times the mouse’s weight [00:19:14]. This greatly increases friction, allowing mice to turn corners with centripetal acceleration approaching six Gs, comparable to F1 cars [00:20:45]. This increased control enabled builders to push speed limits, with mice zipping along at up to seven meters per second [00:21:00].
The Future of Micromouse
The challenges and strategies in robotics competitions remain dynamic. Micromouse is far from a “solved problem” [00:12:06]. Every standard feature today was once an experiment [00:21:36]. Ongoing experimentation includes:
- Six- and eight-wheel designs [00:21:57].
- Omnidirectional movement [00:22:01].
- Computer vision [00:22:01].
The competition continues to drive innovation in robotics, combining major disciplines like engineering, programming, and embedded systems [00:22:24]. Nearly 50 years after its inception, Micromouse remains a vibrant field, reminding us that even a “simple problem” can lead to complex and continuous advancements [00:23:19].