Q5: Sequential Decision Making Under Uncertainty – Fundamentals of Sensing, Tracking, and Autonomy 2

Question 1¶

Consider a discrete-time transition system with nondeterministic nature and perfect state sensing.

Let 𝑋 = ℤ, 𝑈 = ℤ, Θ = {−1, 0, 1}, and 𝑥ₖ₊₁ = 𝑓(𝑥ₖ, 𝑢ₖ, 𝜃ₖ) = 𝑥ₖ + 𝑢ₖ + 𝜃ₖ, 𝜃ₖ ∈ Θ.

Which of the following forward projections 𝑋₂(𝑥₁, 𝑢₁) are correct?

Question 2¶

Using the same system as in Question 1 (𝑥ₖ₊₁ = 𝑥ₖ + 𝑢ₖ + 𝜃ₖ, Θ = {−1, 0, 1}), which of the following statements are true?

For any 𝑥₁ ∈ ℤ and 𝑢₁ ∈ ℤ, the set 𝑋₂(𝑥₁, 𝑢₁) always contains exactly three elements.

For any 𝑥₁ ∈ ℤ and 𝑢₁ ∈ ℤ, the set 𝑋₂(𝑥₁, 𝑢₁) always contains exactly two elements.

For some 𝑥₁ ∈ ℤ and 𝑢₁ ∈ ℤ, the set 𝑋₂(𝑥₁, 𝑢₁) may contain exactly two elements.

The set 𝑋₂(𝑥₁, 𝑢₁) is always centered at 𝑥₁ + 𝑢₁.

The set 𝑋₂(𝑥₁, 𝑢₁) is always centered at 𝑥₁.

Changing 𝑢₁ shifts 𝑋₂(𝑥₁, 𝑢₁) without changing its size.

Changing 𝑢₁ changes the number of elements in 𝑋₂(𝑥₁, 𝑢₁).

Nature introduces uncertainty of ±1 around the nominal next state 𝑥₁ + 𝑢₁.

The robot can sometimes choose 𝜃ₖ to guarantee reaching a specific state.

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

Question 3¶

Consider 𝑥ₖ₊₁ = 𝑎𝑥ₖ + 𝑢ₖ + 𝜃ₖ with Θ = {−1, 0, 1} for a fixed non-zero 𝑎 ∈ ℤ \ {0}.

Which of the following statements are true?

For any 𝑥₁ ∈ ℤ, for any 𝑢₁ ∈ ℤ, and for any fixed 𝑎 ∈ ℤ \ {0}, the reachable set 𝑋₂(𝑥₁, 𝑢₁) always has exactly 3 elements.

For any 𝑥₁ ∈ ℤ, for any 𝑢₁ ∈ ℤ, and for any fixed 𝑎 ∈ ℤ \ {0}, the reachable set 𝑋₂(𝑥₁, 𝑢₁) always has exactly 2 elements.

For any 𝑥₁ ∈ ℤ and for any 𝑢₁, 𝑢₂ ∈ ℤ, if 𝑎 = -1, then 𝑋₃ always has exactly 5 elements.

For any 𝑥₁ ∈ ℤ and for any 𝑢₁, 𝑢₂ ∈ ℤ, if 𝑎 = 2, then 𝑋₃ always has exactly 7 elements.

For any 𝑥₁ ∈ ℤ and for any 𝑢₁, 𝑢₂ ∈ ℤ, if 𝑎 = 3, then 𝑋₃ always has exactly 9 elements.

For any 𝑥₁ ∈ ℤ and for any 𝑢₁, 𝑢₂ ∈ ℤ, if 𝑎 = 4, then 𝑋₃ always has exactly 9 elements.

For any 𝑥₁ ∈ ℤ and for any 𝑢₁, 𝑢₂, 𝑢₃ ∈ ℤ, if 𝑎 = 1, then 𝑋₄ always has exactly 7 elements.

For any 𝑥₁ ∈ ℤ and for any 𝑢₁, 𝑢₂, 𝑢₃ ∈ ℤ, if 𝑎 = 2, then 𝑋₄ always has exactly 13 elements.

For |𝑎| ≥ 3, the size of the reachable set triples at each stage: |𝑋ₖ₊₁| = 3·|𝑋ₖ|.

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

Question 4¶

Consider 𝑥ₖ₊₁ = 𝑥ₖ + 𝑢ₖ + 𝜃ₖ with 𝑃(𝜃ₖ = −1) = 1/4, 𝑃(𝜃ₖ = 0) = 1/2, 𝑃(𝜃ₖ = 1) = 1/4. Let 𝑃(𝑥₁ = 0) = 1.

Which of the following statements are true?

If 𝑢₁ = 1, then 𝑃(𝑥₂ = 1) = 1/4, 𝑃(𝑥₂ = 2) = 1/2, 𝑃(𝑥₂ = 3) = 1/4.

If 𝑢₁ = 1, then 𝑃(𝑥₂ = 0) = 1/4, 𝑃(𝑥₂ = 1) = 1/2, 𝑃(𝑥₂ = 2) = 1/4.

If 𝑢₁ = 0, the state 𝑥₂ is deterministically 0.

If 𝑢₁ = 0, then 𝑃(𝑥₂ = −1) = 1/4, 𝑃(𝑥₂ = 0) = 1/2, 𝑃(𝑥₂ = 1) = 1/4.

The probability distribution over 𝑥₂ depends on the specific value of 𝜃ₖ chosen by the robot.

If 𝑢₁ = −1, then 𝑃(𝑥₂ = −2) = 1/4, 𝑃(𝑥₂ = −1) = 1/2, 𝑃(𝑥₂ = 0) = 1/4.

If 𝑢₁ = 2, then 𝑃(𝑥₂ = 1) = 1/4, 𝑃(𝑥₂ = 2) = 1/2, 𝑃(𝑥₂ = 3) = 1/4.

For any integer 𝑢₁, the possible values of 𝑥₂ are 𝑢₁ − 1, 𝑢₁, and 𝑢₁ + 1.

For any integer 𝑢₁, 𝑃(𝑥₂ = 𝑢₁) = 1/2.

For any integer 𝑢₁, 𝑃(𝑥₂ = 𝑢₁ − 1) = 𝑃(𝑥₂ = 𝑢₁ + 2).

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

Question 5¶

Using the same probabilistic system as in Question 4:

Question 6¶

Which of the following prevent convergence of backward value iteration to finite values (for all states)?

In the nondeterministic setting, nature causes trajectories that have cycles in the worst case.

In the nondeterministic setting, nature causes multiple possible trajectories that arrive at the goal.

In the probabilistic setting, nature causes trajectories for which cycles occur with some probability greater than zero.

In the probabilistic setting, nature causes trajectories for which cycles occur with probability zero.

In the nondeterministic setting, the goal cannot be guaranteed to be reached from some initial states.

The optimal cost-to-go is less than the optimal cost-to-come at some states.

Cycles of negative total cost are possible in spite of nondeterministic nature's worst-case actions.

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

Question 7¶

Consider the plan-based state transition graph shown above. Every edge traversal costs one unit. The labels on edges indicate transition probabilities (edges labeled "1" are deterministic; edges labeled "1/2" occur with probability 1/2).

The expected total cost from 𝑥_𝐼 to 𝑥_𝐺 is finite.

The expected total cost from 𝑥_𝐼 to 𝑥_𝐺 is infinite.

The expected total cost from 𝑥_𝐼 to 𝑥_𝐺 is an irrational number.

The expected total cost from 𝑥_𝐼 to 𝑥_𝐺 is 9.

The expected total cost from 𝑥_𝐼 to 𝑥_𝐺 is 11.

The expected total cost from 𝑥_𝐼 to 𝑥_𝐺 is 7.

The expected total cost from 𝑥_𝐼 to 𝑥_𝐺 is 13.

The shortest possible path from 𝑥_𝐼 to 𝑥_𝐺 traverses exactly 3 edges.

The shortest possible path from 𝑥_𝐼 to 𝑥_𝐺 traverses exactly 2 edges.

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

Question 8¶

Using the same graph as in Question 7, consider running probabilistic backward value iteration starting from 𝐺₀(𝑥) = 0 for all 𝑥.

The cost-to-go estimate after 𝑘 stages is strictly less than the estimate after 𝑘 + 1 stages, for all 𝑘 ≥ 1.

After a large number of stages, the cost-to-go becomes exactly fixed and all additional updates are zero.

The cost-to-go converges but never exactly reaches the limit in any finite number of iterations.

The convergence is monotone: each iteration only increases (or maintains) the cost-to-go estimates.

The cost-to-go oscillates above and below the true value before converging.

Backward value iteration cannot be applied to this graph because it contains cycles.

Despite the cycles in the graph, the expected cost is finite because every cycle is traversed with probability strictly less than 1.

The expected cost is finite only because all cycles have negative cost.

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

Lovelace

QUIZ 5: Sequential Decision Making Under Uncertainty¶

Question 1¶

Question 2¶

Question 3¶

Question 4¶

Question 5¶

Question 6¶

Question 7¶

Question 8¶

Authors¶

Give feedback on this content