Completed: / exercises

QUIZ 1: Discrete Planning, Search, and Value Iteration

Due date: 2026-03-19 23:59.
Recommended Resources:

Question 1: Equivalent Action Sequences

For a Gridbot with no obstacles, which of the following action sequences are equivalent to ↑ ↑ → ← ↓, in terms of where the robot ends up?
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 2: Gridbot Reachability

For a Gridbot with obstacles, which choices for 𝑈 would allow it to reach every white tile that is accessible from 𝑥_𝐼? A white tile is accessible if there is a connected sequence of neighboring white tiles from it to 𝑥_𝐼.
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 3: Gridbot Model Properties

Which are properties of the Gridbot model?
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 4: Search Algorithms

Select all of the true statements regarding search (and no false ones!):
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 5: Discrete Planning on a Graph

Consider the discrete planning problem shown above.
Choose the correct options:
Warning: You have not logged in. You cannot answer.

Question 6: Value Iteration with the Provided Code

Consider the following value iteration code valit_simple.py from
https://github.com/alexanderjlavalle/RPPL. It computes the optimal stationary cost-to-go using a termination action.
We encode the graph from Question 5 as follows, where 𝑎 = 0, 𝑏 = 1, 𝑐 = 2, 𝑑 = 3, 𝑒 = 4:
G = nx.DiGraph()
G.add_nodes_from([0, 1, 2, 3, 4])
G.add_edge(0, 1, weight=2)  # a -> b
G.add_edge(1, 0, weight=1)  # b -> a
G.add_edge(1, 2, weight=4)  # b -> c
G.add_edge(2, 3, weight=3)  # c -> d
G.add_edge(2, 4, weight=7)  # c -> e
G.add_edge(3, 2, weight=1)  # d -> c
G.add_edge(3, 3, weight=1)  # d -> d
G.add_edge(3, 4, weight=1)  # d -> e

valit(G, 4)
If you execute this code with valit(G, 4) (goal = 𝑒), which of the following are true about the output?
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 7: Value Iteration — Fixed-Length Plans

The valit_simple.py from Question 6 computes the optimal stationary cost-to-go (with a termination action, no fixed plan length). You want to modify it to instead compute the optimal cost-to-go for fixed-length plans of exactly 𝐾 steps (no termination action).
Which of the following modifications are correct and necessary? (There are only 2 incorrect options below).
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Question 8: Fixed-Length Plans on a Ring

Consider a bidirectional ring of 10 nodes (0 through 9), where every adjacent pair is connected in both directions with edge weight 1, as shown in the figure above. To construct this graph, modify the below code (from valit_simple.py) that creates a linear bidirectional graph, without the ring structure:
#This example is a linear bidirectional graph of length g2_length.
g2_length = 20
G2 = nx.DiGraph()
G2.add_nodes_from([i for i in range(g2_length)])

for i in range(g2_length-1):
    G2.add_edge(i, i+1, weight=1)
for i in range(1, g2_length):
    G2.add_edge(i, i-1, weight=1)
Once you modified the above code to instead have the ring structure, use the fixed-length code from Question 7 and run it on the graph with goal = 0.
We use the same notation as in HW1:
  • Let G(x,k) be a comma-delimited string denoting the cost to go to state x on a fixed k-step path from states 0-9. We use the symbol X to denote that a fixed k-step path to the goal does not exist.
  • Let G*(x) be a comma-delimited string denoting the cost to go to state x indeterminate length path from states 0-9. We use the symbol X to denote that a path to the goal does not exist.
Which of the following are true?
Choose the correct answers
Warning: You have not logged in. You cannot answer.

Authors

Steven M. LaValle, Anna LaValle.
?