Milestone 3
Objective
For Milestone 3, our objective was to successfully avoids other robots in at least 1ft distance and make the robot capable of maze exploration using DFS.
Hardware Updates
Going into this milestone, our robot was using right hand wall-following to traverse mazes. This requred two wall sensors, a forward-facing and right-facing sensor to accurately traverse the maze. Before implementing our new algorithm, our robot would need accurate information about the walls on all sides to make informed decisions about where to go next. Therefore, we added a left-facing wall sensor. With sensors facing forward, left, and right, our robot could determine every wall surrounding it after entering an unexplored square. It can assume that there is no wall behind it because it just came from that square (except at the start, when we assume the robot starts with a wall behind it).
IR Detection - Robot Avoidance
To detect other robots, we used a phototransistor for transmission and IR LEDs for emission. A phototransistor is an electronic switching and current amplification component which relies on exposure to light to operate. When light falls on the junction, reverse current flows which are proportional to the luminance. If we connect the output of the transistor to a pin on the Arduino, we can see the corresponding values on the Serial output depending on whether there is an IR detection or not.
Because we used a pull-up configuration, the Arduino reads 0 when there is IR detection. Additionally, we used a digital pin because we’re currently usingfive out of the six available analog pins (three for wall sensors, two for line sensors) and we didn’t want to use up all of them right now. In the very near future, we will start looking into Schmitt triggers to free up some of these used pins.
Another reason we decided to use digital pins is because Arduinos can only support interrupts on a digital pin. However, using interrupts proved to be impractical because when the phototransistor detects IR, it calls the interrupttoo many times and the robot just stops, instead of turning around. Therefore, we just decided to add a simple if-statement in our followLine() method so that before it moves forward, it checks for other robots. A video of our robot avoiding another robot is found below.
Our robot can detect IR from about a foot away, but it’s sometimes hard to make sure that the IR is level with the phototransistor.
Navigation Algorithm - Depth First Search (DFS)
We chose to implement a modified DFS algorithm since DFS is relatively simple to get working and it doesn't use much memory. To implement DFS, we realized that we need a stack. So we downloaded the StackArray libraries from the Arduino playground. We created the 2d array maze[9][9] for the 10 x 10 maze. At each coordinate we update the wall information and send it to the GUI, so we wanted a way to store that information at each {x,y} coordinate. The code that implements this is below:
struct point {
int x;
int y;
bool explored;
int backpointerx;
int backpointery;
};
typedef struct point point;
StackArray stack;
point maze[9][9];
Navigation Algorithm - Depth First Search (DFS)
We chose to implement a modified DFS algorithm since DFS is relatively simple to get working and it doesn't use much memory. To implement DFS, we realized that we need a stack. So we downloaded the StackArray libraries from the Arduino playground. We created the 2d array maze[9][9] for the 10 x 10 maze. At each coordinate we update the wall information and send it to the GUI, so we wanted a way to store that information at each {x,y} coordinate. The code that implements this is below:
struct point {
int x;
int y;
bool explored;
int backpointerx;
int backpointery;
};
typedef struct point point;
StackArray stack;
point maze[9][9];
DFS Algorithm Demonstrating
Below is the pseudo-code demonstrating our algorithm.
procedure DFS-iterative(G,v):
let S be a stack
S.push(v)
while S is not empty
v = S.pop()
if v is not labeled as discovered:
label v as discovered
for all edges from v to w in G.adjacentEdges(v)
S.push(w)
The following code snippet illustrates our DFS algorithm:
void DFS(point p){
stack.push(p);
while (!stack.isEmpty ()){
point v = stack.pop();
moveTo(v);
maze[v.x][v.y].explored = true;
frontwall = analogRead(frontWallSensor);
rightwall = analogRead(rightWallSensor);
leftwall = analogRead(leftWallSensor);
if(robotdir == 0){
if((rightwall < wallThresholdRight) && (!maze[v.x+1][v.y].explored)){ //right wall not detected and right point not explored
Serial.println("pushed rightt");
maze[v.x+1][v.y].backpointerx = v.x;
maze[v.x+1][v.y].backpointery = v.y;
stack.push(maze[v.x+1][v.y]);
}
if((leftwall < wallThresholdLeft) && (!maze[v.x-1][v.y].explored)){ //left wall not detected and left point not explored
Serial.println("pushed leftt");
maze[v.x-1][v.y].backpointerx = v.x;
maze[v.x-1][v.y].backpointery = v.y;
stack.push(maze[v.x-1][v.y]);
}
if((frontwall < wallThresholdFront) && (!maze[v.x][v.y+1].explored)){ //front wall not detected and front point not explored
Serial.println("pushed front");
maze[v.x][v.y+1].backpointerx = v.x;
maze[v.x][v.y+1].backpointery = v.y;
stack.push(maze[v.x][v.y+1]);
}
}
if(robotdir == 1){
if((rightwall < wallThresholdRight) && (!maze[v.x][v.y-1].explored)){ //right wall not detected and right point not explored
Serial.println("pushed rightt");
maze[v.x][v.y-1].backpointerx = v.x;
maze[v.x][v.y-1].backpointery = v.y;
stack.push(maze[v.x][v.y-1]);
}
if((leftwall < wallThresholdLeft) && (!maze[v.x][v.y+1].explored)){ //left wall not detected and left point not explored
Serial.println("pushed leftt");
maze[v.x][v.y+1].backpointerx = v.x;
maze[v.x][v.y+1].backpointery = v.y;
stack.push(maze[v.x][v.y+1]);
}
if((frontwall < wallThresholdFront) && (!maze[v.x+1][v.y].explored)){ //front wall not detected and front point not explored
Serial.println("pushed front");
maze[v.x+1][v.y].backpointerx = v.x;
maze[v.x+1][v.y].backpointery = v.y;
stack.push(maze[v.x+1][v.y]);
}
}
if(robotdir == 2){
if((rightwall < wallThresholdRight) && (!maze[v.x-1][v.y].explored)){ //right wall not detected and right point not explored
Serial.println("pushed rightt");
maze[v.x-1][v.y].backpointerx = v.x;
maze[v.x-1][v.y].backpointery = v.y;
stack.push(maze[v.x-1][v.y]);
}
if((leftwall < wallThresholdLeft) && (!maze[v.x+1][v.y].explored)){ //left wall not detected and left point not explored
Serial.println("pushed leftt");
maze[v.x+1][v.y].backpointerx = v.x;
maze[v.x+1][v.y].backpointery = v.y;
stack.push(maze[v.x+1][v.y]);
}
if((frontwall < wallThresholdFront) && (!maze[v.x][v.y-1].explored)){ //front wall not detected and front point not explored
Serial.println("pushed front");
maze[v.x][v.y-1].backpointerx = v.x;
maze[v.x][v.y-1].backpointery = v.y;
stack.push(maze[v.x][v.y-1]);
}
}
if(robotdir == 3){
if((rightwall < wallThresholdRight) && (!maze[v.x][v.y+1].explored)){ //right wall not detected and right point not explored
Serial.println("pushed rightt");
maze[v.x][v.y+1].backpointerx = v.x;
maze[v.x][v.y+1].backpointery = v.y;
stack.push(maze[v.x][v.y+1]);
}
if((leftwall < wallThresholdLeft) && (!maze[v.x][v.y-1].explored)){ //left wall not detected and left point not explored
Serial.println("pushed leftt");
maze[v.x][v.y-1].backpointerx = v.x;
maze[v.x][v.y-1].backpointery = v.y;
stack.push(maze[v.x][v.y-1]);
}
if((frontwall < wallThresholdFront) && (!maze[v.x-1][v.y].explored)){ //front wall not detected and front point not explored
Serial.println("pushed front");
maze[v.x-1][v.y].backpointerx = v.x;
maze[v.x-1][v.y].backpointery = v.y;
stack.push(maze[v.x-1][v.y]);
}
}
}
}
Maze Navigation Algorithm Demonstration
This video shows our robot exploring a 5x4 maze using DFS:
This video shows our robot exploring a 5x4 maze in a different configuration using DFS:
Adjustments to Navigation Algorithm
We were later advised against using the StackArray library in our maze navigation algorithm due to the additional overhead that is added when calling library functions and initializing the data structures. Therefore, we got the same behavior as a stack by replacing our stack with an array that can fit all maze entries and a pointer to the last entry that corresponds to a location that has been "pushed" to our "stack." We use the tens place of the number to represent the x position in the maze and the ones place to represent the y position in the maze. Using this conversion, we changed the use of the stack from the StackArray library to using our own linear array. The main difference is that we do not remove the entries from the array as we would with a stack. Instead, in order to know whether DFS has finished, we have to iterate over the entries in the array from the last pointer to the first entry in the table to see if there is a point that has not yet been visited. This can be seen in the code snippet below:
stack[0] = 0;
bool finished = false;
while (!finished){
point v;
for (int i = last; i >= 0; i --) {
int x = stack[i]/10;
int y = stack[i]%10;
if (!maze[x][y].explored) {
v = maze[x][y];
break;
}
else if (i == 0) {
finished = true;
break;
}
}
if (finished) {break;}
When we compile the program, it currently does not show that any less dynamic memory is utilized by the Arduino, and this may be a result of maintaining the two-dimensional point array. If we need to reduce the memory consumption caused by this, then we intend to adjust our integer array into a point array.