====== BFS & DFS Implementation (2023) (IN-PROGRSS) ======
**Author:** Francis Palustre Email: <palusf1@unlv.nevada.edu>
\\
**Date:** Last modified on <11/13/23>
\\
**Keywords:** Navigation, BFS, DFS, Robotino, cpp,
\\

{{ :sampleimageforwritingtutorial.jpg?200 |}}
\\
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 =====
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>  
  * Know how to code in CPlusPlus and are familiar with function handling
\\
  * Know how Breadth-First and Depth-First Search algorithms work
\\
  * Know how to navigate within the terminal in Linux
\\
  * This tutorial may also attract readers who are interested in implementing algorithms in their own projects
</fc>
\\ \\ 
The rest of this tutorial is presented as follows:
  * [[bfs_and_dfs_implementation_v2#setup_and_understanding|Setup and Understanding]]
  * [[bfs_and_dfs_implementation_v2#general_functions|General Functions]]
  * [[bfs_and_dfs_implementation_v2#robotino_functions|Robotino Functions]]
  * [[bfs_and_dfs_implementation_v2#breadth_first_search|Breadth First Search]]
  * [[bfs_and_dfs_implementation_v2#depth_first_search|Depth First Search]]
  * [[bfs_and_dfs_implementation_v2#final_words|Final Words]]

==== Setup and Understanding ====
To setup Robotino, please take a look at the following wikis:
\\
[[https://www.daslhub.org/unlv/wiki/doku.php?id=how_to_setup_robotino_for_programming_and_navigation|How to Setup Robotino for Programming and Navigation]]
\\
[[https://www.daslhub.org/unlv/wiki/doku.php?id=robotino_api2_setup|Robotino API2 Setup]]
\\
[[https://www.daslhub.org/unlv/wiki/doku.php?id=robotino_hello_world|Hello World on the Robotino]]
\\
\\
To understand how Breadth-First Search and Depth-First Search work, please take a look at the following wikis and links:
\\
[[https://www.daslhub.org/unlv/wiki/doku.php?id=breadth-first_search_and_depth-first_search|Breadth-First Search and Depth-First Search]]
\\
\\
[[https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/|Breadth-First Search (GeeksForGeeks)]]
\\
[[https://www.programiz.com/dsa/graph-bfs/|Breadth-First Search (Programiz)]]
\\
\\
[[https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/|Depth-First Search (GeeksForGeeks)]]
\\
[[https://www.programiz.com/dsa/graph-dfs|Depth-First Search (Programiz)]]
==== General Functions ====
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.

    double getCurrentTime() {
         struct timeval tv; //timeval struct to store time values
         gettimeofday(&tv, NULL); //get current time and store in timeval
         
         //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 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====
 {{ youtube>GH0YCbQobio?large }}
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 ====
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 ====

This tutorial's objective was to implement the BFS and DFS algorithm into Robotino using an alternative method when compared to the first version. Complete source code for the algorithms can be found at the beginning of the tutorial. Once the concepts were conveyed the reader could try to implement BFS and DFS and other path planning algorithms into their own projects.
\\
\\
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.
\\
\\
For questions, clarifications, etc, Email: <palusf1@unlv.nevada.edu>