Introduction to Autonomous Robotics: Maze Solvers - 180D-FW-2023/Knowledge-Base-Wiki GitHub Wiki

Sections:

  • Introduction
  • History of Micromouse
  • Fundamentals of Maze-Solving Algorithms
  • Algorithm Examples
  • Design and Engineering of Micromouse Robots
  • Machine Learning and AI in Micromouse Robots
  • Challenges and Future Directions
  • Conclusion

Introduction

This article is intended to thoroughly explain the concept of Micromouse robots.

Micromouse robots are small, intelligent vehicles designed to find the most efficient path through a maze, unaided. They’re a marvel of engineering; creations that fuse mechanical design, electronic circuitry, and computer algorithm development to create a machine capable of navigating incredibly complicated labyrinths.

On top of being able to even complete these complex processes in the first place, current Micromice are incredibly quick - today’s world record in a Micromouse competition is held by Ng Beng Kiat, whose Micromouse solved its maze in merely 3.921 seconds!

worldrecordimage

Reference: https://singaporerecords.com/fastest-robotic-mouse-racer/

Even though this current technology is extremely impressive, these autonomous robots had to go through years and years of development to get to the point of modernity. In order to understand the ins and outs of Micromouse robots, we must first understand the history behind them.

History

Some time after the concept of Micromouse originated at an IEEE (Institute of Electrical and Electronics Engineers) conference in New York, the first legitimate Micromouse competition was held in 1980, placing its origins back in the mid-20th century.

After the first competition, the concept exploded. Micromouse events soon gained international popularity, most notably in the United Kingdom, United States, Japan, and throughout other parts of Asia. Iteration after iteration evolved the technology significantly. Now, thanks to the advances over the years, modern Micromouse competitions showcase the absolute cutting edge in sensors, microcontrollers, and artificial intelligence.

Design and Engineering of Micromouse Robots

Generally, any Micromouse will consist of the same essential subsystems: infrared and/or ultrasonic sensors detect walls, helping the robot navigate. The microcontroller processes sensor data to make decisions. Motors execute these decisions, and the power supply ensures the robot can operate throughout its journey.

A Micromouse robot's true capabilities is often determined by its components. Every substandard part can cost valuable seconds- a higher quality IR LED or a better tuned motor can easily be the make or break for a winning competition time.

It’s not only components- material choice matters as well, especially when it comes to higher level competitions, so lightweight materials and compact designs that enhance speed and maneuverability are key. The most successful Micromice tend to cleanly fuse electronic components together with clever mechanical design.

Reference: https://globaltronic.pt/en/product/micromouse-kit/

Fundamentals of Maze-Solving Algorithms

Thus far, we’ve looked at the development of Micromouse technology largely in terms of the physical- the sensor technology, the processors we use, the creative mechanical design. However, no advance in technology could make a Micromouse capable without its essentials: in order to function, the mice need a brain. In other words, they need an algorithm.

The navigation algorithm that lies at the core of any Micromouse robots’ operation is, simply put, a rule-based system engineered specifically to solve mazes. Although simple in theory, these algorithms can get extremely sophisticated. Below, we will discuss some of the most popular maze-solving algorithms used by autonomous robots: DFS (Depth-First Search), BFS (Breadth-First Search), and Flood Fill.

Depth-First Search (DFS):

As one might expect, Depth-First search does exactly that- it explores a tree/graph by going as far as possible along each branch, or to the maximum depth possible, before backtracking. For each branch, the algorithm makes its way down, checking every node, and continues until either it finds its target node or the end of the branch is reached. If said end is reached without finding a node that meets the search criteria, the algorithm backtracks, trying again with the next branch. This process then continues until either the target node is found or all the nodes in the tree/graph have been checked.

We typically use a stack data structure to implement DFS (although recursion can be used as well). Since stacks are LIFO (Last-In-First-Out), they most effectively support the DFS logic of traversing all the way down one branch before changing to another.

Breadth-First Search (BFS):

In contrast, BFS explores a graph/tree level by level. The algorithm starts from the root node and examines all its neighbors, For each of those nodes, the algorithm will explore their unvisited neighbors- so on and so forth. BFS can be visualized as a sort of ripple effect, beginning from the root node and reaching out to all neighboring nodes layer by layer. Note that since BFS processes nodes in the order that they are encountered, we are ensuring that the earliest discovered paths are the shortest ones.

We typically use a queue data structure to implement BFS. Since queues are FIFO (First-In-First-Out), they most effectively support the BFS logic of checking all the nodes in the order that they were encountered, or level-by-level exploration.

A Quick Look at DFS vs BFS:

Reference: https://www.boardinfinity.com/blog/difference-between-bfs-and-dfs/

Flood Fill:

We would be remiss if we were to discuss the popular algorithms used in autonomous maze-solvers without mentioning Flood Fill. Flood Fill is an extremely popular algorithm due to its accessibility and ease of implementation- and it is commonly used in collegiate projects, Micromouse included.

Flood Fill works conceptually much like BFS- beginning with a target node, the algorithm expands outward, checking and subsequently filling adjacent nodes should they meet a specific criteria. Generally speaking, it’s a pretty versatile method of determining details about the area connected to a given node, which makes it quite useful for maze discovery.

Using information gathered about the presence of surrounding walls, a Micromouse using Flood Fill can assign values to each cell in the maze, representing their Manhattan distance. (Manhattan distance is, in essence, the grid-based distance between two points, as found when navigating with only straight segments and right angles.)

This value assignment consequently creates a gradient that guides the robot to its destination, as it can simply follow a sequence of increasing/decreasing values.

Example of Flood Fill Assignment:

floodfillimage

Reference: https://www.researchgate.net/figure/Flood-Fill-Algorithm-sample-maze-solved_fig1_315969093

Although these algorithms tend to reign supreme in terms of popularity, they are not the only options for our autonomous maze-solvers. Algorithms like Dijkstra’s and the A* Search Algorithm integrate weighted graphs and heuristic functions, respectively, allowing for even further developments in path selection.

Machine Learning and AI in Micromouse Robots

Of course, as we discuss the algorithms that determine how these robots navigate, we have to acknowledge the growing power of artificial intelligence and machine learning in the field. The inclusion of AI and ML has truly revolutionized Micromouse robots- they are now capable of learning from past experiences, improving further over time. After implementing neural networks and reinforcement learning, we are seeing modern robots adapting to all sorts of different mazes with unexpected proficiency. With the power of AI, the possibilities in this domain seem truly endless.

Challenges and Future Directions

Despite all the progress made, there are still plenty of challenges remaining in the development of Micromice.

A major battle- if not the biggest one- faced in the further development of Micromouse deals with miniaturization. How can we further compress these robots without compromising power? Not only that, what is to be done about the high costs of sophisticated sensors? Development cannot continue without testing, but the price is difficult to pay. Due to this, simulation is playing a growing role, since it allows for extensive testing without requiring (often expensive) physical prototypes.

Conclusion

Now, all that being said, the development continues. Advancements in robotics and AI are creating even more capable and autonomous Micromouse robots. Micromouse robots exemplify the rapid advancement in robotics, encapsulating the challenges- and also the difficulties- of the field. Their continued evolution is relevant not only to competitions, but also greatly contributes to the broader landscape of robotics, with exciting implications for much wider spread technology like autonomous vehicles. These little machines keep pushing the envelope even further, paving the way for far-reaching, incredible technology in our future.