HW2: Discrete Planning, Geometric Modeling – Fundamentals of Sensing, Tracking, and Autonomy 2

Question 1: Value Iteration vs. Dijkstra, Running Times¶

In this exercise, you will experimentally compare value iteration and forward Dijkstra search for grid-based path planning.

You may use the provided implementation valit_grid.py from: https://github.com/alexanderjlavalle/RPPL

The Boolean variable use_dijkstra switches between the two methods; alternatively, you may use the GUI.

(a) Experimental Setup¶

Run both algorithms on at least three different grid worlds. You may:

Use the provided examples, or
Generate your own environments (e.g., using draw_circles.py).

Include challenging cases, such as:

Dense obstacle fields,
Narrow passages,
Varying goal distances.

(b) Parameter Study¶

For each environment, systematically vary:

Grid resolution,
Neighbor radius,
Obstacle arrangement.

Measure:

Running time,
Number of states explored.

Summarize your results in a table which reveals/explains the trends in terms of running times and the number of states explored.

(c) Interpreting Your Results¶

Based on your experimental findings, determine which of the following statements are consistent with your results:

Dijkstra is generally faster when the goal is reachable, because it can terminate once the goal is found.

Value iteration is always faster than Dijkstra, regardless of resolution or neighbor radius.

Value iteration computes the optimal cost-to-go for all states, not just a single shortest path.

Increasing grid resolution increases running time for both algorithms.

Increasing the neighbor radius increases the branching factor in the underlying graph.

The neighbor radius has no effect on running time.

For any given resolution and neighbor radius, both algorithms produce paths with identical Euclidean length.

A larger neighbor radius generally produces shorter Euclidean paths due to increased branching factor.

Warning: You have not logged in. You cannot answer.

Question 2: Value Iteration vs. Dijkstra, Path Quality¶

Using the same setup as in Question 1 (varying grid resolution, neighbor radius, and obstacle characteristics), analyze how these factors affect:

The number of stages in the plan,
The Euclidean length of the resulting path.

Based on your experimental findings, determine which of the following statements are consistent with your results:

With 4-connectivity (only axis-aligned neighbors), paths follow staircase patterns.

With 8-connectivity (diagonal neighbors included), the Euclidean path length decreases compared to 4-connectivity.

The number of stages in the plan is always equal to the Euclidean path length.

Both algorithms produce optimal paths for the same underlying graph.

Dijkstra always produces shorter paths than value iteration on the same graph.

Increasing grid resolution generally leads to paths that better approximate the true Euclidean shortest paths.

Increasing grid resolution always decreases the number of stages.

Obstacle density affects which states are reachable and can change path lengths significantly.

Decreasing grid resolution always increases the lengths of the optimal paths.

Warning: You have not logged in. You cannot answer.

Question 3: Segment Intersection Test¶

Let (𝑎, 𝑏) and (𝑐, 𝑑) be two line segments in general position (no three points are collinear). Let lt(·,·,·) denote the left-turn test. Consider the following proposition about whether the two segments intersect:

The segments (𝑎, 𝑏) and (𝑐, 𝑑) intersect ⟺ lt(𝑎, 𝑐, 𝑑) ≠ lt(𝑏, 𝑐, 𝑑) and lt(𝑎, 𝑏, 𝑐) ≠ lt(𝑎, 𝑏, 𝑑).

Which of the following statements are correct observations or reasoning steps in proving the above proposition?

If lt(𝑎, 𝑐, 𝑑) ≠ lt(𝑏, 𝑐, 𝑑), then 𝑎 and 𝑏 lie on opposite sides of the line through 𝑐 and 𝑑.

If lt(𝑎, 𝑏, 𝑐) ≠ lt(𝑎, 𝑏, 𝑑), then 𝑐 and 𝑑 lie on opposite sides of the line through 𝑎 and 𝑏.

If both conditions hold, each segment crosses the line containing the other.

If 𝑎 and 𝑏 lie on the same side of the line through (𝑐, 𝑑), then the segments cannot intersect (in general position).

One of the two conditions is also sufficient to guarantee intersection.

The proposition is false for any two intersecting line segments ''in general position''.

The proposition is true for any two intersecting line segments ''in general position''.

The proposition also holds true for intersecting collinear segments without modification.

Warning: You have not logged in. You cannot answer.

Question 4: Segment Intersection, Degenerate Cases¶

Explain what happens to the intersection test from Question 3 when general position is violated:

(a) The segments are collinear (all four points on the same line).
(b) One segment endpoint lies exactly inside the other segment.
(c) Propose an extension to handle both degenerate cases.

Which of the following are true?

When all four points are collinear, all four left-turn tests return 0, so the condition evaluates to FALSE even if the segments overlap/intersect.

To handle collinear cases, one must additionally check whether any segment endpoint lies exactly inside the other segment.

A correct extension: First perform the general-position test. If either lt(𝑎, 𝑐, 𝑑) = lt(𝑏, 𝑐, 𝑑) = 0 or lt(𝑎, 𝑏, 𝑐) = lt(𝑎, 𝑏, 𝑑) = 0, add a small random perturbation to all coordinates and perform the general-position test again. This handles all cases.

A correct extension: if either lt(𝑎, 𝑐, 𝑑) = lt(𝑏, 𝑐, 𝑑) = 0 or lt(𝑎, 𝑏, 𝑐) = lt(𝑎, 𝑏, 𝑑) = 0, check whether any segment endpoint lies between the endpoints of the other segment (using coordinate comparisons). If it does, the segments intersect. Combined with the general-position test, this handles all cases.

A correct extension: if either lt(𝑎, 𝑐, 𝑑) = lt(𝑏, 𝑐, 𝑑) = 0 or lt(𝑎, 𝑏, 𝑐) = lt(𝑎, 𝑏, 𝑑) = 0, check whether the bounding boxes of the two segments intersect. The bounding box of (𝑎, 𝑏) is the rectangle [min(𝑎ₓ, 𝑏ₓ), max(𝑎ₓ, 𝑏ₓ)] × [min(𝑎ᵧ, 𝑏ᵧ), max(𝑎ᵧ, 𝑏ᵧ)], and similarly for (𝑐, 𝑑). If the boxes overlap, the segments intersect. Combined with the general-position test, this handles all cases.

A correct extension: if either lt(𝑎, 𝑐, 𝑑) = lt(𝑏, 𝑐, 𝑑) = 0 or lt(𝑎, 𝑏, 𝑐) = lt(𝑎, 𝑏, 𝑑) = 0, check whether max(𝑎ₓ, 𝑏ₓ) ≥ min(𝑐ₓ, 𝑑ₓ) AND max(𝑐ₓ, 𝑑ₓ) ≥ min(𝑎ₓ, 𝑏ₓ), and similarly for 𝑦. If true, the segments intersect. Combined with the general-position test, this handles all cases.

Warning: You have not logged in. You cannot answer.

Question 5: Reading Configurations from a Figure¶

The figure above shows a house-shaped rigid body that can freely rotate and translate in the plane. The rigid body has 5 vertices forming a pentagon (square base + triangular roof). The reference point (●) is at the bottom-left corner of the house in the body frame, i.e., at (0, 0) in body coordinates. The vertices of the house are: (0,0), (2,0), (2,2), (1,3), (0,2) in the body frame.

The dark gray house is the original configuration 𝑞₀ = (0, 0, 0). Five transformed configurations A–E are shown in different colors. For each, determine the configuration 𝑞 = (𝑥, 𝑦, 𝜃), (𝑥, 𝑦) ∈ ℝ² and 𝜃 ∈ 𝑆¹, by reading the reference point position and the rigid body rotation from the figure.

Which of the following statements are correct?

Question 6: Configuration A¶

Refer to the figure showing configurations A–E of the house-shaped rigid body. Configuration A is the blue house.

For a configuration 𝑞 = (𝑥, 𝑦, 𝜃), a point in the body frame coordinate system (𝑎, 𝑏) is transformed to the world coordinates (𝑎₁, 𝑏₁) by:

\begin{bmatrix} a_1 \\ b_1 \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} + \begin{bmatrix} x \\ y \end{bmatrix} \\\

Which of the following statements about the configuration A are correct?

The configuration A is achieved by translating the original rigid body by (5, 1).

The roof peak (1, 3) in body frame maps to (6, 4) in world frame.

The roof peak (1, 3) in body frame maps to (5, 3) in world frame.

The bottom-right vertex (2, 0) in body frame maps to (7, 1) in world frame.

The bottom-right vertex (2, 0) in body frame maps to (5, 1) in world frame.

The window center (0.55, 1.45) in body frame maps to (4.55, 1.45) in world frame.

The window center (0.55, 1.45) in body frame maps to (5.55, 2.45) in world frame.

Any point (𝑎, 𝑏) in body frame maps to (𝑎 + 5, 𝑏 + 1) in world frame.

Warning: You have not logged in. You cannot answer.

Question 7: Configuration B¶

Configuration B is the teal/green house.

Which of the following statements are correct about configuration B?

The configuration B is achieved by rotating the original rigid body by -𝜋/2 and then translating by (4, −1) (all performed in the body frame coordinate system).

The configuration B is achieved by translating the original rigid body by (4, −1) and then rotating it by -𝜋/2 (all performed in the body frame coordinate system).

The roof peak (1, 3) in body frame maps to (1, 0) in world frame.

The roof peak (1, 3) in body frame maps to (5, 2) in world frame.

The window center (0.55, 1.45) in body frame maps to (2.55, −0.45) in world frame.

The window center (0.55, 1.45) in body frame maps to (2.45, 0.55) in world frame.

Any point (𝑎, 𝑏) in body frame maps to (−𝑏 + 4, 𝑎 − 1) in world frame.

Any point (𝑎, 𝑏) in body frame maps to (𝑎 + 4, 𝑏 − 1) in world frame.

Warning: You have not logged in. You cannot answer.

Question 8: Configuration C¶

Configuration C is the coral-red house.

Which of the following statements are correct about configuration C?

The configuration C is achieved by rotating the original rigid body by 𝜋 and then translating by (3, 6) (all performed in the body frame coordinate system).

The configuration C is achieved by translating the original rigid body by (3, 6) and then rotating it by 𝜋 (all performed inthe body frame coordinate system).

The roof peak (1, 3) in body frame maps to (2, 3) in world frame.

The roof peak (1, 3) in body frame maps to (3, 2) in world frame.

The window center (0.55, 1.45) in body frame maps to (2.55, 4.45) in world frame.

The window center (0.55, 1.45) in body frame maps to (2.45, 4.55) in world frame.

Any point (𝑎, 𝑏) in body frame maps to (−𝑎 + 3, −𝑏 + 6) in world frame.

Any point (𝑎, 𝑏) in body frame maps to (𝑎 + 3, 𝑏 + 6) in world frame.

Warning: You have not logged in. You cannot answer.

Question 9: Configuration D¶

Configuration D is the deep-pink house.

Which of the following statements are correct about configuration D?

The configuration D is achieved by rotating the original rigid body by -𝜋/2 and then translating by (−2, 2) (all performed in the body frame coordinate system).

The configuration D is achieved by translating the original rigid body by (−2, 2) and then rotating it by -𝜋/2 (all performed in the body frame coordinate system).

The roof peak (1, 3) in body frame maps to (1, 3) in world frame.

The roof peak (1, 3) in body frame maps to (1, 2) in world frame.

The window center (0.55, 1.45) in body frame maps to (−0.55, 3.45) in world frame.

The window center (0.55, 1.45) in body frame maps to (−0.45, 3.55) in world frame.

Any point (𝑎, 𝑏) in body frame maps to (𝑎 − 2, 𝑏 + 4) in world frame.

Any point (𝑎, 𝑏) in body frame maps to (𝑏 − 2, −𝑎 + 4) in world frame.

Warning: You have not logged in. You cannot answer.

Question 10: Configuration E¶

Configuration E is the purple house.

Which of the following statements are correct about configuration E?

The configuration E is achieved by rotating the original rigid body by -𝜋/2.

The configuration E is achieved by rotating the original rigid body by 𝜋/2.

The roof peak (1, 3) in body frame maps to (−3, 1) in world frame.

The roof peak (1, 3) in body frame maps to (1, 3) in world frame.

The window center (0.55, 1.45) in body frame maps to (−1.45, 0.55) in world frame.

The window center (0.55, 1.45) in body frame maps to (0.55, 1.45) in world frame.

Any point (𝑎, 𝑏) in body frame maps to (−𝑏, 𝑎) in world frame.

Any point (𝑎, 𝑏) in body frame maps to (𝑎, 𝑏) in world frame.

Warning: You have not logged in. You cannot answer.

Lovelace

HOMEWORK 2: Discrete Planning, Geometric Modeling.¶

Question 1: Value Iteration vs. Dijkstra, Running Times¶

(a) Experimental Setup¶

(b) Parameter Study¶

(c) Interpreting Your Results¶

Question 2: Value Iteration vs. Dijkstra, Path Quality¶

Question 3: Segment Intersection Test¶

Question 4: Segment Intersection, Degenerate Cases¶

Question 5: Reading Configurations from a Figure¶

Question 6: Configuration A¶

Question 7: Configuration B¶

Question 8: Configuration C¶

Question 9: Configuration D¶

Question 10: Configuration E¶

Authors¶

Give feedback on this content