AI: Value iteration in a grid

Run value iteration for a fixed number of steps and read off the policy.

What to build

A program that runs k iterations of value iteration in a deterministic grid world and prints the values and the greedy policy.

Requirements

  • Cells: . open, # wall, G goal and P pit (both terminal, value 0). Moves N, E, S, W go one cell; into a wall or off the grid, the agent stays. The reward is +10 for entering G, −10 for entering P and −1 otherwise. All open cells start at 0; each iteration updates every open cell from the previous values.
  • Print values: and the grid of values (two decimal places; #, G, P as themselves), then policy: and the grid of best actions for the final values as ^ > v < (ties: N, E, S, W order).

Input

Line 1: rows, columns, γ and k. Then the grid.

Output

values:, the rows, policy:, the rows.

Constraints

At most 10 × 10 cells; k ≤ 100.

Example

Input:

1 4 1 3
...G

Output:

values:
8.00 9.00 10.00 G
policy:
> > > G

Why it works

After k iterations each value is the best total reward reachable in k moves, so values spread outward from the goal one cell per iteration.

Examples

Example 1 · Input
1 4 1 3
...G
Expected output
values:
8.00 9.00 10.00 G
policy:
> > > G
Example 2 · Input
1 4 0.5 2
...G
Expected output
values:
-1.50 4.00 10.00 G
policy:
> > > G

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Each iteration computes new values for every open cell from the old values: the best over N, E, S, W of reward + γ × V(next).

Hint 2

Entering G earns +10, entering P earns −10, any other move earns −1; G and P always have value 0.

Solution

Show one correct solution (try it yourself first)
rows, cols, gamma, k = input().split()
rows, cols, gamma, k = int(rows), int(cols), float(gamma), int(k)
grid = [input() for _ in range(rows)]
MOVES = [("^", -1, 0), (">", 0, 1), ("v", 1, 0), ("<", 0, -1)]
V = {(r, c): 0.0 for r in range(rows) for c in range(cols) if grid[r][c] != "#"}


def outcome(r, c, dr, dc):
    nr, nc = r + dr, c + dc
    if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc] == "#":
        nr, nc = r, c
    reward = {"G": 10, "P": -10}.get(grid[nr][nc], -1)
    return reward, (nr, nc)


def q(values, r, c, dr, dc):
    reward, nxt = outcome(r, c, dr, dc)
    return reward + gamma * values[nxt]


for _ in range(k):
    V = {cell: (max(q(V, *cell, dr, dc) for _, dr, dc in MOVES) if grid[cell[0]][cell[1]] == "." else 0.0) for cell in V}
print("values:")
for r in range(rows):
    print(" ".join(f"{V[(r, c)]:.2f}" if grid[r][c] == "." else grid[r][c] for c in range(cols)))
print("policy:")
for r in range(rows):
    line = []
    for c in range(cols):
        if grid[r][c] != ".":
            line.append(grid[r][c])
            continue
        best = None
        for name, dr, dc in MOVES:
            value = q(V, r, c, dr, dc)
            if best is None or value > best[1]:
                best = (name, value)
        line.append(best[0])
    print(" ".join(line))

Lesson: Markov decision processes →