Maze Solving Robot V3




Intro

This is my third maze solving robot. My previous two versions, for many reasons, never accomplished what I wanted them to accomplish. This robot is capable of finding the end of a non-cyclic line maze, calculating the shortest path from the start point to the end point, and then driving that shortest path. More information about the maze solving algorithm can be found in my tutorial on the topic. I will go over some of the main points below.

Algorithm

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 when 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 without 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 follows:

  • 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 by 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 example, 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. What made this robot difficult to program was the fact that it has no encoders and its sensors are collinear. 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.

Construction

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.



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 power 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 it 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 in 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 whereas 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 in transistor. This could be used to turn them off when not needed inorder to 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)