01 / Problem
Sequence actions that change what is reachable.
The agent must move through a grid, collect a key, unlock a door, and reach a goal. Position alone is not enough to describe the decision state: orientation, key possession, and door status all affect valid transitions.
02 / State + actions
Represent task progress explicitly.
For a fixed map, the state included grid position, orientation, key possession, and door status. Randomized layouts required additional variables for key and goal placement. Actions included moving forward, turning, picking up the key, and unlocking the door, with invalid actions handled by the transition and cost model.
state = (x, y, orientation, has_key, door_state)
actions = {forward, left, right, pickup, unlock}03 / Method and results
Use backward induction over a finite horizon.
I initialized terminal-state cost, propagated value estimates backward through the deterministic transition model, and stored the lowest-cost action for each reachable state. The implementation generated separate policies for supplied fixed layouts and a state representation intended to cover the randomized 8 by 8 layout family described in the course project.
04 / Limitations and next steps
State-space growth is the central constraint.
- Every added map variable multiplies the table size.
- A finite planning horizon can exclude solutions that require more steps.
- The transition model is known and discrete; perception and model uncertainty are outside scope.
The next useful experiment would log policy success and planning cost across the full provided layout set, with failure cases grouped by horizon and state encoding.