AI: The optimal policy in a slippery world

Solve an MDP with uncertain moves to convergence.

What to build

A program that finds the optimal values and policy of a grid world where moves can slip.

Requirements

  • Cells: . open, # wall, G terminal with value +1, P terminal with value −1. From an open cell, an action goes the intended way with probability 0.8 and to each perpendicular side with probability 0.1; into a wall or off the grid, the agent stays. V(s) = r + γ × maxₐ Σ P(s′ | s, a) V(s′), with living reward r.
  • Run value iteration from 0 until the largest change is below 1e-9. Print the values grid (two decimal places; #, G, P as themselves), then the policy grid with ^ > v < (ties: N, E, S, W order).

Input

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

Output

The values rows, then the policy rows.

Constraints

At most 8 × 8 cells; γ ≤ 1 and every cell can reach a terminal.

Example

Input:

3 3 -0.04 1
..G
.#P
...

Output:

0.89 0.95 G
0.84 # P
0.79 0.74 0.50
> > G
^ # P
^ < <

Why it works

The values are the unique solution of the Bellman equations, and value iteration approaches it; acting greedily on the final values chooses moves whose likely slips are also safe.

Examples

Example 1 · Input
3 3 -0.04 1
..G
.#P
...
Expected output
0.89 0.95 G
0.84 # P
0.79 0.74 0.50
> > G
^ # P
^ < <
Example 2 · Input
1 3 -0.1 0.9
..G
Expected output
0.54 0.76 G
> > G

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

Hints

Hint 1

A move goes the intended way with probability 0.8 and to each side with 0.1; compute the expected next value for each of the four actions.

Hint 2

Keep iterating until the largest change in a whole pass is below 1e-9, then take the best action in each cell.

Solution

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


def step(cell, d):
    r, c = cell[0] + MOVES[d][0], cell[1] + MOVES[d][1]
    return (r, c) if 0 <= r < rows and 0 <= c < cols and grid[r][c] != "#" else cell


def q(values, cell, d):
    a, b = SIDES[d]
    return living + gamma * (0.8 * values[step(cell, d)] + 0.1 * values[step(cell, a)] + 0.1 * values[step(cell, b)])


open_cells = [cell for cell in V if grid[cell[0]][cell[1]] == "."]
while True:
    new = dict(V)
    for cell in open_cells:
        new[cell] = max(q(V, cell, d) for d in MOVES)
    change = max((abs(new[cell] - V[cell]) for cell in open_cells), default=0)
    V = new
    if change < 1e-9:
        break
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)))
for r in range(rows):
    line = []
    for c in range(cols):
        if grid[r][c] != ".":
            line.append(grid[r][c])
            continue
        best = None
        for d in MOVES:
            if best is None or q(V, (r, c), d) > q(V, (r, c), best):
                best = d
        line.append(best)
    print(" ".join(line))

Lesson: Markov decision processes →