P3S Path Planning Project Post

In the field of autonomous robotics, simultaneous localization and mapping, or SLAM, is a vital technology that makes it possible for automated robots to navigate through unfamiliar environments with ease. Two crucial tasks in this intricate process are mapping, which entails creating a map of the surrounding area, and localization, which involves the robot figuring out its own position in relation to a map. The robot has a lidar that allow it to gather precise environmental data. The robot uses this data to carefully feed into specialized SLAM algorithms, which are meant to continuously improve and update its understanding of its own location and gradually create a complete map of its surroundings.

The method of choice for path planning in our project was the Breadth-First Search (BFS) algorithm. This choice was mainly motivated by the intrinsic properties of BFS: its simplicity and effectiveness in finding the shortest path in an unweighted graph. Because of the way BFS explores the environment, it is especially well-suited for this task. It makes sure that no viable path is missed by methodically assessing every option. The mBot’s ability to navigate and map its environment effectively is enhanced by the implementation of BFS, which enables it to make thoughtful decisions at every turn.

BFS Implementation Overview:
The pseudocode below provides a simplified overview of our BFS implementation:

function breadthFirstSearch(start, goal, grid):
Initialize an empty queue
Initialize a set for visited nodes
Initialize a map to track the parent of each visited node

Enqueue the start node into the queue
Add the start node to the visited set

while the queue is not empty:
    Dequeue a node from the front of the queue

    if this node is the goal:
        return reconstructPath(goal, parentMap)

    for each neighbor of the current node:
        if neighbor is not in visited set and not blocked:
            Enqueue the neighbor
            Add the neighbor to visited set
            Mark the current node as the parent of the neighbor

return an empty path if the goal is not reachable

function reconstructPath(goal, parentMap):
Initialize an empty path list
Set the current node as the goal

while current node is not null:
    Insert the current node at the beginning of the path list
    Set the current node to its parent in the parentMap

return the path list

The Breadth-First Search (BFS) algorithm begins by initializing data structures for node traversal: a queue for nodes to be visited, a set to track visited nodes, and a map for parent tracking. Nodes are dequeued and their neighbors are examined; unvisited, accessible neighbors are enqueued and marked as visited, with their parent noted for path reconstruction. If a dequeued node is the goal, a path is formed from the goal to the start by tracing each node's parent from the map. If the goal is unreachable, the algorithm concludes by returning an empty path. This process ensures a systematic exploration of the environment, ultimately finding the shortest path to the goal, if one exists.

Map and Path Visualization

During the implementation, I visualized the robot’s path and the map it traversed. This involved highlighting visited cells, the current path, and obstacles.

Initial Map: Shows the grid with start and goal positions, along with any obstacles.

During BFS: Visited cells are marked, showing the expanding search area.

Final Path: Once the goal is reached, the path from start to goal is highlighted.

Pros and Cons: Path planning vs. Bug Algorithm

The global search strategy, which is frequently represented by algorithms such as Breadth-First Search (BFS), provides an all-encompassing examination of the surroundings by carefully assessing every possible path in order to determine the most effective one. This helps the robot weigh all the options and choose the best course, especially in complex environments with multiple possible routes. This thoroughness can, however, be a disadvantage as it frequently necessitates substantial computational resources and time, particularly in complex or large-scale environments. The Bug algorithm, on the other hand, takes a more localized approach, concentrating on the immediate environment for navigation. This may not always result in the shortest or most efficient path, especially in environments with complex obstacles, even though it can be faster and more efficient in terms of computation. Furthermore, global search methods bridge the gap left by the Bug algorithm’s limitations in scenarios where a more comprehensive understanding of the environment is required by taking the entire map into account when determining a path.

Reflection on the implementation process

The application of the Bug algorithm clarified several autonomous navigation strategies and demonstrated how a robot such as the mBot can navigate using a straightforward, goal-oriented methodology. The integration of the BFS algorithm presented a more significant challenge, especially in terms of allowing the robot to navigate to each cell accurately while taking into account all directional movements (up, down, left, and right). The challenge was making sure the robot could precisely track and follow the chosen path, which was essential to the BFS algorithm’s effectiveness. However, I also faced some challenges to. Getting the robot to go the desired output, I had to create a path to the target which was really hard to accomplish at first.

The coding part also required a lot of work on the finding the path. One really hard aspect of the project was to implement the BFS algorithm. The algorithm sounds simple enough when you understand it, but it was really hard to come up with the coding solution for it. I had to do a lot of testing for it. When I finally completed this, I ran the output from the build that I got to the navigation website and was successful in finding a path to all the maze that was given to us. I also created my own map for running a demo in the course. I ran the output of the build file in the website and it worked perfectly fine. However, I couldn’t run the code on the robot in real time to navigate the maze. The probable reasons for this might include navigation or the bug in the modules or API. However, Overall It was a great project where I got to learn a lot of the navigation processes on mBot.