loading
Picture of Maze Solving Robot
DSC06003.JPG
DSC06001.JPG
DSC06002.JPG
DSC05514.JPG






In this instructable I will be showing you how to build a maze solving robot. This is actually my 3rd attempt at making one. The first was a complete failure. The second was alright at finding the end of the maze, but it could not go back and drive the quickest path. This is my current and 3rd one. It is able to find the end of the maze and then, when put back at the start, drive the shortest path to the end of the maze without going down any dead ends. What surprises me is that it really does not mess up. 

This was just a short introduction, everything else from theory, building, and programming will be explained in later steps. 

Parts list:

General Parts:
  • 3 1in Spacers (Home Depot)
  • Bolts and nuts that fit the spacers (Home Depot)
  • Hook up wire (I use 22 gauge)
  • Solder
  • .100" Female and Male headers
  • Velcro

Tools:
  • Soldering Iron
  • Philips Screw driver
  • Wire Strippers
  • Something to cut the wire with
 
Remove these adsRemove these ads by Signing Up

Step 1: The Theory Part 1

What are the steps In maze solving?
There are basically 2 steps. The first is to drive through the maze and find the end of it. The second is to optimize that path so your robot can travel back through the maze, but do it perfectly with out going down any dead ends.

How does the robot find the end of the maze?
I use a technique called the left hand on the wall. Imagine you are in a maze and you keep your left hand on a the edge of the wall at all times. Doing this would eventually get you out of a non-looping maze. This instructable will only deal with mazes that do not loop back on themselves.

This left hand on wall algorithm can be simplified into these simple conditions:
- If you can turn left then go ahead and turn left,
- else if you can continue driving straight then drive straight,
- else if you can turn right then turn right.
- If you are at a dead end then turn around.

The robot has to make these decisions when at an intersection. An intersection is any point on the maze where you have the opportunity to turn. If the robot comes across an opportunity to turn and does not turn then this is consider going straight. Each move taken at an intersection or when turning around has to be stored.

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.

Step 2: The Theory Part 2

Picture of The Theory Part 2
maze9.tiff
maze10.tiff
Ok so now you have a path. In this case it is "LBLLBSR", but how does the robot change that into the correct path? Well lets take a look at what the correct path would be. Look at the photos for the correct path.

Final correct path = SRR

So we need our path to go from LBLLBSR to the right path that is SRR. To start off we look at where we went wrong. A "B" indicates the robot turned around meaning it went down the wrong path. To optimize the path we have to get rid of the "B" by using some substitution. 
 

Step 3: The Theory Part 3

Picture of The Theory Part 3
Lets look at the first 3 moves in the path "LBLLBSR". These moves are "LBL".
That move looks like the photo.

Instead of turning left then turning around and turning left again, the robot should have gone straight. So we can say that LBL = S.

This substitution is what the robot uses to optimize the path. That is one example but here is the whole list:

LBR = B
LBS = R
RBL = B
SBL = R
SBS = B
LBL = S

You 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).
 

Step 4: The Theory Part 4

Picture of The Theory Part 4
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 

Step 5: The Design

Picture of The Design
DSC05349.JPG
DSC05355.JPG
DSC05353.JPG
DSC05356.JPG
I first want to say that your robot does not have to built in the same manner mine is. The biggest thing I see is that I designed and laser cut a chassis for my robot. I will post the AutoCAD file, but this is about all I can do. So if you are not able to laser cut the design, do not worry. As long as you have some Arduino, the same sensors, and motors then you should be able to get my code to work on your robot with minor changes. Recently I was just helping some one online who made a copy of mine without laser cut parts. The code ran on his robot with little tweaking. 

You can see in the photos the design I made and the parts I used a laser cutter to make. The parts are made from acrylic that is .08" thick. This can be found at The Home Depot.

In the third photo you can see the bottom deck in my 2 deck chassis design. The bottom deck has mounting holes in the rear to bolt the motors on, holes in the front to bolt the ball caster on, a hole to bolt the Arduino on, and 2 tabs in the front where the sensor bolts onto. The bottom deck also has 3 mounting holes that allow it to be connected to the top deck using bolts and spacers.

The top deck has a single, large hole to run wires from the battery pack that is velcroed on top to the electronics on the bottom deck. It also has 3 holes that allow it to be connected to the bottom deck. 

It is a simple, compact design that allows for a simple assembly with minimal wiring.

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

Step 6: Attaching The Motors

Picture of Attaching The Motors
DSC05358.JPG
In this step I simply attached my motors to the top side of the bottom deck using 2 #2 bolts for each one. You can see that I have a little bit of wire attached to each motor, this is because the motors were removed from my previous maze robot. Then attach the wheels by simply pressing them onto the motor shaft. You have to line the "D" shaped shaft up with hole in the center of the wheel.

Step 7: The Arduino

Picture of The Arduino
DSC05360.JPG
DSC05363.JPG
DSC05365.JPG
The first thing you should do in this step is follow the instructions to assemble your RBBB. Those instructions are available here. You will need to snip part of the board off like it says you can do at the bottom of the instructions because you will not be needing it.  "If you dont’ need the power jack or regulator just snip them both off. The easiest way to cut the board is with a large pair of tin snips, but hack saws, jewelers saws and band saws also work well." Do not solder any headers onto the board besides the ones used for the FTDI programming port. 

Next solder a 9 pin strip of female headers on the left side of the board from pins labeled "5v" to "A0". This will mate with the sensor plug later. Solder a 4 pin strip of female headers on the right side of the board from pins labeled "D5" to "D8". These pins will be used to control the motor controller. Finally solder a 2 pin strip of female headers on the front right of the board on the GND and 5V pins. These will supply power to the motor controller.

You can ignore the fact that the motor controller and top deck in the photos. We will get to those.





Step 8: The Motor Controller

I designed a PCB for my motor controller. I have uploaded the Eagle files for you. I used the Dorkbot service to have them made.

If you do not use a PCB, you can always make this simple circuit on some prototype board. 

Now to wire the motor controller up. I have a labeled diagram in the photos. Looking at the last photo, I have the motor on the bottom of the picture connected to the what I have labeled as "M1-A" and "M1-B". These are the outputs of the motor controller for the first motor. I have the motor in the top of the last photo connected to what I have labeled as "M2-A" and "M2-B". These are the outputs of the motor controller for the second motor. 

Now time for the inputs of the motor controller. The Arduino digital output 7 gets wired to what I have labeled as "In 1A". This is the first input of the first motor. The Arduino digital output 6 gets wired to what I have labeled as "In 1B". This is the second input of the first motor. The Arduino digital output 5 gets wired to what I have labeled as "In 2A". This is the first input of the second motor. The Arduino digital output 8 gets wired to what I have labeled as "In 2B". This is the second input of the second motor.

Finally Power and ground get connected to the Arduino's 5v and Gnd pins at the front of the board. In the picture I have the wires attached but not plugged in yet.

As you can see I also went ahead and used some of the #2 nuts and bolts to bolt down the ball caster and Arduino.

Step 9: The Sensor

Picture of The Sensor
DSC05412.JPG
The sensor comes as an array of 8 sensors. There are 2 on the end that can be removed and need to be removed. I used a pair of side cutters to do this. A 9 pin strip of female headers has to be soldered on to the sensor from "GND" to pin "6" of the sensor. I then plugged in a strip of male headers.

These sensors put out an analog voltage based on how much IR light is being reflected back. We can use these to detect the white and black areas on the maze. The sensor outputs a low voltage near 0V if the sensor detects a white surface. The sensor outputs a voltage near VIN if it detects a dark surface. 




Step 10: Attach The Top Deck

Picture of Attach The Top Deck
DSC06002.JPG
DSC06012.JPG
DSC05406.JPG
Bolt the top deck on using the 1in spacers and some bolts and nuts. Use velcro to attached the battery pack to the top deck. Run the leads from the battery pack through the hole in the top deck to the bottom deck. This battery pack already has a built in power switch. 

I found it easiest to leave the screw out of the battery pack. The screw prevents the battery pack from opening, but it has clips that do a good job of keeping it closed without the screw. This allows the batteries to easily be changed by sliding the battery pack open. That means you do not necessarily have to  lift the battery pack off the velcro to change the batteries.

Step 11: Attach and Wire The Sensor

Picture of Attach and Wire The Sensor
DSC05992.JPG
DSC05473.JPG
The sensor array bolts onto the front of the robot using #2 bolts. The pin on the far left of the sensor is GND and gets wired to GND on the Arduino. The second most left pin is Vcc and it gets wired to the 5V pin on the Arduino. The pins labeled 6-1 on the analog sensor get wired to the Arduino analog pins from 5-0. So pin 6 on the sensor gets wired to the Arduino analog pin 5, pin 5 of the sensor gets wired to the Arduino analog pin 4, etc. 

Step 12: Attach Power

Picture of Attach Power
The last thing to do is wire the battery pack to the Arduino. This is done by soldering the wires to the power pins at the rear of the Arduino RBBB. The battery pack has a built in power switch so that is why we can simply solder the power leads straight to the back of the Arduino RBBB. The robot is now complete.

Step 13: The Program

Picture of The Program
I had fun writing this program. Basically there are a few functions that take care of the whole maze solving process. The left hand on the wall function holds the logic to read the sensors and navigate the maze following those rules I outlined earlier. The turning functions are programmed in a fashion so that the robot continues to turn until it sees the black line in which case it then drives forward. There is also a function programmed with a little line following capabilities. It is no PID line following, but does allow the robot to stay on course. This function also controls the robot's speed. 

The more detailed function is that of shortening the path.  A letter is stored at every intersection that indicates the direction the robot took. If the previous letter was a "B", indicating a wrong turn, the function that shortens the path is run to substitute letters in place of those 3 letter sequences outlined earlier.

Finally there is a function that replays the shortest path that the robot calculated when the robot is picked up and then placed back down on the black line. The robot can detect when it is placed back down and then runs the shortest calculated path.

You can view the code here or of course download it on this page. 


AjayD made it!3 months ago

Sir,I had tried working Hard to make this BOT and it turned out pretty well.It took more than a month and a half to make it.Finally made it.I just made minute changes in the code.The results were actually amazing.....here is the link of the vid.....Sorry about the middle finger in the video.Those were for my friends they thought that I couldn't make it.....Would soon write Instructable on it....Thank you for this....

https://drive.google.com/open?id=0B-f1xWTJwulda2Qw...

2015-03-26.jpg20150405_011618.jpg20150405_011629.jpg
patrickmccb (author)  AjayD3 months ago

Nice job!

g.knightz4 months ago

brilliant work you have done.. can this project use only 5 sensor.. help is needed..

g.knightz4 months ago

urgent help... can i use arduino mega, and digital line sensor instead of analog line sensor, also can i use 12v dcmotor for for this project .. i provide link of component that i want to use and need your advice does it can be use..

http://cytron.com.my/p-mdd10a

http://cytron.com.my/p-lss05

frafi13 years ago
hi. I dont get the exact parts which you used. firstly, can i use a arduino uno instead of the one which you used?

can i use regular DC motors? (http://www.rhydolabz.com/index.php?main_page=product_info&cPath=121&products_id=815)

and can i use a motor driver (http://www.rhydolabz.com/index.php?main_page=product_info&cPath=108&products_id=858)

if yes, could you please guide me through the process, it would be of great help.
thanks
sadam khan frafi14 months ago

dear can you send me its complete codes ?

patrickmccb (author)  frafi13 years ago
That motor driver will work, but you do not want that motor. That motor operates at 12 volts. You would have to get a 12v battery pack and regulate it down to 5v for the other parts. I would find a 5v motor.
sadam khan4 months ago

need its complete codding please .

Afroty4 months ago

I can't get the code. Can somebody reupload it please.

To which pin in arduino should we connect the 2nd pin right next to VCC

AjayD5 months ago

Sir,you didn't mentioned the value of the Cap on the Motor Controller Ckt.Also you have not included that in your PCB.Is is not necessary??

Plz give me code with atmega avr 16/32..if it's teotorial i'll highly appreciate that.

Ken908918 months ago

Hey Patrick, the link for the code has expired. Do you think we can get an updated one?

Victora49 months ago

the code not download, please help me!!

Mate can u explain the this value for me ? because im not using the same sensor

(leftCenterReading>200 ||
rightCenterReading>200
why is 200?

nschreiber081311 months ago

Well done. Honestly I have to say that was the best tutorial I could find on a line solving robot but I have one question. Where can I get the code because the code no longer exist anymore. Can you help me out there. Thanks. :)

Nevermind I found the code I believe something must be wrong with my internet. Wish me good luck improving it. :)

ajayo211 months ago

Great Work...
Can i use EEPROM library to store the path?
U didn't used an LCD... So, were u testing the path and storing the character using serial monitor all the time?

petrisor231 year ago

A question:

how is your PWM pin?

petrisor231 year ago

A question:

I have a l298 driver and Arduino Uno V3

can you help me to change the code for my robot?

Crazyspud1 year ago

Hi,

Did you use the 30:1 motor or a different ratio? mMy robot is extremely fast (almost out of control)

Thanks

shary7021 year ago

Hello,

The robot I have built does not move in a straight line i.e. it keeps getting off the black line always.

Can you provide me a solution for this?

robozaurus1 year ago
Hey, nice work. I'm building a maze solver myself but I have one question if I leave the start point and have a L shaped turn to the right, according to the algorithm I can't make left so leaves my 2 options go straight or turn right, my issue is how do I detect if I can go straight or not, since all the sensor are on the same line, they will be both true for right and straight even if in fact i can't go straight because it's a turn. I tought using another sensor ahead, offseted forward from the line sensors array. Waiting for an answer. Thanks :)
patrickmccb (author)  robozaurus1 year ago
You have to drive forward some to see if the line continues on (i.e. you can go straight) only then does the robot make the decision. This motion is kind of disguised because the robot has to drive forward anyway in order to turn in place and end up centered on the line.
Good ideea, will try that. Thank's for the input. :)
jaseel11 year ago
Can u give the PCB layout of ine sensor array?
patrickmccb (author)  jaseel11 year ago
I did not make the line sensor array. You should be able to get more information about it by visiting the Pololu website.
ggonzales1 year ago
Hi. .do you have a "C" program for this? I need it for my school project. We're using ATmega32u4 as our microprocessor. I would be very thankful of you. :)
frafi13 years ago
can i use a arduino uno to do this project..
and could you plz tell more specifically how to make the motor controller?
patrickmccb (author)  frafi13 years ago
Any Arduino should work. The motor controller is outlined on step 8. I provided the schematic in the photos. A schematic is about as clear as I can make it. You can also google for L293D or SN754410, both have the same pinout and are pretty common so there are probably other articles on them.
how to get motor controller from dorkbot..?
plz help me.!
kumaran2012 years ago
Great work!!!! i had a query... Do i have to make changes in your coding When i use Arduino UNO?
can i use cny 70 sensors for this project ?
muno13 years ago
So I wrote some code to test the sensors and I realized that the sensors are not sending any signal back to the microcontroller. So I removed the sensor from the design and I put on 5V from the board and the ground from the board and put the entire senor on a piece of black tape (for it to set all of the outputs to around 5V) then I put an led on each hole and realized that it isnt lighting up at all. Is it an adequate conclusion to come to that the sensor is defective? Thanks again for all the help.
muno13 years ago
I have finished building the design with the same motors and chips you have used except I used an arduino uno. but I am running into issues when I first put in the power both motors go forward about an inch and then stop. I am not sure what to do to solve this issue I have it on a straight black tape maze right now just to see if it is working but I am not sure what could be the issue, is there any way to test if the sensors are working or any way to isolate the problem, and as always thank you for your help.
patrickmccb (author)  muno13 years ago
You can write some code to see if the sensor readings are correct. A common issue I have seen is that people do not put their sensors close enough to the ground. How high off the ground is your line sensor? The optimal distance is 0.125" (3 mm)
muno13 years ago
thank you for this posting first and foremost, I was wondering do I have to have the same gear ratio or will any two motors work (i want to maintain your code to be consistent), also will the same code work on a arduino uno...Thank you very much for your time :)
patrickmccb (author)  muno13 years ago
No matter what motors you use, parts of the code will have to be changed unless you copy my design perfectly. Everything is based off of timing.

The same code will work on an Arduino Uno.
Thanks for the help your designs are well thought out and I appreciate it.
mr.kitux3 years ago
Next step could be to change L for R and R for L so it would come back to the start by itself and then go back to the goal through the shortest path :)
We purchased the motor controller that you suggested (http://www.sparkfun.com/products/9457), and we are now having trouble deciding which holes are corresponding on the two boards (yours that you made personally and the one on Sparkfun). Could you please tell me which hole on your board corresponds to which hole on my board? Such as In-1A = AIN1 or something like that. Thank you.
(an image of my board is attached)
09457-04.jpeg
A couple questions.
1. What happens when you plug it in? Should some kind of software or something pop up? Does it need to be a mac or windows or can in be both?
2. does the arduino need power when it is connected for the program to be put on it?
3. Is there alternate software I need to read this code or put it on the arduino?
patrickmccb (author)  pingpongkid53 years ago
1. Nothing happens when you plug it in. Operating system does not matter.
2. The programming cable supplies power for you.
3. You need to install the Arduino IDE (http://arduino.cc/en/Main/Software) to view the code, edit it, and upload it.
Is there an alternative site to get this board? Or would you happen to have an extra? I need this for a school project and the guy at Dorkbot will not respond to my order. Thanks.
patrickmccb (author)  pingpongkid53 years ago
The board is a very simple circuit which you could make yourself. Really most motor drivers will do. Something like this would work fine http://www.sparkfun.com/products/9457

As for Dorkbot, you have to send him the files and he normally responses in a day or two.
Thank you very much. Is the schematic any different?
patrickmccb (author)  pingpongkid53 years ago
It works the same as a basic motor controller. You have to input power for the chip, the motors, and you have inputs and outputs. You also have pwm speed control.
janoo4u3 years ago
Can we use Arduino UNO instread of freeduino.
If yes then can u explain PIN Diagram.
patrickmccb (author)  janoo4u3 years ago
Yes you can. The connections are the same.
How do you add the code to the arduino? Like how is it connected to the computer?
patrickmccb (author)  pingpongkid53 years ago
Did I leave that out? Sorry, it takes an FTDI Programming cable
Here is one: http://www.sparkfun.com/products/9718
frafi13 years ago
i need help, i think i'd prefer buying the motor driver, so how about this?? http://www.pololu.com/catalog/product/713 and can i use regular DC motors with these??

and could you tell me how to connect this motor driver to the arduino (the same way you told in step 8)and about the DC motor..

plz reply soon, i want to do this robot very soon..
thank you
patrickmccb (author)  frafi13 years ago
That motor driver is fine. It is very similar to connect as the one I used. The AIN1, AIN2, BIN1, and BIN2 are the direction inputs. AO1, AO2, BO1, and BO2 are the outputs that go to the motors. There are also PWM pins which I make use of in my latest code, but I have yet to update the tutorial. You can tie these to +5v to use the controller as I did in this tutorial. Then connect power to the controller and your motor supply voltage to VMOT.

Do not use a regular DC motor. Use a 5-6V gear motor.
rmartin273 years ago
How long does it take to build this robot?
patrickmccb (author)  rmartin273 years ago
If you have all the parts then it is up to how quickly you can solder for the most part. Maybe an hour with all the parts in front of you.
BeFit4 years ago
Great work!
jobard4 years ago
What happens if after the first recognizing run, you place it in a different start location?
patrickmccb (author)  jobard4 years ago
It would not work properly. It is meant to solve it from the same starting position. It has to be reset if you want it to solve it from another.
Nice. How do you reset it if you want it to go the long way agaibn AFTER it has calculated the shortest path.? Nice, though.
patrickmccb (author)  blinkyblinky4 years ago
Hit the reset button on the Arduino or turn it off and on again.
kimvellore4 years ago
Nice concept. Thank you for explaining in detail. I enjoyed reading it.
hyruler_4 years ago
that is awesome
maximeke24 years ago
Can you please give me some information about your sensor? Does it use LEDs or infrared, and also the type/datasheet of emitter/transmitter?
patrickmccb (author)  maximeke24 years ago
On the first page of the instructable I provided the links to all of the different parts, including this one. Here is the link where you can find more information about it http://www.pololu.com/catalog/product/960
oops... I was just looking for the sensor and didn't read it. Sorry about that
error324 years ago
I have used some parts from the pololu store before. Very good quality!
Though i personally liked it better to make my own PIC based board instead of the too easy arduino solution.
SHIFT!4 years ago
This is a great 'ible, but you forgot the most crucial thing- The Title! Please name this project soon!
patrickmccb (author)  SHIFT!4 years ago
Thanks for the heads up. I thought I named it...