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 the constant advancement of robotics-related technology can quickly make robotics kits obsolete. This certainly causes difficulty for schools to update and maintain their robots. For that reason, research is being conducted on how to create a cheaper Micromouse teaching kit geared towards economically disadvantaged students and areas.

Brainstorming

There were multiple objectives that I had set for my project. As I already stated, the overall goal of the project was to create a robot that can map all mazes and solve them by traversing the shortest path from beginning to end. I planned to design my own robot from scratch and wanted to keep the cost of the robot around at most $150. This would be easily doable if I substituted some of the standard components for cheaper items (ex. cardboard wheels), but for the sake of function, I still wanted to use better parts in some areas. I planned to purchase an encoder/wheel set and possibly an IR sensor array. An arduino microcontroller acting as the brain would be available to me in the lab and I could laser cut a chassis using the lab laser cutter. I knew that I would be able to find a suitable chassis design online.

I also planned to design and create my own maze to solve. When considering maze construction, I decided that it would be a more efficient use of time to build a line maze rather than construct a standard walled maze found in Micromouse competitions. For the maze specs, I wanted to make it at least 56” x 44”, which is a 2x2 grid of poster board sheets. I also wanted to make these sheets interchangeable so that I could create more than one maze design. With regard to maze completion time, I was not entirely sure what I should have set the goal for, since I was designing my own maze and there was no precedent run time to compare to. So I decided to just set an arbitrary goal runtime at 15 seconds.

For the programming, I planned to implement Dijkstra’s algorithm as my maze mapper and use nodes to organize the resulting map into a single shortest path to solve the maze. I planned to use the Arduino coding platform and Arduino language (variant of C/C++) in order to accomplish this, since I was already familiar with the program and after some research found that it was actually a quite suitable platform for such projects. Figures 1 and 2 show sketches of my initial design and components.

Design and Creation

The maze was fairly straightforward to build. I used poster board and black electrical tape so the materials costs were minimized. First, I used a pencil and ruler to draw out a grid system on each piece of poster board, with each grid square being 3” x 3”. Then, I erased all unnecessary lines, leaving the layout of the design I created, as seen in Figure 3. The starting position is marked with an “S” and the finishing position is the 3” x 3” box marked with an “F.” The final dimensions of the maze are 16 x 12 grid. I found a tutorial for building line mazes on the website of Pololu Robotics and Electronics which helped me in understanding how to

properly lay down the tape. The final constructed maze can be seen in Figure 4.

Soon after creating my project plan, I reversed my decision to build a robot from scratch. A large part of this decision had hinged on whether or not the encoders I had been planning to purchase would be installable on the Pololu 3pi robot, which had already been built and available for use in the lab. The 3pi had been designed so that it could excel in solving simple line mazes. Features that would be particularly useful for my project included five reflectance sensors for line reading, an LCD screen for easier user interaction, and the customizability of the 3pi to be able to fit encoders. Figure 5 shows in detail the many features of the 3pi.

While the standard 3pi robot was left largely intact, there were some modifications I had to make in order to accommodate the encoders. I replaced the standard 30:1 Micro Metal Gearmotor with the 30:1 Micro Metal Gearmotor HP 6V with Extended Motor Shaft. The extended shaft allowed for me to solder on the encoder and place a 5-tooth gear onto the shaft, which is read by the encoder to calculate turning distance of the wheel. The addition of encoders forced the wheel position further outward from the body of the 3pi. Figure 6 shows the modified 3pi robot. Only

the encoder attached to the left wheel was fully wired and used in this project. Figure 7 shows the specific wiring of the encoder. The white and brown wires attach to the two motor pins (M1 and M2) which allow the motor to run. The red wire connects to the power supply and the black wire connects to ground. The yellow and orange wires are the two data outputs (OUT A and B) for the encoder. They are connected to digital pins PD0 and PD1 on the 3pi robot (not shown in Figure 6 or 7). Figures 8 and 9 diagram an encoder both uninstalled and installed. 

As I began to write the robot’s maze mapping code, I also decided to make a change. I was troubled by the feasibility of actually implementing Dijkstra’s algorithm in Arduino. The algorithm uses data structures such as nodes that I have previously worked with in Java, but not in Arduino. The structure in which code is implemented in Arduino also differs from Java, which affected the ability to use Dijkstra’s algorithm as well. I re-researched effective Micromouse algorithms and decided instead to implement the Flood Fill algorithm. Essentially, flood fill assigns values for all cells based on their distance from the target endpoint. As the robot traverses the maze, it updates the distance of each cell based on newly acquired information about the walls surrounding that cell. Figure 10 demonstrates a small snippet of the actions that a robot takes as it moves through the maze using flood fill algorithm. The initial image shows the distance of each cell to the endpoint, in this case the center, assuming there are no walls in the maze. As walls become known to the robot, they change from light grey to black.

Bill of Materials

Item

Qty.

Unit Price

Total Price

30:1 Micro Metal Gearmotor HP 6V with Extended Motor Shaft

2

$16.95

$33.90

Optical Encoder Pair Kit

2

$8.95

$17.90

Pololu 3pi robot

1

$74.95*

$74.95*

Electrical tape

1

$2.72*

$2.72*

Poster board

4

$0.65*

$2.60*

Total Cost

$132.07*

*estimation

Results

I achieved the majority of my goals either entirely or to some limited degree. My overarching goal of creating a robot that could map mazes and solve them by traversing the shortest path was only partially realized. I was able to implement a more basic algorithm, the left wall follower. However, this algorithm only allowed the robot to solve mazes without loops and lacked any mapping capacity. As a result, the robot could complete the maze when placed in very specific starting locations, but it could not complete the maze from the true starting point. Unfortunately I was unable to successfully implement the flood fill code to the 3pi. I was successful in keeping the cost below $150, with an estimate of around $132. More than half of this cost stemmed from the standard 3pi robot. Had I designed my own robot, I certainly would have been able to decrease the total cost even further. I also accomplished all of my goals regarding maze design and construction. I was satisfied with the complexity of my final maze design, and although I knew it would be difficult to create a perfectly accurate sized and neat maze, my work on that was as much as I could have hoped for. The installation of functional encoders onto the 3pi was an additional success. This seemed to be a choke point in terms of project completion for other similar projects that I found online, so I am glad that I was able to get them working. Although I was not able to extensively test the encoders with maze run throughs, they provided ideal output readings when hooked up to an oscilloscope.

Conclusion

There are various improvements and additions that could be made for this project. The addition of the encoders introduced some issues with motor values for turning because the wheels were pushed further out from the robot body. Also, there was a lack of digital I/O lines on the 3pi itself, so I could only attach one encoder, in this case, the left wheel encoder. This affected my ability to take accurate encoder readings. The Arduino software also posed a challenge as it was difficult to debug my code. The flood fill algorithm could also be improved upon since it returns the shortest path distance wise, but not necessarily time wise. My maze design, however, would not have encountered this type of problem even had the code been functioning. Some other improvements that could be made include implementing flood fill first in Java and then translating into Arduino so I could debug beforehand in the jGrasp software, and create my own robot so that I could have more I/O lines available for customization.