What Is SLAM?
SLAM or Simultaneous Localization and Mapping, is the process of how the mbot builds a map using its radar. The mbot does this by first using the Lidar on top to scan its surroundings and then using its starting position as a basis to build the map around it. To do this it it makes estimates of whether a space is filled or not based on the confidence of the grid spaces it scans. It then has three different types of squares occupied squares, marked as grey, unoccupied squares marked as white, and unknown squares marked with grey. It is however important to note that SLAM is susceptible to noise which and be caused by moving too quickly through a space or going over it again.
Early Image of a SLAM Generated Map with a little bit of noise
My Algorithm
My path-planning algorithm uses Breadth First Search to look through the grid of the map coordinate square by coordinate square until it reaches its goal. The first step that it takes is to initialize the map’s cells. I do this with two loops and assign the x and y coordinates as well as the cell’s index. This loop also assigns each cell a visited and queued bool value, this is used later to determine whether a cell has already been visited so that I don’t re-add and change the parents of a cell that already exists. The next step in my algorithm is to start the graph search, I find the neighbors. I actually ran into some issues with this step where I accidentally mirrored the x and y coordinated causing my robot to teleport and then run away from the goal.
After it finds the neighbors it assigns those neighbors the parent of the current node. Finally, it takes the neighbors, adds them to the to-visit list, and then takes the node at the front of the to-visit list and repeats the process until the list is empty or the goal target is located. I ran into an issue with the implementation of this section due to the issues mentioned above and it took piecemeal testing to fix these issues. I think the biggest challenge I ran into in this project was the above mentioned issue, as it stumped me on what was wrong for the longest time. I had tested multiple other things and accidentally looked over the fact that the x and y values I was calling for were reversed.
An Image of my Path Finding Algorithm Tested on a SLAM-made map
Final Thoughts
When comparing this, to my experience with the Bug Algorithm, I found this generally easier, due to the fact I could test my algorithm at any time without a robot. As for the other pros and cons, for a path planning algorithm, you generally need to know what the location looks like in advance. However, if you are using a bug algorithm, it can move toward the area without seeing it as long as you have some sort of obstacle detection. This is why each of these has their own pros and cons.
