Flappy Bird as a Stochastic Shortest Path Problem

Final programming exercise for ETH 151-0563-01 — Dynamic Programming and Optimal Control (Fall 2025, Prof. Raffaello D'Andrea). A flapping-wing vehicle has to slip through an endless side-scrolling corridor of obstacles with stochastic actuation, delayed input effects, and random obstacle spawning. We formulate it as an infinite-horizon stochastic shortest-path (SSP) problem with K = 7 770 states and L = 3 inputs and solve it offline by dynamic programming.

The optimal policy navigating an endless obstacle field. Even with stochastic strong flaps and the bird's delayed reaction, the DP-derived policy clears every gap.

---

Problem setup

The state at time k is

xₖ = (yₖ, vₖ,  d¹ₖ … dᴹₖ,  h¹ₖ … hᴹₖ)

• yₖ, vₖ — bird altitude and vertical velocity (vₖ ∈ {-Vmax, …, Vmax}).
• dⁱₖ — horizontal distance to the i-th nearest obstacle (dⁱₖ = 0 encodes "obstacle slot empty").
• hⁱₖ — gap centre height of obstacle i.
• M = ⌈X / Dmin⌉ — max obstacles visible at once.

Inputs uₖ ∈ {U_no_flap, U_weak, U_strong}. A strong flap is stochastic: the velocity update is vₖ₊₁ = vₖ + uₖ + w⁽ᶠˡᵃᵖ⁾ - g with w⁽ᶠˡᵃᵖ⁾ uniform on {-V_dev, …, V_dev}. Weak flap and no flap are deterministic.

Stage cost penalises effort but rewards staying alive:

g(xₖ, uₖ) = h(uₖ) − 1,   h(U_no_flap)=0,  h(U_weak)=λ_weak,  h(U_strong)=λ_strong

Negative stage cost → the policy must keep the bird alive forever (collision is the absorbing terminal state with finite penalty). With these parameters and X=8, Y=14, M=2, Vmax=2, the state space has K = 7 770 non-terminal states.

---

Solution

The repo implements the full DP pipeline as the assignment requires it:

1. ComputeTransitionProbabilities.py — builds the transition tensor P ∈ ℝ^{K × K × L} by enumerating, for every (state, input) pair, the joint distribution over (w_spawn, w_h, w_flap) and the resulting next state.
2. ComputeExpectedStageCosts.py — builds the expected stage cost Q ∈ ℝ^{K × L} (Q[i, u] = E[g(xₖ, uₖ) + α · P(collision | xₖ, uₖ)]).
3. Solver.py — solves the Bellman equation J*(i) = min_u { Q[i,u] + Σⱼ P[i,j,u] J*(j) } and extracts the greedy policy μ*(i) = argmin_u { ... }.

The solver supports several backends with warm-starting for fast re-solves under tweaked parameters:

Backend	Notes
Value iteration (VI)	sync and async variants, with ε-convergence stopping
Generalised Policy Iteration (GPI)	fewer outer iterations, each one cheaper than full PI
Linear-programming solve via scipy	exact baseline, used to sanity-check the iterative methods

A full performance study lives in experiments/ — see the Analysis section below.

---

Analysis

Beyond the assignment's correctness tests, the repo includes the experiments used for the bonus optimisation report:

File	What it does
experiments/benchmark_solvers.py	Wall-clock comparison of VI / async VI / GPI / LP on the assignment instance.
experiments/compare_vi.py	Sync vs async value iteration: iteration count and time to ε-convergence.
experiments/hyperparameter_search.py	Grid-search ε and damping for the iterative solvers.
experiments/warmstart_hyperparameter_search.py	Same grid but with warm-starting the next solve from the previous J*.
experiments/investigate_epsilon_performance.py	Trade-off plot: tightening ε vs. final-cost regret.

The two key wins from the warm-start work:

Warm-starting consistently roughly halves the wall-clock for a sequence of related solves, with no detectable regret on the final policy quality.

---

Running it yourself

The project ships an environment.yml for conda:

conda env create -f environment.yml
conda activate dpoc_pe

# Interactive simulator (you control the bird with W / S)
python simulation.py

# Compute the optimal policy, then run the simulator under it
python main.py

# Headless recording: compute (or load) policy, then save N rendered frames as PNG
python record_demo.py --frames 180

# Course test harness
python -m pytest tests/

Inputs are hold-down in the interactive simulator:

• W — weak flap
• S — strong flap (stochastic)
• nothing — no flap (gravity wins)
• R — reset, Esc — quit

---

Repo layout

dpoc-flappy-bird/
├── README.md
├── LICENSE
├── environment.yml
├── Const.py                          # Problem constants (X, Y, Vmax, M, λ's, …)
├── ComputeTransitionProbabilities.py # Builds P ∈ ℝ^{K×K×L}
├── ComputeExpectedStageCosts.py      # Builds Q ∈ ℝ^{K×L}
├── Solver.py                         # VI / async VI / GPI / LP backends
├── utils.py                          # Geometry helpers (is_collision, is_passing, …)
├── simulation.py                     # Pygame interactive + policy-driven simulator
├── main.py                           # End-to-end: compute then visualise
├── record_demo.py                    # Headless frame recorder for the README GIF
├── validate_main.py                  # Sanity checks against gold reference
├── test.py                           # Smoke test
├── gold_main/                        # Reference solution from the course (validation)
├── tests/                            # Course-provided unit tests
├── experiments/                      # Solver benchmarks + warm-start study
└── docs/
    ├── PE_instructions.pdf           # Original assignment handout
    └── images/                       # README assets + analysis plots

---

Authors

Built in a two-person group:

• Federico Cominelli (@fedecomi04)
• Jaeryeong (Nicole) Kim (@nicolejrkim)

Course: ETH 151-0563-01 — Dynamic Programming and Optimal Control, Fall 2025, Prof. Raffaello D'Andrea, Institute for Dynamic Systems and Control. The original assignment specification (©2025 Antonio Terpin, Marius Baumann — IDSC, ETH Zurich) is included verbatim at docs/PE_instructions.pdf.

---

License

The exercise-specific implementations are released under the MIT License — see LICENSE. The course framework, gold reference, and assignment PDF retain their original IDSC ETH copyright.