The goal of this lab is to make the robot capable of maze exploration using DFS, BFS, Dijkstra, or A* (show that your robot can do different maze configurations, with at least one of them to be a minimum size of 4x5). In addition, the robot is also able to update the GUI.
We created a Matlab simulation of the robot traversing the maze. Each intersection is mapped as a xy coordinate with the first intersection denoted as (1,1). Since stacks can not be searched, we opted to use an array with a pointer. The search order was N,E,S,W. The pseudocode for the maze traversal displayed in the simulation is as follows:
if( next_pos is new && next_pos not blocked by wall){ advance to next_pos update path and cur_pos flag = 0 } else if(next_pos is old || blocked by wall){ change direction //(if current dir N => E, if E =>S, etc.) flag = flag +1 // flag is how many times direction changed if(flag == 4) //all options are either blocked or old from non blocked options, choose oldest, so robot will spend less in returning to position where it goes to a new square end }
To get a better understanding of the robot’s mapping capabilities, we mapped what the robot would ‘see’ if it had only a front wall sensor vs if it had three wall sensors (front, left and right). We found that it is necessary that the robot have three sensors in order to properly map the maze.
A updated and more efficient maze traversal algorithm is currently in progress, and will be continually optimized until the competition. The key difference between the two algorithms is how the robot reacts when all the neighboring points are either blocked by walls or have already been traversed. The new algorithm has a frontier array with a pointer (curfront); when the robot is in the situation described above, it traverses back until is able to reach the latest point in the frontier and advances accordingly from there.
Originally, we had been powering the radios with a power source in order to keep the voltage at 3.3V. Since the robot needs to be able to move around, we added a voltage regulator. This allows only 3.3V to be sent to the radio from the arduino, so the radio is able to function and the robot is no longer tethered to the power source.
The maze information is sent to the base station in a message that describes the data at each square. The main thing that is displayed on the GUI are the walls at each node. When the front and left wall sensors see a wall, they will update the corresponding bits to show that. We send the data to the base station in the following function:
void sendMessage(unsigned long message[3]){ // Ping out role. if (role == role_ping_out) { radio.stopListening(); printf("now sending %lu...",message); bool ok = radio.write(&message, sizeof(unsigned long)*3); if (ok) printf("ok..."); else printf("failed.\n\r"); radio.startListening(); // Wait here until we get a response, or timeout (250ms) unsigned long started_waiting_at = millis(); bool timeout = false; while ( ! radio.available() && ! timeout ) if (millis() - started_waiting_at > 200 ) timeout = true; // Describe the results if ( timeout ) printf("Failed, response timed out.\n\r"); else { // Grab the response, compare, and send to debugging spew unsigned long got_message[3]; radio.read( &got_message, sizeof(unsigned long)*3); // Spew it printf("Got response %lu, round-trip delay: %lu\n\r",got_message,millis()); } // Try again 1s later delay(1000); } // Pong back role. Receive each packet, dump it out, and send it back if ( role == role_pong_back ) { // if there is data ready if ( radio.available() ) { // Dump the payloads until we've gotten everything unsigned long got_message[3]; bool done = false; while (!done) { // Fetch the payload, and see if this was the last one. done = radio.read( &got_message, sizeof(unsigned long)*3 ); // Spew it and decryption to GUI printf("Got payload %lu...",got_message); //decrypt(got_message); // Delay just a little bit to let the other unit // make the transition to receiver delay(20); } radio.stopListening(); // Send the final one back. radio.write( &got_message, sizeof(unsigned long)*3 ); printf("Sent response.\n\r"); radio.startListening(); } }
Then, the actual traversal of the maze, along with GUI updates, is shown in the video below.
The depth-first search nature of the algorithm is emphasized in the fact that the robot travels in a certain direction for as long as it possible can until it is forced to backtrack its path. This occurs in the bottom right-hand corner and upper left-hand corner of the camera frame.
In addition, GUI updates are representative of what the camera actually sees. For example, the robot approaches a cell with two walls multiple times; however, only one wall get updated until the robot revisits it. We hope to optimize this feature by the competition by implementing a third wall sensor.
This clip tests the full functionality of the communication between the two radios, the packaging of the data, and decryption the array of data into the following print statements as expected (NOTE: not all print statements shown for the sake of condesing code length). A more in depth explanation is in Lab 3.
Serial.println("reset"); delay(1000); Serial.println("0,0,west=false"); delay(1000); Serial.println("1,0,south=true,west=true"); delay(1000); Serial.println("0,0,west=true,north=true"); delay(1000); Serial.println("0,1,north=true,east=true"); delay(1000); Serial.println("1,1,west=false"); delay(1000); Serial.println("2,1,west=false"); delay(1000); Serial.println("3,1,south=true"); delay(1000); Serial.println("3,0,west=true,south=true"); delay(1000); Serial.println("2,0,north=true,west=true,east=true"); delay(1000); Serial.println("3,0,west=true,south=true"); delay(1000); Serial.println("3,1,south=true"); delay(1000); Serial.println("3,2,east=true,south=true"); delay(1000); Serial.println("3,1,south=true");
The Milestone 3 Work Distribution is as follows:
- Vini: Matlab Simulation
- Nathalia and Priya: Radio Communication and GUI Updates
- Nathalia and Priya: Final Maze Traversal
The Lab Report Work Distribution is as follows:
- Nathalia: Code Explanations
- Priya: Code Section Write Up Drafts
- Nathalia: Pictures and Videos
The website work distribution is as follows:
- Nathalia: Website Milestone 3 Set Up and Maintenance