Author: Francis Palustre Email: palusf1@unlv.nevada.edu
Date: Last modified on <11/09/23>
Keywords: Navigation, BFS, DFS, Robotino, cpp,

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.

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:

* 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 interesting in implementing algorithms in their own projects

The rest of this tutorial is presented as follows:

• Setup and Understanding
• General Functions
• Robotino Functions
• Breadth First Search
• Depth First Search
• Final Words

To setup Robotino, please take a look at the following wikis:
How to Setup Robotino for Programming and Navigation
Robotino API2 Setup
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:
Breadth-First Search and Depth-First Search

Breadth-First Search (GeeksForGeeks)
Breadth-First Search (Programiz)

Depth-First Search (GeeksForGeeks)
Depth-First Search (Programiz)

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 are functions that used for Robotino's movement

Algorithm for BFS

Algorithm for DFS

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 <fill in the blank>. In the big picture, the problem of <fill in the blank> can be solved with this tutorial.

For questions, clarifications, etc, Email: palusf1@unlv.nevada.edu