Back to Blogs
Project Guides

How Our MicroMouse Solves a Line Maze: LSRB, Path Simplification and PD Control

ElectroPhobia Team
12 min read
How Our MicroMouse Solves a Line Maze: LSRB, Path Simplification and PD Control

A look inside the Meshmerize MicroMouse built by the Robotics Club, WRC: how it explores a line maze with the left-hand rule, shrinks its recorded path to the shortest route, and follows the line with a tuned PD controller.

A line maze is a grid of lines on the floor, with junctions, dead ends and one finish zone. The robot gets two runs. In the dry run it explores and learns the maze. In the actual run it has to drive the shortest route from start to finish as fast as possible.

This article explains how the Meshmerize MicroMouse, built at the Robotics Club, WRC by Aabiskar Regmi, Prashant Bhandari, Sanjog Sapkota and Siddartha Gupta, does it. The robot placed 1st at Locus (Pulchowk Campus), 2nd at Delta 5.0 (IOE Dharan) and 5th at Techfest, IIT Bombay 2024. The code snippets come from the team's open-source repository, linked at the end.

Hardware (version 2)

  • Controller: Arduino Nano
  • Line sensor: 8-channel QTR reflectance array (analog), read with Pololu's QTRSensors library
  • Motor driver: SparkFun TB6612FNG (version 1 used an L293D)
  • Motors: N20 micro gear motors
  • Power: two 3.7 V Li-ion/LiPo cells with voltage regulation, including a buck converter
  • Controls: three buttons (calibrate, choose rule, start) and a status LED
  • PCB: custom boards designed in KiCad for each hardware version

Later versions moved to a refined Nano PCB (v3.x) and an ESP32-based board.

Step 1: calibration

Lighting and surfaces change from venue to venue, so the robot calibrates on the actual track before every run. After the first button press, it sweeps left and right over the line while recording each sensor's minimum and maximum readings:

for (int i = 0; i <= 100; i++) {
  if (i < 25 || i >= 75) left(motor1, motor2, 200);
  else                   right(motor1, motor2, 200);
  qtra.calibrate();
  delay(10);
}

For each sensor, the decision threshold is the midpoint between its own minimum and maximum. This matters because the eight sensors are never perfectly identical:

thr[i] = (qtra.calibrationOn.minimum[i] + qtra.calibrationOn.maximum[i]) / 2;

Step 2: following a segment with PD control

Between junctions, the robot simply follows the line. readLineBlack() returns a weighted position from 0 (line under the first sensor) to 7000 (line under the last), so 3500 means perfectly centred. The error is the distance from centre, and the controller turns it into a speed difference between the wheels:

int position = qtra.readLineBlack(sensors1);
int error = 3500 - position;
int motorSpeed = kp * error + kd * (error - lastError);
lastError = error;

int rightMotorSpeed = BaseSpeed - motorSpeed;
int leftMotorSpeed  = BaseSpeed + motorSpeed;

This is a PD controller: proportional plus derivative, with no integral term.

  • The P term steers in proportion to how far off-centre the robot is.
  • The D term reacts to how fast the error is changing. It damps the correction before the robot overshoots, which is what stops the side-to-side wobble at speed.

An integral term is often left out of line followers. The line keeps moving under the robot, so steady-state error isn't really the problem. Integral wind-up through sharp turns causes more trouble than it solves.

The team's final values for v2 were kp = 0.151 and kd = 0.8 at a base speed of 255. The repository notes that tuned values varied between hardware versions, roughly 0.05–0.151 for kp and 0.1–0.8 for kd. Those numbers only make sense for this robot's weight, motors and sensor spacing. Gains don't transfer between robots, so you have to tune your own. Our line follower guide explains the tuning procedure.

Each motor speed is clamped between 0 and the maximum, so a large correction can't ask for an impossible value.

Step 3: detecting junctions

The follow loop exits when either outer sensor sees the line (a side branch) or when no inner sensor sees it (a dead end):

if ((sensors1[0] > thr[0]) || (sensors1[7] > thr[7])) return;   // junction
else if (/* sensors 1–6 all below threshold */) return;          // dead end

At a junction, the robot records which directions are open:

  1. It brakes and nudges forward slightly, to straighten up if it entered at an angle.
  2. It notes whether the left or right outer sensor sees a line.
  3. It drives forward a little more, so the wheels line up with the junction, and checks whether a line continues straight ahead.
  4. If all inner sensors see the line, it has reached the finish zone, a solid block rather than a single line.

Step 4: choosing a turn with LSRB

During the dry run, the robot explores using a fixed priority. With the left-hand rule (LSRB), it takes the first available option from: Left, Straight, Right, and finally Back (U-turn at a dead end).

char select_turnL(char found_left, char found_straight, char found_right) {
  if (found_left)          return 'L';
  else if (found_straight) return 'S';
  else if (found_right)    return 'R';
  else                     return 'B';
}

Following one wall, in this case the left one, is guaranteed to reach the exit of any maze without loops. It isn't efficient, since it explores dead ends along the way, but that's fine for the dry run. The robot also has an RSLB (right-hand) mode, chosen with a button at the start. Some mazes are much shorter to explore with one rule than the other, and the team could pick after seeing the track.

Every decision is appended to a path array, for example L S B L R ….

Step 5: simplifying the path

Here's where the dry run pays off. Each time a B appears in the middle of the last three moves, that sequence went into a dead end and back out, and it can be replaced with a single equivalent turn. The trick is to treat each move as an angle (R = 90°, B = 180°, L = 270°, S = 0°), add the three together, and convert the sum back into one move:

// called after every new turn is recorded
if (path_length < 3 || path[path_length - 2] != 'B') return;

int total_angle = 0;
for (int m = 1; m <= 3; m++) {
  switch (path[path_length - m]) {
    case 'R': total_angle += 90;  break;
    case 'L': total_angle += 270; break;
    case 'B': total_angle += 180; break;
  }
}
total_angle %= 360;
// 0 → 'S', 90 → 'R', 180 → 'B', 270 → 'L'
path_length -= 2;

Example: L B L is 270 + 180 + 270 = 720°, which is 0° mod 360. The robot went left into a dead end, turned around, then turned left again, ending up facing the direction it originally came from, straight on. So L B L becomes S. Likewise L B S becomes R, and S B L becomes R.

Because simplification runs after every turn, nested dead ends collapse automatically, and when the dry run ends, path already holds the shortest route the robot found. This approach was popularized by Pololu's 3pi robot maze-solving guide, credited in the references, and it's a good example of a small idea doing a lot of work.

Step 6: the actual run

After the dry run, the robot stops at the finish, flashes the LED and waits. Placed back at the start and given a button press, it replays the simplified path. At each junction it follows the segment, then immediately executes the next stored turn, with no decisions to make. That's why the actual run is so much faster.

The robot also ramps its speed up over the first ~120 ms of each run (40 → 60 → 80 PWM) instead of jumping to full speed. Sudden full power on N20 motors makes the wheels slip and the robot lose the line in the first few centimetres.

Lessons from competition

  • Calibrate on site, every time. Venue lighting changed sensor readings more than anything else.
  • Junction handling is where runs fail, not straight-line following. The small "nudge forward" delays (10–60 ms) needed retuning whenever speed or battery voltage changed.
  • Battery voltage affects tuning. A freshly charged pack makes the same PWM values drive faster, and PD gains tuned on a half-empty battery can overshoot on a full one.
  • The left-hand rule can be slow on some maze layouts. Being able to switch to the right-hand rule at the start line was a cheap advantage.

Source code and credits

The full code (black-line and white-line versions), KiCad PCB files for each hardware version, and photos are on GitHub. The project is maintained by Prashant Bhandari, with initial development by Siddartha Gupta. See also the MicroMouse project page.

New to robots like this? Start with Build a Line-Following Robot, and the motors, drivers and sensors on Day 4 of the ElectroLab course.

References

Tags

MicroMousemaze solvingLSRB algorithmPID controlline followerArduino NanoQTR sensorrobotics competition