HW4. Triangulation and Temporal Filtering¶

Due date: 2026-06-13 23:59.

Recommended Resources:

SF: Sensing and Filtering, Steven M. LaValle, PDF
Recorded Lectures and Slides

Part 1: Problems Using Visualizer¶

In the first part of the homework, you will explore trajectory filtering and spatial triangulation for a mobile robot using an interactive visualization tool. Rather than reasoning only analytically, you will observe how sets of sampled trajectories evolve over time under a motion model and how sensor measurements prune those sets via intersections of preimages.

2dPlusTimeFiltering

State Space and Environment¶

The robot moves in a square planar environment:

E = [-1,1] \times [-1,1] \subset \mathbb{R}^2 . \\\

The robot state includes position, heading, speed, and time:

(x_1, x_2, \theta, s, t) \in X, \quad (x_1, x_2) \in E, \\\

in which:

𝜃 ∈ 𝑆¹ is the heading (direction of motion),
𝑠 ≥ 0 is the speed along the heading.

Time¶

Time is discretized into measurement stages:

t \in \{0,1,2,3,4\}. \\\

At each time stage:

Starting from the sampled initial states at time 𝑡 = 0, trajectories are propagated forward using the motion model.
Available sensor measurements at that time are applied to prune inconsistent trajectories.
Only surviving trajectories are propagated into the next stage.

Initial Conditions¶

At time 𝑡 = 0, you may set up the initial conditions, resulting in the robot’s initial state being either known or partially/fully unknown. You may set up:

Initial 𝑥₁ and 𝑥₂ values as 𝑥₁,₀ and 𝑥₂,₀.
Initial heading 𝜃₀.
Initial speed, 𝑠₀.

The visualization tool generates an initial set of states by sampling:

positions (𝑥₁, 𝑥₂) on a uniform grid in 𝐸,
headings 𝜃 from a finite set of angles,
speeds 𝑠 from a finite set of values.

If no initial conditions are specified, the resulting samples represent complete uncertainty over the state space, and, therefore, over the possible trajectories. The visualizer only shows the (𝑥₁, 𝑥₂, 𝑡) projections of the trajectories. To visualize the paths that the robot executes, you need to further project the trajectories onto the (𝑥₁, 𝑥₂)-plane.

Motion Model¶

Each sampled state generates a candidate trajectory evolving over time. Between measurement stages, time can be further discretized into Δ𝑡 intervals, and each trajectory evolves according to:

\begin{bmatrix} x_1 \\ x_2 \\ t \end{bmatrix}_{k+1} = \begin{bmatrix} x_1 \\ x_2 \\ t \end{bmatrix}_{k} + \begin{bmatrix} 𝑠_k \cos \theta_k \\ 𝑠_k \sin \theta_k \\ 1 \end{bmatrix} \Delta t . \\\

with optional bounded changes at each Δ𝑡 for:

heading 𝜃,
speed 𝑠.

Sensors¶

At each time stage, the following geometric sensors may report measurements.

1. Distance-to-Boundary Sensor¶

This nondeterministic sensor reports the distance from the robot’s position to the closest boundary of the environment:

h_1(x_1, x_2, \theta, 𝑠, t, d) = \min\{1 - |x_1|, 1 - |x_2|\} + 𝑑, \qquad 𝑑 ∈ [−\varepsilon_1, \varepsilon_1]. \\\

Geometrically, the preimage of this sensor is a thick band parallel to the boundary of the square.

2. Vertical 𝑥₁-Strip Sensor¶

This sensor constrains the 𝑥₁-coordinate:

h_2(x_1, x_2,\theta,𝑠,t,d) = x_1 + d, \qquad d \in [-\varepsilon_2,\varepsilon_2]. \\\

Its preimage is a vertical strip in the (𝑥₁, 𝑥₂)-plane.

3. Horizontal 𝑥₂-Strip Sensor¶

This sensor constrains the 𝑥₂-coordinate:

h_3(x_1, x_2,\theta,𝑠,t,d) = x_2 + d, \qquad d \in [-\varepsilon_3,\varepsilon_3]. \\\

The corresponding preimage is a horizontal strip in the (𝑥₁, 𝑥₂)-plane.

Triangulation and Trajectory Filtering¶

At a given time stage, any subset of sensors may be active.

Let the available measurements at a given time stage 𝑡 be denoted by 𝑦₁, 𝑦₂, and 𝑦₃, corresponding to sensors ℎ₁, ℎ₂, and ℎ₃, respectively. The set of states consistent with all available measurements is given by the intersection of the corresponding preimages:

\Delta(y_1, y_2, y_3) = H_1^{-1}(y_{1}) \, \cap \, H_2^{-1}(y_{2}) \, \cap \, H_3^{-1}(y_{3}). \\\

𝑃ₜ ⊆ E denotes the projection of consistent states at time 𝑡 onto position space. That is, 𝑃ₜ consists of all position pairs (𝑥₁, 𝑥₂) for which there exists a state with position (𝑥₁, 𝑥₂) that lies in the intersection of the preimages. Therefore, 𝑃ₜ represents the region in 𝐸 at time stage 𝑡 consistent with sensing.

A trajectory is kept at time stage 𝑡 if its position (𝑥₁(𝑡), 𝑥₂(𝑡)) lies in 𝑃ₜ. Trajectories that violate any measurement constraint are permanently discarded/filtered out.

Visualization¶

The visualization tool takes as input a set of parameters that define the initial conditions, sampling resolution, and motion model of the robot. These parameters determine which candidate trajectories are generated and how they evolve over time before being pruned by sensor measurements. The parameters are listed below:

Initial Conditions:

𝑥₁,₀: Initial value of the robot’s 𝑥₁-position at time 𝑡 = 0 (if unspecified, all grid positions are used).
𝑥₂,₀: Initial value of the robot’s 𝑥₂-position at time 𝑡 = 0 (if unspecified, all grid positions are used).
𝜃₀: Initial heading angle at time 𝑡 = 0 (if unspecified, all sampled headings are used).
𝑠₀: Initial speed at time 𝑡 = 0 (if unspecified, all sampled speeds are used).

Sampling Parameters:

𝑥₁/𝑥₂ grid points: Number of grid points used to discretize the environment 𝐸 for initial position sampling.
heading samples: Number of discrete heading values used to sample possible directions of motion.
speed samples: Number of discrete speed values used to sample possible magnitudes of motion.
𝑠ₘₐₓ: Maximum allowable speed used when sampling speeds and applying speed changes.

Motion Model:

time step, Δ𝑡: Time increment used to propagate trajectories between measurement stages.
heading can change: Enables or disables random bounded changes in heading during propagation.
speed can change: Enables or disables random bounded changes in speed during propagation.
max heading change, Δ𝜃/Δ𝑡: Maximum change in heading allowed per time step when heading variation is enabled.
max speed change, Δ𝑠/Δ𝑡: Maximum change in speed allowed per time step when speed variation is enabled.

Measurements at time stages 𝑡 = {0, 1, 2, 3, 4}: For each time stage 𝑡, the following inputs may be provided:

ℎ₁ (dist): Measurement reported by the distance-to-boundary sensor, specifying the robot’s distance to the closest boundary of the environment at time 𝑡.
ℎ₂ (𝑥₁-strip): Measurement reported by the vertical strip sensor, constraining the robot’s 𝑥₁-coordinate at time 𝑡.
ℎ₃ (x₂-strip): Measurement reported by the horizontal strip sensor, constraining the robot’s 𝑥₂-coordinate at time 𝑡.

Measurement tolerances for each of the sensors can also be specified as 𝜀₁, 𝜀₂, and 𝜀₃.

Operating the Visualizer¶

Initialize: Resets the visualizer by resampling the initial set of trajectories at time 𝑡 = 0 using the current parameter values and clearing all previous propagation and pruning results.
Next Stage (propagate + prune): Advances the motion model by one time stage by propagating all currently surviving trajectories forward in time and then removing any trajectories that violate the sensor constraints at the new stage, rendering:

a horizontal plane at the current time 𝑡.
individual sensor preimages (faint colored regions).
𝑃ₜ, the projection of the intersection of all active preimages (highlighted region).
surviving trajectories in (𝑥₁, 𝑥₂, 𝑡) space, such that (𝑥₁, 𝑥₂) ∈ 𝑃ₜ.

Run All: Automatically executes all remaining stages from the current time until the final stage, repeatedly applying propagation followed by pruning at each stage.
Reset to Defaults: Restores all visualizer parameters to their default values but does not automatically resample trajectories or restart the simulation. To apply the restored defaults, the visualizer must be reinitialized using Initialize.
Quit: Closes the visualization tool.

This helps visually interpret:

which regions of space are consistent with the measurements.
how sensing interacts with the motion model and dynamics.
how triangulation emerges from intersecting geometric constraints.
what paths the robot can execute in the environment, satisfying the initial conditions, motion model, and the sensor measurements.

Note: Any change to parameters—whether manual or via Reset to Defaults — takes effect only after clicking Initialize.

Question 1¶

In the visualizer, do not change any default settings except for the initial conditions. In particular:

Keep the sampling resolutions, motion model, sensor measurements and tolerance parameters unchanged.
Use the default values for everything except the initial conditions 𝑥₁,₀, 𝑥₂,₀, 𝜃₀, 𝑠₀.

Which of the following statements are TRUE? (6 correct statements)

Important note: Keep in mind that the paths that the robot can execute are the projection of the visualized trajectories onto the (𝑥₁, 𝑥₂)-plane.

Setting 𝑥₁,₀ = 0, 𝑥₂,₀ = 0, leaving 𝜃₀ unspecified, and fixing 𝑠₀ = 0.2 results in four straight-line paths with different headings, all originating from the origin and forming a radial pattern.

Setting 𝑥₁,₀ = 0, 𝑥₂,₀ = 0, 𝜃₀ = 0°, and 𝑠₀ = 0.1 results in exactly one straight-line path.

Leaving 𝑥₁,₀ and 𝑥₂,₀ unspecified, fixing 𝜃₀ = 90°, and fixing 𝑠₀ = 0.5 results in parallel paths (ignore singleton paths).

Leaving 𝑥₁,₀, 𝑥₂,₀, and 𝜃₀ unspecified while fixing 𝑠₀ = 0.5 results in a single cluster of paths emanating from the origin 𝑥₁ = 0, 𝑥₂ = 0.

Fixing only 𝑥₁,₀ and leaving 𝑥₂,₀, 𝜃₀, and 𝑠₀ unspecified results in paths that all originate from the same line in (𝑥₁, 𝑥₂)-plane at 𝑡 = 0.

Setting 𝑥₁,₀ = 1.5 and leaving all other initial conditions unspecified results in no possible paths.

Fixing 𝜃₀ while leaving 𝑥₁,₀, 𝑥₂,₀, and 𝑠₀ unspecified guarantees that all paths will remain parallel (ignore singleton paths).

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

Question 2¶

In the visualizer, use the default values for everything except the following sampling parameters:

number of 𝑥₁/𝑥₂ grid points,
number of heading samples,
number of speed samples,
maximum speed 𝑠ₘₐₓ.

Which of the following statements are TRUE? (7 correct statements)

Increasing the number of 𝑥₁/𝑥₂ grid points while keeping heading and speed samples fixed increases the total number of paths.

With 𝑥₁,₀ = 𝑥₂,₀ = 0, increasing the number of heading samples (up to 100) while keeping the rest of sampling parameters fixed increases the number of path directions from the origin.

With 𝑥₁,₀ = 𝑥₂,₀ = 0, increasing the number of speed samples (up to 100) while keeping all other sampling parameters fixed does not expand the set of reachable points in the (𝑥₁, 𝑥₂)-plane.

With 𝑥₁,₀ = 𝑥₂,₀ = 0, increasing the maximum speed while keeping the number of speed and heading samples fixed increases the number of paths generated.

With 𝑥₂,₀ = −1 and 𝑥₁,₀ unspecified, increasing the number of 𝑥₁/𝑥₂ grid samples (while keeping all other parameters fixed) increases the number of paths that start on 𝑥₂ = −1, but does not expand the set of 𝑥₂ values they can reach at 𝑡 = 4.

Reducing the number of heading samples to 1 while leaving all other parameters at their default values results in paths that are either points (stationary robot) or straight, parallel lines (for nonzero speeds)

Setting the number of speed samples to 1 and fixing 𝑠ₘₐₓ = 0.5 results in paths that have identical speeds (unless on the boundary).

Increasing both the number of heading samples and the number of speed samples produces curved paths.

If all initial conditions are left unspecified, the total number of paths generated equals (number of 𝑥₁/𝑥₂ grid points)² × (heading samples) × (speed samples).

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

Question 3¶

In the visualizer, use the default values for everything except the motion model parameters listed below:

You may vary the time step Δ𝑡.
Heading can change is set to ON, unless otherwise stated.
Speed can change is set to ON, unless otherwise stated.
You may vary the maximum heading change per step, Δ𝜃/Δ𝑡.
You may vary the maximum speed change per step, Δ𝑠/Δ𝑡.

When Heading can change and/or Speed can change are set to ON, during each Δ𝑡 a random change in heading and/or speed (within the specified maximum values) is applied to the trajectory.

Which of the following statements are TRUE? (3 correct statements)

Varying Δ𝑡 while keeping all other parameters fixed has no effect on the generated paths.

Disabling ''Heading can change'' and enabling ''Speed can change'' results in straight-line paths (unless on the boundary).

Enabling ''Heading can change'' and disabling ''Speed can change'' results in straight-line paths (unless on the boundary).

With 𝑥₁,₀ = 𝑥₂,₀ = 0, if both ''Heading can change'' and ''Speed can change'' are disabled, then ''heading max change'' or ''speed max change'' parameters have no effect.

With 𝑥₁,₀ = 𝑥₂,₀ = 0, decreasing the ''heading max change per step'' reduces the curvature of the paths. (true)

With 𝑥₁,₀ = 𝑥₂,₀ = 0, increasing the ''speed max change per step'' increases the number of turns paths take.

Changing motion model parameters can reduce the number of surviving trajectories, even if no sensor measurements are applied.

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

Question 4¶

In this question, consider only the measurements at time 𝑡 = 0.

Do not change any default sampling, motion model, or visualization parameters.
Ignore trajectory propagation and pruning at later stages.
Focus only on the geometric preimages of the sensors at 𝑡 = 0.

Which of the following statements are TRUE? (3 correct statements)

The measurement ℎ₁ = 0.8, 𝜀₁ = 0.4 has the same preimage as ℎ₂ = 0, 𝜀₂ = 0.6, ℎ₃ = 0, 𝜀₃ = 0.6.

The measurement ℎ₁ = 1.0, 𝜀₁ = 0.2 has the same preimage as ℎ₂ = 0, 𝜀₂ = 0.2, ℎ₃ = 0, 𝜀₃ = 0.2.

The measurement ℎ₁ = 0.5, 𝜀₁ = 0.1 has the same preimage as ℎ₂ = 0, 𝜀₂ = 0.5, ℎ₃ = 0, 𝜀₃ = 0.5.

The measurement ℎ₁ = 0.7, 𝜀₁ = 0.3 has the same preimage as ℎ₂ = 0, 𝜀₂ = 0.3, ℎ₃ = 0, 𝜀₃ = 0.3.

The measurement ℎ₁ = 0.4, 𝜀₁ = 0.4 has the same preimage as ℎ₂ = 0, 𝜀₂ = 0.6, ℎ₃ = 0, 𝜀₃ = 0.6.

The measurement ℎ₁ = 0.2, 𝜀₁ = 0.1 has the same preimage as ℎ₂ = 0, 𝜀₂ = 0.9, ℎ₃ = 0, 𝜀₃ = 0.9.

For any 𝑎 ∈ (0, 1), the measurement ℎ₁ = 𝑎, 𝜀₁ = 1 − 𝑎 is equivalent to ℎ₂ = 0, 𝜀₂ = 1 − 𝑎, ℎ₃ = 0, 𝜀₃ = 1 − 𝑎.

There exist distance-to-boundary measurements whose preimages cannot be exactly reproduced by any combination of strip sensors.

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

Question 5¶

Use the visualizer with all parameters set to their default values except for the sensor measurements specified below.

Sensor measurements:

At 𝑡 = 0: ℎ₂ = −1, ℎ₃ = −1, with tolerances 𝜀₂ = 𝜀₃ = 0.2, defining the region 𝑃₀.
At 𝑡 = 4: ℎ₂ = 1, ℎ₃ = 1, with tolerances 𝜀₂ = 𝜀₃ = 0.2, defining the region 𝑃₄.

With the setup above, a path survives if:

its initial position lies in 𝑃₀ at time 𝑡 = 0, and
its position at time 𝑡 = 4 lies in 𝑃₄.

The questions below ask which changes to the default parameters can likely result in at least one surviving path reaching 𝑃₄.

Which of the following statements are TRUE? (5 correct statements)

Enabling ''Heading can change'' alone is guaranteed to generate at least one surviving path.

Enabling ''Heading can change'' and increasing ''max heading change per step'' will generate at least one surviving path.

Increasing the maximum speed, 𝑠ₘₐₓ, alone will generate at least one surviving path.

Increasing the number of heading samples and increasing the maximum speed, 𝑠ₘₐₓ, increases the likelihood that at least one path reaches 𝑃₄.

Enabling ''Heading can change'' and increasing the maximum speed 𝑠ₘₐₓ increases the likelihood that at least one path reaches 𝑃₄.

When ''Heading can change'' is disabled, increasing the number of heading samples alone can never produce survivors unless the maximum speed, 𝑠ₘₐₓ, is also increased.

When ''Heading can change'' is enabled, increasing only the 𝑥₁/𝑥₂ grid samples can produce surviving paths even if the maximum speed remains 𝑠ₘₐₓ = 0.5.

When ''Heading can change'' is enabled, increasing maximum speed, 𝑠ₘₐₓ, alone is sufficient to produce survivors.

When ''Heading can change'' is disabled, increasing both the maximum speed, 𝑠ₘₐₓ, and the number of heading samples is sufficient to produce surviving paths.

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

Question 6¶

Use the visualizer with all parameters set to their default values except for the following.

At 𝑡 = 0:

ℎ₂ = −1, ℎ₃ = −1, 𝜀₂ = 𝜀₃ = 0.2, defining 𝑃₀.

At intermediate times:

𝑡 = 1: ℎ₁ = 0.3, 𝜀₁ = 0.2.
𝑡 = 2: ℎ₁ = 0.5, 𝜀₁ = 0.2.
𝑡 = 3: ℎ₁ = 0.8, 𝜀₁ = 0.2.

At 𝑡 = 4:

ℎ₂ = 1, ℎ₃ = 1, 𝜀₂ = 𝜀₃ = 0.2, defining 𝑃₄.

You are not allowed to change these sensor measurements or the default tolerances, but you may change any other parameter in the visualizer.

A path survives if:

its initial position lies in 𝑃₀ at 𝑡 = 0, and
its position at 𝑡 = 4 lies in 𝑃₄.

Your task is to adjust the visualizer parameters so that at least one path survives at time 𝑡 = 4. Then, submit the complete set of parameter values you used, excluding sensor measurements and tolerances (which must remain unchanged).

Format your answer as shown below:

initial 𝑥₁,₀: ___
initial 𝑥₂,₀: ___
initial heading 𝜃₀: ___
initial speed 𝑠₀: ___

𝑥₁/𝑥₂ grid points: ___
heading samples: ___
speed samples: ___
𝑠ₘₐₓ: ___

time step Δ𝑡: ___
heading can change: ___
speed can change: ___
max heading change Δ𝜃/Δ𝑡 (deg): ___
max speed change Δ𝑠/Δ𝑡: ___

Question 7¶

Use the visualizer with all parameters set to their default values except for the following sensor measurements and tolerances:

𝑡 = 0: ℎ₂ = -0.9, ℎ₃ = -0.9, 𝜀₂ = 𝜀₃ = 0.4.
𝑡 = 1: ℎ₂ = 0.8, ℎ₃ = -0.8, 𝜀₂ = 𝜀₃ = 0.4.
𝑡 = 2: ℎ₂ = 0.7, ℎ₃ = 0.7, 𝜀₂ = 𝜀₃ = 0.4.
𝑡 = 3: ℎ₂ = -0.6, ℎ₃ = 0.6, 𝜀₂ = 𝜀₃ = 0.4.
𝑡 = 4: ℎ₂ = -0.5, ℎ₃ = -0.5, 𝜀₂ = 𝜀₃ = 0.4.

Similarly to the previous question, your task is to adjust the visualizer parameters so that at least one path survives at time 𝑡 = 4. Then, submit the complete set of parameter values you used, excluding sensor measurements and tolerances (which must remain unchanged).

Format your answer as shown below (put default if you didn't update a value):

initial 𝑥₁,₀: ___
initial 𝑥₂,₀: ___
initial heading 𝜃₀: ___
initial speed 𝑠₀: ___

𝑥₁/𝑥₂ grid points: ___
heading samples: ___
speed samples: ___
𝑠ₘₐₓ: ___

time step Δ𝑡: ___
heading can change: ___
speed can change: ___
max heading change Δ𝜃/Δ𝑡 (deg): ___
max speed change Δ𝑠/Δ𝑡: ___

Lovelace

HW4. Triangulation and Temporal Filtering¶

Part 1: Problems Using Visualizer¶

State Space and Environment¶

Time¶

Initial Conditions¶

Motion Model¶

Sensors¶

1. Distance-to-Boundary Sensor¶

2. Vertical 𝑥₁-Strip Sensor¶

3. Horizontal 𝑥₂-Strip Sensor¶

Triangulation and Trajectory Filtering¶

Visualization¶

Operating the Visualizer¶

Question 1¶

Question 2¶

Question 3¶

Question 4¶

Question 5¶

Question 6¶

Question 7¶

Part 2: Analytical Problems¶

Question 8¶

Question 9¶

Question 10¶

Authors¶

Give feedback on this content