Algorithm Selection: DFS vs BFS

Study Notes

Depth-First Search (DFS) explores as far as possible along each branch before backtracking, but may not guarantee finding the shortest path, especially in grid scenarios.
DFS might get stuck in deep paths, especially if the goal is located far from the starting point.

BFS explores all neighbor nodes at each level before moving to the next level, guaranteeing a path to the end node.
BFS can be inefficient in grid scenarios with large branching factors, leading to extensive node exploration.

Dijkstra's algorithm is designed for finding the shortest path in weighted graphs with non-negative edge weights.
In grid scenarios with uniform edge weights of 1 unit, Dijkstra's algorithm may not offer significant advantages over A* while being less efficient due to lack of heuristic guidance.
Dijkstra's algorithm finds the optimal path but doesn't consider the goal's location during exploration.

A* algorithm guides the robot from its current position to a specified goal location within a grid-based environment.
A* initializes the robot's position and calculates heuristic values g(n), h(n), and f(n) for the current cell.
g(n) represents the cost of reaching the cell from the start point.
h(n) estimates the remaining distance to the goal using the Manhattan distance heuristic.
f(n) = g(n) + h(n), and the algorithm selects the next cell with the lowest f(n) value to progress towards the goal efficiently.
A* ensures an optimal and obstacle-aware route from the robot's starting point to the specified destination.

Manhattan distance measures the shortest path between two points by summing the horizontal and vertical distances, aligning well with the grid structure.
Manhattan distance is admissible, never overestimating the cost to reach the goal, making A* less likely to waste time exploring dead-end paths.

Before making a move, the robot checks its surroundings to detect obstacles and recalculates the path using A* to find an alternative route that bypasses the obstacle.

Step 1: Initialize data structures and variables, including start and goal vertices, priority queue, distances, previous vertices, and visited vertices.
Step 2: Explore neighbors in the main loop, removing the vertex with the lowest total cost from the priority queue, marking vertices as visited, and getting the adjacency list of the current vertex.
Step 3: Evaluate neighbor nodes, calculating coordinates based on the grid, skipping obstacles, and calculating the total cost for each neighbor.