ACS6121 - Unit 03 (Planning 1)

Question 1

What is the main goal of path planning in robotics?

Answer 1

To find a sequence of actions that moves a robot from an initial to a goal state.

Question 2

How are discrete spaces typically represented in robot planning?

Answer 2

As a graph, where states are vertices and actions are edges.

Question 3

What is the key difference between DFS and BFS?

Answer 3

DFS uses a stack and may go deep quickly; BFS uses a queue and explores level by level.

Question 4

What does Dijkstra’s algorithm minimize?

Answer 4

The total cost-to-come from the initial state to each node.

Question 5

What does A* use in addition to cost-to-come 𝑔(𝑥)?

Answer 5

A heuristic estimate of cost-to-go ℎ(𝑥).

Question 6

When is the A* algorithm guaranteed to find the optimal solution?

Answer 6

When the heuristic is admissible (i.e. never overestimates the true cost).

Question 7

What are common distance metrics used as heuristics in A*?

Answer 7

Manhattan distance (𝐿_1) and Chebyshev distance (𝐿_∞).

Question 8

Why is Dijkstra’s algorithm inefficient on large graphs?

Answer 8

It explores all possible paths without any guidance toward the goal.

Question 9

What does it mean if a vertex is “alive” in a search?

Answer 9

It’s in the queue and may still be expanded.

Question 10

What kind of planning is covered in this unit?

Answer 10

Discrete global planning using graph search algorithms.

Question 11

1. Multiple Choice:
   Which algorithm always finds the shortest path in a graph with equal edge weights?
   A) Depth First Search
   B) Breadth First Search
   C) Greedy Search
   D) Random Walk

Answer 11

→ Correct Answer: B) Breadth First Search

Question 12

2. True/False:
   A* is guaranteed to find an optimal path if the heuristic overestimates the true cost.

Answer 12

→ False

Question 13

3. Fill in the Blank:
   In A*, the priority function is 𝑓(𝑥) = ___+___

Answer 13

→ g(x) + h(x)

Question 14

4. Short Answer:
   What makes A* more efficient than Dijkstra’s algorithm?

Answer 14

→ It uses a heuristic to guide the search toward the goal.

Question 15

5. Multiple Choice:
   Which metric is best suited for 4-directional grid movement?
   A) Chebyshev
   B) Manhattan
   C) Euclidean
   D) Angular

Answer 15

→ Correct Answer: B) Manhattan