Maze Solving Robot (3 IR Sensors)

Description: This is a Line Maze solving robot which uses the LSRB Algorithm to solve the maze. Unlike on many websites, this is done by using an IR Sensor array (which is more accurate of course) but I have found a way of using just 3 IR Sensors for Maze solving. This saves lots of money and so proves to be an easy plus cheaper choice for hobbyists. There is a lot to learn in this tutorial so let's get started:)

Introduction

Before starting with the actual project I would like to mention a few prerequisites I hope you are familiar with this.

>> Familiar with Soldering on general purpose PCB

>>Familiar with the Arduino's circuit/pin diagram and its hardware.

>>Basic Physics(Center of mass, Friction,Center of gravity and Wheels)

>>Basic Electronics(wires, power supply, current, voltage, Ohm's Law)

Hardware Manual for Maze Solving Robot

1.Symmetrical Chassis

2.Motor Driver

3.Gyroscope(Optional)

4.60 RPM DC Motors

5.Wheels

6.IR Sensor

7.Arduino Pro Mini

1. Symmetrical Chassis

It is very important to have a Symmetrical Chassis.

If the chassis is not symmetrical then the Center of Mass(COM) of the Robot car will not be at the center. If this happens the robot will keep on shifting towards the right or towards the left which will cause problems or flaws in your shortest path algorithm.

2. Motor Driver(L298N)

This will be used for driving the DC Motors. L298N is a dual-channel meaning that it can control two motor's direction simultaneously. To learn more about it refer here.

3. Mpu 6050

MPU6050 is 6 axis acceleration plus gyroscope module. This means it can measure acceleration in X, Y and Z direction plus it can measure the Yaw, Pitch and Roll of the body in motion. It is recommended to learn about this module before moving further.

4. 60 RPM DC Motors

These Motors will be used to move the Robot. Why 60 RPM motors? well if your are getting started it's better to get started with slow motors. Robot with slow speed are more stable and easy to control. To many Strong RPM, motors will be difficult to control(you will need strong PID Controler for that). so to get started its recommended to use 60 RPM DC Motors.

5. Wheels

These are one of the most important components in Maze solving Robot. Make sure you have wheels that have better traction and are made of good quality rubber.These wheels will be connected to DC Motors.

6. IR Sensor

These sensors will plan an important role in detecting the type of intersection. You will learn more about the intersection and maze solving algorithm in detail in further sections. It recommended to know how these sensors work. For detailed information on these sensors refer to this link

7.Arduino Pro mini

This will be the brain of our robot. All the processing and computation of the algorithm will take place in this microcontroller. It is highly recommended to learn about arduino very well before moving any further. For detailed info about arduino refer to this link

"LSRB" Algorithm

This is the algorithm by which the robot solves the maze. In "LSRB" L stands for 'LEFT', S for 'STRAIGHT', R for RIGHT, and B for 'BACK' or BACKWARD. These LEFT, RIGHT, STRAIGHT, and BACK are the directions that the robot follows. This Algorithm is simple and straight forward. In this algorithm LEFT direction has the highest priority and the BACK (U-Turn) direction has the least priority. Let's see what this algorithm looks like:

• Step 1: Always follow LEFT whenever there is a turn possible
• Step 2: If LEFT is not possible go STRAIGHT.
• Step 3: If LEFT and STRAIGHT both are not possible take RIGHT.
• Step 4: if LEFT, STRAIGHT, and RIGHT are not possible go BACK( or it means take a U-Turn)

This means that whenever robot is on a turning point or an intersection it will always go LEFT whenever possible. if LEFT is not possible then STRAIGHT and if both are not possible then RIGHT. If all the three turns are not possible then and then only BACK. This is the only thing you need to understand the LSRB algorithm. Based on this there are 8 scenarios possible. Let's take a look one by one:

1.Simple or Straight lane: Here LEFT is not possible but the STRAIGHT path is. so robot will follow the Straight Path.

2.Left Turn(left only): As the name suggests it's a left turn so LEFT is possible here. According to LSRB algorithm robot should follow left whenever possible. so robot will take left turn here.

3.Right Turn(rightonly): Again as the name suggests it's a right turn so LEFT and STRAIGHT path are both not possible so according to LSRB Algorithm robot will take Right turn.

4. T intersection(T): This intersection has a T like shape so it's called T intersection. Here Robot can take the left turn as you can see in the picture. So by algorithm Robot will take a Left Turn.

5. Left T Intersection(straightor left): Again by image, we can see Robot can take left path so Robot will take left turn here.

6.Right T Intersection(Straightor right): Here Left is not possible but the Straight path is. so the robot will take left turn

7.Dead End: Here LEFT, STRAIGHT, and RIGHT all three are not possible. so Robot will take U Turn here.

8. Four lane intersection(Cross): Here again by the image Left turn is possible so the robot will take left turn here.

9. End of Maze: Here the maze ends so the robot will stop here.

Now let's take a quick look at how can we turn this into code:

//LSRB ALGORITHM

IR1 = <PIN 1>
IR2 = <PIN 2>
IR3 = <PIN 3>

void setup 
{
  DECLARE IR1 IR2 AND IR3 AS INPUTS
}

void loop 
{
  IR1 = digitalRead(<PIN 1>)
  IR2 = digitalRead(<PIN 2>)
  IR3 = digitalRead(<PIN 3>)

  if (IR1 == LOW && IR2 == HIGH && IR3 == LOW)//Straight path
    {
     Forward();
    }

  if (IR1 == HIGH && IR2 == LOW && IR3 == LOW)//Left turn
    {
     Left();
    }

  if (IR1 == LOW && IR2 == LOW && IR3 == HIGH)//Right Turn
    {
      Right();
    }

  if (IR1 == HIGH && IR2 == LOW && IR3 == HIGH)//T Intersection
    {
      Left(); // As left is possible
    }

  if (IR1 == HIGH && IR2 == HIGH && IR3 == LOW)//Left T Intersection
    {
      Left();// As Left is possible
    }

  if (IR1 == LOW && IR2 == HIGH && IR3 == HIGH)//Right T Tntersection
    {
     Forward();//As Straight path is possible
    }

  if (IR1 == LOW && IR2 ==LOW && IR3 == LOW)//Dead End
    {
     U_Turn(); //As no other direction is possible
    }

  if (IR1 == HIGH && IR2 == HIGH && IR3 == HIGH)//4 Lane intersection
    {
     Left(); //As no other direction is possible
    }

  if (IR1 == HIGH && IR2 == HIGH && IR3 == HIGH)//End of Maze
    {
     Stop(); //As no other direction is possible
    } 
}

well, the code is pretty easy, but one question remains. The condition for 4 lane intersection and End of Maze seems similar. How can our robot distinguish 4 lane intersection from End of Maze? well, the answer is pretty simple as well. Make the robot go little further. Now if the values of sensor remains the same then it's the end. but if the right and left sensor change values then its a 4 way intersection. so simple right? let's take a quick look into its code:

if (IR1 == HIGH && IR2 == HIGH && IR3 == HIGH)
    {
     Forward();
     delay(<Time>);
     Stop();

     if (IR1 == HIGH && IR2 == HIGH && IR3 == HIGH)
        {
          Serial.println("ËND OF MAZE");
          Stop();
        }
     else
        {
         Serial.println("FOUR WAY INTERSECTION");
         Left();
        }
    }

Note: For no detection, sensor value is LOW and if black line is detected sensor value is HIGH.

Shortest Path Algorithm

This is the Algorithm robot uses to calculate the shortest path in a maze. It uses the path taken using LSRB Algorithm and converts it into the shortest path. How? well let see how this works. Consider a maze in the image below. Now let's place a robot here and let's visualize its path by LSRB Algorithm. we can that by using LSRB Algorithm Robot will take LEFT, LEFT, BACK, RIGHT, STRAIGHT. In short, we can say Robot follows L, L, B, R, S. Now as a person we can directly say shortest path is just the RIGHT or 'R' turn here. But how does a robot do this? Well shortest path algorithm makes use of substitutions here. These substitutions are given below:

• 1. LBR = “B”
• 2. LBS = “R”
• 3. RBL = “B”
• 4. SBL = “R”
• 5. SBS = “B”
• 6. LBL = “S”

Now lets shorten the path by substitution method. In the path {L, L, B, R, S}, LBR = 'B' so Path now becomes { L, B, S}. Now LBS = 'R' so final path becomes { R} which is correct as discussed earlier. Now let's quickly see how can we turn this algorithm into Arduino code:

void CALCULATE_SHORTEST_PATH(char MAZE_ARRAY[], int SIZE_OF_ARRAY)
{
  /*ONCE THE ROBOT COMPLETES THE MAZE THE FINAL SHORTEST PATH CALCULATED
  IS STORED IN THE ROBOT MEMORY.THIS SHORTEST PATH IS USED TO COMPLETE
  THE SAME MAZE IN SHORTEST AMOUNT OF TIME.(L :LEFT, R:RIGHT, B:BACK,S:STRAIGHT)
  BELOW ARE THE FEW SUBSTITUTIONS TO CONVERT FULL MAZE PATH TO ITS 
  SHORTEST PATH:
  LBL = S
  LBR = B
  LBS = R
  RBL = B
  SBL = R
  SBS = B
  LBL = S */

  char ACTION;
  
  for(int i = 0; i <= SIZE_OF_ARRAY-2; i++)
    {
      ACTION = MAZE_ARRAY[i];
           
      if(ACTION == 'B')
        {
          if(MAZE_ARRAY[i-1]== 'L' && MAZE_ARRAY[i+1] == 'R')
            {
              MAZE_ARRAY[i] = 'B';
              MAZE_ARRAY[i-1] = 0;
              MAZE_ARRAY[i+1] = 0;
              REARRANGE(MAZE_ARRAY,SIZE_OF_ARRAY,i-1,i,i+1); 
            }

           if(MAZE_ARRAY[i-1]== 'L' && MAZE_ARRAY[i+1] == 'S')
            {
              MAZE_ARRAY[i] = 'R';
              MAZE_ARRAY[i-1] = 0;
              MAZE_ARRAY[i+1] = 0;
              REARRANGE(MAZE_ARRAY,SIZE_OF_ARRAY,i-1,i,i+1);
            }

            if(MAZE_ARRAY[i-1]== 'R' && MAZE_ARRAY[i+1] == 'L')
            {
              MAZE_ARRAY[i] = 'B';
              MAZE_ARRAY[i-1] = 0;
              MAZE_ARRAY[i+1] = 0;
              REARRANGE(MAZE_ARRAY,SIZE_OF_ARRAY,i-1,i,i+1);         
            }

            if(MAZE_ARRAY[i-1]== 'S' && MAZE_ARRAY[i+1] == 'L')
            {
              MAZE_ARRAY[i] = 'R';
              MAZE_ARRAY[i-1] = 0;
              MAZE_ARRAY[i+1] = 0;
              REARRANGE(MAZE_ARRAY,SIZE_OF_ARRAY,i-1,i,i+1);             
            }

            if(MAZE_ARRAY[i-1]== 'S' && MAZE_ARRAY[i+1] == 'S')
            {
              MAZE_ARRAY[i] = 'B';
              MAZE_ARRAY[i-1] = 0;
              MAZE_ARRAY[i+1] = 0;
              REARRANGE(MAZE_ARRAY,SIZE_OF_ARRAY,i-1,i,i+1);             
            }

            if(MAZE_ARRAY[i-1]== 'L' && MAZE_ARRAY[i+1] == 'L')
            {
              MAZE_ARRAY[i] = 'S';
              MAZE_ARRAY[i-1] = 0;
              MAZE_ARRAY[i+1] = 0;
              REARRANGE(MAZE_ARRAY,SIZE_OF_ARRAY,i-1,i,i+1);
            }
            
          i = -1;
        }
       
       delay(100);   
    }
}

Key to remember : When robot is encountered a'BACK'path it means that it has followed a wrong path or way. So main objective of shortest path is to Eliminate all the ‘Backs ‘ or ‘B’ of the robot.

Is shortest Path Algorithm Possible with 3 IR sensors?

Well if you are using just 3 IR Sensors then it's difficult. For making it work you will have to make the robot to follow the absolute straight path using PID Algorithm. If your robot follows absolute straight path then only its possible to implement shortest path Algorithm in it.

If you think it's possible by 3 sensors please dm me or share it with me in the comment section below.

PID Controller (Optional)

PID in pid controller stands for proportional integral and derivative. This will be used in our robot to follow a perfectly straight path. But what does these 3 terms exactly mean? lets see these terms one by one :

1.Proportional: This term is proportional to the error(E) term. The more the error the more the value of the proportional part. This value is responsible for turning of the robot. For example, if the error is large then the robot's action will also be strong. so basically proportional is responsible for the strength of action of the robot. The drawback of proportional is that it creates lots of oscillations. like if the robot contains only the Proportional part then the vehicle will keep on oscillating from left to right. well, it will go straight but will oscillate a lot. The gain obtained by Proportional control is denoted by 'KP'.

P = KP x Error

2. Integral: Even after oscillations are removed by derivative part still a small offset remains. This offset is removed by the Integral part by taking into account all the errors. The integral term increases with time. The gain obtained by integral is denoted by 'KI'.

I = I + KI x Error

3 Derivative: The Derivative term reduces or eliminates the oscillations generated by Proportional Term. This will make movement of robot smoother. The robot will follow a straight without oscillations.The gain obtained by Derivative is denoted by 'KD'.

D = KD x (Error - Previous_Error)/Time

The formula for PID is given by :

So the final PID value is obtained by summing these terms:

PID = P + I + D

The main goal in PID is to reduce error term as much as possible.Before moving on to coding there are three main elements required by PID Controller. lets see them one by one :

1. FeedBack: Feedback is a process by which a fraction of the output is used as input in the iteration. Feedback in our case is provided by MPU6050.and what kind of feedback are we getting? we are getting gyro values as feedback.

2.Actuator: This thing is plays the role in changing the output of the system. It can be a servo motor, DC motor, or any other motor. In our case, the actuators are two dc motors of the robot.

3.SetPoint: This is the ideal point or value that we want to achieve. It is obtained by eliminating the error completely.

Now let's convert this theory into code.

double PID_CONTROLLER(double FEEDBACK, double dt)
{
  double ERROR_VALUE;
  double PREVIOUS_ERROR_VALUE = 0;
  double SETPOINT = <desired_value>; //put the desired value decided by you here.
  double KP = <value>; //put the value you want here.
  double KI = <value>; //put the value you want here.
  double KD = <Value>; //put the value you want here.
  double P;
  double I;
  double D;
  double INTEGRAL;
  double DERIVATIVE;
  double OUTPUT_VALUE;

  ERROR_VALUE = SETPOINT - FEEDBACK; //Here the feedback is YAW from MPU6050

  P = KP*ERROR_VALUE; 

  INTEGRAL += ERROR_VALUE*dt;
  I = KI*INTEGRAL;

  DERIVATIVE += (ERROR_VALUE-PREVIOUS_ERROR_VALUE)/dt;
  D = KD*DERIVATIVE;

  OUTPUT_VALUE = P + I + D ;

  PREVIOUS_ERROR_VALUE = ERROR_VALUE;

  return OUTPUT_VALUE;
  
}

To know more about pid visit this link

Tuning Of PID Values :

• There are many ways by which Kp, Ki and Kd values of the system is tuned one of which is manual tuning through which stability can be easily achieved. Initially the Kp, Ki and Kd values are set to zero. Then Kp value is increased from zero till a point where the system starts to oscillate from its mean position.
• As the Kp value is increased, it was seen that response of the system increase gradually. Keeping the Kp value a constant the Ki value is then increased till a point where it is seen from the system that a small inclination towards a direction tends to accelerate the vehicle towards that direction. When the Kp and Ki values are properly obtained, then the Kd value is increased. The Kd value is increased such that rapid acceleration is reduced considerably.
• Proper KD value results in lesser overshoots and oscillations. After obtaining the rough Kp, Ki and Kd values a fine tuning is done. The above steps are repeated a number of times to obtain the best combination of gain value

Need for PID Controller

Well, even with symmetrical chassis you may have noticed that the robot still goes a little bit left or right while following a line The reason for this is the DC Motors. The DC motors that hobbyists use are not perfect. No two motors are alike. There is always minute differences between their mechanical structure. If your robot is following an absolute straight path then you are lucky, congrats! but many times this doesn't happen and the robot will usually go little to left or right. This can affect your shortest path algorithm if you are not using the IR Sensor array. One more need for PID is when you use very high RPM Motors.

To overcome this there are many options:

1. Using good quality DC Motors (Doesn't guarantee straight path)

2. Using good quality Wheels (Doesn't guarantee straight path)

3. Using highly mechanically accurate Chassis(doesn't guarantee straight path)

4. Reducing the speed of one motor so that both motor's speed matches perfectly(But still after doing this also there is still minute error which makes the robot go little off track).

5. Using Rotatory Encoders(might work very well sometimes)

6. Using PID Controller(guarantees the straight path for the robot if coded perfectly).

Out of all these options, only the PID controller guarantees the absolute straight path for the robot.

please note if you are using very high RPM Motors it's necessary for you to use PID otherwise the robot will go off track 110%. Due to this PID Controller plays an important role and should be used in this robot.

Construction of the Robot

The construction of the robot is very easy. I am pretty sure that just the images will be sufficient enough for you to construct the hardware. so I am providing just the images. (More Images will soon be added along with circuit Images).

Note: If you face any problem while constructing the robot be free to dm or comment under the comment section.

Final Code

The final code and Individual circuit schematics will soon be provided below the end of the article. Feel free to contact me if you have any doubts. Please note that the code will be an implementation of just the LSRB Algorithm. There is a shortest path function in the code which you can use it for implementing shortest path algorithm. You can try to use that function to implement Shortest path for 3 IR Sensors. If you are able to do it just by 3 sensors please let me know as I would like to learn about it :)

Video: Don't forget to check the working video of this awesome project :)