ECE 3400 Team 1 Milestone 3
Goal/Objectives
The main goal of this milestone was to have the robot be capable of maze exploration using a certain algorithm. Besides this, we were also required to have our robot be able to detect other robots through the use of IR emitters and IR detectors.
So we split up the goals into 2 sub-tasks:
- Constructing a functional IR detection circuit
- Designing an efficient maze navigation algorithm
Implementing Robot Detection
To implement robot detection, we are using 940 nm IR emitters and an 880 nm IR detector. The IR robot sensor circuit is fairly simple. It consists of an 880 nm IR detector and an IR emitter is connected directly to ground and to power in series with a 10K resistor.
Additional components:
Initially, the IR could only be detected from a short distance away. So we added a 2N3903 transistor, with an output to an analog pin on the Arduino, connected to ground directly and power through the IR detector. This amplifies the output from the IR detector making it more sensitive to the emitted IR so it can detect robots from father away.
Robot Detection Code:
To demonstrate the robot's detection ability, we used the following code that turned a blue LED on when IR was detected.
int sensorValue = analogRead(A0);
float voltage = sensorValue * (5.0/1023.0);
if (voltage < 4) {
digitalWrite(7, HIGH);
}
else {
digitalWrite(7, LOW);
}
This code outlines the rather simple logic of an IR detector. The analog values are converted into voltages on a 5.0 scale. 4.0 seemed to be a good threshold value as the voltage was always higher than that when there was no IR detected. If the voltage drops below 4, then IR was detected and the robot should take action to avoid the incoming robot. In this test case an LED is turned on.
Navigation Algorithm
For our navigation algorithm we decided upon a dijkstra explorer. The robot internally stores a view of the maze as a 10 by 10 matrix. The basic cycle it has is to first use its 3 wall sensors to learn about the wall around it and update the matrix with this data. If there are no walls leading to a previously invalid note in the matrix, then the node is denoted as valid and unexplored. The algorithm then uses dijkstra's algorithm to find the closest unexplored node, and then it pathfinds to it. Here are some code snippets:
Dijkstra's algorithm (Some initialization removed for brevity):
while (!(al_isempty(al))) {
// get node by FILO
byte n0 = al_pop(al);
byte x = get_x(n0);
byte y = get_y(n0);
if (get_searched(x, y, maze)) continue;
byte dist = get_dist(x, y, maze);
byte turns = get_turns(x, y, maze);
byte path = get_path(x, y, maze);
if (n0 != root) dir = (get_pointback(x, y, maze) + 2) % 4;
/* Handle extended BFS */
byte so_template[4] = {0, 1, 3, 2};
byte search_order[4];
byte turn_count[4] = {0, 1, 1, 2};
for (byte i=0; i<4; i++) search_order[(i + dir) % 4] = so_template[i];
/* Handle path relaxation to all valid, unsearched neighbors */
for (byte b=0; b<4; b++) {
byte i = search_order[b];
byte n1 = get_neighbor(x, y, i);
byte nx = get_x(n1);
byte ny = get_y(n1);
byte ndist = get_dist(nx, ny, maze);
byte nturns = get_turns(nx, ny, maze);
if (
is_valid(nx, ny, maze) // handle unknown walls later
&& !(get_searched(nx, ny, maze))
&& !(get_bit(path, i))
&& ((dist < ndist) || (dist == ndist && turns < nturns))
) {
set_dist(dist + 1, nx, ny, maze);
set_turns(turns + turn_count[b], nx, ny, maze);
set_pointback((i + 2) % 4, nx, ny, maze); // MODIFIED
if (get_explored(nx, ny, maze)) // don't further search unexplored nodes,
al_shift(make_pos(nx, ny), al); // only path relax
}
}
set_searched(1, x, y, maze);
}
}
Footage Compilation
The following video shows the funcitonality of the robot detection. When the IR emitter is moved in line with the IR detector, the voltage drops, which can be seen as the serial output on the screen, and the blue LED turns on.
Maze Exploration