mdp_apps.ipynb

    "For example, as we have the same reward regardless of the action, let's consider a reward of **r** units for a particular state and let's assume the transition probabilities to be 0.1, 0.2, 0.3 and 0.4 for 4 possible actions for that state.\n",
    "We will further assume that a particular action in a state leads to the same state every time we take that action.\n",
    "The first term inside the summation for this case will evaluate to (0.1 + 0.2 + 0.3 + 0.4)r = r which is equal to R(s) in the first update equation.\n",
    "<br>\n",
    "There are many ways to write value iteration for this situation, but we will go with the most intuitive method.\n",
    "One that can be implemented with minor alterations to the existing `value_iteration` algorithm.\n",
    "<br>\n",
    "Our `DMDP` class will be slightly different.\n",
    "More specifically, the `R` method will have one more index to go through now that we have three levels of nesting in the reward model.\n",
    "We will call the new class `DMDP2` as I have run out of creative names."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class DMDP2:\n",
    "\n",
    "    \"\"\"A Markov Decision Process, defined by an initial state, transition model,\n",
    "    and reward model. We also keep track of a gamma value, for use by\n",
    "    algorithms. The transition model is represented somewhat differently from\n",
    "    the text. Instead of P(s' | s, a) being a probability number for each\n",
    "    state/state/action triplet, we instead have T(s, a) return a\n",
    "    list of (p, s') pairs. The reward function is very similar.\n",
    "    We also keep track of the possible states,\n",
    "    terminal states, and actions for each state.\"\"\"\n",
    "\n",
    "    def __init__(self, init, actlist, terminals, transitions={}, rewards={}, states=None, gamma=.9):\n",
    "        if not (0 < gamma <= 1):\n",
    "            raise ValueError(\"An MDP must have 0 < gamma <= 1\")\n",
    "\n",
    "        if states:\n",
    "            self.states = states\n",
    "        else:\n",
    "            self.states = set()\n",
    "        self.init = init\n",
    "        self.actlist = actlist\n",
    "        self.terminals = terminals\n",
    "        self.transitions = transitions\n",
    "        self.rewards = rewards\n",
    "        self.gamma = gamma\n",
    "\n",
    "    def R(self, state, action, state_):\n",
    "        \"\"\"Return a numeric reward for this state, this action and the next state_\"\"\"\n",
    "        if (self.rewards == {}):\n",
    "            raise ValueError('Reward model is missing')\n",
    "        else:\n",
    "            return self.rewards[state][action][state_]\n",
    "\n",
    "    def T(self, state, action):\n",
    "        \"\"\"Transition model. From a state and an action, return a list\n",
    "        of (probability, result-state) pairs.\"\"\"\n",
    "        if(self.transitions == {}):\n",
    "            raise ValueError(\"Transition model is missing\")\n",
    "        else:\n",
    "            return self.transitions[state][action]\n",
    "\n",
    "    def actions(self, state):\n",
    "        \"\"\"Set of actions that can be performed in this state. By default, a\n",
    "        fixed list of actions, except for terminal states. Override this\n",
    "        method if you need to specialize by state.\"\"\"\n",
    "        if state in self.terminals:\n",
    "            return [None]\n",
    "        else:\n",
    "            return self.actlist\n",
    "        \n",
    "    def actions(self, state):\n",
    "        \"\"\"Set of actions that can be performed in this state. By default, a\n",
    "        fixed list of actions, except for terminal states. Override this\n",
    "        method if you need to specialize by state.\"\"\"\n",
    "        if state in self.terminals:\n",
    "            return [None]\n",
    "        else:\n",
    "            return self.actlist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only the `R` method is different from the previous `DMDP` class.\n",
    "<br>\n",
    "Our traditional custom class will be required to implement the transition model and the reward model.\n",
    "<br>\n",
    "We call this class `CustomDMDP2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class CustomDMDP2(DMDP2):\n",
    "    \n",
    "    def __init__(self, transition_matrix, rewards, terminals, init, gamma=.9):\n",
    "        actlist = []\n",
    "        for state in transition_matrix.keys():\n",
    "            actlist.extend(transition_matrix[state])\n",
    "        actlist = list(set(actlist))\n",
    "        print(actlist)\n",
    "        \n",
    "        DMDP2.__init__(self, init, actlist, terminals=terminals, gamma=gamma)\n",
    "        self.t = transition_matrix\n",
    "        self.rewards = rewards\n",
    "        for state in self.t:\n",
    "            self.states.add(state)\n",
    "                      \n",
    "    def T(self, state, action):\n",
    "        if action is None:\n",
    "            return [(0.0, state)]\n",
    "        else:\n",
    "            return [(prob, new_state) for new_state, prob in self.t[state][action].items()]\n",
    "        \n",
    "    def R(self, state, action, state_):\n",
    "        if action is None:\n",
    "            return 0\n",
    "        else:\n",
    "            return self.rewards[state][action][state_]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can finally write value iteration for this problem.\n",
    "The latest update equation will be used."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def value_iteration_taxi_mdp(dmdp2, epsilon=0.001):\n",
    "    U1 = {s: 0 for s in dmdp2.states}\n",
    "    R, T, gamma = dmdp2.R, dmdp2.T, dmdp2.gamma\n",
    "    while True:\n",
    "        U = U1.copy()\n",
    "        delta = 0\n",
    "        for s in dmdp2.states:\n",
    "            U1[s] = max([sum([(p*(R(s, a, s1) + gamma*U[s1])) for (p, s1) in T(s, a)]) for a in dmdp2.actions(s)])\n",
    "            delta = max(delta, abs(U1[s] - U[s]))\n",
    "        if delta < epsilon * (1 - gamma) / gamma:\n",
    "            return U"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These algorithms can be made more pythonic by using cleverer list comprehensions.\n",
    "We can also write the variants of value iteration in such a way that all problems are solved using the same base class, regardless of the reward function and the number of arguments it takes.\n",
    "Quite a few things can be done to refactor the code and reduce repetition, but we have done it this way for the sake of clarity.\n",
    "Perhaps you can try this as an exercise.\n",
    "<br>\n",
    "We now need to define terminals and initial state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "terminals = ['end']\n",
    "init = 'A'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's instantiate our class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['stand', 'dispatch', 'cruise']\n"
     ]
    }
   ],
   "source": [
    "dmdp2 = CustomDMDP2(t, r, terminals, init, gamma=.9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': 124.4881543573768, 'B': 137.70885410461636, 'C': 129.08041190693115}"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value_iteration_taxi_mdp(dmdp2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are the expected utility values for the states of our MDP.\n",
    "Let's proceed to write a helper function to find the expected utility and another to find the best policy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def expected_utility_dmdp2(a, s, U, dmdp2):\n",
    "    return sum([(p*(dmdp2.R(s, a, s1) + dmdp2.gamma*U[s1])) for (p, s1) in dmdp2.T(s, a)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from utils import argmax\n",
    "def best_policy_dmdp2(dmdp2, U):\n",
    "    pi = {}\n",
    "    for s in dmdp2.states:\n",
    "        pi[s] = argmax(dmdp2.actions(s), key=lambda a: expected_utility_dmdp2(a, s, U, dmdp2))\n",
    "    return pi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the best policy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'C': 'cruise', 'A': 'stand', 'B': 'stand'}\n"
     ]
    }
   ],
   "source": [
    "pi = best_policy_dmdp2(dmdp2, value_iteration_taxi_mdp(dmdp2, .01))\n",
    "print(pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have successfully adapted the existing code to a different scenario yet again.\n",
    "The takeaway from this section is that you can convert the vast majority of reinforcement learning problems into MDPs and solve for the best policy using simple yet efficient tools."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## GRID MDP\n",
    "---\n",
    "### Pathfinding Problem\n",
    "Markov Decision Processes can be used to find the best path through a maze. Let us consider this simple maze.\n",
    "![title](images/maze.png)\n",
    "\n",
    "This environment can be formulated as a GridMDP.\n",
    "<br>\n",
    "To make the grid matrix, we will consider the state-reward to be -0.1 for every state.\n",
    "<br>\n",
    "State (1, 1) will have a reward of -5 to signify that this state is to be prohibited.\n",
    "<br>\n",
    "State (9, 9) will have a reward of +5.\n",
    "This will be the terminal state.\n",
    "<br>\n",
    "The matrix can be generated using the GridMDP editor or we can write it ourselves."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "grid = [\n",
    "    [None, None, None, None, None, None, None, None, None, None, None], \n",
    "    [None, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, None, +5.0, None], \n",
    "    [None, -0.1, None, None, None, None, None, None, None, -0.1, None], \n",
    "    [None, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, None], \n",
    "    [None, -0.1, None, None, None, None, None, None, None, None, None], \n",
    "    [None, -0.1, None, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, None], \n",
    "    [None, -0.1, None, None, None, None, None, -0.1, None, -0.1, None], \n",
    "    [None, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, -0.1, None, -0.1, None], \n",
    "    [None, None, None, None, None, -0.1, None, -0.1, None, -0.1, None], \n",
    "    [None, -5.0, -0.1, -0.1, -0.1, -0.1, None, -0.1, None, -0.1, None], \n",
    "    [None, None, None, None, None, None, None, None, None, None, None]\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have only one terminal state, (9, 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "terminals = [(9, 9)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We define our maze environment below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "maze = GridMDP(grid, terminals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To solve the maze, we can use the `best_policy` function along with `value_iteration`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pi = best_policy(maze, value_iteration(maze))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the heatmap generated by the GridMDP editor using `value_iteration` on this environment\n",
    "<br>\n",
    "![title](images/mdp-d.png)\n",
    "<br>\n",
    "Let's print out the best policy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None   None   None   None   None   None   None   None   None   None   None\n",
      "None   v      <      <      <      <      <      <      None   .      None\n",
      "None   v      None   None   None   None   None   None   None   ^      None\n",
      "None   >      >      >      >      >      >      >      >      ^      None\n",
      "None   ^      None   None   None   None   None   None   None   None   None\n",
      "None   ^      None   >      >      >      >      v      <      <      None\n",
      "None   ^      None   None   None   None   None   v      None   ^      None\n",
      "None   ^      <      <      <      <      <      <      None   ^      None\n",
      "None   None   None   None   None   ^      None   ^      None   ^      None\n",
      "None   >      >      >      >      ^      None   ^      None   ^      None\n",
      "None   None   None   None   None   None   None   None   None   None   None\n"
     ]
    }
   ],
   "source": [
    "from utils import print_table\n",
    "print_table(maze.to_arrows(pi))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can infer, we can find the path to the terminal state starting from any given state using this policy.\n",
    "All maze problems can be solved by formulating it as a MDP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## POMDP\n",
    "### Two state POMDP\n",
    "Let's consider a problem where we have two doors, one to our left and one to our right.\n",
    "One of these doors opens to a room with a tiger in it, and the other one opens to an empty hall.\n",
    "<br>\n",
    "We will call our two states `0` and `1` for `left` and `right` respectively.\n",
    "<br>\n",
    "The possible actions we can take are as follows:\n",
    "<br>\n",
    "1. __Open-left__: Open the left door.\n",
    "Represented by `0`.\n",
    "2. __Open-right__: Open the right door.\n",
    "Represented by `1`.\n",
    "3. __Listen__: Listen carefully to one side and possibly hear the tiger breathing.\n",
    "Represented by `2`.\n",
    "\n",
    "<br>\n",
    "The possible observations we can get are as follows:\n",
    "<br>\n",
    "1. __TL__: Tiger seems to be at the left door.\n",
    "2. __TR__: Tiger seems to be at the right door.\n",
    "\n",
    "<br>\n",
    "The reward function is as follows:\n",
    "<br>\n",
    "We get +10 reward for opening the door to the empty hall and we get -100 reward for opening the other door and setting the tiger free.\n",
    "<br>\n",
    "Listening costs us -1 reward.\n",
    "<br>\n",
    "We want to minimize our chances of setting the tiger free.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our transition probabilities can be defined as:\n",
    "<br>\n",
    "<br>\n",
    "Action `0` (Open left door)\n",
    "$\\\\\n",
    "    P(0) = \n",
    "    \\left[ {\\begin{array}{cc}\n",
    "    0.5 & 0.5 \\\\\n",
    "    0.5 & 0.5 \\\\\n",
    "    \\end{array}}\\right] \\\\\n",
    "    \\\\\n",
    "    $\n",
    "    \n",
    "Action `1` (Open right door)\n",
    "$\\\\\n",
    "    P(1) = \n",
    "    \\left[ {\\begin{array}{cc}\n",
    "    0.5 & 0.5 \\\\\n",
    "    0.5 & 0.5 \\\\\n",
    "    \\end{array}}\\right] \\\\\n",
    "    \\\\\n",
    "    $\n",
    "    \n",
    "Action `2` (Listen)\n",
    "$\\\\\n",
    "    P(2) = \n",
    "    \\left[ {\\begin{array}{cc}\n",
    "    1.0 & 0.0 \\\\\n",
    "    0.0 & 1.0 \\\\\n",
    "    \\end{array}}\\right] \\\\\n",
    "    \\\\\n",
    "    $\n",
    "    \n",
    "<br>\n",
    "<br>\n",
    "Our observation probabilities can be defined as:\n",
    "<br>\n",
    "<br>\n",
    "$\\\\\n",
    "    O(0) = \n",
    "    \\left[ {\\begin{array}{ccc}\n",
    "    Open left & TL & TR \\\\\n",
    "    Tiger: left & 0.5 & 0.5 \\\\\n",
    "    Tiger: right & 0.5 & 0.5 \\\\\n",
    "    \\end{array}}\\right] \\\\\n",
    "    \\\\\n",
    "    $\n",
    "\n",
    "$\\\\\n",
    "    O(1) = \n",
    "    \\left[ {\\begin{array}{ccc}\n",
    "    Open right & TL & TR \\\\\n",
    "    Tiger: left & 0.5 & 0.5 \\\\\n",
    "    Tiger: right & 0.5 & 0.5 \\\\\n",
    "    \\end{array}}\\right] \\\\\n",
    "    \\\\\n",
    "    $\n",
    "\n",
    "$\\\\\n",
    "    O(2) = \n",
    "    \\left[ {\\begin{array}{ccc}\n",
    "    Listen & TL & TR \\\\\n",
    "    Tiger: left & 0.85 & 0.15 \\\\\n",
    "    Tiger: right & 0.15 & 0.85 \\\\\n",
    "    \\end{array}}\\right] \\\\\n",
    "    \\\\\n",
    "    $\n",
    "\n",
    "<br>\n",
    "<br>\n",
    "The rewards of this POMDP are defined as:\n",
    "<br>\n",
    "<br>\n",
    "$\\\\\n",
    "    R(0) = \n",
    "    \\left[ {\\begin{array}{cc}\n",
    "    Openleft & Reward \\\\\n",
    "    Tiger: left & -100 \\\\\n",
    "    Tiger: right & +10 \\\\\n",
    "    \\end{array}}\\right] \\\\\n",
    "    \\\\\n",
    "    $\n",
    "    \n",
    "$\\\\\n",
    "    R(1) = \n",
    "    \\left[ {\\begin{array}{cc}\n",
    "    Openright & Reward \\\\\n",
    "    Tiger: left & +10 \\\\\n",
    "    Tiger: right & -100 \\\\\n",
    "    \\end{array}}\\right] \\\\\n",
    "    \\\\\n",
    "    $\n",
    "    \n",
    "$\\\\\n",
    "    R(2) = \n",
    "    \\left[ {\\begin{array}{cc}\n",
    "    Listen & Reward \\\\\n",
    "    Tiger: left & -1 \\\\\n",
    "    Tiger: right & -1 \\\\\n",
    "    \\end{array}}\\right] \\\\\n",
    "    \\\\\n",
    "    $\n",
    "    \n",
    "<br>\n",
    "Based on these matrices, we will initialize our variables."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's first define our transition state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "t_prob = [[[0.5, 0.5], \n",
    "           [0.5, 0.5]], \n",
    "          \n",
    "          [[0.5, 0.5], \n",
    "           [0.5, 0.5]], \n",
    "          \n",
    "          [[1.0, 0.0], \n",
    "           [0.0, 1.0]]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Followed by the observation model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "e_prob = [[[0.5, 0.5], \n",
    "           [0.5, 0.5]], \n",
    "          \n",
    "          [[0.5, 0.5], \n",
    "           [0.5, 0.5]], \n",
    "          \n",
    "          [[0.85, 0.15], \n",
    "           [0.15, 0.85]]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And the reward model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "rewards = [[-100, 10], \n",
    "           [10, -100], \n",
    "           [-1, -1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now define our states, observations and actions.\n",
    "<br>\n",
    "We will use `gamma` = 0.95 for this example.\n",
    "<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 0: open-left, 1: open-right, 2: listen\n",
    "actions = ('0', '1', '2')\n",
    "# 0: left, 1: right\n",
    "states = ('0', '1')\n",
    "\n",
    "gamma = 0.95"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have all the required variables to instantiate an object of the `POMDP` class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "pomdp = POMDP(actions, t_prob, e_prob, rewards, states, gamma)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now find the utility function by running `pomdp_value_iteration` on our `pomdp` object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list,\n",
       "            {'0': [array([-83.05169196,  26.94830804])],\n",
       "             '1': [array([ 26.94830804, -83.05169196])],\n",
       "             '2': [array([23.55049363, -0.76359097]),\n",
       "              array([23.55049363, -0.76359097]),\n",
       "              array([23.55049363, -0.76359097]),\n",
       "              array([23.55049363, -0.76359097]),\n",
       "              array([23.24120177,  1.56028929]),\n",
       "              array([23.24120177,  1.56028929]),\n",
       "              array([23.24120177,  1.56028929]),\n",
       "              array([20.0874279 , 15.03900771]),\n",
       "              array([20.0874279 , 15.03900771]),\n",
       "              array([20.0874279 , 15.03900771]),\n",
       "              array([20.0874279 , 15.03900771]),\n",
       "              array([17.91696135, 17.91696135]),\n",
       "              array([17.91696135, 17.91696135]),\n",
       "              array([17.91696135, 17.91696135]),\n",
       "              array([17.91696135, 17.91696135]),\n",
       "              array([17.91696135, 17.91696135]),\n",
       "              array([15.03900771, 20.0874279 ]),\n",
       "              array([15.03900771, 20.0874279 ]),\n",
       "              array([15.03900771, 20.0874279 ]),\n",
       "              array([15.03900771, 20.0874279 ]),\n",
       "              array([ 1.56028929, 23.24120177]),\n",
       "              array([ 1.56028929, 23.24120177]),\n",
       "              array([ 1.56028929, 23.24120177]),\n",
       "              array([-0.76359097, 23.55049363]),\n",
       "              array([-0.76359097, 23.55049363]),\n",
       "              array([-0.76359097, 23.55049363]),\n",
       "              array([-0.76359097, 23.55049363])]})"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "utility = pomdp_value_iteration(pomdp, epsilon=3)\n",
    "utility"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "def plot_utility(utility):\n",
    "    open_left = utility['0'][0]\n",
    "    open_right = utility['1'][0]\n",
    "    listen_left = utility['2'][0]\n",
    "    listen_right = utility['2'][-1]\n",
    "    left = (open_left[0] - listen_left[0]) / (open_left[0] - listen_left[0] + listen_left[1] - open_left[1])\n",
    "    right = (open_right[0] - listen_right[0]) / (open_right[0] - listen_right[0] + listen_right[1] - open_right[1])\n",
    "    \n",
    "    colors = ['g', 'b', 'k']\n",
    "    for action in utility:\n",
    "        for value in utility[action]:\n",
    "            plt.plot(value, color=colors[int(action)])\n",
    "    plt.vlines([left, right], -10, 35, linestyles='dashed', colors='c')\n",
    "    plt.ylim(-10, 35)\n",
    "    plt.xlim(0, 1)\n",
    "    plt.text(left/2 - 0.35, 30, 'open-left')\n",
    "    plt.text((right + left)/2 - 0.04, 30, 'listen')\n",
    "    plt.text((right + 1)/2 + 0.22, 30, 'open-right')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAD8CAYAAACRkhiPAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAIABJREFUeJzsnXlcVNX7xz9nZthXWRSU1Q0UJBREQITUci/XMpc0yg03yi3zq4ZkmltuZWaWmfnT1EpLLS0zFTUVRRQXElkURUUUBVkHnt8fA8Q4wzZzZwHO+/WalzJz7znPXc793HOec56HERE4HA6H0zgR6doADofD4egOLgIcDofTiOEiwOFwOI0YLgIcDofTiOEiwOFwOI0YLgIcDofTiFFbBBhjxoyxs4yxeMbYFcbYorLvv2WMpTDGLpZ9fNU3l8PhcDhCIhGgjEIAPYgolzFmACCGMfZb2W+ziWiPAHVwOBwORwOoLQIkW22WW/anQdmHr0DjcDicegATYsUwY0wM4DyA1gA+J6L3GWPfAgiCrKdwBMBcIipUsu8EABMAwMzMzM/T01NtexoKiXl5AAAPU1MdW8Lh6Ae8TSjn/PnzD4nIXpV9BRGBisIYswbwM4BpALIA3ANgCGATgJtEFF3d/v7+/hQbGyuYPfWdF+PiAAB/d+yoY0s4HP2AtwnlMMbOE5G/KvsKOjuIiLIB/A2gDxFlkIxCAFsABAhZF4fD4XDUR22fAGPMHkAxEWUzxkwAvARgGWPMkYgyGGMMwCAACerW1diY7+qqaxM4HL2CtwnhEWJ2kCOArWV+ARGAXUS0nzH2V5lAMAAXAUwSoK5GxUs2Nro2gcPRK3ibEB4hZgddAqAwQEdEPdQtu7FzMScHAOBrYaFjSzgc/YC3CeERoifA0RDvJiUB4E4wDqcc3iaEh4eN4HA4nEYMFwEOh8NpxHAR4HA4nEYMFwEOh8NpxHDHsB6zpGVLXZvA4egVvE0IDxcBPSbYykrXJnA4egVvE8LDh4P0mFNPnuDUkye6NoPD0Rt4mxAe3hPQY+YlJwPgc6I5nHJ4mxAe3hPgcDicRgwXAQ6Hw2nEcBFQg7feegt79lSfPfP69evw9fVFx44dcf78eWzYsEFL1nGqw9zcHABw9+5dDBs2rMrtsrOz+TXjqMTGjRvx3XffVbvNt99+i6lTpyr9bcmSJZowSwEuAhpm7969GDhwIOLi4mBra8sfKHpG8+bNqxVyLgIcVZBKpZg0aRLGjBmjchlcBFTk008/hbe3N7y9vbFmzRqkpqbC09MTY8eOhY+PD4YNG4a8shR158+fR1hYGPz8/NC7d29kZGQAAF588UW8//77CAgIQNu2bXHixIka61VW1sGDB7FmzRps3rwZ3bt3x9y5c3Hz5k34+vpi9uzZNZa5pnVrrGndWr0TwqmW1NRUeHt7AwCuXLmCgIAA+Pr6wsfHBzdu3FB6zVasWIHOnTvDx8cHH374YUU57dq1w/jx4+Hl5YVevXohPz9fZ8fVUKlrm9Dm8+DFF1/EvHnzEBYWhrVr1yIqKgorV64EAJw7dw4+Pj4ICgrC7NmzK+45QNYb7dOnD9q0aYM5c+YAAObOnYv8/Hz4+vpi1KhRKp2rWkNEevPx8/MjdYiNjSVvb2/Kzc2lnJwcat++PV24cIEAUExMDBERhYeH04oVK6ioqIiCgoLowYMHRES0c+dOCg8PJyKisLAwmjFjBhERHThwgHr27Km0vrFjx9Lu3burLevDDz+kFStWEBFRSkoKeXl5qXWMHGEwMzMjIvlrMnXqVPr++++JiKiwsJDy8vIUrtmhQ4do/PjxVFpaSiUlJdS/f386duwYpaSkkFgspri4OCIieu2112jbtm1aPipOZbT9PAgLC6OIiIiKvyu3fS8vLzp58iQREb3//vsV99SWLVvI3d2dsrOzKT8/n1xcXOjWrVtE9N89WhsAxJKKz10hMosZAzgOwAiyKad7iOhDxpg7gJ0AbABcAPAmERWpW191xMTEYPDgwTAzMwMADBkyBCdOnICzszO6du0KABg9ejTWrVuHPn36ICEhAS+//DIAoKSkBI6OjhVlDRkyBADg5+eH1NTUautNTEystixV+fPRIwA8kYa2CAoKwscff4z09HQMGTIEbdq0Udjm8OHDOHz4MDqWTVHMzc3FjRs34OLiAnd3d/j6+gKo3X3DqTt1aRO6eB4MHz5c4bvs7Gzk5OQgODgYADBy5Ejs37+/4veePXvCqmwRXPv27ZGWlgZnZ+caj08ohFgnUAigBxHlMsYMAMQwxn4DMAPAaiLayRjbCOAdAF8IUF+VyARREVmGS/m/iQheXl44ffq00n2MjIwAAGKxGFKpFAAQHh6OuLg4NG/eHAcPHpSrt7qyVGVxWhoALgLaYuTIkejSpQsOHDiA3r17Y/PmzWj5XJgCIsIHH3yAiRMnyn2fmppacc8AsvuGDwcJT13ahC6eB+WCUxs7ni/7+fK1hdo+gbLeSG7ZnwZlHwLQA0C5x20rZHmGNUpoaCj27t2LvLw8PHv2DD///DO6deuGW7duVVzcHTt2ICQkBB4eHsjMzKz4vri4GFeuXKm2/C1btuDixYtyAgCg1mVZWFggpywzEkf/SE5ORsuWLTF9+nS8+uqruHTpksI16927N7755hvk5spu+Tt37uDBgwe6MplTDbp6HjxPkyZNYGFhgX/++QcAsHPnzlrZb2BggOLi4lptqw6COIYZY2LG2EUADwD8AeAmgGwiKpe0dAAthKirOjp16oS33noLAQEB6NKlC8aNG4cmTZqgXbt22Lp1K3x8fPDo0SNERETA0NAQe/bswfvvv48XXngBvr6+OHXqlEr11rYsW1tbdO3aFd7e3rVyDHO0yw8//ABvb2/4+vri+vXrGDNmjMI169WrF0aOHImgoCB06NABw4YN48Kup+jqeaCMr7/+GhMmTEBQUBCIqGL4pzomTJgAHx8fjTuGWU1dlToVxpg1gJ8BLASwhYhal33vDOAgEXVQss8EABMAwMXFxS+trLsnFKmpqRgwYAASEhIELVcbvBgXB4AvkedwylG3TejqeZCbm1uxNuWTTz5BRkYG1q5dK1j5jLHzROSvyr6CThElomwAfwMIBGDNGCv3OTgBuFvFPpuIyJ+I/O3t7YU0h8PhcPSCAwcOwNfXF97e3jhx4gTmz5+va5MqULsnwBizB1BMRNmMMRMAhwEsAzAWwI+VHMOXiKjaVTf+/v4UGxurlj0NicSy+csepqY6toTD0Q94m1COOj0BIWYHOQLYyhgTQ9az2EVE+xljVwHsZIwtBhAH4GsB6mpU8Budw5GHtwnhUVsEiOgSAIUBOiJKBhCgbvmNmV8fPgQAvGJnp2NLOBz9gLcJ4eH5BPSYVbdvA+A3PIdTDm8TwtPgYgdxOBwOp/ZwEeBwOJxGDBcBDofDacRwEeBwOJxGDHcM6zHb2rXTtQkcjl7B24TwcBHQY5yNjXVtAoejV/A2ITx8OEiP+eHBA/zAI1RyOBXwNiE8etUTuHdP1xboF1/cuQMAGN60qY4t4XD0A94mFPm/y/+n1v561RO4cweoRTpfDofD4QC4m3MXEQci1CpDr0TA0BCYMAEoLNS1JRwOh6P/RP4eiUKpeg9MvRIBFxfg+nVg2TJdW8LhcDj6zf5/92PP1T1YGLZQrXL0SgSsrIA33gA+/hhITNS1NRwOh6Of5BblYvKByfCy98Ks4FlqlaVXjmEAWLMG+P13YOJE4OhR4Lmc0I2KPV5eujaBw9EreJuQseCvBbj99DZOvn0ShmJDtcrSq54AADRrBixfDhw7BmzZomtrdIudoSHsDNW7wBxOQ4K3CeD83fNYd3YdJvlNQrBzsNrl6Z0IAMA77wDdugGzZgGNeUrwtxkZ+DYjQ9dmcDh6Q2NvE9JSKcb/Oh7NzJph6UtLBSlTbRFgjDkzxo4yxq4xxq4wxiLLvo9ijN1hjF0s+/SrtVEi4MsvgdxcYMYMdS2sv3x77x6+5YsnOJwKGnubWHdmHeLuxWFd33WwNrYWpEwhegJSADOJqB1kCeanMMbal/22moh8yz4H61Jou3bABx8A27cDhw4JYCWHw+HUY1KzU7Hg6AIMaDsAQ9sNFaxctUWAiDKI6ELZ/3MAXAPQQt1yAZkItG0LREQAZfmlORwOp9FBRJhycAoYGD7v9zmYgDNmBPUJMMbcIMs3fKbsq6mMsUuMsW8YY02q2GcCYyyWMRabmZkp95uxMbBpE5CSAkRHC2kph8Ph1B92X92NgzcOYnGPxXCxchG0bMFEgDFmDuBHAO8S0VMAXwBoBcAXQAaAVcr2I6JNRORPRP729vYKv4eFAW+/DaxcCVy6JJS1HA6HUz94nP8Y03+bDj9HP0wLmCZ4+YyI1C+EMQMA+wEcIqJPlfzuBmA/EXlXV46/vz/FxsYqfP/oEeDpCbi7A6dOAWKx2ibXC/JKSgAApo3lgDmcGmiMbWLirxOxOW4zzo0/h06OnZRuwxg7T0T+qpQvxOwgBuBrANcqCwBjzLHSZoMBJKhah40NsHo1cPYs8MUXqtta3zAVixvVzc7h1ERjaxMxt2Kw6cImvNvl3SoFQF3U7gkwxkIAnABwGUBp2dfzAIyAbCiIAKQCmEhE1U7wraonAABEQJ8+wOnTwLVrQAtBXM/6zYaysLmTG8PBcji1oDG1iaKSInT8siOeFT1DwuQEmBuaV7mtOj0BtcNGEFEMAGWu6jpNCQWA/Pz8Kn9jTNYL8PYGpk0DfvqprqXXP3aVrZRrDDc8h1MbGlObWH5yOa5mXsWBkQeqFYCHDx+qVY9erRi+evUqJBIJunbtintKFoS0bAl8+CHw88/A3r06MJDD4XC0wL9Z/2Lx8cV43et19GujuM62oKAAw4cPh7GxMZRNqKkLeiUCAFBSUoJTp07B0dERhoaGGDx4MHJzcyt+nzED8PEBpk4Fnj7VoaEcDoejAYgIk/ZPgrHEGGv7rK34XiqV4t1334W5uTlMTEywa9cuFAqQfEXvRKAyxcXF2Lt3LywsLGBqaoqIiAgwJsVXXwF37wLz5+vaQg6HwxGWrfFbcTT1KJa/vBwO5g5Ys2YNbG1tYWBggLVr1+LZs2eC1qdXIuDp6YnQ0FAYGRkp/Jafn4+NGzfCwMAAvXs3QUDAx/jsM9mMIQ6Hw2kIZD7LxMzDM+Fp6omoV6PAGMN7772HR48eKWwrkUjQoUMH7Nq1S606BVknIBSVZwfdunULM2bMwOHDh5GTk1PlPmJxM3z11XKEh4/RlpkcDocjOKdPn0bvL3sjxyUH2AggU3EbIyMjdOnSBcuWLUNgYGDF9zpdJ6ApXFxcsGfPHjx9+hQ5OTmYOnUq7OzsFLYrKbmPt98eC5FIhFatWuH48eM6sJbD4XDqTmpqKgICAiAWixE8Ohg57jlADOQEwMLCAkOHDkVaWhoKCgpw7NgxOQFQF70VgcqYm5tj/fr1yMzMhFQqxSeffAJXV1e5IEpEhOTkZISFhYExBl9fXyTW8xyVK2/dwspbt3RtBoejNzSENpGdnY0+ffrAwMAA7u7uOHfuHEpFpcAAAFkATgB2dnaYOnUqcnJy8PTpU+zZswcuLsLGDCqnXohAZcRiMd5//32kpqaitLQUn322E4x5A5BfRRgfHw9PT08wxtCjRw+159Lqgv1ZWdiflaVrMzgcvaG+tgmpVIoxY8bAxMQETZo0waFDhyCVSv/bIAyADTDeYTykBVJkZmZi/fr1MDeven2AUNQ7EXieKVOGY+3aywCkWLToNEJCQmD4XPq5o0ePwt7eHgYGBhg+fDgKCgp0YyyHw2lU/O9//4OlpSUMDAywbds2hWePt7c3ln+7HJIwCd7yfQub5m2CWMthMeq9CADA5MlAQADw2WeB2LfvBAoLC5GcnIxBgwbBzMysYjupVIpdu3bBxMQEJiYmmDlzprwaczgcjpps2rQJtra2YIxhyZIlchNbxGIxQkJCcPr0aRAR4i/F4yfpT7A2tsbKl1fqxN4GIQJiMfDVV7Joo3PmyL5zd3fHzz//jNzcXGRnZyMiIgLW1v+lYysoKMCnn34KAwODCp8Dh8PhqMLvv/8OBwcHMMYwceJEuSmdRkZGGDRoEJKTkyGVSnHixIkKx+7G2I34J/0frO69GramtjqxvUGIACBbRTxzJvD118CxY/K/WVlZYcOGDXj8+DGkUik++ugjuZlGz549w/Tp08EYg4WFBXbv3q1l65VjIhbDpBFFTORwakKf2sSlS5fg7OwMxhj69u2L+/fvV/xWvrg1OzsbBQUF+Pnnn+Hu7i63/52nd/DBkQ/wcsuXMarDKG2b/x9EpDcfPz8/Uodnz4jc3Yk8PIgKCmq3z7Zt28jBwYEgi3Yq97G0tKQ//vhDLZs4HE7DIT09nVxdXZU+L8zMzOjDDz8kqVRaq7KG/DCEjBcbU1JWktp2AYglFZ+7DaYnAACmprJIo4mJwNKltdtn9OjRyMjIABHh2LFjaFEpOuHTp0/x8ssvgzGGJk2a4OTJkxqynMPh6Cv37t2Du7s7GGNwcnJCWlpaxW8WFhb46quvQETIzc1FVFRUrRy7vyT+gp+u/YSFoQvRyqaVJs2vGVXVQxMfdXsC5YwcSWRoSHTtmuplXL9+nZycnJQqvrW1NR0+fFgQW6sjOiWFolNSNF4Ph1Nf0FabuHnzJrm5uVU5QrBv3z6Vy35a8JScPnUi7w3eVCQtEsRe6LInwBhzZowdZYxdY4xdYYxFln1vwxj7gzF2o+xfpYnmNcHq1YCZGTBhAlBaWvP2yvDw8MDt27dBREhNTYWTk1PFb9nZ2ejVq1dFD2Hnzp0CWS7PkcePceTxY42UzeHURzTZJs6ePQs3NzcwxtCqVSukpqZW/GZpaYnDhw+DiPDkyRO8+uqrKtez4OgC3Hl6B1+98hUMxAYCWK4eQgwHSQHMJKJ2AAIBTGGMtQcwF8ARImoD4EjZ39Vy/fp1DBs2DPPmzcPOnTuV5hSoDU2bAitWACdOAN98o1IRcri6ulYIwvXr1+Ho+F/mzOzsbIwYMQKMMVhbW2P58uUoKcuDyuFw9Jvdu3fDyckJjDF06dJFYajnl19+qXjwv/zyy2rXd+7OOaw7sw4R/hEIdFIt9EN2djb27duHRYsWYcSIEejWrZtaNgkeQI4xtg/AZ2WfF4kooyzf8N9E5FHDvtUawxiDSCSCRCKBkZERTE1NYWVlhWbNmsHZ2Rnt2rVDQEAAgoKCYGZmju7dgfh44Pp1oFkz4Y6xnNOnT2Pw4MFyswLKMTc3x1tvvYWlS5eqvOrvxbg4AMDfHTuqZSeH01BQt02UlJRgzZo1WLFihdJ2a2Zmhs8//xxjx45Vy05lSEul6PxVZ9zPvY9rU67BCEaIjY3FmTNncOXKFdy6dQv37t3D48eP8ezZMxQWFqK4uBilpaWoxXNa5QBygooAY8wNwHEA3gBuEZF1pd8eE5HCkBBjbAKACQBgbm7u161bN9y7dw9ZWVnIyclBQUEBiouLUVJSUpsTUZVlEItFMDAwgLGxMczMzGBjYwNHR0e4urqiQ4cOCAwMRMeOHSGRqJZxc8+ePQrzg8sxMTFB//79sWbNGjnHc01wEeBw5FGlTeTn52Pu3Ln4/vvvq2yf//vf//C///1PJZukUikSExNx8uRJXL58GcnJycjIyEBWVhZyc3ORn5+P4uJiSAOkQC8APwC4Vrc6yl+An3+GNWvWDO7u7vjqq690LwKMMXMAxwB8TEQ/McayayMClaku0fzzFBQU4OzZszhz5gyuXbuG1NRU3L9/H9nZ2cjNzUVhYSGkUilKSkoh8+fUHZFIBLFYXHHiLS0tYWNjAycnJ7i7u8PX1xchISFo3bq13H6rVq3CRx99hCdPniiUaWhoiKCgICxfvhwBAQHV1j80IQEA8KO3t0r2czgNjdq2iTt37uDdd9/FwYMHkZeXp/C7kZERwsPDsX79erkXv3v37uHvv//GpUuX8O+//+L27dvIysrCkydPkJ+fj6KiIpSUlKC0rs5GawCTASQDot0iSMSy0QwzMzNYWlqiWbNmcHFxgYeHBzp37oyQkJA6jSCoE0paEBFgjBkA2A/gEBF9WvZdIuo4HFQXEagthYWAry9QUAAkJAD5+Q9x8uRJnD9/Hjdu3MCtW7eQmZmJJ0+eIC8vD0VFRZBKpRWe87rCGANjDBKJBAYGBigtLUV+fr7SbcViMby8vLBw4UIMHTpU3UPlcBo158+fx+zZs3HixIkqw8EYGBhAIpGgtLQUUqm0tkMtSil/STQ0NISJiQksLS1hZ2cHZ2dntGrVCh07dkRISAhatGiBfv/XDzG3YnB18lU4Wzmrc5hK0akIMFk8560AHhHRu5W+XwEgi4g+YYzNBWBDRHOqK0sTIgAAx48DYWHA7NnA8uWqlZGUlIRTp04hPj4eSUlJuHv3Lh4+fIicnJyK7p5KbwjPIZFIYGpqCjMzMzRp0gT29vZwc3ODl5cX/Pz8EBwcDGNjY7Xq4HDqC1KpFHFxcfjnn39w+fJlpKWlISMjA48ePcKzZ8/w7NkzFBcXq1UHY0yux29hYQFbW1s4ODigVatWFcPF7du3V2m4eGfCToz4cQTW9F6DyMBItWytCl2LQAiAEwAuAyh/As4DcAbALgAuAG4BeI2IFAfkKqEpEQCA8eOBLVuA2FhZz0AblN/AZ8+eRUJCApKTk3Hv3j08fPgQ9+/fF2QW0fM3sLm5OWxsbNC8eXO4ubnBx8cHwcHBKt/AHI5QJCUlISYmBhcvXkRKSgrS09PlfH9FRUUoLS1V+0UKQMX0bUdHRzRt2rTiRapz584ICAjQ2ovU4/zH8PzcEy5WLvjnnX8gFmkm5IXOh4OEQpMi8Pgx4OkJuLoCp0/Lgs7pA1euXMGoUaNw+fLlKm9+kUgEMzMzGBsbo7CwsMLfIWRX1sLCAnZ2dnBycqroyoaGhsqtj+BwAODhw4c4fvw4Ll68iMTERNy+fRsPHz5EdnZ2xbi5UEOqhoaGMDIyQklJCXJzc6uN+uvi4oLPP/8cAwYMUOfwBGXCrxPwTdw3iJ0QC18Hzb19chGoJTt2ACNHAmvXAtOna6walfnrr78wbtw4pKamVtl4jI2NERwcjFWrVsH3uS7NvXv3EBMTgwsXLuDGjRtIT0/Hw4cP5fwd6gxZlc9QKBcPMzMzWFlZoWnTpnBxcUHbtm3h5+eHkJAQuYitHP2koKAAp06dwvnz53HlyhWkpqYiMzNTboqiUC8bBgYGCi8bLVu2xAsvvIDg4GCFyRX37t3Du+++i99++w1Pnz6tsnw7Ozt89NFHmDRpkkr2aZITaScQ+m0oZgXNwopeKzRaFxeBWkIE9OsHxMQAV68CzsL7ZwTju+++wzvvvQepkilt5UgkEnh7e2PRokUqr2CUSqW4efMmYmJicOnSJSQnJ1f4OypPb1Nnim7l6W3lMyLKp7e5ubnB29sb/v7+CAwM5ENWKiCVSnH16lWcOnUKly5dQmpqKu7evYtHjx4hNzdXkGnWz09RLB92dHBwQMuWLeHt7Y2AgAC1pllfvHgRM2fOxKlTp6pN/CQyNcX7kZFYsmSJSvVog0JpIXy/9EV+cT6uTL4CM0OzmndSAy4CdSAlBfDyAnr1Avbu1WhValM+J7rn/v1YtWqV0imn5YhEIri5uWHatGmYNm2axrMTFRQUIC4uDmfOnEFCQgLS0tJw7949PHr0CHl5eRUPHnXeIiv7O0xMTGBubg47Ozs4ODigdevW8PHxQWBgIDw8PBqMeKSnp+P48eOIi4vDzZs3K3pz5RMQhOrNVV5wWT4BwdXVFe3bt4efnx+CgoK0ktpw//79WLhwIS5fvlztUI+xsTFee+01JE+bBolEovdrZ6KPRePDvz/EwZEH0bdNX43X12BEoKYVwxwOh6P32AKIgGxB2I9aq1VlEWhQoaQ5HA5H57wCoBjA77o2pHbolQj4+flpLWz12bMExghTpug+hLa6n9u3byMoKEhhCKi8218ZY2Nj9OzZE/Hx8Tq3W9Of4uJixMfH44svvsCkSZMqFu6Ym5tDLBZDtsRFeMpntpiamsLBwQEBAQEIDw/H6tWrcerUKeTn5+v83Gj6k5GRgZEjR8LKykrpuXn+u7Zt2+LUqVM6t1vdz9cXvgbcgE2vbQLlaq9ete5XdQsQEm34BCoTGQmsXw+cOgUEqhbQT6O8e+MGAGBNmza13ufChQt48803ce3aNbmbo3ylZOXVyxKJBD4+Pli0aJFeTaurCWWzoDIzM/H06VPBZkEp+xBRhY9D3bns1YUkad26NTp06KA0JIk+c+nSJcycORMnT56Uu88MDAwgFosVnL3NmzfH2rVrMWzYsFrXoUqb0BYPnj2A52ee8G7qjb/f+hsipr137AbjE9C2COTkAO3bA02aAOfPAwa6D+0th7oB5Pbv34/Jkyfj9u3bct+bmZnB0NAQjyvFZReJRGjZsiUiIyMRERGhcccyAOTm5uL06dM4e/YsEhMTkZaWhvv371dMadXEeghLS0vY2trCyckJbdq0qZii6ObmpvbxPHz4X0iSxMTECnHS1Px5ExMTWFtbw97eHk5OTvDw8ICfnx+6du0ql0Nbkxw8eBALFizApUuX5By75b2tp0+fyh2rjY0N5s2bh5kzZ6pUnz4HVRz902jsurIL8ZPi0c6+nVbr5iKgBvv2AYMGydJRzq0x44F2EfKG37hxIxYsWICHDx9WfMcYg52dHYyMjHD37l25t1sHBwe8+eabWLx4MQwNDastu6qV0c9PURRqplBDWxldvpL28uXLciFJnj59Kje9U6gZQeUhScqDlnl5eaFLly61WklbUlKCTZs24dNPP0VycrKcTfb29jA0NMS9e/fkVsObmZlh3LhxWLlypdrXRl9F4FDSIfTZ3gcLQxdiUfdFWq+fi4CaDB0KHDwoCzDXSsfpPiujqRv+/fffx4YNG5Cbm1vxnUgkQquyg09KSpJ7WDPGKrr0ssis+vFAasxUjqlz9erVivDFjx8/Flx4RSIRGGMV5VX+3dHREba2trh+/bpcDB8jIyMMHDgQW7duFfQ66qMI5BXnwXvenOb2AAAgAElEQVSDNwzEBoifFA9jifbvW3VEoH69MmmIdeuAP/4AIiKAQ4cADfkLtUp2djaOHTtWbbRUkUhU0ahLS0txo2y89XmICEVFRQrflz/MKw9NlEdR9PDwgK+vL0JDQ7U2NNGYkEgk6Ny5Mzp37lyn/Wo7BFe+sKy6uftEhLt37+Lu3bsKv5WWluLAgQNwdnZWOgTXkEKSRB+LRkp2Cv4e+7dOBEBdeE+gjM8/B6ZOBb7/Hhg1SicmKDAhMRHSggK89eRJjXkT1B03LxeE59/wRSIROnXqBAcHB5w4cUJuwZqBgQF8fHwQHR2Nfv36qXWsHN2TkJCAWbNm4fjx43KOXRMTE/j7+8PMzAxHjx5FYWGh3H7ls6wYYxoLSeLp6YmOHTtil709jK2tscmj2qj0WuPS/Uvo9GUnjH1hLL4e+LXO7ODDQQJQUgJ07QrcvClLR2lrK2z55Uv7y0Pi3rx5U/AMalVlH6prBrWkpCSMGDECFy5ckGvUlpaWiIiIQGlpKbZt2yaXA7p8OGnmzJmYOHGiSvZztM+hQ4cwf/58xMfHyw3nWFlZ4ZVXXkFwcDCio6PlrjVjDG5ubti8eTN69OhRZdnlGbf++ecfXLp0CUlJSRVRdDURksTY2BimpqYV4SxcXV01GpKkpLQEwd8EI+VxCq5PvQ4bExtBy68LXAQE4tIlwM8PePPN6hPUp6enIyYmBnFxcbhx4wbu3LlT4cjT1NL+qnIpa3ppf0xMDN5++20FP4G9vT0WL16MoqIirF27VsFJ6OjoiLFjx2LRokU1OpY52uXLL7/EqlWrcPPmTaWTAXr27InJkycjJSVF7po3a9YMy5cvx5gxYzRqX0FBAWJjYxEbG4uEhISK3m95DoE65t5VSlUhSZo3b46WLVvCx8cHISEhaNWqVZXi8dnZzzDtt2n4fvD3GOWj2+EDLgIqkpubi5iYGJw7dw6JiYm4desWrly5j0ePnsLU9Bmk0sKKh7lQUxStrKxga2sLZ2dntG3btuJmUzY+OiExEQD0puu7Z88eREZGKowBu7i44Msvv4RUKlUaB8ba2hqvvvoqVq9eDRsb3b0tNVaKioqwaNEifPvtt3LXrvK04B49emD06NGIj4+XEwYrKyvMnDkTCxYs0IXpClTXJrKzsytezq5fv45bt27hwYMHePLkCZ49eyb3cqZue5bYSFDwTgGMHxrD55IPnJ2c0aZNG3Tq1AkhISFwcHBQ6zjris5FgDH2DYABAB4QkXfZd1EAxgPILNtsHhEdrK4cVUVAKpXi3LlzOHPmDK5evYqUlBTcu3evIiSupoKZ2drawtHREa1bt4aXlxe6du0qaDAzfZwJUc6qVavw8ccfy601YIzBy8sL27dvR2lpKWbNmoWTJ0/KLRIyNTVFaGgoPv30U7Rrp9251I2JR48eYcaMGfjll1/krpFEIkGHDh0QHR2NwMBAvP766zh+/LjclE4TExOMHj0aGzZs0LvptppoE6mpqTh16lTdgvYNB9AawAYAj6souIyagvZ5eHio3bPXBxEIBZAL4LvnRCCXiFbWthx/f3/avn17xZzpmzdv4u7duwrZh4QOa9ykSRM4ODhUTFEUibpgxgx/LFhgjOholaoRBH0WgXKkUilmzZqFzZs349mzZxXfi8ViBAUFYffu3QCAGTNm4ODBgwqOZV9fX3z88cd4+eWXtW57Q+PatWuYMWMGjh8/Lpdc3djYGF27dsXKlSvh6emJ8PBw/Pzzz3IOXgMDA/Tt2xfbt2/XSvRQVdGHNrH3+l4M/mEwIr0i4fnQUy/CdxsYGKgsAkLGrnADkFDp7ygAs+pYBtX2wxgjkUhEhoaGZG5uTk2bNqW2bdtSSEgIvfHGGxQVFUW//vorPX78mFRh9GgiAwOiK1dU2l0Qwi5coLALF3RnQB3Jz8+nYcOGkaGhody1MjQ0pMGDB1N+fj7l5eXRe++9R82aNZPbRiQSUdu2bWnz5s26Pox6xZEjRyggIEDhnFtZWdGIESMoIyODiouLacaMGWRmZia3jVgspqCgILp9+7auD6PW6LpNPCl4Qi1WtSCfL3yoSFpU5/3z8/PpyJEjtHz5cho7dix1796d2rdvT46OjmRpaUlGRkYkFoupLKJyXT6xpOqzW9UdFQpSLgKpAC4B+AZAkyr2mwAgFkAsY4xsbW3J3d2d/P39adCgQTRr1izaunUrpaSk1PmEq8ODB0Q2NkQhIUQlJVqtugJd3/DqkJmZSWFhYSQWi+VuVlNTU4qIiKDi4mKSSqW0evVqatmyJYlEIrntWrRoQfPnz6fCwkJdH4resXnzZvLw8FA4Z82aNaP33nuP8vLyiIho3bp1ZGNjo/Dy1L59ezp//ryOj0I1dN0mph2cRiyK0T+3/9FqvZmZmfTjjz/SggUL6PXXX6egoCBq06YN2dvbk7m5ud6KQDMAYsgilX4M4JuayvDz89PUOVSJb76RnaFNm3RTf+S//1Lkv//qpnIBSUhIIB8fH4W3G2tra1q6dGnFdj/99BP5+vqSRCKR265JkyYUHh5OWVlZOjwK3VFYWEgLFy6kFi1aKPSeWrZsSatXryapVEpERD/++CM1b95c4U3R2dmZfv31Vx0fifrosk2cST9DLIrR1ANTdVJ/deilCNT2t8offROB0lKiF18ksrIiysjQtTUNgyNHjpC7u7uCIDg4OND27dsrtouNjaXu3buTsbGxQk+iX79+lJiYqMOj0DxZWVn09ttvK7zJSyQS8vX1pZ9++qli27Nnz1Lbtm0VzqmdnR198cUXOjyKhkORtIh8vvChFqta0JOCJ7o2RwG9FAEAjpX+/x6AnTWVoW8iQESUmEhkZEQ0fLiuLWl4bNmyhZo2baowXNGqVSs6duxYxXbp6en0+uuvk6WlpYKvITAwkI4cOaLDoxCOxMRE6t+/P5mamsodp7GxMXXv3p1iY2Mrtk1JSaHOnTsrDAmZm5vTnDlzdHgUDZNlMcsIUaCfrv5U88Y6QOciAGAHgAzI8umkA3gHwDYAl8t8Ar9UFoWqPvooAkRE0dGyM3XwoHbrHXXlCo3SpWdai0RHR5OVlZXCcEfHjh3p+vXrFdvl5eVRZGSkgniIRCLy9PSkLVu26O4gVODo0aMUGBio4Ni1tLSk119/ndLT0yu2zcnJob59+5KBgYGCSLz55ptUXFyswyPRDrpoE8mPkslksQkN2jlIq/XWBZ2LgFAffRWBwkKidu2IXF2JcnO1V6+unWC6oLi4mMaPH08mJiYKwyA9e/akzMzMim2lUimtXLmS3Nzc5IZCGGPUokULWrhwYcVYuT6xdetW8vT0VHCaN23alCIjIyscu0Sy8zF27FiFYTGJREK9evVSefZbfUXbbaK0tJR6b+tNFkss6PYT/Z1FxUVAC5w4ITtbM2dqr87GKAKVycnJoQEDBii8+RoZGdEbb7xB+fn5ctvv2bOHfHx8FBzLNjY2NG7cOMrOztbJcUilUoqKiiInJycFsXJzc6OVK1cqiNWCBQsUhr9EIhH5+/vTjRs3dHIc+oC228T2S9sJUaB1/6zTWp2qwEVAS0yYQCQWE2nrHmzsIlCZ27dvU1BQkMLbs7m5Oc2aNUth+zNnzlBYWBgZGRnJbW9mZkYDBgygpKQkjdqbnZ1N48aNU+rY9fHxoT179ijss3nzZrK3t1fwkbRt25ZOnTqlUXvrC9psE1l5WWS/3J4CvgogaYn+9Sgrw0VASzx6RNSsGZG/P5E2Rhm4CCjn/Pnz1K5dO4XZMDY2NrRuneIbW1paGg0bNowsLCwUHMvBwcFyTmh1SEpKoldffVVhUZaRkRGFhYXRmTNnFPb57bffyMXFRWFKZ/PmzWn37t2C2NWQ0GabeGffOyReJKaLGRe1Up86cBHQIjt3ys7amjWar2vuzZs09+ZNzVdUj/n111/J2dlZ4SHaokUL2rt3r8L2OTk5NHXqVIU3brFYTO3ataNt27bVqf5jx45RcHCwgmPXwsKChg0bRmlpaQr7xMfHk7e3t4KINWnShFauXKnyuWgMaKtN/J3yNyEKNOdw/ZhpxUVAi5SWEvXtS2RmRqSkfXN0yGeffUa2trZKh1POnj2rsL1UKqVly5YpdSw7OztTdHS0Usfytm3bqF27dgpDU/b29jR16lTKyclR2CcjI4NCQkIU9jEzM6PIyMhGMbOnvlBQXEAe6z3IfY07PSt6pmtzagUXAS2TkkJkakr0yisyUeDoH3PmzClfTi/nWA0ICKgyBMmuXbvI29tb4UFtbW1N/v7+1KJFC6WO3WXLlikVi/z8fBo8eLDSWErDhg1TcGxz9IMPj35IiAL9fuN3XZtSa7gI6ICVK2VnT4l/TzCGXL5MQy5f1lwFjYDi4mJ68803FaZYGhgYUN++fZW+tRMR/fHHH+Tg4KAwzFQ+1LN+/foq64uIiFBY8CUWiyksLExuiiun7mi6TVzLvEaGHxnSyB9HaqwOTcBFQAcUFxN17Ejk6EikqZmH3DEsLI8fP6ZevXopTCE1Njam8PBwunHjBg0cOFChB2FoaEi2trYKaxcMDQ2pa9euFBMTQ0uXLiVra2uFoSgfHx9KSEjQ9aE3GDTZJkpKS6jbN92oySdN6H7ufY3UoSm4COiIc+eIRCKiiAjNlM9FQHPcuHGD/P39lb7pl7/tDxkyhJKTk+X2y8nJoYiICLKzs6tyX3d39wYTykLf0GSb+Or8V4Qo0Obz9S+cuToiIAJHZfz9genTgY0bgdOndW0Np7b88MMPGDx4MOLKEpQoIycnBydOnMBff/0l9/2FCxdw+PBhZGVlVblvamoqwsPDsXTpUrmMXRz95X7ufcz+YzZCXUPxdse3dW2OVuEioCYffQQ4OQETJgDFxbq2hqOMkpISLFu2DK6urhCJRHjjjTeQkJCA0tJSuLi4YMmSJZBKpSAi7NixA46OjgCAzMxMjBs3DowxGBoaQiQSISwsDDdv3gQRwcrKCtHR0RVvVNu3b4e3tzdEIhFu3bqFefPmQSKRwN7eHpMnT0Zubq6OzwSnKt479B7yivPw5YAvwRjTtTnaRdUuhCY+9W04qJxffpENrC1ZImy50SkpFK3lZDoNhZycHJoyZYrCsI1YLCZvb2+5sNXKyMzMpFatWikd7rG2tq4xKUtMTAx17dpV6fqBIUOGKF0/wKkZTbSJ3278RogCRR2NErRcbQLuE9A9w4bJQk434rAuOictLY2GDBmidGVwuQO3OvLz8+mNN95QCDVhYGBAbm5uCt+LxWLq1q0bZdSQbCIpKUmpw9nIyIi6detGp0+fFvI0cOpAbmEuua1xI8/PPKmguEDX5qgMFwE94M4dIktLop49+doBbXL69Gnq1q2bwgPa3NycBg4cWKsYQbNmzVJ4QFeVf7c2eZSrIzs7myZOnKiwqK28h7Jr1y61zgenbsw+PJsQBTqWKkzoEF3BRUBP2LBBdka/+06Y8vrEx1Of+HhhCmtA7Nq1izp06KAw1dPW1pYmTpxYq2ihVeXfbdeuXa3z72ZkZFBoaKjSPMpTp06tcRWwVCql6OhocnZ2rtMitMaMkG0iLiOOxIvENG7fOEHK0yU6FwHIEsk/gHxmMRsAfwC4Ufav0kTzlT/1XQRKSoiCgojs7IiEWBPEp4jKUDW8w/Ps3btXIU8vIEz+3drmUa6OrVu31jkcRWNDqDYhLZFS502dqemKpvQo75EAlukWfRCBUACdnhOB5QDmlv1/LoBlNZVT30WAiOjyZSKJhGjsWPXLaswiUFOgt61bt9aqHF3k3z18+DC5ubkpiI2DgwPt2LGjVmUcPXq0ysB0Q4cObbSOZaHaxNp/1hKiQP936f8EsEr36FwEZDYo5BhORFlKSQCOABJrKqMhiAAR0bx5sjOr7nqhxiYC6enpNGzYMKW5hIODg+no0aO1KiclJYUCAgL0Iv9ubfMoV4cqIaobKkK0iVvZt8h8iTn13tabShuIA09fRSD7ud8fV7HfBACxAGJdXFw0dY60Sl4eUevWRG3aEKkTI6wxiEBsbGyVyV9effXVWid/qQ/5d6OiopRmC+vUqVOts4WpkqymISFEmxi4YyCZLDah5EfJNW9cT6jXIlD501B6AkREf/4pO7vz56texoq0NFrRALv9QqWBLC4upvDw8HqXf7e4uJjeeeedKvMo19ZuVdJW1nfUbRM/Xf2JEAVaHrNcQKt0j76KQKMdDipnzBiZf6Cxxw+TSqW0atUqcnd3V3hYOTk5UVRUVJ0eVg0p/251eZRHjhxZpx7Mli1byNPTU2EYTFkC+8ZIdn42NV/VnF744gUqkhbp2hxB0VcRWPGcY3h5TWU0NBHIzCSytSUKDpbNHGpM5OXlUWRkpMJ4uEgkIk9PT9qyZUudyqsq/26bNm3oxIkTmjkILVPXPMrVceTIEQoMDFRwLFtaWtLrr79O6enpGjoK/WXKgSnEohidSW94PhSdiwCAHQAyABQDSAfwDgBbAEcgmyJ6BIBNTeU0NBEgIvr2W9lZ3rix7vvWN59Aeno6vf7660odu4GBgXWOrHn48GFydXVVmGXj6OhY61k29ZXq8ih/9tlndSorMTGR+vfvr5DjwNjYmLp3705xcXEaOgrhUbVNnL59mlgUo+kHp2vAKt2jcxEQ6tMQRaC0lKhHDyIrK6K7d+u2b30Qgbi4OOrRo4fCuLypqSn179+fEhMT61Redfl3ly9vWOO4taWueZSrIysri8LDw6lJkyYK/ghfX1/at2+fho5CGFRpE0XSIuqwoQM5fepETwueasgy3cJFQM/5919ZXKHXXqvbfvoqAvv27SNfX18Fx26TJk0oPDycsrKy6lReRkYGdevWTWn+3enTp+vFzB59oao8yh4eHkrzKFdHYWEhzZ8/X2EBnUgkopYtW9Lq1av1zrGsSptYemIpIQq091rdBLM+wUWgHrB4sexs799f+330RQSkUimtW7eOWrZsqeB0bNGiBc2fP58KCwvrVCbPv6s+yvIoi8XiavMoV8emTZvIw8ND4Ro3a9aMZs6cqReO5bq2iaSsJDJebEyDdw7WoFW6h4tAPaCwkMjLi8jFhai2q/91KQJ5eXk0c+ZMatasmcJbooeHB23atKnOZRYXF9PUqVOV5t8NDQ2tMRonRznFxcU0atQopXmU+/Xrp1K4icOHD1Pnzp0VZi1ZWVnRiBEjdHat6tImSktL6eXvXiaLJRaU/qRhO8K5CNQTYmJkZ3zGjNpt/3l6On2uxVkcGRkZNGLECLKyslJ4mHTu3JkOHz6sUrk8/672qCqPsomJCYWHh6s0tHb16lXq06ePUsdyz549tepYrkub+D7+e0IU6LMzdXOk10e4CNQjJk2S5SWOjdW1JTLi4+OpZ8+eSh27ffr0oatXr6pU7o4dO8jBwUHBmenm5qaymHDqxo0bN6hTp04KwzuWlpa0YMEClcp88OABjR07VqljuWPHjmoH4hOKh88ekt1yO+ryVReSluiXX0MTcBGoRzx+TOTgQNSpE1FNL2XPpFJ6pgHH3K+//kqdOnVS6tgdO3YsPXjwQKVyjx07Rq1atVKY2dO0adM6rwvgCMuJEyeodevWCtfG3t6eNm9WLbF6YWEhzZ07lxwdHRWGDFu3bk3r168X3LFc2zYRvjecJNESir/XOEKxcxGoZ+zaJTvzn35a/XaChc2VSmn9+vXUunVrhbdCR0dHmjt3bp0du+VU97YZFRWltu0c4dmxY4fCgxsAubq6qtVL27hxI7Vp00bhXnBwcKDZs2erfI9VpjZt4mjKUUIUaO4fc9Wur77ARaCeUVpK1L8/kZkZUWpq1dupIwKFhYU0e/ZshSEZkUhEbdq0oY2qrF4r4/Hjx9SzZ0+l487jx4/nUzrrEcuXL1fqr+nQoYNa/prff/+d/P39lTqWR48erXJvs6Y2kV+cT23Xt6WWa1tSXpHuZzNpCy4C9ZDUVJkI9O9fdTrKuorAgwcPaPTo0QqN2sDAgPz9/en3339X2d7i4mIaOXKk0vy7AwYM4AlP6jnFxcU0ffp0hXDVtc2jXB2XL1+m3r17KwTMMzExoV69etHly5drXVZNbWLBXwsIUaDDSY3L78RFoJ7y6aeyK1BVWtnaiMDly5epV69eShtY796969TAlFGX/LuchkF+fj4NHTpU6RqOoUOHqrWGo7oXFT8/Pzpw4EC1+1fXJq48uEIG0QY06sdRKttXX+EiUE8pLpY5iB0cZA7j56nqhj9w4AD5+fkpdLWtra3V6mqXI0T+XU7DQN08ytVRWFhIc+bMUepYrmrIsqo2UVJaQiHfhJDNMhu6n3tfZZvqK1wE6jHnz8umjE6apPjblrt3aUtZwKGqnG6Ojo40Z84ctZ1umsy/y2kYJCQkUIcOHZTmUVY3rpNUKqUNGzbUOHmhcpuozKbYTYQo0DcXvlHLjvoKF4F6zowZsisRE/PfdzVNv9uwYYPa0+/Onj1LHh4eCo3a1ta2zpEqOY0LIfIoV0dV05itra1pzJgxcr3djJwMslpqRS9++2KDSRdZV7gI1HNycmThJDw8smjUqDEK46USiYQ6deokyBu5PuXf5TQMqsr10Lp1a0FyPcTHx9NLL71Upd+r79d9yfAjQ7qeeV2Ao6mfcBGox5QvyTcyMlW4wa27dCG/nTvVriMnJ4f69eunNP/uqFGj+JROjmAIkUe5OoIOHSL7Pn3+C23SGoQokKi7SK3QJvUdvRYBAKkALgO4WJOhjUUEqgrOJZFYEWMj6ORJ2XQ8ddYJlOffVZbHVp/z73IaBtXlUX7ppZdUvv8qt4nM7EyyXGhJ4uliglhedNq2batSkMP6Sn0QAbvabNuQRWDz5s3Utm3basP03r0rSz7Tvbts7YAqIlBV/l2h3sQ4nLoiZB7lym1i5qGZhCjQibQTFeHOW7VqpdDGmjdvrlK48/oEFwE9pLqEHa1ataJ169Ypdexu3Ci7Kt9+W3sR0PSYLIcjFLdv36bAwECleZRr45MqbxMX7l4g8SIxjf9lvNLthE58pO/ouwikALgA4DyACUp+nwAgFkCsi4uLps6RVhAidV9JCVHXrmUJ6o/EVykCjTn/LqdhcPbs2TrnUQ67cIFCz58j/03+1GxFM3qU96jGeqpLgdqvX786p0DVR/RdBJqX/dsUQDyA0Kq2rY89gcTEROrXr5/SWOs9evRQKdZ6QgKRgQFR6Ot5tPP+/Urfa26eNoejS/bu3UtOTk4KLzVOTk5yeZR33r9PY/74iBAF2nm57pMm0tPTafjw4QpDpoaGhhQYGEhHjhwR8rC0hl6LgFxlQBSAWVX9Xl9E4MiRIxQYGKiwrN7S0pKGDx9O6QIkgpk/X3Z1duzg+Xc5jYvq8ij/cuwXMvvYjPp+31ftNQF5eXkUGRlJTZs2VRiy9fT0rFfhz/VWBACYAbCo9P9TAPpUtb0+i8CWLVvI09NTwenUtGlTioyMFDT/an5+Pg0aNJQA4WO3cDj1CYXYVSNAmAfy7e4raOwqqVRKq1atInd3d7meNmOMWrRoQQsXLhQ8N4KQ6LMItCwbAooHcAXA/6rbXp9EQCqV0sKFC6lFixYKN4W7uzutWrVK0Juiqvy7gJicnXn+XU7jpri4mLpN7EaIAiFIPvCcqnmUq2PPnj30wgsvKDiWbWxsaNy4cZSdnS1ofeqityJQ14+uRSA7O5vGjRunEDxNIpHQCy+8QHv27BG8zuriufvt3k3NXnlIEgmRmsFAOZx6TXZ+NjmudCTz1Z4UfOQPeumll5Tms3jnnXcEHyI9c+YMhYWFKYRRNzMzowEDBlBSUpKg9akCFwE1SEpKogEDBijEUTcyMqKwsDA6c+aM4HXWNv9u2IULFHwknuzsiIKCZDOHOJzGSMT+CBItElGnv76XmzGn7cx2aWlpNGzYMKWO5aCgIDp69KjgddYGLgJ15NixYxQcHKzUsTts2DBKS0sTvE5VcryWz4n+7jvZldqwQXCzOBy959StU8SiGEX+Flnt2pnq2pgmnLw5OTk0ffp0BceyWCymdu3a0datWwWvsyq4CNSCrVu3Urt27RRm2TRt2pSmT5+ukcxY6r6llN/wpaVEPXsSWVoS3bkjuJkcjt5SJC0i7w3e5PypMz0teFrrBZS17W0LhVQqpWXLlpGbm5uCD9HZ2Zmio6M16ljmIqAEqVRK0dHR5OzsrHBR3NzcaNmyZRq5KI8fPxZsvPKXzEz6JTOTiIhu3CAyNiYaNkxwkzkcvWXJ8SWEKNAv138hIvk2UVs0lUe5Onbt2kUdOnRQeA7Y2trS+PHjBXcscxEoIzs7m8aPH68wx1gikVCHDh1oV1V5HNVEW/l3lyyRXbFffhGkOA5Hr7mRdYOMPjKioT8MFaS88hl4yvIoh4aGUmYdxaW2nD59mkJDQxWeD+bm5jRw4EBKTk5Wu45GLQLJyck0cOBAhTy4RkZGFBoaSqdPn65zmbVlzpw5SvPvBgYGCjKH+fqzZ3T92bOKv4uKiLy9iZydZTkIOJyGSmlpKfXc2pMsl1rSnaf/jYE+3yZURZN5lKsjLS2NhgwZQhYWFgr1du3alWIqZ5aqA41OBGJiYqhr164KF9DCwoKGDBmiEcduOZ999lmV+XfPnj0raF3Kxj9PnSJijOjddwWtisPRK767+B0hCrThrPxsCHXCq1dFRoZuVuXn5OTQlClTyM7OTuFF0svLi7Zv317rshqFCGzfvp28vLwULpSdnR1NmTJFI47dcmob10RoqrrhIyJkeYnPndNY1RyOzsh8lkl2y+0oaHMQlZTKz4vWhAhURlfxuaRSKX3yySfk6uqq4MN0cXGhJUuWVOvDbJAiIJVKacmSJeTi4qJwUlxdXemTTz7RqLddH/LvVnXDZ2cTOToS+foS8dBBnIbG2J/HkiRaQpfvK66Q1LQIVEaXkXp37txJ3t7eSl96IyIiFF56G4wIdFLhXSoAABI+SURBVOzYkSIiIpR2j7y9vWmnAKkWq6O6WOezZs3SaN3KqO6G37NHdvVWrtSyURyOBjmSfIQQBfrgzw+U/q5NEaiMLnN2xMTEUEhIiFLH8qBBgyg5ObnhiMDzjt2QkBCVHSW1RZ/z71Z3w5eWEr3yCpGpKVFKinbt4nA0QX5xPrVZ14ZarW1FeUXKAzLqSgQqo8vsfcnJyTRo0CCFCSkNRgREIlGFsmkSTeU/FZo/srLoj2oyIKWlEZmZEfXtKxMFDqc+M//IfEIU6M+bf1a5TU1tQpvo+jmSnZ1NERER5VPiG4YIaDpsRFRUVIPLv7tmjewqanikjMPRKAn3E0gSLaE3f3pT16aohK5HFLgIVMOWLVvqbf7duKdPKe7p02q3kUqJ/P2JmjUjelRzpj0OR+8oKS2h4K+DyXaZLT3IfVDttrVpE7pG3TzKqsBF4DkOHz5Mbm5uOvHqC0ltxz8vXCASi4kmTNCCURyOwGw8t5EQBfo27tsat9UHn0Bd0NYsQ3VEQAQNwxjrwxhLZIwlMcbmaqqeK1euwMfHByKRCL169UJqaioAwNraGsuXLwcR4e7du3jjjTc0ZYLO6NgReO89YNMmICZG19ZwOLUnIycD7//5Pnq498CYF8bo2hzB6dy5M65fv47S0lLs3bsXTk5OAICsrCxMnToVjDE4Oztj3759OrNRoyLAGBMD+BxAXwDtAYxgjLUXqvyHDx8iLCwMEokE3t7euHz5MogIZmZmmDp1KoqLi/H48WPMnj1bqCr1lqgowNUVmDABKCzUtTUcTu2I/D0SBdICbOy/EYwxXZujUQYOHIjbt2+DiLBu3TrY2NgAANLT0zFo0CCIRCK0b98eFy5c0Kpdmu4JBABIIqJkIioCsBPAQHUKLCgowLBhw2BkZAR7e3scP34cJSUlMDQ0xNChQ5Gfn4/c3FysX78eEolEkIOoD5iZAV98AVy7BixfrmtrOJyaOfDvAey+uhvzQ+ejjW0bXZujVaZNm4asrCwQEWbNmgVzc3MQEa5duwY/Pz9IJBIEBQUhPT1d47ZoWgRaALhd6e/0su8qYIxNYIzFMsZiMzMzlRYilUoxbdo0mJubw8TEBD/++COKioogFovRrVs3ZGRkoLCwEHv27IGxsbHmjkbP6dsXGD4c+Phj4N9/dW0Nh1M1uUW5mHxwMtrbt8ecrnN0bY5OWbFiBXJyclBcXIyRI0fCyMgIJSUl+Oeff+Ds7AxDQ0O88soryM3N1YwBqjoTavMB8BqAzZX+fhPA+qq2f94xrIs44PrEyexsOlnHuOMZGUTW1kQvvsjXDnD0lxm/zyBEgWLS6rYYVJU2UR/JzMyknj171jovCfR1dhCAIACHKv39AYAPqtrez8+PduzYQY6Ojgoze1xdXTWSEaghsmmT7Mp+842uLeFwFIm9E0uiRSKa+OtEXZtSL6hNhkJ1RIDJ9tcMjDEJgH8B9ARwB8A5ACOJ6EoV28sZY29vj6VLl+Kdd97RmI36zKknTwAAwVZWddqvtBQICwOuXgWuXwfs7TVhHYdTd6SlUnTZ3AV3c+7i2pRrsDa2rtP+qraJhsLx48fx9ttvIzk5Gc89u88Tkb8qZWrUJ0BEUgBTARwCcA3ArqoEoBxLS0ssWLAARIQHDx40WgEAgHnJyZiXnFzn/UQi2XTRnBxgxgwNGMbhqMj6M+txIeMC1vVZV2cBAFRvEw2F0NBQJCUlobS0FNu3b4eDg4PaZWq0J1BX/Pz86Pz587o2Q294MS4OAPB3x44q7f/hh0B0NHD4MPDyy0JaxuHUnbTsNHht8MKLbi/i1xG/qjQlVN020VBhjOlnT6CuNPR5wtrmgw+Atm2BSZOAvDxdW8NpzBARphycAgLh836f87auR+iVCHCExdgY+PJLIDkZ+OgjXVvDaczsuboHB24cwEfdP4KrtauuzeFUgotAA+fFF4HwcGDlSuDyZV1bw2mMZBdkY/rv09HJsROmd5mua3M4z9F4ltTWQ9a0bi1IOStWAPv3A+PHAydPAmKxIMVyOLXigz8/wINnD3Bg5AFIROo9coRqE5z/4D0BPcbXwgK+FhZql2NrC6xeDZw5A2zcKIBhHE4tOXnrJDae34jILpHo5NhJ7fKEahOc/9Cr2UH+/v4UGxurazP0hj8fPQIAvFQWaEodiIA+fYDTp2XxhVq0qHkfDkcdikqK0PHLjsgtysWVyVdgbmiudplCtomGRIOZHcSRZ3FaGhanpQlSFmPAhg1AcTEwnQ/LcrTAipMrcDXzKjb02yCIAADCtgmODC4CjYhWrWQhp3/6CdBh+HJOI+BG1g18dPwjvNb+NfRv21/X5nCqgYtAI2PGDMDHB5g6VbaimMMRGiLCxP0TYSwxxto+a3VtDqcGuAg0MgwMZCEl7twB5s/XtTWchsh38d/haOpRfPLSJ3C0cNS1OZwa4CLQCOnSBZg8GVi/Hjh3TtfWcBoSD/MeYubhmQh2DsYEvwm6NodTC/g6AT3mSw8PjZW9ZAmwd69s7cC5c7IeAoejLjMPz8TTwqfYNGATREz4d0xNtonGCu8J6DEepqbwMDXVSNmWlrKeQHw8sGaNRqrgNDL+TP4T38V/hzld58CrqZdG6tBkm2is8HUCesyvDx8CAF6xs9NYHYMGyaKMXrkCuLtrrBpOAye/OB8dvugAxhguTboEEwMTjdSjjTZRH+HrBBooq27fxqrbt2veUA3Wr5eFkZg8WbagjMNRhcXHF+Pm45v4csCXGhMAQDttorGhMRFgjEUxxu4wxi6Wffppqi6O6jg7y/wDv/8O/PCDrq3h1EcSHiRg+anlGPvCWPRw76Frczh1RNM9gdVE5Fv2OajhujgqMnkyEBAAREYCZavyOZxaUUqlmPDrBFgZWWFlr5W6NoejAnw4iPP/7d17cBX1FcDx7zEYGFCoEkvRgtApVMFHFWSktlQeUygMMFSpMKMtFc1AgVFsOgYZrRYYlPoYsbyCj9Q6KMgfCCjyUBF0CJSpaYAgDgJieDSGolWp4eHpH7+tydCLWXNz97d37/nMZLibu3f3cNi9h939PcjLc30HjhyBu+/2HY3JJgu2LmBT1SYeHfgoBS3tPn02ynQRmCgiFSLytIicl+F9mTRceaXrTfzkk7Bxo+9oTDY4+OlBil8rpn/n/txyxS2+wzGNlFbrIBFZB6Sa6XgqUAbUAApMA9qr6q0ptlEIFAJ07Nixxwc2ONRXPvziCwA6tGgRyf4+/xwuvxyaN4fycvenMWcy8sWRrHxvJdvGb+P750czzn/U50S2SKd1UFqdxVR1QJj1RGQhsPIM2ygBSsA1EU0nnqSJ+kBv1QrmzXNDTj/4oJuo3phUVuxawdLKpczoNyOyAgD25Z8JmWwdVH/QkBHA9kztK6kWV1ezuLo60n0OHAijR7sWQ+++G+muTZb47PhnTHhlAt0v6E7Rj4oi3bePcyLpMvlMYJaIbBORCqAvMDmD+0qkeQcOMO/Agcj3+9hj0LIljBtnfQfM/7v39Xup+ncVC4cuJD8vP9J9+zonkixjRUBVb1HVy1X1ClUdpqqHMrUv07TatXMT07/5JjzzjO9oTJxsPbiV2VtmM67nOHp36O07HNMErImoSenWW6FPHygqArv6NgAnvzzJ7Stup12rdszsP9N3OKaJWBEwKYnAggWuxdBku5FngMfLHqf8cDmzfz6bNi3a+A7HNBErAuaMLrkEpkyBRYtg9Wrf0Rif9n28j/vW38fQrkO54dIbfIdjmpCNIhpjNcePA1CQH+3Dt/pqa11HsuPHYft298DY5BZVZciiIWz4YAOVEyrp2Kajt1jicE7EkY0imlAF+fneD/bmzd2QEnv3wgMPeA3FeLJkxxJW7V7F9H7TvRYAiMc5kTRWBGKs9NAhSg/5b1TVpw+MHQuPPOImoTG54+h/jnLHq3fQo30PJvWa5Duc2JwTSWJFIMZKDx+m9PBh32EAMGsWtG0LhYVw6pTvaExUitcVU3OshoVDF5J3Vp7vcGJ1TiSFFQETyvnnu2kot2xxQ0uY5Htr/1uU/L2EO6+9k6vaX+U7HJMhVgRMaKNGuWElpkyBqirf0ZhMqj1ZS+GKQi5uczEPXG8Pg5LMioAJTcRdBZw6BZP83x42GTTr7VnsrNnJ3CFzaZXfync4JoOsCJhvpHNnuP9+WLbM/Zjkee/Ie8zYOIObut/E4C42K2zSWT+BGDsWPIFtmef/gVx9J07ANddATQ1UVkLr1r4jMk1FVen3bD/KD5ezc8JOvnNOqulC/InrOeGb9RNIqJZ5ebE82M8+2/UdOHgQpk71HY1pSqXlpazft56HBjwUuwIA8T0nspkVgRibe+AAc2M6bG6vXjBxIsyZA5s3+47GNIWPPv+IorVFXNfhOm67+jbf4aQU53MiW1kRiLEl1dUsifEQntOnw4UXur4DJ074jsak6641d/Fp7aeUDC3hLInnV0Pcz4lsFM9/aZMVWrd2VwIVFW4iGpO91r6/lucqnqP4x8V0u6Cb73BMhNIqAiIyUkR2iMiXItLztPemiMhuEdklIgPTC9PE1fDhMGKEazG0Z4/vaExjHDtxjHEvj6Nr267c85N7fIdjIpbulcB24BfAhvq/FJFuwCigOzAImCsi9jQnoZ54Apo1g/HjbTrKbDTtzWnsObqH+UPm06KZTeSea9IqAqq6U1V3pXhrOPCCqtaq6l5gN9ArnX2Z+LroIpg5E9asgeef9x2N+Sa2/XMbD296mDE/HEPfzn19h2M8aJJ+AiKyHihS1a3B8p+BMlV9Llh+ClilqktTfLYQKAwWL8NdXRgoAGp8BxETlos6los6los6P1DVcxvzwWYNrSAi64BUDYanqupLZ/pYit+lrDaqWgKUBPva2tgOD0ljuahjuahjuahjuagjIo3uZdtgEVDVAY3YbhXQod7yd4GDjdiOMcaYDMpUE9HlwCgRaS4inYEuwJYM7csYY0wjpdtEdISIVAG9gZdFZDWAqu4AlgCVwKvABFUNMxVJSTrxJIzloo7loo7loo7lok6jcxGrAeSMMcZEy3oMG2NMDrMiYIwxOcxLERCRQcFwErtFpDjF+81FZHHw/mYR6RR9lNEIkYu7RKRSRCpE5DURudhHnFFoKBf11rtRRPT0oUqSJEwuROSXwbGxQ0QWRR1jVEKcIx1F5A0ReSc4TxI5E46IPC0i1SKSsi+VOLODPFWIyNWhNqyqkf4AecD7wPeAfOAfQLfT1vktMD94PQpYHHWcMcpFX6Bl8Hp8LuciWO9c3DAlZUBP33F7PC66AO8A5wXL3/Ydt8dclADjg9fdgH2+485QLvoAVwPbz/D+YGAVrp/WtcDmMNv1cSXQC9itqntU9TjwAm6YifqGA38JXi8F+otIqg5o2a7BXKjqG6p6LFgsw/W5SKIwxwXANGAW8EWUwUUsTC5uB+ao6lEAVU3q+MphcqHA/+a3a0NC+ySp6gbgX1+zynDgWXXKgG+JSPuGtuujCFwEfFhvuSr4Xcp1VPUk8AnQNpLoohUmF/WNxVX6JGowFyJyFdBBVVdGGZgHYY6LrkBXEXlbRMpEZFBk0UUrTC7uB24Omqu/AkyKJrTY+abfJ0CIHsMZEGZIidDDTmS50H9PEbkZ6An8NKMR+fO1uRCRs4DHgDFRBeRRmOOiGe6W0PW4q8ONInKZqn6c4diiFiYXo4FSVX1ERHoDfw1y8WXmw4uVRn1v+rgSCDOkxFfriEgz3CXe110GZatQw2uIyABgKjBMVWsjii1qDeXiXNwAg+tFZB/unufyhD4cDnuOvKSqJ9SN1LsLVxSSJkwuxuI6p6Kqm4AWuMHlck2jhuvxUQT+BnQRkc4iko978Lv8tHWWA78OXt8IvK7Bk4+EaTAXwS2QBbgCkNT7vtBALlT1E1UtUNVOqtoJ93xkmAYj1yZMmHNkGa7RACJSgLs9lMRpfcLkYj/QH0BELsUVgY8ijTIelgO/CloJXQt8oqqHGvpQ5LeDVPWkiEwEVuOe/D+tqjtE5I/AVlVdDjyFu6TbjbsCGBV1nFEImYs/AecALwbPxver6jBvQWdIyFzkhJC5WA38TEQqgVPA71X1iL+oMyNkLn4HLBSRybjbH2OS+J9GEXked/uvIHj+8QfgbABVnY97HjIYN3/LMeA3obabwFwZY4wJyXoMG2NMDrMiYIwxOcyKgDHG5DArAsYYk8OsCBhjTA6zImCMMTnMioAxxuSw/wJvKdH74RNWdQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x27bee9a5f60>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_utility(utility)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hence, we get a piecewise-continuous utility function consistent with the given POMDP."
   ]
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}