Global planner (A*, Dijkstra) in ROS - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ component_behavior

intermediate

What does the A* global planner output when given a grid map with obstacles?

Consider a ROS global planner using the A* algorithm on a grid map with obstacles. What will the planner output if a path exists?

A A direct straight line from start to goal ignoring obstacles

B A sequence of waypoints from start to goal avoiding obstacles

C An empty path because A* cannot handle obstacles

D A path that always goes around the map edges regardless of obstacles

💡 Hint

Think about how A* uses heuristics and cost to find paths around obstacles.

A* finds the shortest path by exploring nodes with the lowest estimated total cost, avoiding obstacles by considering them as blocked nodes.

📝 Syntax

intermediate

Which ROS message type is correct for publishing a global plan path?

In a ROS global planner node, which message type should be used to publish the planned path?

A nav_msgs/Path

B geometry_msgs/Twist

C sensor_msgs/LaserScan

D std_msgs/String

💡 Hint

The global plan is a sequence of poses representing the path.

The nav_msgs/Path message contains an array of poses representing the planned path for navigation.

🔧 Debug

advanced

Why does the Dijkstra planner in ROS fail to find a path on a known free map?

Given this simplified Dijkstra planner snippet in ROS, why does it fail to find a path even though the map is free?

while (!open_list.empty()) {
  current = open_list.top();
  open_list.pop();
  if (current == goal) break;
  for (auto neighbor : getNeighbors(current)) {
    if (visited[neighbor]) continue;
    cost[neighbor] = cost[current] + 1;
    open_list.push(neighbor);
  }
}

ROS

while (!open_list.empty()) {
  current = open_list.top();
  open_list.pop();
  if (current == goal) break;
  for (auto neighbor : getNeighbors(current)) {
    if (visited[neighbor]) continue;
    cost[neighbor] = cost[current] + 1;
    open_list.push(neighbor);
  }
}

A The cost is not incremented correctly, so path cost is always zero

B The goal condition is checked after popping, so it never breaks

C The open_list is a stack, causing depth-first search instead of Dijkstra

D The visited array is never updated, causing infinite loops or missed nodes

💡 Hint

Check if nodes are marked visited after processing.

The code never marks nodes as visited after popping them, so nodes can be revisited endlessly or skipped incorrectly.

❓ state_output

advanced

What is the final cost value for the goal node after running Dijkstra on a uniform cost grid?

In a ROS Dijkstra global planner on a grid where each move costs 1, what is the cost value stored for the goal node after completion?

A The number of steps from start to goal along the shortest path

B Zero, because cost is reset at the goal

C Infinity, since the goal is never updated

D The sum of all costs of all nodes in the grid

💡 Hint

Think about what Dijkstra calculates as cost for each node.

Dijkstra calculates the minimum cost to reach each node; for the goal, this is the shortest path length in steps.

🧠 Conceptual

expert

Why is A* generally preferred over Dijkstra for global planning in ROS navigation stacks?

Consider the differences between A* and Dijkstra algorithms in ROS global planners. Why is A* usually preferred?

A A* does not require a cost map, while Dijkstra does

B Dijkstra always finds longer paths than A* due to ignoring obstacles

C A* uses a heuristic to guide search, reducing explored nodes and improving speed

D Dijkstra cannot handle dynamic obstacles, but A* can

💡 Hint

Think about how heuristics affect search efficiency.

A* uses heuristics to estimate distance to goal, focusing search and reducing computation compared to Dijkstra's exhaustive search.

Practice

1. What is the main difference between the A* algorithm and Dijkstra's algorithm in ROS global planners?

easy

A. Dijkstra uses a heuristic, while A* explores all paths evenly.

B. A* uses a heuristic to guide the search, while Dijkstra explores all paths evenly.

C. Both algorithms use heuristics but in different ways.

D. Neither algorithm considers obstacles in the map.

Solution

1. Step 1: Understand Dijkstra's algorithm behavior

   Dijkstra explores all possible paths evenly without using heuristics, ensuring the shortest path but potentially slower.

2. Step 2: Understand A* algorithm behavior

   A* uses a heuristic function to estimate the cost to the goal, guiding the search more efficiently and often faster.

3. Final Answer:

   A* uses a heuristic to guide the search, while Dijkstra explores all paths evenly. -> Option B

4. Quick Check:

   Heuristic guides A*; Dijkstra explores evenly [OK]

Hint: Remember: A* uses heuristics, Dijkstra does not [OK]

Common Mistakes:

• Confusing which algorithm uses heuristics
• Thinking both ignore obstacles
• Assuming both explore paths the same way

2. Which of the following is the correct way to initialize a Dijkstra planner in ROS using C++?

easy

A. auto planner = new DijkstraPlanner();

B. DijkstraPlanner planner = new DijkstraPlanner();

C. auto planner = DijkstraPlanner();

D. DijkstraPlanner planner();

Solution

1. Step 1: Understand object initialization in modern C++

   Using 'auto' with direct initialization calls the constructor properly and manages type automatically.

2. Step 2: Analyze each option

   auto planner = new DijkstraPlanner(); uses 'new' which returns a pointer, not an object. DijkstraPlanner planner = new DijkstraPlanner(); attempts to assign a pointer to an object, causing a type mismatch compile error. DijkstraPlanner planner(); is a function declaration, not an object. auto planner = DijkstraPlanner(); correctly initializes an object with automatic type deduction.

3. Final Answer:

   auto planner = DijkstraPlanner(); -> Option C

4. Quick Check:

   Use auto with constructor for clean initialization [OK]

Hint: Use 'auto planner = ClassName();' for simple object creation [OK]

Common Mistakes:

• Using parentheses that declare a function, not an object
• Using 'new' without managing pointers
• Not using auto for type deduction

3. Given the following ROS global planner code snippet using A*:

std::vector<Point> path = planner.makePlan(start, goal);
std::cout << path.size() << std::endl;

If the planner finds a path with 5 points, what will be printed?

medium

A. 0

B. 4

C. 6

D. 5

Solution

1. Step 1: Understand the return value of makePlan()

   The makePlan function returns a vector of points representing the path from start to goal, including both points.

2. Step 2: Analyze the output of path.size()

   If the planner finds a path with 5 points, the vector size is 5, so printing path.size() outputs 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Path points count equals vector size [OK]

Hint: Path size equals number of points including start and goal [OK]

Common Mistakes:

• Assuming path size excludes start or goal
• Confusing index with size
• Thinking path size counts edges, not points

4. You have this snippet in your ROS global planner node:

std::vector<Point> path = planner.makePlan(start, goal);
for (int i = 0; i <= path.size(); i++) {
  std::cout << path[i].x << "," << path[i].y << std::endl;
}

What is the error in this code?

medium

A. Using <= in the loop causes out-of-bounds access.

B. The loop variable should be a float, not int.

C. The path vector is not initialized.

D. The makePlan function does not return a vector.

Solution

1. Step 1: Analyze the loop condition

   The loop runs from i = 0 to i <= path.size(), which means it tries to access path[path.size()] on the last iteration.

2. Step 2: Understand vector indexing

   Vectors are zero-indexed, so valid indices are 0 to path.size() - 1. Accessing path[path.size()] causes out-of-bounds error.

3. Final Answer:

   Using <= in the loop causes out-of-bounds access. -> Option A

4. Quick Check:

   Loop index must be less than size, not less or equal [OK]

Hint: Use i < path.size() in loops to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= instead of < in loops
• Confusing vector size with last index
• Assuming makePlan returns empty vector

5. In a ROS global planner using A*, you want to modify the heuristic to prefer paths farther from obstacles for safety. Which approach correctly applies this change?

hard

A. Add a penalty to the heuristic cost for points near obstacles.

B. Subtract a penalty from the heuristic cost for points near obstacles.

C. Add a penalty to the heuristic cost for points far from obstacles.

D. Ignore the heuristic and use Dijkstra instead.

Solution

1. Step 1: Understand heuristic modification goal

   To prefer paths farther from obstacles, the heuristic should favor those points by lowering their cost or penalizing points near obstacles.

2. Step 2: Analyze penalty application

   Adding a penalty to the heuristic cost for points near obstacles increases their cost, which discourages paths near obstacles, as desired for safety.

3. Step 3: Choose correct approach

   Add a penalty to the heuristic cost for points near obstacles. correctly adds a penalty to points near obstacles, increasing their heuristic cost and discouraging proximity for safer paths.

4. Final Answer:

   Add a penalty to the heuristic cost for points near obstacles. -> Option A

5. Quick Check:

   Modify heuristic cost to prefer points near obstacles [OK]

Hint: Adjust heuristic cost to favor desired path traits [OK]

Common Mistakes:

• Confusing penalty direction for heuristic
• Ignoring heuristic and switching algorithms unnecessarily
• Not understanding heuristic impact on path choice