{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "95e52dfb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Q6B: Q-learning Taxi problem on a simple 5x5 grid.\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1864dae0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# The agent must pick up at (0, 0) and drop off at (4, 4).\n",
    "# State: taxi row, taxi column, passenger on board (0/1).\n",
    "pickup, destination = (0, 0), (4, 4)\n",
    "moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "action_names = [\"up\", \"down\", \"left\", \"right\", \"pick up\", \"drop off\"]\n",
    "def step(state, action):\n",
    "    row, col, onboard = state\n",
    "    reward, done = -1, False\n",
    "    if action < 4:\n",
    "        dr, dc = moves[action]\n",
    "        row = int(np.clip(row + dr, 0, 4))\n",
    "        col = int(np.clip(col + dc, 0, 4))\n",
    "    elif action == 4:\n",
    "        if (row, col) == pickup and onboard == 0:\n",
    "            onboard, reward = 1, 5\n",
    "        else:\n",
    "            reward = -10\n",
    "    elif action == 5:\n",
    "        if (row, col) == destination and onboard == 1:\n",
    "            reward, done = 20, True\n",
    "        else:\n",
    "            reward = -10\n",
    "    return (row, col, onboard), reward, done\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6c74479b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Completion rate in final 100 episodes: 1.0\n"
     ]
    }
   ],
   "source": [
    "# Train from random taxi positions, with an empty taxi each episode.\n",
    "rng = np.random.default_rng(42)\n",
    "q = np.zeros((5, 5, 2, 6))\n",
    "alpha, gamma = 0.2, 0.95\n",
    "successes = []\n",
    "for episode in range(8000):\n",
    "    state = (int(rng.integers(5)), int(rng.integers(5)), 0)\n",
    "    epsilon = max(0.05, 1 - episode / 6000)\n",
    "    done = False\n",
    "    for _ in range(100):\n",
    "        action = int(rng.integers(6)) if rng.random() < epsilon else int(np.argmax(q[state]))\n",
    "        next_state, reward, done = step(state, action)\n",
    "        target = reward if done else reward + gamma * np.max(q[next_state])\n",
    "        q[state][action] += alpha * (target - q[state][action])\n",
    "        state = next_state\n",
    "        if done:\n",
    "            break\n",
    "    successes.append(done)\n",
    "print(\"Completion rate in final 100 episodes:\", round(np.mean(successes[-100:]), 3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d1b149eb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(4, 0, 0) -> up -> (3, 0, 0) reward: -1\n",
      "(3, 0, 0) -> up -> (2, 0, 0) reward: -1\n",
      "(2, 0, 0) -> up -> (1, 0, 0) reward: -1\n",
      "(1, 0, 0) -> up -> (0, 0, 0) reward: -1\n",
      "(0, 0, 0) -> pick up -> (0, 0, 1) reward: 5\n",
      "(0, 0, 1) -> down -> (1, 0, 1) reward: -1\n",
      "(1, 0, 1) -> down -> (2, 0, 1) reward: -1\n",
      "(2, 0, 1) -> down -> (3, 0, 1) reward: -1\n",
      "(3, 0, 1) -> down -> (4, 0, 1) reward: -1\n",
      "(4, 0, 1) -> right -> (4, 1, 1) reward: -1\n",
      "(4, 1, 1) -> right -> (4, 2, 1) reward: -1\n",
      "(4, 2, 1) -> right -> (4, 3, 1) reward: -1\n",
      "(4, 3, 1) -> right -> (4, 4, 1) reward: -1\n",
      "(4, 4, 1) -> drop off -> (4, 4, 1) reward: 20\n",
      "Passenger delivered: True\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAhYAAAGyCAYAAAC4Io22AAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjExLjIsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvgI3uAAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAKExJREFUeJzt3QuczPX+x/HPjl3LlkVuKSuLRInkmvulVel6ShfkVtHpJBVdrC4unf/B6fYonfBI0lXEoRJCxIaKSAkpljium9hl2YuZ/+Pz3WaavdhLfe38Zub1fDzmsfv7zW93vvP7zs73Pd/v9/fdCI/H4xEAAAALXDZ+CQAAAMECAABYRY8FAACwhmABAACsIVgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAo0P79++WRRx6R9evXO+YM/fjjj6ZMO3fuDHRRAJwGwQIowsyZM01jlpmZGVbnKiUlRZ5//nnZvHlzocf98MMP5vz88ssvZ7xMycnJpkx79uwRJ3nrrbdk/PjxgS4G4AgEC6AICxcuNI1ZuAWL4vrpp5/M+dm7d+8Zf6yGDRvKs88+K/Hx8eIkH330kUydOjXQxQAcITLQBQCA4qpTp47pHQHgXAQLwJK0tDT58MMPzTyAsmXLSqdOnaRjx465jvnnP/8pR44cMd9HRUVJzZo15eqrr5YGDRr4jtGekZEjR8o111wj7du3lzlz5pjhhhtvvNH83nfeeUeGDRsmZcqUkRkzZsivv/4qbdq0kWuvvfa0wweffPKJ6VGoVq2a+T1169bNd9ynn34qq1atktjYWLn99tuL9ZyTkpJk+vTp5vuJEyfK7Nmzzfd33HGHtGjRwjzmCy+8YPZFRERIuXLl5MILL5QbbrhBKlWqZPbr/0EcN26cnDp1Sp544glxuf7oSNXzqY/xwAMPyAUXXGDO7WuvvSZDhgwxIeN0vv32W9950t83a9YsM3zy1FNPSYUKFcw51l6G7777zpxHLaueb//HfvHFF82x99xzT67fPX/+fFOmCRMmmO2XXnpJvv/+e1MP/qHn3//+d67ft3z5clm9erWcOHFCLrroIunZs6eUL1++WOcZCCYMhQAWrFy5UurVq2cak+zsbDl06JBcf/310qtXL3G73b7jtGE/99xzzU0b2cWLF8sll1wib7zxhu8YbfR0aGHp0qXSo0cP04jpfIdNmzbJ1q1bzX3Lli0zDdOBAwdM460N9UMPPZSvXDrur6FFQ4OGkjVr1pjhhNdff913jJZPg4SW93//+58cPnzY/O6vv/66yOd91llnSeXKlc33VapU8T03b4Op4cm7r0aNGubc6DnScLFt2zZf4GjSpImMGjVKRo8e7fvdOmlUy6XnUkNFSeZYeM/TokWL5G9/+5s5R2vXrpXjx4/Lrl27zOM9+OCDZlvPbb9+/aRt27bmuXu9+eabvqDk7/PPPze/20ufd3R0tAko3ueqN31e6rfffpMuXbrITTfdZM6v7n/uuedMvW/fvr3IcwwEHf236QBOr3///h79U0lLSyvw/kOHDnkqVark6dGjhycrK8u3f+PGjZ7IyEjPxIkTCz29TzzxhOess87y/X79qo9XpUoVz/r1633HHTlyxDNjxgxzX5cuXTzHjx/33ffkk0+ax9q5c6dv37x588yxL730Uq7HmzBhgicqKsqzbds2sz158mRz3Ny5c33HaBnat29v9r/99tuFll9/To9bs2aNpzgyMzM9LVq0MOfLX2JioiciIsKzYMECz+HDhz3x8fGexo0b53qeCxcuNI+VlJRU6GN4z1O7du185zUjI8OTnp7u6dixo6dq1aqeffv2+Y7funWrp1y5cp5evXr59jVt2tRz1VVX5fvdw4cP95QpUybXvltuucVTr169AsvSs2dPT8WKFT07duzw7Tt58qQ5B1o+INTQYwH8RdrlrsMbzzzzjERG/jG6qJ+Kr7zySnPFgF+QlxUrVphP7Y8//rjpOtfuff3knPfqi9atW0uzZs182xUrVvR9r5+wY2JifNv6qVx7A7755hvfPh2aOO+888wwgj/9pK7l0GEU7yfzRo0amU/UXmeffbb079/fymtDn9sHH3wgY8aMkUcffVQSExNNL4n2IPjT89e5c2e58847TY+J9iToMJD/8yypPn36mOeitMdGL6HV3qXBgwebXgUvHZrQ3iUdMjl27JjYsm/fPvMc9PH8J5xqD4cO5+jQ044dO6w9HuAEzLEA/iIdp1fvvfeeaZi00dab0i54b7d9RkaGmQehDeott9xi5jnocIg2vMq/G15pY3862hD602EG7+P5l0sbZW3IlbdcetPH9XbD65CEzgfJ6+KLL5a/SsNSQkKCKYc+d23MNXxpY5/3+XrnjOgwiQ716Pn0n3vyZ+Q9h97hFx2GyKtx48Zmnoc29BoKbdC5F3q+dY7MiBEjfK8L/apDMkrroaA5L0CwIlgAFugkPW3cvePqXn379jWflL09A5999pn5xNyhQwffMe+//75Mnjw53+/0Tm4sSN5Jf9ooK+21yDsHomrVqvl+Xucz6FwLpWXWBjWvgvaVlDamem50voROhPSfXFkQnROhk2C1THqetBfhr8h7Dr314z/vxct77rzH6PyQvOdT/ZkejXPOOSdfPVSvXl1atmxp5uYAoYRgAfxFl112mZl8edVVVxX6SVc/LWsAaNeuXa79X3755Rkrlz7m8OHD8wUef/rpXSeG6qdo/+O8PTFF8YYa76dxf/r4Wg7/UKGNekETQ/XT/X333Se33XabtGrVygwTaQDr3bu32OLthdm4caMZcvGn+zQE1q9f32yff/75Zo2OgspZ0Dko6Pnr60HPaVxcHJfJImwwxwL4i3Qugnbx61UZ+mnbn84T0DkV3uEL7QXwDxLamOmloGfCY489ZlbD1LkLeRs9bRy9jaZeTqnd8dqj4l9u7xyMougls0rnL+Slz1l7J9LT0337Xn755Xyf+lNTU83wkF79oVesaBjSeSM6N2HLli1iS61atcyVNrqY1c8//+zbv27dOjMPROvS2xukw0M6lOPfu6KXqBa0nLieAz1neXs49HWhv1Pnu+TtpdHXwrx586w9N8Ap6LEAiknXWNDu8bzGjh0rS5YsMWs36Kfdrl27mi54baz1E7uuXeGdcKlrPui6FTo5UUOINm46LKFDJrbpxFENC0OHDjWXTWovgDZm2ljqJa06h0HpJ3e9DPXuu+82x+mQjg5d6DCGTi4sivZING3a1AQrHerR+RvedSz0uev50GO6detmJqrqEIAOcej6D1533XWXmR/y1Vdf+SZbai+Q/g7vpa86rGPDtGnTzFoeOgyh8z6ysrLM2hR6vrxrbqh7773XlEH36/EaHLRe9bn5l907SfQ///mP6bXSc6HDP951LF599VXTS6PnX3+XTuLUELZhwwazTon/pFkgFETopSGBLgTgZDrur0MFp3P//febT7n6p6QLIHmP1ZChwx7a0HppA6NrV2jo0Cs29NPzwYMHzf8j0QZUF33Shk4bLm10dOErf9owf/zxx+ZTsK6J4aU9AtqAaSN++eWX5/oZ7R3QxZn0k7Y2jDoc0Lx583zPQxs6Lb8ukKVrWmgI0YZVG9/CJpJ6H0PXyti9e7f51K6LTXknSOo6DvqcdQEpbXT1nGgvjl7BogtYaaDQkKNl0vUe/GlvhfboeJ+XPgcNPxpMdKjidE53nry0rr744gvTc6NDFRpgNGjkpRNu9fF1/Qkd1tBeDP+y+9M61TUu9Aoh/f15h6B0DQ59TL1fh0Y0aOhrAAg1BAsAAGANcywAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAELwLZOl1/Hrdui7xW9gywwAAwDl0fRZd2E/XX9HF3xwTLDRU6OIwAAAg+OhCeLo8vmOChfefEWnBdIW/YKQrI+pKgt27dy9wiWdQH+GKvw3noC6cIytE2gz9nz7aMeD/TwUdESy8wx8aKoI5WMTExJjyB/OLJFRQH85BXTgHdeEcWSHWZhQ1jYHJmwAAwBqCBQAAsIZgAQAArCFYAAAAawgWAADAGoIFAACwhmABAACsIVgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAAAIIFAABwHnosAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQSLYvJ4PLIseZncOutWaTq5qdnXZmobGfnZSNl1ZJe9GgEAIIhFBroAwWDt/9ZKn//2kZ8O/ySRrkiJkiiR2iJbUrbIxkMbZfwX4+XWi2+VqTdMlQrRFQJdXAAAAoYeiyKs3LVSOrzRQXb8tsNsZ7uzc91/ynNKPOKROVvmSMfpHSUtI+3M1RYAAKEWLGbNmiVNmjSRihUrSosWLWTx4sUSqvam7ZXr3rtOstxZJkAY7kgpn9lDZie7zFfdVnr/9we+l35z+wW20AAABEuwWLp0qfTp00eGDBkiW7dulZtvvlmuv/562bhxo4SiyesmS3pWurg9brNdKWuA1M6YIxWyBkrSfpf5qtu63xsu5v04T7ambA1wyQEACIJg8eyzz0qPHj1k8ODBUrNmTRk5cqRceuml8sILL0ioyTyVKZPWTfL1VGh4iM2+pYBT5jL7veEiMiLSBBIAAMKRqyRXRaxatUq6dOmSa3+3bt3M/lCzbu86SUlPydlwR0ps9t/MtxESkes477a53x0p2Z5smb15dukXGACAYLoqJC0tTY4fPy7Vq1fPtV+39+/ff9qfy8jIMDev1NRU8zUrK8vcnColLUXKu8qb78tn95AIKXPaY3PCRRk5x32jnIhcICczTzr6uYUa77nmnAcedeEc1IVzZIXIe1Rxy1/iy01dLle+be3NOJ1x48bJmDFj8u3XSZ8xMTHiZDOazDBfdaJm0umzk0+PKv2lZ3xf8/2CBQvOdPGQx5IlSzgnDkFdOAd14RxLgvw9Kj093W6wqFChggkChw4dyrX/4MGDUqNGjdP+XGJiogwbNixXj0VcXJx0795dYmNjxal2H90tjSc1Nt/r1R8VZGCRP7Pg1zdl7rFF0ur8VvLpnZ+WQinhTdH6B5uQkCBRUVGclACiLpyDunCOrBB5j/KOOFgLFhEREdK6dWtZsWKFPPDAA779y5cvlyuuuOK0PxcdHW1ueenJdfIJrlu1rnSo00E+S/5MTrg+lLNFLyN15ZtjoXQdCxG3HHZ9KHIqW+5ufrejn1uocvprKpxQF85BXThHVJC/RxW37CW6KuThhx+Wjz76yKxloV0ikyZNknXr1snQoUMlFA1pNSTnqhBXtqRGzvULEX/wbuv9Ea5TUrlcZel5cc+AlBcAgEArUbDQNSteeeUVGT58uJx99tny/PPPy/vvv296MkLRdQ2ukzsuuUNcES45EjVdUiPnmJ6J3Nxmv96vpt80XaIj8/fQAAAQDko8eVPXsNCb2+3ON5Ez1OjwjwYFXSBr1uZZklb2bUl1fShxmW+b+49FzZBfXTMlMlJPZKS8edObcsNFNwS62AAABMyfTgahHiq8tPdhRs8ZMrPnTLmi1hUirj96LE5ELZVyUZHSv2l/WT94vfS+tHdAywoAQKDx302LQYdCbrvkNnNbs2uT9JqU82/Sp1w7Ra67pJNUKlfpTNcTAABBITy6HSy6sMqFvu+vrNuNUAEAgB+CBQAAsIZgAQAArCFYAAAAawgWAADAGoIFAACwhmABAACsIVgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAAAGsIFgAAwBqCBQAAsIZgAQAArCFYAAAAggUAAHAeeiwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAABDZYeDweOXLkiGRlZdkrCQAACK9gcfjwYXn22WelQYMGUrlyZZk5c6aEm8xst+/7GWv35NoGACDclShYzJkzRw4cOCALFiyQcDRuwWZpP2GZb/ulZdul4VMLzX4AACASWZKTMGjQoLA9ZxoepqxMzrff7RHf/sQeFwegZAAAOAeTN4tBhzteS8ofKvzp/QyLAADCXYl6LP6MjIwMc/NKTU01X3XiZ7BM/py+eqfpmSiM3j991XYZ2LZOaRULv/O+joLl9RTKqAvnoC6cIytE3qOKW/4zHizGjRsnY8aMybd/8eLFEhMTI8EgKdlVrM6dpA1bpcYR5lsEypIlSwL22MiNunAO6sI5lgT5e1R6erozgkViYqIMGzYsV49FXFycdO/eXWJjYyUYHFi9U5IWbivyuA7NGkoPeiwCkqL1DzYhIUGioqJKvwCgLhyIvwvnyAqR9yjviEPAg0V0dLS55aUnN1hO8IB29WT8om2FDoe4InKOi4pk2kqgBNNrKtRRF85BXThHVJC/RxW37CVqBbOzs83CWHrzdovo9ydOnJBQVjbSJYM6xBd6jN6vxwEAEM5K1BKuWrVK6tSpY24VK1aUxx57zHz/+OOPS6jTS0nv7Rhveib86bbu51JTAABKOBTSqVMnX29FONLw0L9tvLQdn7NI1oNd68n9XRvQUwEAwO/ouy8h/+GOXi1rESoAAPBDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAECwAAAAzkOPBQAAsIZgAQAArCFYAAAAawgWAADAGoIFAACwhmABAACsIVgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAAAGsIFgAAwBqCBQAAsIZgAQAArCFYAAAAawgWAADAGoIFAACwhmABAACsIVgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAAAGsIFgAAwBqCBQAACGywSE1Nld9++81eKQAAQPgFizlz5kjz5s0lLi5O6tatK/Xr15f58+dLOMnMdvu+n7F2T65tAADCXYmCxfLly2Xq1Kly5MgROXz4sAwcOFB69uwp27Ztk3AwbsFmaT9hmW/7pWXbpeFTC81+AABQwmDxyiuvSLNmzSQiIsLcRowYIW63W1auXBny51LDw5SVyeL25N6v27qfcAEAwF+cvLljxw7JysqS888/P6TPpQ53vJaUXOgxej/DIgCAcBf5Z38wOztbBg0aJE2bNpWEhITTHpeRkWFu/hM/lQYSvQWD6at35uupyEvvn75quwxsW6e0ioXfeV9HwfJ6CmXUhXNQF86RFSLvUcUtf4TH4ymiycxPhz/69u0rn3/+uSQlJZmJnKczevRoGTNmTL797733nsTExEgwmJ3skqT9RXfudDjXLT3jmcwJAAg96enp0rt3bzl69KjExsbaCxYaKnTS5pIlS0ywaNCgQaHHF9RjoVeVpKSkFFowJ3lj9U7518KiJ6iOvKYBPRYBStH6etSes6ioqEAUAdSF4/B34RxZIfIepe131apViwwWkSUNFXfddZc5QXqFSFGhQkVHR5tbXnpyg+UED2hXT8Yv2lbocIgrIue4qEjWHAuUYHpNhTrqwjmoC+eICvL3qOKWvUSt4ODBg81aFnrJaZkyZeTnn382N730NJSVjXTJoA7xhR6j9+txAACEsxL1WKxZs0Zq1KghQ4cOzbVft/PuCzWJPS72Xf3h33OhPRUaKrz3AwAQzkoULH744QcJZxoe+reNl7bjcxbJerBrPbm/awN6KgAA+B199yXkP9zRq2UtQgUAAH4IFgAAwBqCBQAAsIZgAQAArCFYAAAAawgWAADAGoIFAACwhmABAAAIFgAAwHnosQAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAAAECwAA4Dz0WAAAAGsIFgAAwBqCBQAAsIZgAQAArCFYAAAAawgWAADAGoIFAAAIbLDYv3+/bNq0SY4dO2avJAAAILyCxRdffCGtW7eWli1byu233y7Vq1eXoUOHitvtlnCRmf3Hc52xdk+ubQAAwl2JgsX27dtl2rRpsnv3bvnhhx9kzZo1MmXKFHn77bclHIxbsFnaT1jm235p2XZp+NRCsx8AAIhEluQk9O/fP9d206ZNpVq1aiZohDoND1NWJufb7/aIb39ij4sDUDIAAII0WKgTJ07Ixo0b5fjx4zJ79myJjo6WgQMHSijT4Y7XkvKHCn96//DuDaVsJPNhAQDhq8TBYt++ffLQQw/JkSNHZM+ePTJ27Fg577zzTnt8RkaGuXmlpqaar1lZWeYWDKav3ml6Jgqj909ftV0Gtq1TWsXC77yvo2B5PYUy6sI5qAvnyAqR96jilj/C4/EU0WSe3rfffiudO3eWUaNGycMPP1zgMaNHj5YxY8bk2//ee+9JTEyMBIPZyS5J2l90T0SHc93SM57JnACA0JOeni69e/eWo0ePSmxs7JkJFqpXr15y6NAhWbp0abF7LOLi4iQlJaXQgjnJG6t3yr8WbivyuJHXNKDHIkApesmSJZKQkCBRUVGBKAKoC8fh78I5skLkPUrb76pVqxYZLCJLmlby9jIkJyfLBRdccNqf0TkYestLT26wnOAB7erJ+EXbCh0OcUXkHBfFHIuACabXVKijLpyDunCOqCB/jypu2UsULDp16mTWr9CrQXQS57vvvivfffedTJw4UUKZTsgc1CG+wKtCvPR+Jm4CAMJdiYLFokWL5OWXX5bnn3/eJJdLLrlEtm7dKrVr15ZQ572UVK/+8O+50J4KDRVcagoAQAmDRZUqVQqciBkuNDz0bxsvbcfnLJL1YNd6cn/XBvRUAADwOxZdKCH/4Y5eLWsRKgAA8EOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAA1hAsAACANQQLAABgDcECAABYQ7AAAADWECwAAIA1BAsAAGANwQIAAFhDsAAAANYQLAAAgDUECwAAYA3BAgAAWEOwAAAABAsAAOA89FgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAAAGsIFgAAwBqCBQAAsIZgAQAArCFYAAAAawgWAADAGoIFAACwhmABAACsIVgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAAAGsIFgAAwBqCBQAAsIZgAQAArCFYAAAAawgWAADAGoIFAACwhmABAACsIVgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAAAGsIFgAAwBqCBQAAsIZgAQAArCFYAABwpvz2m8iWLTnf798fFueZYAEAgE0ej8iKFSK33SZSrZpImzY5+y+6SKRtW5EZM0QyM0P2nBMsAACw5eRJkV69RDp3Fpk7V+TUqdz3f/21SO/eIs2aiezZE5Ln/U8Hi7S0NJk/f7588803Ek4ys92+72es3ZNrG6XvlNsjXyUflm9SIsxX3UZgUBfOQV0E6sSfyuml+OCDnO3sbMl0RcobTXvI7GSX+Zrpici5b9s2kfbtRQ4dklAT4fFon03J9enTR2bNmiU33nijzJ49u9g/l5qaKhUrVpSjR49KbGysBJNxCzbLa0nJ4t92uSJEBnWIl8QeFweyaGFp0aZ9MubjzbLv6EnfvpoVy8mo6y+WqxvXDGjZwg114RzURQC9+qrIkCE5QyHaZnQeIK+1/Ju4XWV8h7jcp2TQ2rmS+Pl0kTJlRG65RWTmTAkGxW2//1SPxbRp0yQ5OVmuvPJKCRcaKqaszB0qlG7rfr0fpfvmed8763OFCrX/6EmzX+8HdRFu+LsIIA0TL77o29RQMaXVLeKOyN3M6rbu1/tND8ecOSJ790ooiSzpD2zdulWeeOIJWbVqlQwdOlTCgQ53aE9FYfT++zrXl7KRTFspjW7eUR/9IAV1tek+7Wgc/dFmaVe/qpTRLiVQF2GAv4sAW5kksmu3SGRZM/yhPRVGRJ73IN32eMz9w1e+I2U9bpGpU0WeflrCMlhkZGTIHXfcIRMmTJC6desW+2f05t+VorKysswtGExfvTNfT0Veev9lY5eUVpFQCK2q/akn5dLRizlPAUZdOAd1UQqGzSnecRER4o4oI9Nb3SgDNy4Q2bBBG0VxuuK22SUKFsOGDZOLLrpI+vXrV+yfGTdunIwZMybf/sWLF0tMTIwEg6Rk7YWgJwIAYLFtub2/1BjRN2djwQLHn9r09HS7kzfXrFkjnTt3lqlTp0rlypXNvrFjx0rZsmVlxIgR0q1bNylfvnyxeizi4uIkJSUlaCZvvrF6p/xr4bYij3skob70bVO7VMoUztbu/E3ueXtDkcdN7dtMWtbJea2Cugh1/F0E2JQpImOfEXG75e0mV8lz7X8PDIUYueINGfjdQpFrrslZ28LhtP2uWrVqkZM3i91jERERIQkJCTLTb/bqrl27xOVyyeTJk6VVq1YFBovo6GhzyysqKsrcgsGAdvVk/KJthQ6H6FD+4E4XMseiFHRpVE5qVtxiJmoWVCU6onluxXLSpVFN5lhQF2GDv4sA69xRZPhh8+3gNXPkhba9cyZu5p1joTwecXncMuDrDyXKcyrnstMgaA+L22YXu3+/TZs2Zt0K/1vLli2lXbt25vvq1atLqNIJmXpJaWH0fiZulg6dkKmXlKq8f7Lebb2fiZvURTjh7yLALr9cpHlzEZdLyrqzzSWlRt5Bgd+39X49TsqWFRkwQEIJEweKSdepuLdjvOmZyHUCI8TsZx2L0qXrVEy683LTM+FPt3U/61hQF+GIv4sAe/RRMxSidJ2Ke7+eY3om/Om27jfrWLhcInfdJVKpkoSSP71AVt45FuGwQJb30tPpq7ZL0oat0qFZQzNMQk9FYC+xW/PzQVmc9JV079BarqhfnZ4K6iLs8XcRINqcDh0q8sorvl166ale/aETNTvMfNMMf5ieCl0cS3s5Pv9cJEguZChu+13idSz8PR1C190Wl4aIgW3rSI0jm6VH2zoSxboVAe/+bR1/jvy6xWO+MvxBXYC/i4DR+RQvv5zTA/F//5czLHIq21xSqld/9Ni4QKJ0nEA7Ma6+OmfCZpCEipJgKAQAAJvh4plnRHbuFElMzPnvpl7lyon07Suydq3I/PkiFSqE5HknWAAAYFvt2jkB4+DBnJvav1//J4ZIixYhfb4JFgAAnEnRvy+5UNClpyGIYAEAAKwhWAAAAGsIFgAAwBqCBQAAsIZgAQAArCFYAAAAawgWAADAGoIFAACwhmABAACsIVgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAAAGsIFgAAwBqCBQAAsIZgAQAArCFYAAAAawgWAADAGoIFAACwhmABAACsIVgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAAAGsipZR5PB7zNTU1VYJVVlaWpKenm+cQFRUV6OKEPerDOagL56AunCMrRNoMb7vtbccdEyzS0tLM17i4uNJ+aAAAYKEdr1ix4mnvj/AUFT0sc7vdsnfvXqlQoYJERERIsKY2DUa7d++W2NjYQBcn7FEfzkFdOAd14RypIdJmaFzQUHHeeeeJy+VyTo+FFqZWrVoSCvQFEswvklBDfTgHdeEc1IVzxIZAm1FYT4UXkzcBAIA1BAsAAGANweJPiI6OllGjRpmvCDzqwzmoC+egLpwjOszajFKfvAkAAEIXPRYAAMAaggUAALCGYAEAAKwp9XUsgt2pU6dkzZo1kpKSIpdddpnUqVMn0EUKa9u2bZP169dL69atJT4+PtDFCVuZmZny7bffyqFDh6Rhw4ZSr169QBcprCUnJ8umTZvknHPOkRYtWoTNpEEn27Bhg/z444/SsWNHs8BUKCNYlMDBgwclISFBjh49KvXr15fVq1fLU089JYmJiWeuhlAgDROPP/647Nq1S37++WeZNm0awSJAZsyYIU8++aRUqVJFqlWrJklJSXLdddfJW2+9JZGRvMWUJv3AM3DgQNOANWrUSH766Sc5fPiwzJw5Uzp16lSqZcEf9H3qmmuukQMHDsjHH38c8sGCoZASGDZsmJQpU0a2bNkiS5culVmzZsnIkSNl3bp1Z66GUCANd48++qh5Ay1saVmceRoeNEx8/fXX8sknn5iei/nz58urr77K6S9l+o+uhg8fbnryPvzwQ9m8ebNceeWV8o9//IO6CJDs7Gzp1auXPPLII2FTB7wjF9PJkydl9uzZ8ve//13Kly9v9umnsgYNGsi77757JusIBejSpYt07949aP/fTCi59dZbc30Cq1u3rhkm1ICB0lW7dm3p3Llzrn36HuX9548ofU8//bScf/75MmDAgLA5/fRTFpN2KWZkZEjjxo1z7b/00kvl+++/PxN1AwSlX3/91YSKm266KdBFCVvLli2Tffv2mZ4LHSacOHFioIsUlj777DN55513zN+D/gPOcEGwKEHXu9LJUP50XHnnzp32awYI0snN/fv3l+rVq8ugQYMCXZyw9cUXX8jGjRvNBE79r5pMMg/MnLx+/fqZuUbabuj8l3BBsCgm76zqY8eO5dqv2+XKlbNfM0CQ0U9kd999t3zzzTeyYsUKqVChQqCLFNbd70oXVh4yZIhce+21smPHDq4OKUUjR440oU6vlHr//fd9w1E6HykmJka6du0qoYo5FsWk48bql19+yTfb13sfEK60Abvnnnvk008/leXLl5txfQSezkG68847Ze/evbJ9+/ZAFyesNGrUyPQUzZs3z9wWLlxo9utyBdqjFMrosSgmHfLQtRI++OADufnmm30h48svv5QHHnjgTNYR4PhQocMe+sapY/u6jgUCY//+/XLuuefm2qc9SHrlTs2aNamWUjR8+PBc2zoUMnfuXHnsscfMxP9QRrAogeeee066desmgwcPliZNmsikSZOkXbt20rNnzzNXQzjt+KU2Yt6G7auvvjJDUrpIlgZAlB5dT0QnCGr3u47r601pQ8baCaVLGy798KNrJuiHIV2U6fXXX5fRo0dL5cqVS7k0CFf8d9MS0slQ+iaqM9+bN28u9957L+OWAaDX548dOzbffm3I7rvvvkAUKWxpPWh95KWXnI4YMSIgZQpnuq7Of//7X7MYU61atcwHH716DYGVlpZmevY0iDdr1iykq4NgAQAArGHyJgAAsIZgAQAArCFYAAAAawgWAADAGoIFAACwhmABAACsIVgAAABrCBYAAMAaggUAALCGYAEAAKwhWAAAAGsIFgAAQGz5fzhbuDmbhpCSAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Test one trip: start at (4, 0), collect the passenger, then drop off.\n",
    "state = (4, 0, 0)\n",
    "trip = [state]\n",
    "for _ in range(50):\n",
    "    action = int(np.argmax(q[state]))\n",
    "    next_state, reward, done = step(state, action)\n",
    "    print(state, \"->\", action_names[action], \"->\", next_state, \"reward:\", reward)\n",
    "    state = next_state\n",
    "    trip.append(state)\n",
    "    if done:\n",
    "        break\n",
    "print(\"Passenger delivered:\", done)\n",
    "assert done, \"Increase the training episodes if the policy has not converged.\"\n",
    "coordinates = np.array([(row, col) for row, col, _ in trip])\n",
    "plt.plot(coordinates[:, 1], coordinates[:, 0], marker=\"o\")\n",
    "plt.scatter([pickup[1], destination[1]], [pickup[0], destination[0]],\n",
    "            c=[\"green\", \"red\"], s=100, label=\"Pickup / destination\")\n",
    "plt.xlim(-0.5, 4.5); plt.ylim(4.5, -0.5)\n",
    "plt.xticks(range(5)); plt.yticks(range(5))\n",
    "plt.title(\"Learned taxi route\")\n",
    "plt.grid(); plt.show()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}