This video charting the history and development of the MicroMouse competition, together with an explanation of the  strategies for finding the shortest path, opens with footage from the latest All Japan MicroMouse contest. It really deserves its title of "The Fastest Maze-Solving Competition on Earth". Watch and be amazed at the speed of these tiny robots.

It is Claude Shannon who can be credited with the inspiring later generations to engage in maze-running competitions in which small, autonomous robots called navigate a maze as quickly as possible. In 1952 he built relay-controlled mouse, called Theseus after  the legendary king of Athens who escaped the labyrinth of the Minotaur, that could navigate through a maze by storing the maze pattern as relay states. 

Fast forward 25 years and in 1977 IEEE Spectrum ran an announcement of its Micro-Mouse Maze Contest in which a small autonomous device first has to map the maze using a suitable search and optimisation algorithm.  After working out a route it  re-runs the maze as fast as possible and the one with the shortest time is the winner.

Although there were over 6000 entrants to the competition only 15 actually made it to the final in 1979, held in at the National Computer Conference in New York - but thanks to it being broadcast across the US in the evening news shows from NBC and CBS, hosted by Walter Cronkite, interest in MicroMouse quickly spread, not just in the USA but across the world.

Over 40 years later MicroMouse contest are still held with Japan, Taiwan and the United States, where they are held as part of the annual Applied Power Electronics Conference (APEC), being the principal locations.

This video was recorded in Japan at the 2023 All Japan MicroMouse competition and has contributions from David Otten who is the APEC MicroMouse Chair and Peter Harrison of UKMARS (United Kingdom MicroMouse and Robotics society) which organizes events in the UK and whose Micromouse Online website hosts the Micromouse Book, where you can find lots of information pertaining to the rules and how to design and build a suitable MicroMouse. Both of them have participated in, and won, past competitions.

The devices in the first contest, above, seem comically large in comparison to those in recent contests and you'll also notice a change in the mazes over the years. In 2009 at the 30th All Japan Micromouse Competition, the Half-Size Maze was introduced. It has 32x32 cells, which is half the size of the classic 16x16 maze and makes the competition more challenging, as the micromouses have less space to maneuver.

The video discusses the way strategy has evolved over time. Initially there was Wall Following, the strategy used by the winner of the first ever contest but once the goal was moved from a corner to the middle and free standing walls were introduced this was no longer a guarantee of success and this using this strategy you could be searching for ever. The limitations of a Depth First search is that it might not be the shortest path, while a Breadth First search is highly redundant and a Whole Maze search which looks everywhere is too slow.

The strategy advocated to find the shortest path is Flood Fill which uses an "optimistic approach" which is explained in the video. However, the shortest path isn't necessarily the fastest as turning slows the device down and the winner of the 2017 All Japan won by 131 milliseconds by not following the shortest path but took the path that was the fastest to follow.

Over the years technical advances have improved maneuverability and a MicroMouse capable of moving diagonally was a big innovation.

There's lots more in the video and it's all fascinating.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info