A path finding robot is searching for shortest path Which algorithm will you select? Why? Write the steps how your chosen algorithm works.

Algorithm: A* (A-Star) Search

Why?

• Always finds the shortest path (if the heuristic never overestimates).
• Faster than Dijkstra/BFS because a heuristic guides it toward the goal.
• Complete: finds a path if one exists.

Key formula: f(n) = g(n) + h(n)

• g(n) = actual cost from start to node n
• h(n) = estimated cost from n to goal (e.g., Manhattan or Euclidean distance)

Steps:

1. Put the start node in the open list (g = 0); the closed list is empty.
2. Select the node with the lowest f(n) from the open list.
3. If it is the goal, stop and go to step 7.
4. Move it to the closed list.
5. For each neighbor (skip obstacles and closed nodes): compute g, h, and f; add it to the open list or update it if a cheaper path is found, recording the current node as its parent.
6. Repeat from step 2. If the open list becomes empty, no path exists.
7. Trace parent links back from the goal to the start to get the shortest path.

— rhs