My Arduino Bot Solved a Maze That It's Never Seen

• Tue, Jun 23, 2015
• 6m read

Table of contents

Watch the Demo

My robot, lovingly named Pyat after a certain Warlock, had never seen this particular maze before solving it, and it didn’t anticipate the maze’s - admittedly simple - structure. Pyat was able to complete the whole thing from start to finish using little more than some basic encoded behaviors. It’s programmed to complete any maze (theoretically), but unlike other robots that simply follow one wall to the end of the maze, Pyat uses a widely-known concept in robotics called Subsumption Architecture to navigate mazes in the same way that a human might.

When a person gets stuck in a maze, they very rarely have any idea what the maze looks like; otherwise they could just walk right out. So, how do you get out? Well, as I stated before, if the maze is simply-connected, you can just keep your hand on one wall and walk forward, and you’ll eventually make it to the end. But let’s assume you don’t know that trick. If you want to make it out before you die of old age, the most important thing is to ensure you’re not going in circles. One way to do this is to leave a trail of some sort - breadcrumbs, torches, red paint - whatever works. If you get to a dead end, just follow your trail back to the previous intersection and make a different choice. Repeat this, and eventually you’ll find your way out. It may not be the most efficient strategy, but it gets the job done. This is exactly what Pyat is programmed to do.

For those of you wondering how I accomplished this, I independently built Pyat using servos and other basic electrical components, and programmed it in C over the course of a few weeks, for my Robotics class. If you want, you can build one just like it. It runs on an Arduino Microprocessor with the BOE (Board of Education) Shield, two IR sensors, and two front contact whiskers.

Here’s a look at the hardware and state initialization in code:

1void setup() {
2  pinMode(7, INPUT);   // Right whisker
3  pinMode(5, INPUT);   // Left whisker
4  // ... IR sensor setup ...
5  servoLeft.attach(13);
6  servoRight.attach(12);
7  // ... initialize state variables ...
8  Serial.begin(9600);
9}

How it works

Subsumption Architecture in its simplest form is just layered behaviors. Depending on specific input coming from its sensors, the robot will elevate to a higher behavior, or de-elevate to a lower behavior. Here’s the architecture I defined for this robot:

The architecture I’ve defined for Pyat in the above diagram is slightly more complex than others, due to its conditional structure. For example, the Cruise behavior cannot possibly subsume the Return to wall behavior or the Return to intersection behavior unless a wall or an intersection has previously been detected. If not, Pyat will continue to cruise indefinitely until its behavior is elevated by an event detected by the whiskers or IR sensors. Also, the Follow the wall behavior is completely different depending on whether or not one, two, or zero walls are detected.

Here’s a simplified version of the main loop and how it checks sensors to decide which behavior to activate:

 1void loop() {
 2  byte wLeft = digitalRead(5);
 3  byte wRight = digitalRead(7);
 4  int irLeft = irDistance(9, 10);
 5  int irRight = irDistance(2, 3);
 6  boolean whiskersTouched = whiskerCheck(wLeft, wRight, irLeft, irRight);
 7  if(!whiskersTouched) {
 8    irCheck(irLeft, irRight);
 9  }
10}

For example, the whiskerCheck function handles what happens when the robot bumps into a wall:

 1boolean whiskerCheck(byte wLeft, byte wRight, int irLeft, int irRight) {
 2  if((wLeft == 0) && (wRight == 0)) {
 3    wReactBothWhiskers(irLeft, irRight); // Back up and turn around
 4    return true;
 5  } else if(wLeft == 0) {
 6    wReactLeftWhisker(irLeft, irRight);
 7    return true;
 8  } else if(wRight == 0) {
 9    wReactRightWhisker(irLeft, irRight);
10    return true;
11  }
12  return false;
13}

Let’s take a look at Pyat’s brain while it completes the maze: Pyat creates a grid on the floor as it moves.

• When the program starts, it begins at the origin (0,0), and after every subsequent movement, Pyat uses displaced distance and angle to compute the current position’s exact coordinates relative to the origin.

• When an important event or sequence of important events occurs in accordance with the subsumption architecture, Pyat records its current position as a wall or an intersection where a choice (left, right, or forward) was made.

  • This is useful when Pyat gets lost; it can get itself back on track via the two lowest-level behaviors, activated after 15 steps (measured in grid units) of uninterrupted cruising.

To keep track of intersections and choices, Pyat uses a simple stack data structure:

1// data[0][0] = absolute xPos
2// data[0][1] = absolute yPos
3// data[0][2] = direction (left = -1 / straight = 0 / right = 1)
4typedef struct {
5  int data[100][3];
6  int len;
7} Stack;
8
9Stack choices;

Here’s how the robot tracks its position on a virtual grid as it moves:

1void forwardTracking(int time) {
2  float distanceHypotenuse = (float) time / GRID_UNIT;
3  // ... calculate new position based on angle ...
4  currentPosition[0] = absX;
5  currentPosition[1] = absY;
6  // Actually move the robot
7  if(time >= 0) forward(time);
8  else backward(-time);
9}

When the robot reaches an intersection or needs to remember a choice point, it pushes the current position and decision onto the stack:

1void choicesPush(int d[]) {
2  if (choices.len < 100) {
3    for(int i=0; i<3; i++) {
4      choices.data[choices.len][i] = d[i];
5    }
6    choices.len++;
7  }
8}

What this means

This maze-solving technique potentially allows my robot to navigate more non-trivial patterns, such as a maze with another “island” maze inside of it, Inception-style. The robot can follow walls, make decisions at intersections, maintain a dynamic grid to mark intersection positions, identify when it’s stuck, and remember movements required to return to an intersection where it can make a new choice. (Note: I have not yet seen it attempt to destroy planet Earth, so I did not include this behavior in the diagram, though it may be a problem in the future.)

The video may not seem incredibly impressive, because after all, that’s a pretty simple maze. Also, even though my subsumption architecture seems to be well-defined, whether or not I’ve implemented it correctly in the code is another question entirely. Feel free to take a look at the code below and shout at me in the comments. Hopefully you’re at least a little bit impressed, because this took a lot of work, and I love my little Pyat.

Source Code

Related Posts

• Three and a Half Weeks of AI Coding Challenges
• Mario Typer: Rewriting a Buggy OBJ Parser for 3D Games
• Space Warz: Java Game Inspired by Space Invaders