DASL Wiki

User Tools

Site Tools

Trace:
bfs_and_dfs_implementation_v2

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
bfs_and_dfs_implementation_v2 [2023/11/09 17:39] – [General Functions] fpalustrebfs_and_dfs_implementation_v2 [2023/11/13 09:56] (current) – fpalustre
Line 1: Line 1:
-====== BFS & DFS Implementation V2 (IN-PROGRSS) ======+====== BFS & DFS Implementation (2023) (IN-PROGRSS) ======
 **Author:** Francis Palustre Email: <palusf1@unlv.nevada.edu> **Author:** Francis Palustre Email: <palusf1@unlv.nevada.edu>
 \\ \\
-**Date:** Last modified on <11/09/23>+**Date:** Last modified on <11/13/23>
 \\ \\
-**Keywords:** Navigation, BFS, DFS, Robotino, C++,+**Keywords:** Navigation, BFS, DFS, Robotino, cpp,
 \\ \\
  
 {{ :sampleimageforwritingtutorial.jpg?200 |}} {{ :sampleimageforwritingtutorial.jpg?200 |}}
 \\ \\
-The photo above depicts <fill in the blank> which allows you to <fill in the blank>. The big picture problem is <fill in the blank>. Solving this partially or completely is important because <fill in the blank>. This tutorial shows you how to <fill in the blank> and takes approximately <fill in the blank> hours to complete. +The photo above depicts the environment used for travel which allows you to visually see the intended path that should be taken for Robotino . The big picture problem is understanding the traversal process and how it came to be. Solving this partially or completely is important because this gives robots an autonomous navigation process, limiting human interference. This tutorial shows you how to apply BFS and DFS to Robotino and should take approximately 1-2 hour to complete. 
 \\ \\
 ===== Motivation and Audience ===== ===== Motivation and Audience =====
-This tutorial's motivation is to find ways for robots to autonomously navigate their environments. Readers of this tutorial assumes the reader has the following background and interests: +This tutorial's motivation is to find ways for robots to autonomously navigate within their environments. Readers of this tutorial assumes the reader has the following background and interests: 
  
 <fc blue>   <fc blue>  
Line 21: Line 21:
   * Know how to navigate within the terminal in Linux   * Know how to navigate within the terminal in Linux
 \\ \\
-  * This tutorial may also attract readers who are interesting in implementing algorithms in their own projects+  * This tutorial may also attract readers who are interested in implementing algorithms in their own projects
 </fc> </fc>
 \\ \\  \\ \\ 
Line 57: Line 57:
 ==== General Functions ==== ==== General Functions ====
 General functions are functions that are found in both files of BFS and DFS General functions are functions that are found in both files of BFS and DFS
-\\ 
 \\ \\
   * getCurrentTime() gets the current time in UTC in seconds. It is used to provide the time needed for a movement for Robotino.   * getCurrentTime() gets the current time in UTC in seconds. It is used to provide the time needed for a movement for Robotino.
Line 64: Line 63:
          struct timeval tv; //timeval struct to store time values          struct timeval tv; //timeval struct to store time values
          gettimeofday(&tv, NULL); //get current time and store in timeval          gettimeofday(&tv, NULL); //get current time and store in timeval
-         return (tv.tv_sec) + tv.tv_usec / 1000000.0; //convert time to seconds and add microseconds for precision+          
 +         //convert time to seconds and add microseconds for precision 
 +         return (tv.tv_sec) + tv.tv_usec / 1000000.0; 
 +    } 
 + 
 +  * roboMove() prints the final path from the algorithm and will result into the movement of Robotino 
 + 
 +    void roboMove(map<string, vector<string> > newGraph, string startNode, string desiredNode) { 
 +         vector<string> roboPath = BFS(newGraph, startNode, desiredNode); //or DFS 
 +          
 +         //couts the final path 
 +         for (vector<string>::iterator it = roboPath.begin(); it != roboPath.end(); it++) { 
 +             cout << *it << " "; 
 +          } cout << endl; 
 +           
 +         //movement of Robotino 
 +         for (int i = 0; i < int(roboPath.size()) - 1; i++) { 
 +             //movement is based on current and next value in path 
 +             int currPos = atoi(roboPath.at(i).c_str()); 
 +             int nextPos = atoi(roboPath.at(i + 1).c_str()); 
 +              
 +              if ((currPos + 6) == nextPos) { 
 +                  moveY(0,1); 
 +              } 
 +               
 +              if ((currPos - 6) == nextPos) { 
 +                  moveY(1,0); 
 +              } 
 +               
 +              if ((currPos - 1) == nextPos) { 
 +                  moveX(1,0); 
 +              } 
 +               
 +              if ((currPos + 1) == nextPos) { 
 +                  moveX(0,1); 
 +              } 
 +         } 
 +         omni.setVelocity(0,0,0); 
 +    } 
 +  
 +  * removeEdges() removes the edges of selected nodes. Can be used to represent obstacles/walls. Works because you can have a disconnected graph (as in, floating nodes), but you cannot have unconnected edges 
 + 
 +    map<string, vector<string> > removeEdges(map<string, vector<string> > graph, vector<string> removeVec) { 
 +         for (vector<string>::iterator it = removeVec.begin(); it != removeVec.end(); it++) { //for every edges of the current node... 
 +         vector<string> adjNodes = graph[*it]; 
 +          
 +         for (vector<string>::iterator edges = adjNodes.begin(); edges != adjNodes.end(); edges++) { //for every node of those edges... 
 +              for (vector<string>::iterator it = roboPath.begin(); it != roboPath.end(); it++) { 
 +                    
 +                   //disconnects the connected nodes from current edge 
 +                   vector<string>::iterator removeNode = remove(graph[*edges].begin(), graph[*edges].end(), *it); 
 +                    
 +                   graph[*edges].erase(removeNode, graph[*edges].end()); //getting rid of edges  
 +               } 
 +               graph[*it].clear(); //removing current node 
 +         }
     }     }
 ==== Robotino Functions ==== ==== Robotino Functions ====
 Robotino functions are functions that used for Robotino's movement Robotino functions are functions that used for Robotino's movement
 +
 +  * moveX() is the movement in the horizontal direction
 +
 +    void moveX(int first, int second) {
 +         int checker = first - second; //determines if movement is positive or negative
 +         int distance = abs(checker); //how much travel is needed
 +         
 +         double start_time = getCurrentTime();
 +         double end_time = (distance * 1.772)+ start_time; //offset of 1.772 is used (can change to whatever is yours)
 +         double elapsed_time = 0;
 +         
 +         for (int i =0; i < distance;i++) {
 +              if (checker > 0) { //if positive...
 +                   elapsed_time = 0; //resetting time to avoid continous movement
 +                   do {
 +                       elapsed_time = getCurrentTime(); //updating elapsed time
 +                       omni.setVelocity(0.0015,-0.2,0); //velocity of Robotino (adjust accordingly)
 +                       } while (elapsed_time < end_time);
 +              } else { //if negative...
 +                   elapsed_time = 0;
 +                   do {
 +                       elapsed_time = getCurrentTime();
 +                       omni.setVelocity(-0.00151,0.2,0);
 +                   } while (elapsed_time < end_time);
 +              }
 +         }
 +         omni.setVelocity(0,0,0); //setting velocity to 0 for precautionary sake
 +    }
 +
 +  * moveY() is the movement in the vertical direction
 +
 +    void moveY(int first, int second) { //same comments applied to this function
 +         int checker = first - second;
 +         int distance = abs(checker);
 +         
 +         double start_time = getCurrentTime();
 +         double end_time = (distance * 1.772)+ start_time;
 +         double elapsed_time = 0;
 +         
 +         for (int i =0; i < distance;i++) {
 +              if (checker > 0) { //if positive...
 +                   elapsed_time = 0;
 +                   do {
 +                       elapsed_time = getCurrentTime();
 +                       omni.setVelocity(0.2,-0.00131,0);
 +                       } while (elapsed_time < end_time);
 +              } else {
 +                   elapsed_time = 0;
 +                   do {
 +                       elapsed_time = getCurrentTime();
 +                       omni.setVelocity(0.2,-0.00131,0);
 +                   } while (elapsed_time < end_time);
 +              }
 +         }
 +         omni.setVelocity(0,0,0);
 +    }
 ==== Breadth First Search==== ==== Breadth First Search====
 + {{ youtube>GH0YCbQobio?large }}
 Algorithm for BFS Algorithm for BFS
 +
 +    vector<string> BFS(map<string, vector<string> > graph, string startingNode, string desiredNode) {
 +         //Creating containers of visited and queued nodes
 +         vector<string> visited;
 +         queue<vector<string> > queue;
 +         
 +         queue.push(vector<string>(1, startingNode)); //starting the queue with our starting node
 +         
 +         while (!queue.empty()) {
 +             vector<string> path = queue.front(); //store node item in path
 +             queue.pop(); //removes node from queue
 +             
 +             string currNode = path.back(); //tailed node becomes current node
 +             
 +             //iterates through a set to find the current value in the path
 +             vector<string>::iterator findCurr = find(visited.begin(), visited.end(), currNode);
 +             
 +             if (findCurr == visited.end()) {
 +                  visited.push_back(currNode); //marks as visited
 +                  
 +                  vector<string> adjNodes = graph[currNode]; //neighbor nodes of current
 +                  
 +                  for (vector<string>::iterator it = adjNodes.begin(); it != adjNodes.end(); it++) { //iterates through the adjNodes
 +                      vector<string> newPath = path;
 +                      newPath.push_back(*it); //add neighbor to newPath vector
 +                      queue.push(newPath); //adds resultant path to queue
 +                      
 +                      if (*it == desiredNode) { //if desired found, return current path
 +                         return newPath;
 +                      }
 +                  }
 +              }
 +          }
 +          //if no path, return empty vector
 +          return vector<string>();
 +    }
 +
 ==== Depth First Search ==== ==== Depth First Search ====
-Algorithm for DFS+Algorithm for DFS.  
 +\\ 
 +There are two ways to traverse in DFS, an iterative approach and recursive approach. The following is a recursive approach because it is the most common. In the source code, there will be iterative as well. 
 + 
 + 
 +    vector<string> DFS(map<string, vector<string> > &graph, const string &startingNode, const string &desiredNode, map<string, bool> &visited) { 
 +         //mark the current node as visited 
 +         visited[startingNode] = true; 
 +          
 +         //containers of current path 
 +         vector<string> path; 
 +          
 +         //get adjacent nodes of starting node 
 +         vector<string> adjNodes = graph[startingNode]; 
 +          
 +         //iterate through adjacent nodes 
 +         for ( vector<string>::iterator it = adjNodes.begin(); it != adjNodes.end(); it++) { 
 +             const string& nextNode = *adjNodes; 
 +              
 +              //check if next node has been visited 
 +              if (!visited[nextNode]) { 
 +                 //recursively call DFS on the next node 
 +                  vector<string> subPath = DFS(graph, nextNode, desiredNode, visited); 
 +                   
 +                  //if subPath not empty, path to desired node is found 
 +                  if (!subPath.empty()) { 
 +                     //insert current node at beginning of subPath and return final path 
 +                     subPath.insert(subPath.begin(), startingNode); 
 +                     return subPath; 
 +                  } 
 +              } 
 +          } 
 +          //if no path, return empty vector 
 +          return vector<string>(); 
 +    } 
 ==== Final Words ==== ==== Final Words ====
  
Line 77: Line 260:
 \\ \\
 \\ \\
-Speculating future work derived from this tutorial, includes <fill in the blank>. In the big picture, the problem of <fill in the blank> can be solved with this tutorial.+Speculating future work derived from this tutorial, includes applying these and other algorithms such as Dijkstra and A* to Robotino and other robots. In the big picture, the problem of autonomous navigation can be solved with this tutorial.
 \\ \\
 \\ \\
bfs_and_dfs_implementation_v2.1699580361.txt.gz · Last modified: by fpalustre