Lab 4 (Radio Communication and Full Robotic Integration)

Radio Communication

During this lab we implemented radio transmission of maze data from the robot to the base station radio and worked on the FPGA code to correctly display the maze configuration on the screen. On the robot side, we implemented a manual override button, augmented wall sensing behavior, added robot detection hardware and avoidance code, and added a green LED signaling the completion of maze exploration.

Sending Maze Information Wirelessly

We have implemented an efficient scheme to store maze information on the arduino and send it to the base station. The code below shows the struct definition for a node, as well as the declaration of the 2-D array that holds the structs for all of the nodes. Each node has information for its neighbors, orientation of entrance by the robot, and whether it has been visited. 

typedef struct{                           // this structure contains the properties intrinsic to each node
  bool neighbor[OR_NUM] = {0, 0, 0, 0};   // each node has four neighbors
  ORIENTATION or_backtrack;               // opposite of the orientation in which the node was first entered
  ORIENTATION or_forward;                 // orientation in which the node was first exited
  bool visited = false;                   // tracks whether node has been visited
} node_t;

node_t maze[MAZE_WIDTH][MAZE_HEIGHT];     // initialize all nodes in the maze
int robot_x = 0;                          // initial x coordinate always 0
int robot_y = 0;                          // initial y coordinate always 0
ORIENTATION path_or;                      // the orientation to travel next
ORIENTATION robot_orientation;            // the current orientation of the robot
STATE current_state;                      // current maze mapping state

The code below shows how the stored information for the robot's position, orientation, and detected walls are sent as an array of bits to the base station Arduino. The first eight bits are for the x and y position of the robot, the next three are for walls detected on either the left, middle, or right sides, and the last two bits are for orientation (N,S,E,W).

void construct_maze_msg() { // assembles message to send to base station
  // robot x = 4 bits to represent 0-8
  maze_msg[0] = bitRead(robot_x, 0);
  maze_msg[1] = bitRead(robot_x, 1);
  maze_msg[2] = bitRead(robot_x, 2);
  maze_msg[3] = bitRead(robot_x, 3);
  // robot y = 4 bits to represent 0-8
  maze_msg[4] = bitRead(robot_y, 0);
  maze_msg[5] = bitRead(robot_y, 1);
  maze_msg[6] = bitRead(robot_y, 2);
  maze_msg[7] = bitRead(robot_y, 3);
  // wall detection, 1 if detected; RML = 8:10
  maze_msg[8] = right_wall_flag;
  maze_msg[9] = mid_wall_flag;
  maze_msg[10] = left_wall_flag;
  // orientation = 2 bits to represent NWSE
  maze_msg[11] = bitRead(robot_orientation, 0);
  maze_msg[12] = bitRead(robot_orientation, 1);
  // robot detection, 1 if detected
  maze_msg[13] = robot_detected;
}

To read the information sent by the transmitting radio device, the base station Arduino read the 14 bits with the statement 

done = radio.read( got_maze, sizeof(got_maze) );

To write this received information to the FPGA, it was written in two bytes, toggling a valid bit so each byte could be read accurately on the FPGA. The code to write the bits from the Arduino to the FPGA is shown below. Delays are included to allow time for the pins to be set before toggling the valid bit.

if (radio_ready) {
  digitalWrite(bit13, LOW);
  delay(5);
  
  digitalWrite(bit5, got_maze[0]);
  digitalWrite(bit6, got_maze[1]);
  digitalWrite(bit7, got_maze[2]);
  digitalWrite(bit8, got_maze[3]);
  
  digitalWrite(bit9, got_maze[4]);
  digitalWrite(bit10, got_maze[5]);
  digitalWrite(bit11, got_maze[6]);
  digitalWrite(bit12, got_maze[7]);
  
  digitalWrite(bit13, HIGH);
  delay(10);
  digitalWrite(bit13, LOW);
  delay(5);
  
  digitalWrite(bit5, got_maze[8]);
  digitalWrite(bit6, got_maze[9]);
  digitalWrite(bit7, got_maze[10]);
  
  digitalWrite(bit8, got_maze[11]);
  digitalWrite(bit9, got_maze[12]);
  
  digitalWrite(bit10, got_maze[13]);
  digitalWrite(bit11, LOW);
  digitalWrite(bit12, LOW);
  digitalWrite(bit13, HIGH);
  delay(10);
  digitalWrite(bit13, LOW);
  radio_ready = false;
}

Updating the Base Station Display

We are able to display accurate information on the display sent by the robot arduino. Our method is by using serial/parallel communication between the arduino and the FPGA. First the x and y locations (each four bits) are written from the arduino to the FPGA GPIO pins. Then this is written to a temporary variable and the valid bit is set low. Once it is set high, then the wall locations and absolute direction of the robot are written to the GPIO pins. Then all this data is written to relevant variables to use for the logic of drawing on the screen. The information is sent in two bytes; the first byte is for coordinate information, and the second byte is for wall and orientation information. Please see the code below for this serial/parallel implementation. 

if (VALID && !LAST_VALID) begin
	if (COUNTER == 0) begin
		temp_byte1 = ARDUINO_INPUT; //
		COUNTER = 1'b1; //
		WRITE_FLAG = 1'b0;
	end else begin
		temp_byte2 = ARDUINO_INPUT;
		COUNTER = 1'b0; //
		WRITE_FLAG = 1'b1; //
	end
end
LAST_VALID <= VALID;

The four statements below were used to write the information in temp_byte1 and temp_byte2 from the Arduino to variables for robot position, detected walls, and orientation.

ROBOT_X = temp_byte1[3:0];
ROBOT_Y = 4'b1000 - temp_byte1[7:4];
WALL_LOC = temp_byte2[2:0]; //
ABS_DIR = temp_byte2[4:3];

We used a 30 by 30 pixel tile template for each square the robot is in. We initialize it all to black and then add a red square in the middle to indicate that the robot has been there (as the background of the screen is black). Then depending on which walls were detected and the absolute direction of the robot, we write yellow pixels to the corresponding pixels in the tile template. We used four bit values to represent different colors that we decode later in the VGA driver module. Please see the Verilog code below for this implementation. 

if ((WALL_LOC[0] == 1 && ABS_DIR == 0) || (WALL_LOC[1] == 1 && ABS_DIR == 1) || (WALL_LOC[2] == 1 && ABS_DIR == 2)) begin
// have a wall to the right
// change the colors of the right three columns to be the wall color
	for (idx_row = 0; idx_row < 30; idx_row = idx_row + 1) begin
		tile_template[idx_row][27] = 4'b1111;
		tile_template[idx_row][28] = 4'b1111;
		tile_template[idx_row][29] = 4'b1111;
	end
end

if ((WALL_LOC[0] == 1 && ABS_DIR == 1) || (WALL_LOC[1] == 1 && ABS_DIR == 2) || (WALL_LOC[2] == 1 && ABS_DIR == 3)) begin
// have a wall to the front
// change the colors of the top three rows to be the wall color
	for (idx_col = 0; idx_col < 30; idx_col = idx_col + 1) begin
		tile_template[27][idx_col] = 4'b1111;
		tile_template[28][idx_col] = 4'b1111;
		tile_template[29][idx_col] = 4'b1111;
	end		
end

if ((WALL_LOC[0] == 1 && ABS_DIR == 2) || (WALL_LOC[1] == 1 && ABS_DIR == 3) || (WALL_LOC[2] == 1 && ABS_DIR == 0)) begin
// have a wall to the left
// change the colors of the top three rows to be the wall color
// can I use the idx_row variable again here?
	for (idx_row = 0; idx_row < 30; idx_row = idx_row + 1) begin
		tile_template[idx_row][0] = 4'b1111;
		tile_template[idx_row][1] = 4'b1111;
		tile_template[idx_row][2] = 4'b1111;
	end		
end

if ((WALL_LOC[0] == 1 && ABS_DIR == 3) || (WALL_LOC[1] == 1 && ABS_DIR == 0) || (WALL_LOC[2] == 1 && ABS_DIR == 1)) begin
// have a wall to the front
// change the colors of the top three rows to be the wall color
	for (idx_col = 0; idx_col < 30; idx_col = idx_col + 1) begin
		tile_template[0][idx_col] = 4'b1111;
		tile_template[1][idx_col] = 4'b1111;
		tile_template[2][idx_col] = 4'b1111;
	end	
end

Once this process is done, we set our variable updating to 1 to indicate that we can start updating the M9K RAM. We loop through the tile template and one by one assign the pixel values to the M9K RAM. This data is inputted to the VGA driver by the M9K RAM where we use a series of ternary operators to decode the color values and write the relevant colors to the screen. Our robot is red, walls are yellow, background is black, and grid is white - and we hardcoded in the yellow walls surrounding the maze. Below is the code used to decide the color used based on the 4 bit value stored in memory for each pixel. Please see the below image for an example of our output to the screen when testing our robot in a small maze. 

.PIXEL_COLOR_IN(VGA_READ_MEM_EN ? 
(MEM_OUTPUT == 4'b0010 ? BLUE : 
(MEM_OUTPUT == 4'b0001 ? RED: 
((MEM_OUTPUT == 4'b1111 ? YELLOW: 
(((VGA_PIXEL_X-15)%30 == 0 || (VGA_PIXEL_Y-15)%30 == 0) ? WHITE : 
(VGA_PIXEL_Y < 3)  || (VGA_PIXEL_Y >= 267) || (VGA_PIXEL_X < 3)  || (VGA_PIXEL_X >= 267)? YELLOW : BLACK))))) : BLUE),

5 x 6 Maze Mapping

Below are videos demonstrating the maze mapping ability of the robot. The first video is for a small maze near the lab benches, and the second video is on a test 9 x 9 maze.

2 x 3 Maze Mapping

9 x 9 Maze Mapping

Full Robotic Integration

Override Button

We added a push button to the robot to initiate maze mapping in case the robot fails to detect the 950-Hz tone. The robot will sit idle until either the 950-Hz tone is detected or the button is pressed.

while(!tone_flag && (digitalRead(BUTTON) != HIGH)){
	tone_detect();
}

Wall Sensing

Wall sensing has been improved by placing the wall sensors on a multiplexer freeing up analog pins for other uses. Each time the wall sensing function is called, the sensors are checked and the wall flags are updated.

void update_wall_sensors() { // reads wall sensors and updates flags
  left_wall_val = mux(WALL_L);
  mid_wall_val = mux(WALL_M);
  right_wall_val = mux(WALL_R);

  left_wall_flag = flag_update(left_wall_val, wall_threshold);
  mid_wall_flag = flag_update(mid_wall_val, wall_threshold);
  right_wall_flag = flag_update(right_wall_val, wall_threshold);
}

Robot Detection

Physically detecting other robots is simple using a phototransistor circuit with adjustable gain from a BJT and setting a flag whenever the digital pin attached to the circuit reads high. We used a potentiometer to vary the range of robot detection and achieve an optimal 1.5-foot detection distance.

robot_detected = digitalRead(PHOTOTRANSISTOR);

The code below shows how the robot takes action when a robot is detected. If there is a robot detected, it turn around 180 degrees and escape. Otherwise, it will continue forward and explore more of the maze. The switch statement below if for the forward explore state. The implementation for the other states is very similar.

switch(robot_detected) {
	case false:
	default:       
	  forward_explore(); // by default, continue with FORWARD_EXPLORE
	  break;
	case true:
	  turn(DIR_LEFT, DEG_180);
	  current_state = FORWARD_ESCAPE; // if robot detected during this state, go to FORWARD_ESCAPE
	  consecutive_turn_counter++;
	  break;
}

Navigation Algorithm and Robot Avoidance

Maze mapping and robot avoidance proved to be the most complex aspects of the robot’s behavior. Our robot uses a state machine to navigate this behavior. There are two phases of maze mapping, “forward” and “backtrack,” as well as two phases of robot avoidance, “explore” and “escape,” for a total of four states. Following an outline of the terminology used in our algorithm, the four possible robot states are described and outlined in the table that follows.

Terminology

The following list outlines the terminology used in our maze mapping and robot avoidance algorithm:

The Four Maze Mapping States

Mapping States

Stop Condition for Maze Exploration

If every visited node in the maze has all of its neighbors marked true (no matter whether the adjacent nodes have been visited), then the maze mapping is complete regardless of the configuration of the maze. This works even when there are closed sections within the maze. We only check for the stop condition when in the forward_explore state.

bool maze_complete() { // checks condition for completion of the maze
  for(int x = 0; x < MAZE_WIDTH; x++) {                         // iterate through each x coordinate
    for(int y = 0; y < MAZE_HEIGHT; y++) {                      // iterate through each y coordinate
      if(maze[x][y].visited) {                                  // if we've visited this node...
        for(int n = 0; n < 4; n++) {                            // ...and not every neighbor is marked true...
          if(maze[x][y].neighbor[n] == false) {
            return false; 
          } // ...then we're not done with the maze.
        }
      }
    }
  }
  return true;
}

Green LED

When the stop condition is met, the green LED is illuminated and the robot backtracks to (0,0) and stops.

// illuminate LED if maze complete
if(maze_done) {
	digitalWrite(LED_GREEN, HIGH);
}

9 x 9 Maze Robot Navigation