lbinder
Abstract
The goal of this project was to create an autonomous line maze solving robot with inspiration from the Micromouse maze solving competition. The algorithm of choice for mapping the maze and solving for the shortest distance to the end was the Flood Fill algorithm. Flood fill allows the robot to set and update the distance from any point in the maze to the end as it collects information on walls, dead ends, etc. Once it maps the entire maze, the shortest path is revealed. The implications of such technology extend to areas such as autonomous driving, area mapping, search and rescue, and even teaching. To complete my task, I utilized a modified Pololu 3pi robot with optical encoders and high power gearmotors. I used the Arduino programming language and software to code the 3pi. I designed my own line maze, a 16 x 12 grid with 3” x 3” grid squares. My goal was to traverse this maze within 15 seconds. The flood fill code is currently a work in progress. The provisional code uses a left wall following algorithm which allows the robot to solve mazes without infinite loops.
Background
The goal of my project was to create a robot that is capable of mapping out an unknown maze and then navigating the shortest possible path through the maze in the least amount of time. The idea for this project was based off of the Micromouse competition, and the robot and maze were designed and built with the secondary goal of following Micromouse competition regulations so that the robot could theoretically compete. Micromouse is an event in which small, mice-like robots are placed into a 16 x 16 maze and must autonomously map and solve it. Outside of the niche of Micromouse competition, it seems that many robotics hobbyists as well as university research teams are looking at different methods and algorithms for maze mapping and solving. Research into this topic has the potential to be applied to a wide variety of academic subjects as well as everyday life.
Research
The concept of having a robot map a foreign environment can be applied to numerous real world functions. For example, self driving cars need to have the ability to detect shifts in a constantly changing environment and adjust accordingly. While a self driving car does navigate on mapped roadways, the constant variability in factors such as surrounding vehicles, obstructions, and traffic patterns are circumstances in which an autonomous vehicle’s response time and efficiency must be well tested.
Similarly, mapping technology could also be applied to robots that map caves, explore new areas, or perform search and rescue operations. In scenarios such as these, the algorithm in play influences the robot’s ability to create accurate, whole pictures and the speed in which it can do so. It can also affect variables that are not necessarily present or entirely the same as in testing and research, such as the safety of the vehicle.
The idea of finding the shortest possible path is also very important in a variety of fields. The algorithm I initially planned to use, Dijkstra’s algorithm, is not just limited to the function of finding the shortest path. In computer science, optimization of a program is a key component just as traversing the shortest possible distance in a maze is. A faster program means less processing power and less time needed to execute. Translated into real life, optimization of anything equates to a more efficient use of time and resources.
Autonomous technology can additionally be utilized in the classroom setting. There has been a push to introduce amateurs and beginners to the fundamentals of robotics through Micromouse-esque competitions. This type of project combines many skills such as CAD, electronics work, construction, and programming, all while keeping the designer engaged with the desire to perform well in competition as an incentive. However, such technology can expectedly be expensive for schools and learning programs to afford, and...
Read more »
maks.przybylski
Ben Peters
Joanna
Spencer