Maze Solving Robot V3

 

This is my third maze solving robot. The two before it never worked the way I wanted them to. I felt that I am now capable of making one that does exactly what I want it to. Read my maze solving tutorial.

Click here to download my code or click here to just view my code.


Maze solving basics:


The robot needs to be programmed with an algorithm that lets it navigate the entire maze or until it finds the end. My robot uses the left hand on the wall technique. This technique says that if at an intersection turn left if you can, else go straight if you can, else turn right if you can, else turn around because you are at a dead end. This algorithm will allow the robot to navigate a maze and find the end of it.


The second part of maze solving is taking the path the robot traveled and shortening it to the correct path to the end of the maze with out traveling down any dead ends. This part of maze solving is a bit trickier. The robot has to memorize the path it travels using the left hand on the wall technique and then shorten that path. The robot memorizes the path by storing each turn as a letter in an array.


The movements get stored as followed:

left turn = “L”

right turn = “R”

turn around = “B”

go straight = “S”


A “B” indicates a mistake in the path taken. A perfect path would not have the robot drive down a dead end and a “B” indicates a dead end was taken. So when shortening the path, the robot looks for these dead ends taken and tries to get rid of them using a few things it is programmed to know. It is programmed with multiple 3 letter sequences that tell it what to replace wrong moves with.


These 3 letter sequences are as follows:


LBR = B

LBS = R

RBL = B

SBL = R

SBS = B

LBL =  S


Some of these sequences are never actually found during the left hand on the wall maze solving algorithm. For instance, SBS (straight, turn around, straight) would never come up during maze solving. However, some of these sequences are needed during the shortening of the path, because they will appear when other parts of the path are removed and replaced.


The maze in the video can be seen below. I will demonstrate the maze solving technique from the starting location indicated by the red circle.


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


So the correct path to get to the end from that location is to turn right. This is the process that the robot uses and it is demonstrated in the video. The difficulty in programming this robot was the fact that it has no encoders and its sensors are in a line. This means that it was hard to keep the robot lined up and many steps had to be taken to have the robot flawlessly identify intersections.




Now onto the construction of the robot:


I designed my robot chassis using AutoCAD. It is made up of 2 plates that bolt together using spacers:


I then brought my design to my high school where we have a brand new laser cutter. This was the first thing ever cut on it. I cut it out of acrylic plastic.

The motors and wheels are the ones from my old maze solving robot. They are available at Pololu.

The top deck gets bolted on with 1” spacers. This deck will hold the battery pack.

The micro-controller is a RBBB Arduino board. The motor controller board is one that I designed. It is a simple L293D motor driver break out board.

The reflectance sensor is from Pololu. It comes with 8 sensors, but 2 of them on the end can be removed to make it a 6 sensor array instead.

As you can see, everything has a place to bolt down including the ball caster and micro-controller.

The robot runs on 4 rechargeable AAA 1.2V 1800mAH batteries. The battery holder gets attached to the top of the robot using velcro. This battery holder has a built in on-and-off switch.

The sensor bolts onto the front tabs of the robot chassis.

Lastly, the sensor is wired to the analog inputs of the micro-controller and power is distributed.

    Update 07/26/11

    I have changed the robot again in order to make a cleaner and simpler design. This change is based around wanting to integrate the two separate boards I had on the previous design into one. I was using a RBBB Arduino and my own motor driver breakout board. That worked, but was not as clean as I wanted it to be.

    So I designed a new PCB. This one is basically an Arduino with a built on motor driver (SN754410). It has only the pins I need broken out so that it can interface with the sensor array and the motors. Another advantage I added to this board was access to the enable pins on the motor driver which I did not previously have. These enable pins are connected to PWM pins on the Arduino so the speed can be controlled. There is also a LED on pin 13 for debugging.

This is what it looked like before the new board:

This is what is looks like after the new board:

    Along with a new board, there is also new code. First off I made it drive faster. The robot is programmed to use the LED to show what it is currently doing. The LED is solid when driving, blinks one sequence when done solving the maze, and another when done driving the shortest path. The robot is also programmed so that it knows when it is placed down after solving the maze and it will then run the shortest path. This way you can take your time placing the robot back down at the starting position where as before it was a timed thing. You can see this in the new video when the LED goes from blinking to solid after the robot is placed down. 

    Update 08/21/11

    Well I changed the PCB again. I am calling this the final change on this robot. There are a few changes on the PCB. The biggest change is I added a 3 pin header for Pololu's boost regulator. This is the same power setup found on their 3pi robot, but I went with the 2.5-9.5v one. I am using it to supply a constant 6v to the motor driver and motors. This constant supply allows me to tweak the program until it is perfect and not have to worry about the robot slowing down due to battery drain. To accommodate for adding the regulator to the board (I did not want to change the PCB size) I moved the LED to the front of the board and used a 3mm one instead of 5mm. Another change I added was I broke out a digital pin next to the analog pins that allows the IR LEDs on the Pololu reflectance sensor array to be controlled. This is possible because the reflectance sensor array has a built on transistor. This could be used to turn them off when not needed and save power.

 

There is a new video at the top you can watch. It uses my new code I wrote which makes it faster. 



(Click here to download the EagleCAD schematic and board files.)