Objective
Our goals for this milestone were to successfully avoid other robots and implement a maze exploration algorithm. For robot detection, we used IR LEDS to signal our presence to other robots and a phototransistor to detect other robots. For maze exploration, we used a memory-efficient version of DFS as discussed below.
Materials
- 4 940nm IR Emitters
- QSE113/114 NPN Silicon phototransistor (acceptance angle of 50 degrees)
- Resistors (330 Ohms, 120 kOhms)
Robot Detection
For robot detection, we used a NPN silicon phototransistor with an aceptance angle of 50 degrees. This phototransistor passes more or less current depending on the amount of infra-red light falling on it. Based on experimentation, we learned that the serial monitor read a higher value when the amount of IR-light falling on the phototransistor increased. During the lab, we also learned that the blue-tinted IR emitters are the only compatible emitters that work with our phototransistor.
Our goal was to find a solid threshold that would signal that another robot is close enough for our robot to act on the information. We tested multiple times under different lighting conditions and using different resistors in our phototransitor circuit to modify the sensitivity of the phototransitor. We finally went with a 120 kOhm resistor, with a threshold of 650 on the serial monitor reading from the arduino since we wanted our robot to act on the information from the phototransistor if there was a robot within one and a half tiles in front of us, which can be seen in the circuit diagram below.
Diagram showing the circuit layout of the phototransistor and the interaction between
the emitter and the phototransistor.
Our emitter circuit was quite simple. We simply connected each IR emitter to the arduino with a series resistance of 330 Ohms. So, our emitters will turn on as soon as the robot is on. We placed an IR emitter on the front, back and on the sides of the robot so that other robots can detect our presence from any direction. A video of our robot turning around upon detecting a robot within one and a half tiles in front of it is shown below.
Robot turns around when it detects the emitter (our simulated robot).We have also added videos demonstrating the testing process of making the phototransitor detect the IR signals from the emitter and determining an appropriate threshold below:
Video showing our robot detecting another robot leading to the green LED lighting up. Video showing the corresponding serial monitor readings.Maze Exploration - DFS
The first step in completing our dfs algorithm was to re-orient our robot. Previous robot movements relied on prioirtizing going straight, right, or left (specifically, we did these prioiritizations in right hand wall following). For a DFS algorithm to work efficiently, our robot has to prioritize a direction in the maze that is not dependent on the way the robot is facing. Therefore, we created new functions to prioritize checking and moving to north, east, west, and then south. These functions look at the direction the robot is facing, and use our previous commands of turning left/right/straight to move the robot in the new direction it is supposed to go.
In the picture below we demonstrate which way our robot compass is oriented relative to the maze. Our robot prioritizes north, then east, then west, then south. Everytime our robot hits an intersection, we update our x and y position and choose a direction to go based on our prioizitations, walls, and already visited intersections (otherwise referred to as nodes). Based on the direction we choose to go in, we update our robot's direction as well.
This is how the maze looks to our robot. We've marked visited (red) nodes and unvisited (green) nodes. You can see here how our robot prioitized north until it came to the wall, and is now prioiziting east since it can't move north.
We keep track of our current x and y positions with global variables, and increment/decrement based on the direction we choose. North and south increment and decrement y, respectively. East and west increment and decrement x, respectively. Each node has it's own x and y position. We update a 2D array of visited nodes everytime we come to a new intersection.
When our robot reaches an intersection, we first check if north is free by checking if there is a wall there or if it has been visited. Then we do the same for the other directions. If everything has a wall or has been visited, our robot will backtrack.
Robot sucessfully does DFS on 6x6 maze. The robot stops when all nodes our visited.We keep a backtrack direction associated with each node indicating the opposite direction from which this node was approached by the robot, so that if we visit the node again (since sometimes we may hit a dead end and we need to move back to a visited node to keep moving through the maze and find the other unvisited nodes), our robot knows which way to go. The robot will look at the backtrack direction associated with the node, and move in that direction. For example, if the robot moves from (0, 0) to (0, 1), the backtrack direction saved to (0, 1) will be South since the robot approached (0, 1) from the North. When backtracking, we want to go the opposite way. We chose this backtracking method, as well as choosing an iterative version of DFS instead of recursion, to save memory space on the Arduino.
Robot sucessfully does DFS on smaller maze. Here, we wanted to verify our backtracking, so our robot backtracks all the way back to the start.Since we cannot guarantee that, in a maze, every intersection with be open to the robot, we also added in code to either stop when the robot has visited all the nodes or when the robot backtracks to 0,0 and has no other unexplored direction to go to.
We have provided relevant DFS code below:
This is the node struct we use to save information about every intersection:
typedef struct {
//add array of directions you have gone to with respect to this node
boolean walls[3]; // front - 0, right - 1, left - 2
int xpos;
int ypos;
int backtrackDir; //put here direction to go when backtracking
} node;
This is the main DFS code:
void dfs(node curr) {
// push this node to the path stack and the array of visited nodes
Serial.println("Visited?");
Serial.println(visited[xcounter][ycounter]);
if(visited[xcounter][ycounter] == 0){ //if it hasn't been visited, put the node in the visited array
seen[xcounter][ycounter] = curr; // put node in array
visited[xcounter][ycounter] = 1; // mark this position as seen
Serial.println("in 'if'");
done++;
}
//move in the prioritized direction
if (isNorthFree(curr)) {
ycounter++;
turnNorth();
backval = 2; //when backtracking, go south
}
else if (isEastFree(curr)) {
xcounter++;
turnEast();
backval = 3; //when backtracking, go west
}
else if (isWestFree(curr)) {
xcounter--;
turnWest();
backval = 1; //when backtracking, go east
}
else if (isSouthFree(curr)){
ycounter--;
turnSouth();
backval = 0; //when backtracking, go north
}
else{ // backtrack
backtrack(); // this node has been visited before if no options are available, get bactrack pointer and go that direction
}
}
The following is an example of a helper function that makes the robot turn a certain direction based on the current direction it is facing:
// turn north
void turnNorth() {
if(dir == 0) { // facing north
straight();
delay(200);
}
else if (dir == 1) { // facing east
delay(600);
turnLeft();
straight();
}
else if (dir == 2) { // facing south
delay(600);
turnLeft();
turnLeft();
straight();
}
else { // facing west
delay(600);
turnRight();
straight();
}
dir = 0;
}
The following is an example of a helper function that determines whether a certain direction is free:
/ wall to the north? returns True if free, false if blocked
boolean isNorthFree(node curr) {
if (dir == 0 && !curr.walls[0] && !visited[xcounter][ycounter+1]) { // going north and no wall in front
return true;
}
else if (dir == 1 && !curr.walls[2] && !visited[xcounter][ycounter+1]) { // going east and no wall to left
return true;
}
else if (dir == 3 && !curr.walls[1] && !visited[xcounter][ycounter+1]) {
return true;
}
else {
return false;
}
}
This is how we backtrack to a previously visited adjacent node:
void backtrack(){ // this node has been visited before if no options are available, get bactrack pointer and go that direction
// if x and y are both 0 and we are backtracking, then there are no more nodes to visit
if (xcounter == 0 && ycounter == 0) {
// I have explored all options so I am done
while (1) {
servoStop();
}
}
int bkpt;
bkpt = seen[xcounter][ycounter].backtrackDir;
if(bkpt == 0){
turnNorth();
ycounter++;
}
else if(bkpt == 1){
turnEast();
xcounter++;
}
else if(bkpt == 2){
turnSouth();
ycounter--;
}
else {
turnWest();
xcounter--;
}
}
In our main loop function, if there is an intersection, we call DFS on the current node. Otherwise, we line correct.