Q6: Information Spaces and Filtering – Fundamentals of Sensing, Tracking, and Autonomy 2

Question 1¶

Which of the following are correct notation for information transitions?

%T: 𝜂ₖ₊₁ = 𝜙(𝜂ₖ, 𝑢ₖ, 𝑦ₖ₊₁) %T: 𝜂ₖ = 𝜙(𝜂ₖ₋₁, 𝑢ₖ₋₁, 𝑦ₖ) %T: 𝜂ₖ₋₁ = 𝜙(𝜂ₖ₋₂, 𝑢ₖ₋₂, 𝑦ₖ₋₁) %F: 𝜂ₖ₊₁ = 𝜙(𝜂ₖ, 𝑢ₖ, 𝑦ₖ) %T: 𝜂ₖ₊₁ = 𝜙(𝜙(𝜂ₖ₋₁, 𝑢ₖ₋₁, 𝑦ₖ), 𝑢ₖ, 𝑦ₖ₊₁) %F: 𝜂ₖ₊₁ = 𝜙(𝜙(𝜂ₖ₋₁, 𝑢ₖ, 𝑦ₖ), 𝑢ₖ₊₁, 𝑦ₖ₊₁) %F: 𝜂ₖ = 𝜙(𝜂ₖ₋₁, 𝑢ₖ, 𝑦ₖ₋₁) %F: 𝜂ₖ₊₂ = 𝜙(𝜂ₖ, 𝑢ₖ₊₁, 𝑦ₖ₊₂) %T: 𝜂ₖ₊₂ = 𝜙(𝜙(𝜂ₖ, 𝑢ₖ, 𝑦ₖ₊₁), 𝑢ₖ₊₁, 𝑦ₖ₊₂) %F: 𝜂ₖ₊₁ = 𝜙(𝜂ₖ₊₁, 𝑢ₖ, 𝑦ₖ₊₁)

𝜂ₖ₊₁ = 𝜙(𝜂ₖ, 𝑢ₖ, 𝑦ₖ₊₁)

𝜂ₖ = 𝜙(𝜂ₖ₋₁, 𝑢ₖ₋₁, 𝑦ₖ)

𝜂ₖ₋₁ = 𝜙(𝜂ₖ₋₂, 𝑢ₖ₋₂, 𝑦ₖ₋₁)

𝜂ₖ₊₁ = 𝜙(𝜂ₖ, 𝑢ₖ, 𝑦ₖ)

𝜂ₖ₊₁ = 𝜙(𝜙(𝜂ₖ₋₁, 𝑢ₖ₋₁, 𝑦ₖ), 𝑢ₖ, 𝑦ₖ₊₁)

𝜂ₖ₊₁ = 𝜙(𝜙(𝜂ₖ₋₁, 𝑢ₖ, 𝑦ₖ), 𝑢ₖ₊₁, 𝑦ₖ₊₁)

𝜂ₖ = 𝜙(𝜂ₖ₋₁, 𝑢ₖ, 𝑦ₖ₋₁)

𝜂ₖ₊₂ = 𝜙(𝜂ₖ, 𝑢ₖ₊₁, 𝑦ₖ₊₂)

𝜂ₖ₊₂ = 𝜙(𝜙(𝜂ₖ, 𝑢ₖ, 𝑦ₖ₊₁), 𝑢ₖ₊₁, 𝑦ₖ₊₂)

𝜂ₖ₊₁ = 𝜙(𝜂ₖ₊₁, 𝑢ₖ, 𝑦ₖ₊₁)

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

Question 2¶

Consider a 4×4 grid 𝐸₁ with rows A–D and columns 1–4. Cells A2, B2, and C2 are obstacles. The robot can move Up (U), Down (D), Left (L), or Right (R). If the robot tries to move into a wall or obstacle, it stays in its current cell.

The robot's sensor reports the number of neighbors (up, down, left, right) that are either a wall or an obstacle, the sensor values can be 0, 1, 2, 3, or 4.

The robot does not know its starting cell.

The sensor value-based groups are: 𝑦₀ = 1: {B3, B4, C3, C4, D3}; 𝑦₀ = 2: {A3, A4, B1, C1, D1, D2, D4}; 𝑦₀ = 3: {A1}.

Which of the following are true?

The initial sensor reading 𝑦₀ = 3 immediately localizes the robot to A1.

If the initial reading is 𝑦₀ = 1, the robot could be in any of {B3, B4, C3, C4, D3}.

If the initial reading is 𝑦₀ = 2 and the robot moves D and reads 𝑦₁ = 1, the robot must be at A3.

B3 and B4 cannot be distinguished by any single move: for every action 𝑢 ∈ {U, D, L, R}, the sensor reading after the move is identical for both starting cells.

The shortest action sequence that produces different sensor readings from B3 vs B4 is D, D (two moves down).

A3 and A4 can be distinguished in two moves.

The shortest action sequence distinguishing A3 from A4 is D, D, D (three moves down), ending at D3 (𝑦₃ = 1) vs D4 (𝑦₃ = 2).

There exists an strategy that guarantees localization of the robot in at most 2 moves.

The minimum number of moves for guaranteed localization on this grid is 5.

The action sequence D, D localizes the robot on this grid.

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

Question 3¶

Now consider grid 𝐸₂ with the same rules as Question 2, but with obstacles at A4, B4, C4.

The sensor value-based groups are: 𝑦₀ = 0: {B2, C2}; 𝑦₀ = 1: {A2, B1, B3, C1, C3, D2, D3}; 𝑦₀ = 2: {A1, A3, D1}; 𝑦₀ = 3: {D4}.

Which of the following are true?

The initial sensor reading 𝑦₀ = 3 immediately localizes the robot to D4.

If the initial reading is 𝑦₀ = 0, a single move D distinguishes B2 from C2: B2 → C2 (𝑦₁ = 0) vs C2 → D2 (𝑦₁ = 1).

The initial sensor reading 𝑦₀ = 1 narrows the robot's position to at most 3 cells.

If the initial reading is 𝑦₀ = 0, moving U results in the same sensor reading regardless of starting cell.

The action sequence L, U produces a unique (𝑦₀, 𝑦₁, 𝑦₂) triple for every starting cell, guaranteeing localization in 2 moves.

The action sequence D, D also localizes every cell on this grid.

For the action sequence L, U from cell B3: B3 → B2 (𝑦₁ = 0) → A2 (𝑦₂ = 1), giving signature (1, 0, 1).

For the action sequence L, U from cell C3: C3 → C2 (𝑦₁ = 0) → B2 (𝑦₂ = 0), giving signature (1, 0, 0).

The minimum number of moves for guaranteed localization on this grid is 2.

Every 2-move action sequence localizes the robot on this grid.

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

Question 4¶

Now consider grid 𝐸₃ with the same rules as Question 2, but with obstacles at B4 and D3.

The sensor groups are: 𝑦₀ = 0: {B2, C2}; 𝑦₀ = 1: {A2, A3, B1, B3, C1, C3}; 𝑦₀ = 2: {A1, C4, D1, D2}; 𝑦₀ = 3: {A4, D4}.

Which of the following are true?

The initial sensor reading 𝑦₀ = 0 narrows the position to {B2, C2}, and a single move U resolves them: B2 → A2 (𝑦₁ = 1) vs C2 → B2 (𝑦₁ = 0).

The initial sensor reading 𝑦₀ = 3 narrows the position to {A4, D4}, and a single move U resolves them: A4 stays at A4 (𝑦₁ = 3) vs D4 → C4 (𝑦₁ = 2).

No 2-move action sequence can localize the robot on this grid.

The action sequence L, D localizes the robot.

The action sequence R, U localizes the robot.

The action sequence R, D localizes the robot.

The action sequence D, R localizes the robot.

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

Question 5¶

Consider the two-bit filter wiht a state 𝑖 ∈ {T, F}. The state is updated based on whether the most recent observation matches the previous observation. The update rule is:

If the current observation equals the previous observation, the filter state stays the same.
If the current observation differs from the previous observation, the filter state flips.

The observation alphabet is {𝑎, 𝑏}. Which of the following are true?

If 𝑖₀ = T and the observation sequence is 𝑎𝑏𝑏𝑎, then 𝑖₃ = T.

If 𝑖₀ = T and the observation sequence is 𝑎𝑏𝑏𝑎, then 𝑖₃ = F.

If 𝑖₀ = T and the observation sequence is 𝑎𝑏𝑎𝑏, then 𝑖₃ = T.

If 𝑖₀ = T and the observation sequence is 𝑎𝑎𝑎𝑎, then 𝑖₃ = F.

If 𝑖₀ = T and the observation sequence is 𝑎𝑎𝑎𝑎, then 𝑖₃ = T.

If 𝑖₀ = F and the observation sequence is 𝑎𝑏𝑎, then 𝑖₂ = F.

If 𝑖₀ = F and the observation sequence is 𝑎𝑏𝑏, then 𝑖₂ = T.

The filter state after any observation sequence depends only on the number of symbol changes, not on the specific symbols.

The two-bit filter requires storing all previous observations.

If the observation sequence has an even number of symbol changes, the filter state returns to its initial value.

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

Question 6¶

Consider the two-bit filter from Question 5, but now with observation alphabet {𝑎, 𝑏, 𝑐}. The same update rule applies: the filter state flips when the current observation differs from the previous one, and stays when they match.

Which of the following are true?

If 𝑖₀ = T and the observation sequence is 𝑎𝑏𝑐, then 𝑖₂ = T.

If 𝑖₀ = T and the observation sequence is 𝑎𝑏𝑐𝑐𝑏𝑎, then 𝑖₅ = F.

If 𝑖₀ = T and the observation sequence is 𝑎𝑎𝑏𝑏𝑐𝑐, then 𝑖₅ = T.

If 𝑖₀ = T and the observation sequence is 𝑎𝑏𝑐𝑎, then 𝑖₃ = T.

If 𝑖₀ = T and the observation sequence is 𝑎𝑏𝑏𝑏, then 𝑖₃ = F.

The two-bit filter with three observations requires one bit of memory more than the two-observation version from the previous problem.

The two-bit filter with three observations requires the same amount of memory as the two-observation version from the previous problem.

The sequence 𝑎𝑏𝑎𝑏𝑎 produces 𝑖₄ = T (starting from 𝑖₀ = T), because there are 4 symbol changes.

The two-bit filter output depends on which specific symbols appear, not just whether consecutive symbols match.

The filter state can be computed as: 𝑖ₖ = 𝑖₀ if and only if the total number of symbol changes from stage 0 to stage 𝑘 is even.

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

Question 7¶

Consider derived information spaces, information feedback plans, and the concept of eliminating surprise.

Which of the following are true?

For a memoryless system with only sensor feedback, 𝜅(𝜂ₖ) = 𝑦ₖ.

If the derived I-space is the stage counter 𝒦, then 𝑖ₖ₊₁ = 𝜙_der(𝑖ₖ, 𝑢ₖ, 𝑦ₖ₊₁) = 𝑖ₖ + 1.

Eliminating surprise means that 𝑖ₖ₊₁ must be predictable given 𝑖ₖ, 𝑢ₖ, and 𝑦ₖ₊₁.

Eliminating surprise means that the robot always knows its exact configuration.

The derived information transition 𝜙_der must be consistent: 𝜅(𝜙(𝜂ₖ, 𝑢ₖ, 𝑦ₖ₊₁)) = 𝜙_der(𝜅(𝜂ₖ), 𝑢ₖ, 𝑦ₖ₊₁).

A memoryless system must store all previous observations to compute the next action.

If surprise is not eliminated, different histories mapping to the same derived I-state could lead to different derived I-states after the same action and observation.

An information feedback plan maps information states to actions: 𝜋 : 𝒥 → 𝑈.

The stage counter derived I-space depends on which observations are received.

A sensor feedback plan is a special case where the action depends only on the most recent observation.

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

Question 8¶

Consider gap navigation trees (GNTs), billiard trajectories in polygons, and combinatorial filters.

Which of the following are true?

For gap navigation trees, the robot moves along the shortest possible path in terms of Euclidean distance.

The bitangent case causes a gap to appear or disappear.

For almost all polygons and almost all initial positions and orientations, the billiard trajectory will reach every open set.

In a gap navigation tree, the tree structure encodes how gaps split, merge, appear, and disappear as the robot moves.

Gap appearances and disappearances occur at inflection rays.

In a billiard trajectory, the angle of incidence equals the angle of reflection at each bounce.

Gap navigation trees require the robot to know its exact global coordinates at all times.

A combinatorial filter operates on a discrete information space with a finite or discrete set of states and discrete state transitions.

Billiard trajectories in polygons always return to the starting point after finitely many bounces.

The unfolding technique transforms a billiard trajectory into a straight line in a reflected copy of the polygon.

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

Lovelace

QUIZ 6: Information Spaces and Filtering¶

Question 1¶

Question 2¶

Question 3¶

Question 4¶

Question 5¶

Question 6¶

Question 7¶

Question 8¶

Authors¶

Give feedback on this content