Completed: / exercises

QUIZ 2: Geometric Transformations and Configuration Spaces

Due date: 2026-03-26 23:59.
Recommended Resources:

Question 1: Equivalent Action Sequences with Rotations

For a Gridbot with no obstacles, which of the following action sequences are equivalent to ↷ ↑ ↶ ↑ ↶, in terms of the robot’s final state?
Choose the correct answers:
Warning: You have not logged in. You cannot answer.

Question 2: Left-Turn Test

The left-turn test for a triple of points 𝑎, 𝑏, and 𝑐 computes the 𝑘-th component of the cross product:
\vec{V} \times \vec{W},
in which
\vec{V} = b - a, \quad \vec{W} = c - b. \\\
In two dimensions, this corresponds to:
\left( \vec{V} \times \vec{W} \right)_k = \begin{vmatrix} V_x & W_x \\ V_y & W_y \end{vmatrix} = V_x W_y - V_y W_x \, . \\\
  • If the result is positive, the points form a left turn.
  • If the result is negative, the points form a right turn.
  • If the result is zero, the points are collinear.
Consider the following five determinants:
\textbf{A:} \quad \begin{vmatrix} 1 & 0 \\ 0 & 1 \end{vmatrix} \\\
\textbf{B:} \quad \begin{vmatrix} 1 & 1 \\ 0 & 0 \end{vmatrix} \\\
\textbf{C:} \quad \begin{vmatrix} 0 & 1 \\ 1 & 0 \end{vmatrix} \\\
\textbf{D:} \quad \begin{vmatrix} 0 & -1 \\ 1 & 0 \end{vmatrix} \\\
\textbf{E:} \quad \begin{vmatrix} 2 & -3 \\ 3 & -1 \end{vmatrix} \\\
For each statement below about performing a left turn test for a triple of points 𝑎, 𝑏, and 𝑐, which ones are correct?
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 3: Configuration Space Obstacles, Minkowski Sums

Three base shapes are shown in the first row: a circle, a square, and an equilateral triangle. The origin of each shape is located at its center (indicated by a dot).
A robot 𝒜 and an obstacle 𝒪 are each defined as one of these shapes in ℝ². The robot is allowed to translate only (no rotation).
The configuration space obstacle is defined as: 𝒞_obs = 𝒪 ⊕ (−𝒜), in which ⊕ denotes the Minkowski sum.
Six candidate shapes (A–F) for 𝒞_obs are shown.
For each statement below, determine whether it correctly identifies the obstacle 𝒪 and robot 𝒜 that produce the given 𝒞_obs.
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 4: Metric Space Properties

A function 𝜌: ℝ² × ℝ² → ℝ is a metric if for all 𝑥, 𝑦, 𝑧:
  • 𝜌(𝑥, 𝑦) ≥ 0, and 𝜌(𝑥, 𝑦) = 0 iff 𝑥 = 𝑦.
  • 𝜌(𝑥, 𝑦) = 𝜌(𝑦, 𝑥) (symmetry).
  • 𝜌(𝑥, 𝑦) + 𝜌(𝑦, 𝑧) ≥ 𝜌(𝑥, 𝑧) (triangle inequality).
Consider the following ten functions, where 𝑥 = (𝑥₁, 𝑥₂) and 𝑦 = (𝑦₁, 𝑦₂):
\rho_1(x,y) = \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2} \quad \text{(Euclidean, } L^2\text{)} \\\
\rho_2(x,y) = |x_1-y_1| + |x_2-y_2| \quad \text{(Manhattan, } L^1\text{)} \\\
\rho_3(x,y) = \max(|x_1-y_1|, |x_2-y_2|) \quad \text{(} L^\infty\text{)} \\\
\rho_4(x,y) = (x_1-y_1)^2 + (x_2-y_2)^2 \quad \text{(squared Euclidean)} \\\
\rho_5(x,y) = 0, \forall x, y \in \mathbb {R}^2 \quad \text{(constant)} \\\
\rho_6(x,y) = \begin{cases} 0 & \text{if } x = y \\ 1 & \text{if } x \neq y \end{cases} \quad \text{(discrete)} \\\
\rho_7(x,y) = |x_1-y_1| \quad \text{(ignores second coordinate)} \\\
\rho_8(x,y) = (x_1-y_1) + (x_2-y_2) \quad \text{(signed differences)} \\\
\rho_9(x,y) = \left(|x_1-y_1|^4 + |x_2-y_2|^4\right)^{1/4} \quad \text{(}L^4\text{)} \\\
\rho_{10}(x,y) = |x_1 \cdot y_1 + x_2 \cdot y_2| \quad \text{(absolute dot product)} \\\
Which of the above are metrics?
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 5: Checking Metric Axioms from Distance Values

Consider three distinct points 𝑥 = (0, 0), 𝑦 = (3, 0), and 𝑧 = (0, 4) in ℝ².
Suppose a function 𝜌 is proposed as a metric. Assume that 𝜌 satisfies 𝜌(𝑎, 𝑎) = 0 for all 𝑎, and 𝜌(𝑎, 𝑏) = 𝜌(𝑏, 𝑎) for all 𝑎, 𝑏 (symmetry holds).
For each assignment of distances below, determine whether 𝜌 could be a valid metric (i.e., all three metric axioms are satisfied for these points).
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 6: Distances on a Flat Torus

Consider a two-link robot arm with joint angles 𝛼, 𝛽 ∈ [0, 2𝜋). A configuration is 𝑞 = (𝛼, 𝛽). The configuration space is 𝒞 = 𝑆¹ × 𝑆¹, a flat torus.
The distance between two angles on 𝑆¹ is:
d_{S^1}(\theta, \theta') = \min \{ |\theta - \theta'|, 2\pi - |\theta - \theta'|\} \\\
and the distance between two configurations 𝑞 = (𝛼, 𝛽) and 𝑞′ = (𝛼′, 𝛽′) on the torus is:
\rho(q, q') = \sqrt{d_{S^1}(\alpha, \alpha')^2 + d_{S^1}(\beta, \beta')^2} \\\
Compute distances and select all correct statements:
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 7: Configuration Space Dimension for Chains of Bodies

For each of the following robots, determine the dimension of the configuration space 𝒞. Select all correct statements.
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 8: Configuration Space Topology

For each system below, identify whether the stated configuration space 𝒞 is correct.
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 9: 2D Rotations

The 2D rotation matrix by angle 𝜃 is:
R(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} \\\
Which of the following are true?
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 10: 3D Rotations

The canonical 3D rotation matrices about the coordinate axes are:
R_z(\alpha) = \begin{bmatrix} \cos\alpha & -\sin\alpha & 0 \\ \sin\alpha & \cos\alpha & 0 \\ 0 & 0 & 1 \end{bmatrix} \\\
R_y(\beta) = \begin{bmatrix} \cos\beta & 0 & \sin\beta \\ 0 & 1 & 0 \\ -\sin\beta & 0 & \cos\beta \end{bmatrix} \\\
R_x(\gamma) = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos\gamma & -\sin\gamma \\ 0 & \sin\gamma & \cos\gamma \end{bmatrix} \\\
Which of the following are true?
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Authors

Anna LaValle, Steven M. LaValle.
?