Mobile Robot Control 2024 Ultron:Solution 3

Exercise 3: Global Navigation

A* Algorithm

The A* algorithm is a widely used heuristic search algorithm for finding the shortest path from a start node to a goal node in a graph. It combines the strengths of Dijkstra's algorithm and Greedy Best-First-Search. The core idea of A* is to use a heuristic function to prioritize paths that seem more promising to reach the goal.

The steps for running the algorithm for A* are as follows.

1. Initialization:
   • Create the open list (priority queue) and closed list (empty).
   • Initialize the start node with g(start) = 0 and f(start) = h(start), then add it to the open list.
2. Main Loop:
   • While the open list is not empty:
     • Select the node current from the open list with the lowest f value.
3. Goal Check:
   • If current is the goal node, reconstruct and return the path from start to goal.
4. Process Neighbors:
   • For each neighbor of current:
     • Ignore the neighbor if it's in the closed list.
     • Calculate the tentative g value (tentative_g = g(current) + cost(current, neighbor)).
     • If the neighbor is not in the open list or the tentative g is lower than g(neighbor):
       • Update g(neighbor), f(neighbor), and set the parent of the neighbor to current.
       • Add the neighbor to the open list if it's not already there.
5. Path Reconstruction or Failure:
   • If the goal is reached, reconstruct the path using the parent references.
   • If the open list is empty and the goal has not been reached, return failure indicating no path exists.

A* implementation assignment

1. Initialization:
   • Create the open list (priority queue) and closed list (empty).
   • Initialize the start node with g(start) = 0 and f(start) = h(start), then add it to the open list.
2. Main Loop:
   • While the open list is not empty:
     • Select the node current from the open list with the lowest f value.
3. Goal Check:
   • If current is the goal node, reconstruct and return the path from start to goal.

Answers of the questions

1. How could finding the shortest path through the maze using the A* algorithm be made more efficient by placing the nodes differently? Sketch the small maze with the proposed nodes and the connections between them. Why would this be more efficient?

2. Would implementing PRM in a map like the maze be efficient?

3. What would change if the map suddenly changes (e.g. the map gets updated)?

4. How did you connect the local and global planner?

5. Test the combination of your local and global planner for a longer period of time on the real robot. What do you see that happens in terms of the calculated position of the robot? What is a way to solve this?

6. Run the A* algorithm using the gridmap (with the provided nodelist) and using the PRM. What do you observe? Comment on the advantage of using PRM in an open space.