"""A small grid world: a discrete stand-in for a robot reaching task. The agent starts at S and must reach the goal G. Hazard cells H end the episode with a penalty, walls # block movement, and every other move costs a small step penalty. With slip > 0 the chosen move is replaced by a random perpendicular move with that probability, so the MDP becomes stochastic. """ from __future__ import annotations from dataclasses import dataclass, field import numpy as np # Actions: 0 = up, 1 = right, 2 = down, 3 = left (row, column offsets). MOVES: tuple[tuple[int, int], ...] = ((-1, 0), (0, 1), (1, 0), (0, -1)) ACTION_NAMES: tuple[str, ...] = ("up", "right", "down", "left") DEFAULT_LAYOUT: tuple[str, ...] = ( "S....", ".##.H", "...#.", ".H...", "...#G", ) @dataclass class GridWorld: layout: tuple[str, ...] = DEFAULT_LAYOUT step_reward: float = -1.0 goal_reward: float = 10.0 hazard_reward: float = -10.0 slip: float = 0.0 n_actions: int = 4 cells: list[tuple[int, int]] = field(init=False) index: dict[tuple[int, int], int] = field(init=False) def __post_init__(self) -> None: self.rows = len(self.layout) self.cols = len(self.layout[0]) if any(len(r) != self.cols for r in self.layout): raise ValueError("all layout rows must have the same length") # Every non-wall cell is a state. self.cells = [(r, c) for r in range(self.rows) for c in range(self.cols) if self.layout[r][c] != "#"] self.index = {cell: i for i, cell in enumerate(self.cells)} starts = [i for i, (r, c) in enumerate(self.cells) if self.layout[r][c] == "S"] if len(starts) != 1: raise ValueError("layout needs exactly one start cell S") self.start = starts[0] @property def n_states(self) -> int: return len(self.cells) def char(self, s: int) -> str: r, c = self.cells[s] return self.layout[r][c] def is_terminal(self, s: int) -> bool: return self.char(s) in "GH" def _move(self, s: int, a: int) -> int: r, c = self.cells[s] dr, dc = MOVES[a] nr, nc = r + dr, c + dc if 0 <= nr < self.rows and 0 <= nc < self.cols and self.layout[nr][nc] != "#": return self.index[(nr, nc)] return s # bumping into a wall or the edge leaves the agent in place def _reward(self, s_next: int) -> float: ch = self.char(s_next) if ch == "G": return self.goal_reward if ch == "H": return self.hazard_reward return self.step_reward def transitions(self, s: int, a: int) -> list[tuple[float, int, float, bool]]: """Return the model p(s', r | s, a) as (probability, s', r, done) tuples.""" if self.is_terminal(s): return [(1.0, s, 0.0, True)] outcomes: list[tuple[float, int]] = [(1.0 - self.slip, a)] if self.slip > 0.0: outcomes += [(self.slip / 2, (a + 1) % 4), (self.slip / 2, (a + 3) % 4)] result = [] for p, a_eff in outcomes: s2 = self._move(s, a_eff) result.append((p, s2, self._reward(s2), self.is_terminal(s2))) return result def reset(self) -> int: return self.start def step(self, s: int, a: int, rng: np.random.Generator) -> tuple[int, float, bool]: """Sample one transition. The learner only sees (s', r, done), never the model.""" outcomes = self.transitions(s, a) probs = np.array([o[0] for o in outcomes]) k = int(rng.choice(len(outcomes), p=probs)) if len(outcomes) > 1 else 0 _, s2, r, done = outcomes[k] return s2, r, done def render_policy(self, policy: np.ndarray) -> str: arrows = "^>v<" lines = [] for r in range(self.rows): row = "" for c in range(self.cols): ch = self.layout[r][c] if ch in "#GH": row += ch else: row += arrows[int(policy[self.index[(r, c)]])] lines.append(row) return "\n".join(lines) if __name__ == "__main__": env = GridWorld() print(f"{env.n_states} states, {env.n_actions} actions, start state {env.start}") print("\n".join(env.layout))