Maze Solving Robot

How do you solve mazes?

There are essentially 2 stages. The initial step is to navigate through the maze and locate its conclusion. The next step is to enhance the route so that your robot can navigate the maze again flawlessly, avoiding all dead ends. How does the robot locate the maze’s endpoint?

I employ a method known as the left hand on the wall. Picture yourself in a labyrinth as you consistently trace your left hand along the wall. Accomplishing this task will eventually lead you to escape a maze without any loops. This guide will specifically focus on mazes that do not have any looping paths. This algorithm of placing the left hand on the wall can be simplified to these basic conditions:

– If you are able to make a left turn, feel free to do so.

– if you are able to keep driving in a straight line, then proceed straight ahead.

If you are able to make a right turn, then proceed with turning right.

– When faced with a dead end, simply reverse direction. This is a crucial decision-making process for the robot at intersections. An intersection is a point within the maze where you can choose to change direction. If the robot fails to turn when presented with the chance to turn, it is viewed as continuing in a straight path. Every action made at a junction or while changing direction must be remembered.

L = left turn
R= right turn
S= going straight past a turn
B= turning around

So let us apply this method to a simple maze and see if you can follow it. View the photos to see this method in action.
The red circle will be the robot.

As you can see in the photos for this example, the final path is LBLLBSR.

Alright, you now have a route. How does the robot convert “LBLLBSR” into the right path in this situation? Let’s examine the right course of action. Examine the pictures to find the right route.

The ultimate accurate route is SRR.

We need to change our direction from LBLLBSR to the correct path, which is SRR. We begin by examining our mistakes. A “B” shows the robot changed direction, signaling it took the incorrect route. In order to improve the route, we need to eliminate the “B” through substitution.

Let’s examine the initial 3 steps in the route “LBLLBSR”. These actions are known as “LBL”.

That movement appears similar to the picture. Instead of making two left turns and then turning around, the robot should have proceeded straight ahead. Therefore, it can be stated that LBL equals S. This replacement is utilized by the robot to enhance the route. This is just one instance, however, here is the complete roster: LBR.

= B
LBS = R
RBL = B
SBL = R
SBS = B
LBL = SYou may not come across all of these when maze solving, but they are required when optimizing the path. Some even put “B” back into the path. This is required to further optimize the path correctly. You can figure out why for yourself or just trust me.

Lets optimize our path now that we know how to:
Path = LBLLBSR
LBL = S so our new path would be: SLBSR
We also know LBS = R so our new path would be: SRR
As you can see we got the path that we were looking for.

My robot optimizes the path as it travels. The path is stored in an array and every time it goes to store a new move, it checks to see if the previous move was a “B”, if it was then it optimizes the path. You need to know at least 3 moves to optimize the path: The move before and after the turn around (and the turn around itself).

Here is another example.

Using the left hand on the wall algorithm, here is the path the robot would take:
LLLBLLLRBLLBSRSRS

Now here is the process of shortening that path:
LL(LBL = S)LL(RBL = B)(LBS = R)RSRS

The new path would be:
LLSLLBRRSRS

Continue shortening it until all the “B”s are gone:
LLSL(LBR = B)RSRS

The new path would be:
LLSLBRSRS

Continue shortening it:
LLS(LBR = B)SRS

The new path would be:
LLSBSRS

Continue shortening it:
LL(SBS = B)RS

The new path would be:
LLBRS

Continue shortening it:
L(LBR = B)S

The new path would be:
LBS

The final path is:

LBS = R

I want to clarify that your robot doesn’t need to be constructed in the same way as mine. The main thing I notice is that I created and used a laser cutting machine to make a frame for my robot. I’ll upload the AutoCAD file, but that’s pretty much all I can handle. If you cannot laser cut the design, there is no need to fret. If you have an Arduino, identical sensors, and motors, you can make my code function on your robot with minimal modifications. Lately, I assisted someone online who replicated my design but did not include laser-cut components. The code operated on his robot with minimal adjustment.

You can observe in the pictures the design I created and the components I utilized a laser cutter to produce. The components are created using acrylic material measuring .08 inches in thickness. This is available for purchase at The Home Depot.

The third photo displays the lower level in my two-tier chassis plan. The lower level features mounting holes at the back for attaching motors, at the front for attaching the ball caster, a hole for the Arduino, and 2 tabs at the front for the sensor. The lower deck also includes 3 mounting holes for attachment to the upper deck with bolts and spacers.

The upper deck features a sole, spacious opening for routing wires from the battery pack, which is secured with velcro on top, to the electronics located on the lower deck. It has three openings which enable connection to the lower platform as well.

It is a straightforward, space-saving design that enables easy assembly with minimal wiring.

You will see in the next steps how and where the parts fit on.