Milestone 3 Robot Avoidance and Maze Exploration
Objectives
For Milestone 3, we want the robot to be able to explore the maze using some algorithms. We also add in the robot detection feature so that our robot will turn around when it sees other robots, avoiding crashes.
- Materials Used:
- 1 Arduino Uno
- 1 USB A/B Cable
- 4 IR Emitters
- 1 IR Receiver
- Variuos Resistors
- 1 Solderless breadboard
Robot Avoidance
1. Milestone 2 required that the robot be able to perform right-hand following around an arbitrary set of walls. In order to accomplish Milestone 3, we had to add a wall sensor to the left of the robot. We also added IR emitters and receiver for robot detection purposes. Basically, we want to sense any robots within a foot in front of us, and we want to react to it to avoid crashes.
2. The robot avoidance involved placing a 940nm emitter on each side of the robot (so 4 in total) and placing an IR receiver on the front. The 940nm emitter is to signal other robots of our existence, and the IR sensor on the front is to sense IR signal emitted from other robots. The IR sensor on the front is connected to an analog pin on the Arduino.
3. The logic and sensing are based on a series of threshold values. The threshold value is the point at which a nearby robot should be sensed (i.e. if the sensor reads a value less than X, this means that the robot is within the 1-foot range). Here are the pictures of the robot with all the required aspects of Milestone 3 included.
4. In order to find a threshold value (the value below which we knew there was a robot closeby), we hooked up an IR emitter to a battery-powered circuit. We found that when another robot was less than 2 squares away, the IR receiver showed an analog value less than 700. Therefore we chose the IR threshold value to be 700. Here is our code for using the IR sensor to detect other robots.
5. We calibrated all the sensors to detect walls and robots at the appropriate distances. In order to show what the robot was “seeing,” we added LEDs. The red LED lights up when the robot sees a wall on any side, while the blue LED lights up when it sees a robot in front of it. This is meant to demonstrate that the robot knows what it is seeing around it and is processing that information accordingly. Here is a video showing our robot traversing through a maze and turning around to avoid a robot in front of it.
Maze Exploration
1. There are different algorithms that we could have used for maze exploration, such as BFS, DFS, A*, etc. We ended up choosing to use DFS because we felt that later on when we optimize, we may be able to map adjacent nodes just by using our sensors. This would cut out the time that it takes to physically move the robot to that node and map it there. Additionally, DFS and BFS work better on different types of maps, and since the map configurations are random, it is impossible to know which will do better on the day of the competition. If we are able to map more than one node at a given location in the end, then DFS will play a crucial role in our optimization. Regardless, we would need to store which nodes have been visited. Later on, we may combine the two, or slightly modify our current implementation of DFS to optimize memory storage, since we are running low on storage.
2. Depth First Search is a searching algorithm that traverses a graph. It starts from one root node and goes as far as possible along each branch, mapping its children first, before backtracking and exploring nodes of the same depth and their children. Because the maze is a graph and not a tree, we had to store the visited states because graphs can contain cycles, and without knowing the visited nodes, we could infinitely search the maze. We call the DFS function as our search method in the line follow function when it reaches an intersection.
3. To implement DFS in Arduino, we had a matrix that stored the current location and orientation of the robot, the walls that are present around it, as well as whether a node was visited. We did this by using a bit and having global directions NORTH = 1, EAST = 2, SOUTH = 4,WEST = 8, so when combined using an or statement, the resulting bit can encode uniquely what combination of walls are around the node. For example, 9 would mean walls are to the North and West of the node.
4. We also had an array that stored the turn history of the robot and a global stack pointer that we incremented and decremented when we added or “popped” a direction (*Note: in reality we just returned the direction at the stack index and moved the stack index, we did not actually use the Stack data structure in Arduino). We added the opposite turn of the current turn to the array at the stack pointer so that when it was backtracking, it turned in the correct direction.
5. The most difficult part was by far backtracking, which was called upon reaching a deadend. A dead end is a node with all walls or visited states surrounding it. To backtrack, we had to “pop” directions and follow the directions until there was an open, unvisited state. We then had to go to the unvisited state and update the direction at that junction so that the robot would not follow the same deadend path again. We would then continue adding the directions to the array until we reached another deadend, and backtracked again until, finally, we reached the original state, and the robot lit up the green LED.
6. Below is our DFS implementation.
7. We then ran our robots in three different maze configurations. The first one was a small maze without any walls; the second one was a 4 by 5 maze without any dead ends; the last one was a 4 by 5 maze with two dead ends. The videos below show our robot successfully traversing three mazes using DFS.
Robot was traversing a small maze without any walls inside.
Robot was traversing a 4*5 maze without any dead end.
Robot was traversing a 4*5 maze without dead ends.