ACS6121 - Unit 04 (Planning 2)

Question 1

What is a configuration space (C-space)?

Answer 1

The set of all possible configurations of a robot; each point represents a unique position/orientation.

Question 2

What does 𝐶_obs represent?

Answer 2

The set of all configurations where the robot collides with obstacles.

Question 2

What is the Minkowski difference used for?

Answer 2

To compute 𝐶_obs by “growing” obstacles with the shape of the robot.

Question 3

What is a roadmap in motion planning?

Answer 3

A graph embedded in 𝐶_free used to find paths using discrete search.

Question 4

What is vertical cell decomposition?

Answer 4

Divides 𝐶_free into convex cells by extending vertical lines from obstacle vertices.

Question 5

What makes sampling-based planning scalable?

Answer 5

It doesn’t require explicit computation of 𝐶_obs; instead, it samples and builds a graph incrementally.

Question 6

What are reflex vertices in motion planning?

Answer 6

Vertices in a polygon with internal angles greater than 𝜋, used in visibility graph methods.

Question 7

What is the tradeoff in sampling resolution?

Answer 7

High resolution = better accuracy but slower; low resolution = faster but might miss valid paths.

Question 8

What defines the topology of a space?

Answer 8

A set of open subsets satisfying specific closure and union rules.

Question 9

What is 𝐶_free?

Answer 9

The set of all configurations where the robot does not collide with any obstacles.

Question 10

1. Multiple Choice:
   Which roadmap method minimizes collision risk due to uncertainty?
   A) Vertical Cell Decomposition
   B) Maximum-Clearance (Voronoi)
   C) Visibility Graph
   D) Breadth-First Search

Answer 10

→ Correct Answer: B) Maximum-Clearance (Voronoi)

Question 11

2. True/False:
   In sampling-based planning, the robot always finds the shortest path.

Answer 11

→ False

Question 12

3. Fill in the Blank:
   The _______________ of a configuration space is the subset where the robot is not in collision.

Answer 12

→ Free space (𝐶_free)

Question 13

4. Short Answer:
   What are the two key properties a roadmap must satisfy?

Answer 13

→ It must be connected (a path exists if one exists in 𝐶_free) and reachable (initial and goal configurations can connect to it).

Question 14

5. Multiple Choice:
   Which of these is not a step in combinatorial planning?
   A) Compute 𝐶_obs
   B) Build roadmap
   C) Random sampling
   D) Discrete graph search

Answer 14

→ Correct Answer: C) Random sampling