HW3. Virtual Sensors¶

Due date: 2026-02-05 23:59.

Recommended Resources:

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

3D Preimage Visualization¶

In this part of the assignment, you will explore preimages of virtual sensors for a planar mobile robot with heading.

Rather than reasoning purely algebraically, you will use an interactive visualization tool to build geometric intuition about how different sensor mappings partition the state space. You are strongly encouraged to interact with the visualizer extensively before answering the questions that follow below:

3DPreimageVisualizer-5sensors

Problem Setup¶

For questions in this part of the homework, consider a point-sized mobile robot moving in a planar environment:

E \subset \mathbb{R}^2, \\\

which is either:

a square:

E = [-1,1]^2, \\\

or a disk:

E = {(x,y)\in\mathbb{R}^2 \mid x^2+y^2 \le 1}. \\\

The robot state is:

x = (x,y,\theta) \in X = E \times S^1, \\\

where 𝜃 ∈ 𝑆¹ denotes the robot’s heading.

A virtual sensor is modeled as a mapping:

h : X \to Y, \\\

where the observation space 𝑌 ⊂ ℝ depends on the sensor definition.

Sensor Models¶

The visualizer implements the following sensor mappings:

Sensor 𝒉₁: Distance to the closest boundary. This sensor measures the shortest distance from the robot’s position to the boundary of the environment, ∂𝐸, regardless of orientation:

h_1(x,y,\theta) = \operatorname{dist}((x,y), \partial E). \\\

Sensor 𝒉₂: Distance along heading. This sensor measures how far the robot is free to move straight ahead in the direction of its heading 𝜃:

ℎ_2(x,y,\theta)= \inf \{ t > 0 | (x,y) + t(\cos \theta,\sin \theta) \notin E. \}. \\\

Here, inf denotes the infimum of a set, which means: the greatest value that is less than or equal to every element of the set. In this context, ℎ₂(𝑥, 𝑦, 𝜃) represents the distance from position (𝑥, 𝑦) along heading 𝜃, at which the robot is about to leave the environment 𝐸.

Sensor 𝒉₃: Distance behind the robot. This sensor measures the distance to the boundary directly behind the robot, i.e., along the direction 𝜃 + 𝜋:

h_3(x,y,\theta)= h_2(x,y,\theta+\pi). \\\

Sensor 𝒉₄: Corridor width along heading. This sensor measures the total free space along the robot’s forward–backward direction by summing the distance in front and behind:

h_4(x,y,\theta) = h_2(x,y,\theta) + h_3(x,y,\theta). \\\

Sensor 𝒉₅: Two-ray aperture sensor. This sensor measures the distance to the closest boundary along two rays at angles 𝜃 + 𝛼 and 𝜃 − 𝛼, and reports the smaller of the two distances:

h_5(x,y,\theta) = \min\{ h_2(x,y,\theta+\alpha), h_2(x,y,\theta-\alpha) \}.

⚠️ Note About the Visualizer¶

As seen in previous assignments, numerically computing roots of real-valued functions is subject to sampling limitations and numerical error. For the same reasons, this visualizer provides only a rough approximation of a preimage. It may miss some valid states or include extra ones.

Therefore, while the visualizer is useful for building intuition, use it as guidance while still applying analytical reasoning to answer the following questions correctly.

Visualizer Recommended Use¶

Choose the environment first. Select either the disk or the square environment.
Select a sensor. Choose one of the five sensors ℎ₁ through ℎ₅.
Set a sensor value and compute. Enter a value of the sensor output and click Compute. The visualizer will numerically estimate the preimage of that value by sampling:

all (𝑥, 𝑦) positions in the environment, and
all heading angles 𝜃 ∈ 𝑆¹.

Choose the sampling resolution. You can control the resolution using:

𝑁ₓᵧ (sampling over position), and
𝑁𝜃 (sampling over heading).
Larger values produce a more detailed approximation, but they also take longer to compute.
Recommendation: use values no larger than about 100 for both 𝑁ₓᵧ and 𝑁𝜃.

Animate preimages (optional). You may display an animation of preimages for sensor values ranging from ℎₘᵢₙ to ℎₘₐₓ.

Select ℎₘᵢₙ, ℎₘₐₓ,and how many intermediate steps are shown, and click Play Animation.
Example: an animation for sensor ℎ₂ is shown below.

Change the viewing angle. You can rotate and manipulate the 3D view to observe preimages from different perspectives.

This is especially useful for building intuition about the geometry and dimension of preimage sets.
For example, the same preimage can appear very different when viewed from another angle.

%✅ℎ₁⁻¹(0) = ∂𝐸 × 𝑆¹. %❌ℎ₁⁻¹(0) = 𝐸 × 𝑆¹. %✅ℎ₁⁻¹(1) = {(0, 0)} × 𝑆¹. %❌ℎ₁⁻¹(1) = {(𝑥,𝑦) ∣ 𝑥² + 𝑦² = 1} × 𝑆¹. %✅ℎ₁⁻¹(2) = ∅. %✅ℎ₁⁻¹(1/2) = {(𝑥,𝑦,𝜃) ∣ 𝑥² + 𝑦² = 1/4}. %✅The dimension of preimage ℎ₁⁻¹(1/2) is 2. %✅The range of ℎ₁ is exactly [0,1]. %❌The dimension of all preimages is 2. %✅ The set {(𝑥,𝑦,𝜃) ∣ ℎ₁(𝑥,𝑦,𝜃) > 0} equals int(𝐸) × 𝑆¹, in which int(𝐸) denotes all points strictly inside 𝐸, not on the boundary. %✅ ∀ 𝜃₁ ≠ 𝜃₂, if (𝑥, 𝑦, 𝜃₁) ∈ ℎ₁⁻¹, then (𝑥, 𝑦, 𝜃₂) ∈ ℎ₁⁻¹.

%✅ ℎ₁⁻¹(0) = ∂𝐸 × 𝑆¹. %❌ ℎ₁⁻¹(0) = 𝐸 × 𝑆¹. %✅ ℎ₁⁻¹(1) = {(0, 0)} × 𝑆¹. %❌ ℎ₁⁻¹(1) = [−1,1] × {0} × 𝑆¹. %✅ ℎ₁⁻¹(2) = ∅. %✅ [−1, 1] × {-1} × 𝑆¹ ⊂ ℎ₁⁻¹(0). %❌ℎ₁⁻¹(1/2) = [−1/2, 1/2]² × 𝑆¹. %✅The dimension of preimage ℎ₁⁻¹(1/2) is 2. %✅The range of ℎ₁ is exactly [0,1]. %❌The dimension of all preimages is 2. %✅ The set {(𝑥,𝑦,𝜃) ∣ ℎ₁(𝑥,𝑦,𝜃) > 0} equals int(𝐸) × 𝑆¹, in which int(𝐸) denotes all points strictly inside 𝐸, not on the boundary. %✅ ∀ 𝜃₁ ≠ 𝜃₂, if (𝑥, 𝑦, 𝜃₁) ∈ ℎ₁⁻¹, then (𝑥, 𝑦, 𝜃₂) ∈ ℎ₁⁻¹.

%❌ ℎ₂⁻¹(0) = ∂𝐸 × 𝑆¹. %❌ ℎ₂⁻¹(0) = 𝐸 × 𝑆¹. %❌ ℎ₂⁻¹(1) = {(0, 0)} × 𝑆¹. %✅ {(0, 0)} × 𝑆¹ ⊂ ℎ₂⁻¹(𝟣). %✅ ℎ₂⁻¹(1) can be expressed as the union over 𝜃 ∈ 𝑆¹ of planar circular arcs, each of which is located in a plane parallel to the (𝑥,𝑦)-plane. %❌ ℎ₂⁻¹(2) = ∅. %✅ ℎ₂⁻¹(1/2) can be expressed as the union over 𝜃 ∈ 𝑆¹ of planar circular arcs, each of which is located in a plane parallel to the (𝑥,𝑦)-plane. %✅ The range of ℎ₂ is exactly [0,2]. %❌ The dimension of all preimages is 2. %❌ The set {(𝑥,𝑦,𝜃) ∣ ℎ₂(𝑥,𝑦,𝜃) > 0} equals int(𝐸) × 𝑆¹, in which int(𝐸) denotes all points strictly inside 𝐸, not on the boundary. %❌ ∀ 𝜃₁ ≠ 𝜃₂, if (𝑥, 𝑦, 𝜃₁) ∈ ℎ₂⁻¹, then (𝑥, 𝑦, 𝜃₂) ∈ ℎ₂⁻¹.

%❌ ℎ₂⁻¹(0) = ∂𝐸 × 𝑆¹. %❌ ℎ₂⁻¹(0) = 𝐸 × 𝑆¹. %❌ ℎ₂⁻¹(1) = {(0, 0)} × 𝑆¹. %❌ {(0, 0)} × 𝑆¹ ⊂ ℎ₂⁻¹(𝟣). %✅ ℎ₂⁻¹(1) can be expressed as the union over 𝜃 ∈ 𝑆¹ of line segments, each of which is located in a plane parallel to the (𝑥,𝑦)-plane. %❌ ℎ₂⁻¹(2) = ∅. %✅ ℎ₂⁻¹(1/2) can be expressed as the union over 𝜃 ∈ 𝑆¹ of line segments, each of which is located in a plane parallel to the (𝑥,𝑦)-plane. %❌ The range of ℎ₂ is exactly [0,1]. %❌ The dimension of all preimages is 2.

Question 4¶

In the visualizer, for the square environment, select sensor ℎ₂, which measures the distance to the boundary along the robot heading.

For this environment, which statements are true about ℎ₂ and its preimages?

%❌ ℎ₄⁻¹(0) = ∂𝐸 × 𝑆¹. %✅ ℎ₄⁻¹(0) = ∅. %❌ ℎ₄⁻¹(2) = ∅. %✅ {(0, 0)} × 𝑆¹ ⊂ ℎ₄⁻¹(2). %✅ The set {(𝑥,𝑦,𝜃) ∣ ℎ₄(𝑥,𝑦,𝜃) = 2} consists exactly of states for which the line through (𝑥,𝑦) in direction 𝜃 passes through the origin. %❌ ℎ₄ is independent of 𝜃 (i.e., changing 𝜃 does not change the value). %❌ For every (𝑥,𝑦) ∈ 𝐸 and every 𝜃 ∈ 𝑆¹, we have ℎ₄(𝑥,𝑦,𝜃) ≥ 1. %❌ The set {(𝑥,𝑦,𝜃) ∣ ℎ₄(𝑥,𝑦,𝜃) > 0} equals int(𝐸) × 𝑆¹. %✅ ℎ₄⁻¹(1) can be expressed as the union over 𝜃 ∈ 𝑆¹ of line segments, each of which is located in a plane parallel to the (𝑥,𝑦)-plane.

Question 5¶

In the visualizer, for the disk environment, select sensor ℎ4, which measures the corridor width along the heading.

For this environment, which statements are true about ℎ4 and its preimages?

ℎ₄⁻¹(0) = ∂𝐸 × 𝑆¹.

ℎ₄⁻¹(0) = ∅.

ℎ₄⁻¹(2) = ∅.

{(0, 0)} × 𝑆¹ ⊂ ℎ₄⁻¹(2).

The set {(𝑥,𝑦,𝜃) ∣ ℎ₄(𝑥,𝑦,𝜃) = 2} consists exactly of states for which the line through (𝑥,𝑦) in direction 𝜃 passes through the origin.

ℎ₄ is independent of 𝜃 (i.e., changing 𝜃 does not change the value).

For every (𝑥,𝑦) ∈ 𝐸 and every 𝜃 ∈ 𝑆¹, we have ℎ₄(𝑥,𝑦,𝜃) ≥ 1.

The set {(𝑥,𝑦,𝜃) ∣ ℎ₄(𝑥,𝑦,𝜃) > 0} equals int(𝐸) × 𝑆¹.

ℎ₄⁻¹(1) can be expressed as the union over 𝜃 ∈ 𝑆¹ of line segments parallel to the (𝑥,𝑦)-plane.

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

%❌ ℎ₁ ∼ ℎ₂. %❌ ℎ₂ ∼ ℎ₃. %❌ ℎ₂ ∼ ℎ₄. %❌ ℎ₂ ⪰ ℎ₃. %❌ ℎ₃ ⪰ ℎ₂. %❌ ℎ₂ ⪰ ℎ₁. %❌ ℎ₁ ⪰ ℎ₂. %❌ ℎ₄ ⪰ ℎ₁. %❌ ℎ₄ ⪰ ℎ₂. %❌ ℎ₄ ⪰ ℎ₃. % ✅ Sensors ℎ₁, ℎ₂, ℎ₃, ℎ₄ are incomparable.

%❌ ℎ₂₃ ⪰ ℎ₁. %❌ ℎ₁ ⪰ ℎ₂₃. %✅ ℎ₂₃ ⪰ ℎ₂. %❌ ℎ₂ ⪰ ℎ₂₃. %✅ ℎ₂₃ ⪰ ℎ₃. %❌ ℎ₃ ⪰ ℎ₂₃. %✅ ℎ₂₃ ⪰ ℎ₄. %❌ ℎ₄ ⪰ ℎ₂₃.

Question 7¶

Consider the sensors ℎ₁, ℎ₂, ℎ₃, ℎ₄ and the additional (vector-valued) sensor:

h_{23}(x,y,\theta)=\big(h_2(x,y,\theta), \, h_3(x,y,\theta)\big). \\\

Which statements are TRUE? (Select all that are true.)

%❌ ℎ₅⁻¹(0) = ∂𝐸 × 𝑆¹. %❌ ℎ₅⁻¹(0) = 𝐸 × 𝑆¹. %✅ {(0, 0)} × 𝑆¹ ⊂ ℎ₅⁻¹(1). %✅ ℎ₅⁻¹(1) can be expressed as the union over 𝜃 ∈ 𝑆¹ of planar circular arcs. %✅ ℎ₅⁻¹(1/2) can be expressed as the union over 𝜃 ∈ 𝑆¹ of planar circular arcs. %❌ The range of ℎ₅ is exactly [0, 1]. %❌ ℎ₅ is independent of 𝜃. %❌ The set {(𝑥,𝑦,𝜃) ∣ ℎ₅(𝑥,𝑦,𝜃) > 0} equals int(𝐸) × 𝑆¹. %✅ ℎ₅⁻¹(1) = ℎ₂⁻¹(1) ∩ ℎ₃⁻¹(1) for 𝛼 = 90°. %✅ ℎ₅⁻¹(1) = ℎ₂⁻¹(1) for 𝛼 = 0°.

%✅ ℎ₅ ∼ ℎ₂, for 𝛼 = 0°. %❌ ℎ₅ ∼ ℎ₃, for 𝛼 = 0°. %✅ ℎ₅ ⪰ ℎ₂, for 𝛼 = 0°. %✅ ℎ₂ ⪰ ℎ₅, for 𝛼 = 0°. %❌ ℎ₅ ∼ ℎ₃, for 𝛼 = 90°. %❌ ℎ₅ ∼ ℎ₂, for 𝛼 = 90°. %❌ ℎ₅ ⪰ ℎ₃, for 𝛼 = 90°. %❌ ℎ₃ ⪰ ℎ₅, for 𝛼 = 90°. %❌ ℎ₅ ∼ ℎ₄, for 𝛼 = 90°. %❌ ℎ₄ ⪰ ℎ₅, for 𝛼 = 90°.

%✅The sensor output ℎ is independent of 𝜃. %✅For any environment 𝐸 ∈ {𝐸₁, 𝐸₂}, ℎ(𝑝,𝜃,𝐸) = 0 if and only if 𝑝 ∈ ∂𝐸. %❌ℎ⁻¹(0) contains all states with 𝑝 ∈ ∂𝐸₁ ∪ ∂𝐸₂. %✅ℎ⁻¹(0) = (∂𝐸₁ × 𝑆¹ × {𝐸₁}) ∪ (∂𝐸₂ × 𝑆¹ × {𝐸₂}). %✅If ℎ(𝑝,𝜃,𝐸) = 1, then necessarily 𝑝 = (0, 0). %❌If ℎ(𝑝,𝜃,𝐸) = 1, then necessarily 𝐸 = 𝐸₁. %✅There exist two different states 𝑥₁ = (𝑝,𝜃,𝐸₁) and 𝑥₂ = (𝑝,𝜃,𝐸₂) with the same 𝑝 and 𝜃 such that ℎ(𝑥₁) ≠ ℎ(𝑥₂). %❌ For every 𝑝 ∈ 𝐸₁ ∩ 𝐸₂, dist(𝑝, ∂𝐸₁) = dist(𝑝, ∂𝐸₂). %✅ There exist 𝑝 ∈ 𝐸₁ ∪ 𝐸₂ such that dist(𝑝, ∂𝐸₁) = dist(𝑝, ∂𝐸₂). %✅ For any state with 𝐸 = 𝐸₁, ℎ(𝑝,𝜃,𝐸₁) ≤ 1. And for any state with 𝐸 = 𝐸₂, ℎ(𝑝,𝜃,𝐸₂) ≤ 1.

Multiple robots¶

Consider 10 point-sized mobile robots moving in a planar square environment

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

Each robot has no heading and no internal degrees of freedom. The state of robot 𝑖 is given only by its position

p_i = (x_i,y_i) \in E, \quad \forall i \in \{1,\dots,10\}. \\\

The state space of the system is denoted by 𝑋.

A virtual sensor is modeled as a mapping:

h : X \to Y, \\\

where 𝑌 is the observation space.

Let the detection region be a fixed set 𝑉 ⊂ 𝐸. Define the following three sensor mappings:

Sensor ℎ₆:

h_6(x) = \begin{cases} 1, & \text{if } \,\, ∃i ∈ \{1, . . . , 10\}\,|\, p_i \in V,\\ 0, & \text{otherwise.} \end{cases} \\\

Sensor ℎ₇:

h_7(x) = \begin{cases} 1, & \text{if }\, ∀ i ∈ \{1, . . . , 10\},\,\, p_i \in V,\\ 0, & \text{otherwise.} \end{cases} \\\

Sensor ℎ₈:

h_8(x) = \bigl| \{ i ∈ \{1,...,10\} \mid p_i \in V \} \bigr|. \\\

%❌ 𝑋 = ℝ². %❌ 𝑋 = ℝ¹⁰. %❌ 𝑋 = ℝ³⁰. %✅ 𝑋 ⊂ ℝ²⁰. %✅ 𝑋 = 𝐸¹⁰ = 𝐸 × 𝐸 × ⋯ × 𝐸 (10 times). %❌ Each state in 𝑋 is a single point in the plane. %✅ Each state in 𝑋 is a 10-tuple (𝑝₁,…,𝑝₁₀) with 𝑝ᵢ ∈ 𝐸. %❌ The state space 𝑋 depends on the detection region 𝑉.

Question 11¶

Which of the following statements about the state space 𝑋 are TRUE?

%✅ 𝑉 ⊂ 𝐸. %❌ 𝑉 = 𝐸. %❌ 𝑉 ⊂ ℝ²⁰. %✅ A robot is in the detection region if and only if its position lies in 𝑉. %✅ If a state 𝑥 ∈ 𝑉¹⁰, then ℎ₆(𝑥) = ℎ₇(𝑥) = ℎ₈(𝑥) = 1. %✅If a state 𝑥 ∈ 𝑉 × 𝐸⁹, then at least one robot is guaranteed to be in 𝑉.

Question 12¶

Which of the following statements about the detection region 𝑉 are TRUE?

%✅ ℎ₆ detects whether at least one robot lies in 𝑉. %❌ ℎ₆ detects whether all robots lie in 𝑉. %❌ ℎ₆ counts the number of robots that lie in 𝑉. %✅ ℎ₆(𝒙) = 1 if and only if exactly one robot lies in 𝑉. %✅If a state 𝑥 ∈ 𝑉 × 𝐸⁹, then ℎ₆(𝑥) = 1. %✅ If a state 𝑥 ∈ 𝑉¹⁰, then ℎ₆(𝑥) = 1.

Question 13¶

Which of the following statements about sensor ℎ₆ are TRUE?

%✅ ℎ₇ detects whether all robots lie in 𝑉. %❌ ℎ₇ detects whether at least one robot lies in 𝑉. %❌ ℎ₇ counts the number of robots that lie in 𝑉. %❌If a state 𝑥 ∈ 𝑉 × 𝐸⁹ then ℎ₇(𝑥) = 1. %✅ If a state 𝑥 ∈ 𝑉¹⁰, then ℎ₇(𝑥) = 1. %❌ ℎ₇(𝒙) = 1 if and only if exactly one robot lies in 𝑉.

Question 14¶

Which of the following statements about sensor ℎ₇ are TRUE?

%❌ ℎ₈(𝒙) ∈ {0,1} for all states. %❌ If a state 𝑥 ∈ 𝑉 × 𝐸⁹ then ℎ₈(𝑥) = 1. %✅ If a state 𝑥 ∈ 𝑉¹⁰, then ℎ₈(𝑥) = 10. %❌ℎ₆ ∼ ℎ₇. %❌ℎ₇ ∼ ℎ₈. %❌ℎ₆ ⪰ ℎ₇. %❌ℎ₇ ⪰ ℎ₈. %✅ℎ₈ ⪰ ℎ₆. %✅ℎ₈ ⪰ ℎ₇.

Question 15¶

Which of the following statements about sensor ℎ₈ are TRUE?

Authors¶

Anna LaValle.

Give feedback on this content

Comments about these exercises

Lovelace