HW5. Nondeterministic and Probabilistic Information Spaces¶

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

Recommended Resources:

SF: Sensing and Filtering, Steven M. LaValle, PDF

Kalman Filters¶

Recall that with a Kalman filter the robot's motion is modeled with

x_{k+1} = A_kx_k + B_ku_k + w_k \\\

And the robot's sensing is modeled with

y_{k+1} = C_{k+1}x_{k+1} + v_{k+1} \\\

In which

xₖ represents the robot's position at step k
uₖ represents the action taken at step k
wₖ represents the motion noise at step k
yₖ represents the sensor observation at step k
vₖ represents the sensor noise at step k

Kalman Script 1¶

These exercises will use the following interactive script.

ManualKalman

This script shows how the Kalman filter's information state evolves on a simple robot with the following state space X, action space U, and observation space Y

X = Y = U = \mathbb{R}^2 \\\

This script has four actions:

"Set to this distribution". Sets an initial Gaussian probability distribution with a particular mean and covariance. This should be used after starting up the script.
"Set these noise parameters". Sets the covariance matrices for the movement noise and sensor noise. This can be altered at any point without resetting the existing estimation of the robot's state and state covariance.
"Apply this movement". Applies a robot's movement to the information space and updates the mean and covariance. The robot moves the specified distance along the x and y axes subject to the movement noise.
"Apply this sensor reading". Applies a sensor reading to the information space and updates the mean and covariance. The sensor reports the robot's position in the state space subject to the sensor noise.

To use the script, first set the initial Gaussian probability distribution by setting a mean position and an initial covariance matrix and hit the "Set to this distribution" button. A green dot indicates where the mean estimation of the robot's position is and a heatmap shows the probability distribution of the potential robot states.

Problem 1¶

Choose the correct statements about the system simulated by the ManualKalman script.

Problem 2¶

Choose the correct statements.

Use the ManualKalman script provided to determine which answers are correct.

If a sensor works only intermittently (some movement steps have no associated sensor data), then the robot's position becomes more uncertain as additional movements are applied.

Regardless of the covariance of the sensor and movement noise, the probability distribution function of the robot's position must always be symmetric when reflected over the y axis at the x value corresponding to the mean position estimate.

For a fixed mean and covariance of the robot's estimated position, a sensor reading close to the mean will lead to greater certainty about the robot's position than a sensor reading farther from the mean.

The covariance matrices of the noise and the starting position are symmetric because for two random variables X and Y, the value of cov(X,Y) is equal to cov(Y,X).

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

Kalman Script 2¶

These exercises will use the following interactive script.

Kalman

This script is intended to show the performance of the Kalman filter under different levels of sensor and movement noise. One of the models is intentionally broken. The movement and sensor errors for this model are not Gaussian.

To use the script, select a model. Hitting "next step" will cause the robot to move and a sensor reading to be taken. The chart will show four different points:

filter mean - This is the filter's current guess as to the robot's location based on the movement and sensor history.
movement model prediction - This was the filter's guess as to the robot's location after applying the most recent movement but before applying the most recent sensor reading.
sensor data - This was where the most recent sensor reading placed the robot.
actual location - This is the robot's actual location. This usually would not be available in real applications, but it is being shown here to show how well the filter is doing at tracking the robot's position.

There are four models. Run each of them and then answer the following four questions (each model is the answer to one question).

Problem 3¶

Which model has very low Kalman gain for both coordinates? In other words, in which model is the sensor noise significantly higher than the movement noise?

Problem 4¶

Which model has very high Kalman gain for both coordinates? In other words, in which model is the sensor noise significantly lower than the movement noise?

Problem 5¶

Which model has a sensor that has a very low amount of noise when determining the robot's x coordinate but a very high amount of noise when determining the robot's y coordinate?

Problem 6¶

Which model is broken? The sensor and movement noise should be obviously non-Gaussian.

Additional Questions about Kalman Filters¶

Problem 7¶

Choose the correct statements about Kalman filters.

Kalman filters are very effective when the measurement noise is bimodal, but not when it is trimodal.

Under certain circumstances (linear motion model, linear sensor mapping, Gaussian noise), the Kalman filter gives the same means and variances as Bayes Rule does while maintaining a data structure that is small and easy to work with.

Kalman gain rises as the variance of the movement noise rises and falls as the variance of the sensor measurement noise rises.

High Kalman gain will cause the filter to prioritize the predictions of the motion model and low Kalman gain will cause the filter to prioritize positions consistent with the sensor readings.

Kalman filters are inappropriate to use when one of the elements of the state space corresponds to the rate of change of another element of the state space (for example, one element of the state space is the position along some axis, and another element is the current speed along that axis).

An extended Kalman filter makes a linear approximation of the movement and sensor functions at each step of the estimation.

An extended Kalman filter does not make the assumption that the movement or sensor noise is Gaussian.

In practice, Kalman filters are often used even in situations where the movement or sensor noise is non-Gaussian because in many situations it is "close enough".

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

Nondeterministic Information Spaces, Localization, Mapping¶

The next few questions will use the following environments, action sets, and observation set.

Each environment is a 4x4 grid in which each square can be uniquely identified by a letter+number. For example, A3 or B1.

After the robot moves, it takes a sensor reading. The robot's sensors can detect the color of the square it is in (red, green, yellow, clear). A unique sensor reading (blocked) is returned if the robot attempts to make a movement that would take it off the edge of the grid (in this case, the robot remains in the square that it started in). The set of observations is shown in the diagram below as the set Y.

The three environments E₁, E₂, E₃ are shown in the diagram. Each square is labelled by the sensor reading the robot receives when it moves into the square.

The robot is able to move into the grey squares, but the sensor reading associated with each grey square is not known in advance. They can be considered spaces that were "unexplored" at the start of the robot's movements. The robot cannot start in a grey square.

So,

Each square in the environment is assigned a color (red, green, yellow, or clear).
The robot's sensors have no error.
The color of the grey squares are not known until they are visited.
The robot cannot start in a grey square.

A robot might be using one of three action sets. Each action within these action sets can have more than one possible outcome for where the robot moves. The set U₁ contains only one action, "move", in which the robot tries to move to one of the four squares adjacent to its current location. The set U₂ contains the actions "horizontal" (in which the robot attempts to move left or right) and "vertical" (in which the robot attempts to move up or down). The set U₃ contains the actions "down/left" (in which the robot attempts to move down or left) and the action "up/right" (in which the robot attempts to move up or right).

Problem 8¶

Consider a robot with the action set

U_1 = \{\text{move}\} \\\

Let 𝑦̃ = [y₀, y₁, y₂, y₃, ..., yₖ] be the sensor history.
Let ũ = [u₁, u₂, u₃, ..., uₖ] be the actuation history.
Let [x₀, x₁, x₂, x₃, ..., xₖ] be the sequence of states that the robot traversed. Unlike the sensor and actuation history, this is unlikely to be known.

The state x₀ denotes the starting state prior to any movement attempts. Assume that x₀ is NOT in a grey square to start with. The observation y₀ denotes the observation received from the starting state (this will never be the "blocked" result).

Let 𝑋ₛ(𝑦̃,ũ) be the set of states consistent with 𝑦̃ and ũ.

Choose the correct statements.

If the robot is in E₂ and 𝑦̃ = ["clear", "red"] then 𝑋ₛ(𝑦̃,ũ) consists of only one state.

If the robot is in E₃ and 𝑦̃ = ["clear", "red", "blocked"] then 𝑋ₛ(𝑦̃,ũ) consists of only one state.

If the robot is in E₁, and yₖ₋₁ = "clear", yₖ = "green", and 𝑦̃ does not contain any "red", then xₖ = D4

If the robot is in E₁, and yₖ₋₁ = "clear", yₖ = "green", and 𝑦̃ does not contain any "yellow", then xₖ = D4

There exists an assignment of colors to the center four squares of E₂ and E₃ such that any 𝑦̃ and ũ that is possible in E₂ is also possible to get in E₃.

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

Problem 9¶

Consider a robot with the action set

U_2 = \{\text{horizontal, vertical}\} \\\

Let 𝑋ₛ(𝑦̃,ũ) be the set of states consistent with 𝑦̃ and ũ.

Choose the correct statements.

If the robot is in E₁ and ũ consists entirely of "vertical"s, then there exists an assignment of sensor readings to the remaining grey squares such that a 𝑦̃ consisting entirely of "red" or a 𝑦̃ consisting entirely of "yellow" are both possible.

If the robot is in E₂, x₀=A1, and 𝑦̃ contains no "blocked" sensor readings, then it is possible for x₇ to be C1.

If the robot is in E₁, and ũ = ["vertical", "vertical", "horizontal", "vertical", "vertical"] then 𝑦̃ = ["red", "red", "red", "clear", "clear", "green"] is a possible sensor history.

If the robot is in E₃, ũ = ["horizontal", "horizontal", "vertical", "vertical"], 𝑦̃ = ["clear", "blocked", "clear", "clear", "blocked"], then 𝑋ₛ(𝑦̃,ũ) contains four states.

There exists an assignment of colors to the center four squares of E₂ and E₃ such that any 𝑦̃ and ũ that is possible in E₂ is also possible to get in E₃.

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

Problem 10¶

Consider a robot with the action set

U_3 = \{\text{down/left, up/right}\} \\\

Let 𝑋ₛ(𝑦̃,ũ) be the set of states consistent with 𝑦̃ and ũ.

Choose the correct statements.

If ũ consists entirely of "down/left" or entirely of "up/right", and at least seven movements have been made, then 𝑦̃ must contain at least one "blocked".

For all k ∈ ℕ, there exists a ũ and 𝑦̃ with y₀ = "green" such that for all assignments of colors to the center four squares of E₂ and E₃, 𝑋ₛ(𝑦̃,ũ) ≠ ∅ for both E₂ and E₃

If the robot is in E₁, u₁, = "down/left", u₂ = "up/right", u₃ = "down/left", and y₀, y₁, y₂ ≠ "blocked", then y₃ cannot be "blocked".

ũ = ["down/left","down/left","down/left","down/left"] and 𝑦̃=["clear", "green", "clear", "clear", "red"] is a possible actuation history and sensor history for more than one of the environments.

There exists an assignment of colors to the center four squares of E₂ and E₃ such that any 𝑦̃ and ũ that is possible in E₂ is also possible to get in E₃.

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

Authors¶

Hannah Erickson

Give feedback on this content

Leave your comments below: