S32_vacuum_actions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "eX7aeXwosFP1",
   "metadata": {},
   "source": [
    "# Actions over time"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "kKptqemT9NvF",
   "metadata": {
    "colab_type": "text",
    "tags": [
     "no-tex"
    ]
   },
   "source": [
    "<a href=\"https://colab.research.google.com/github/gtbook/robotics/blob/main/S32_vacuum_actions.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "AGLSAwAy9iuQ",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "outputId": "8e5f4d6e-a5ba-4011-9fa9-a9ef3627686b",
    "tags": [
     "remove-cell"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Note: you may need to restart the kernel to use updated packages.\n"
     ]
    }
   ],
   "source": [
    "%pip install -U -q gtbook\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "BG7SOd3Ai1TE",
   "metadata": {
    "tags": [
     "remove-cell"
    ]
   },
   "outputs": [],
   "source": [
    "import gtsam\n",
    "\n",
    "import gtbook\n",
    "import gtbook.display\n",
    "from gtbook import vacuum\n",
    "from gtbook.discrete import Variables\n",
    "\n",
    "VARIABLES = Variables()\n",
    "def pretty(obj):\n",
    "    return gtbook.display.pretty(obj, VARIABLES)\n",
    "def show(obj, **kwargs):\n",
    "    return gtbook.display.show(obj, VARIABLES, **kwargs)\n",
    "\n",
    "# From section 3.1:\n",
    "X = VARIABLES.discrete_series(\"X\", [1], vacuum.rooms)\n",
    "state_prior = gtsam.DiscreteDistribution(X[1], \"0/0/1/0/0\")\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "g8_dorfVrpEV",
   "metadata": {
    "tags": [
     "no-pdf"
    ]
   },
   "source": [
    "```{index} action; stochastic action\n",
    "```\n",
    "\n",
    "> Using the language of probability to describe systems with uncertainty in the effects of actions.\n",
    "\n",
    "<img src=\"Figures3/S32-iRobot_vacuuming_robot-04.jpg\" alt=\"Splash image with vacuuming robot in action\" width=\"40%\" align=center style=\"vertical-align:middle;margin:10px 0px\">"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "-XwLo9UxiUyl",
   "metadata": {},
   "source": [
    "```{index} conditional probability distribution\n",
    "```\n",
    "In the real world, robots do not always execute actions perfectly, for a\n",
    "variety of reasons. \n",
    "To model the uncertainty when executing an action, we will once again use the\n",
    "language of probability. \n",
    "We will use *conditional probability distributions* to model how we can affect the state \n",
    "of the robot by actions. \n",
    "Recall that in Chapter 2 we used conditional probabilities to model\n",
    "the effects of uncertainty in sensing at a specific moment in time.\n",
    "Here, we use conditional probabilities to model the uncertainty in state transitions when\n",
    "actions are executed.\n",
    "\n",
    "```{index} graphical model\n",
    "```\n",
    "We can model this using graphs, with directed edges that specify conditional\n",
    "probabilities on variables.\n",
    "We can use these \"graphical models\" to generate sample system trajectories\n",
    "for a fixed sequence of actions.\n",
    "Such sample trajectories can be used for planning, as we will see later in the chapter.\n",
    "In addition, the graphical model approach allows us to easily extend probabilistic actions to\n",
    "factored state representations, which can provide significant computational advantages."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "tykhkLT25whd",
   "metadata": {},
   "source": [
    "```{index} action space\n",
    "```\n",
    "In our example, we assume that our robot is equipped with navigation software that implements four\n",
    "primitive actions: *move left, move right, move up, move down*,\n",
    "which we will denote by *L,R,U,D*.\n",
    "Together, these four actions define the **action space**.\n",
    "The nominal effects of these actions (i.e., the effects of the actions without taking into account uncertainty) \n",
    "are to move the robot from the current room to an adjacent\n",
    "room, according to the direction specified by the action.\n",
    "For example, executing the *move down* action from the living room should take the robot into the hallway.\n",
    "\n",
    "\n",
    "<figure id=\"fig:Stochastic\">\n",
    "<img src=\"https://github.com/gtbook/robotics/blob/main/Figures3/S32-Actions.png?raw=1\" style=\"width:14cm\" alt=\"\" />\n",
    "<figcaption>Our robot is equipped with\n",
    "four primitive actions: Left, Right, Up, and Down.\n",
    "</figcaption>\n",
    "</figure>\n",
    "\n",
    "We can represent these actions graphically by making a slight modification to our state space graph\n",
    "from the previous section.\n",
    "Instead of using undirected edges to denote adjacency, each action contributes a directed edge, as shown in \n",
    "Figure [1](#fig:Stochastic).\n",
    "Note that to simplify notation  we use *L,R,U,D*\n",
    "instead of *move left, move right, move up, move down* to label the edges."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aD01OMUKc-_c",
   "metadata": {},
   "source": [
    "## Probabilistic Outcomes of Actions\n",
    "\n",
    "> Actions are uncertain.\n",
    "\n",
    "<figure id=\"fig:Mud\">\n",
    "<img src=\"https://github.com/gtbook/robotics/blob/main/Figures3/N3-Mud.png?raw=1\" style=\"width:14cm\" alt=\"\" />\n",
    "<figcaption>Mobile robot driving in mud.</figcaption>\n",
    "</figure>\n",
    "\n",
    "In the real world, robots do not always execute actions perfectly, for a variety of reasons.\n",
    "For example, as shown in Figure [2](#fig:Mud),\n",
    "a robot may attempt to drive forward in an outdoor environment but mud\n",
    "under its wheels might prevent it from traveling as far as desired.\n",
    "\n",
    "<figure id=\"fig:Pickup\">\n",
    "<img src=\"https://github.com/gtbook/robotics/blob/main/Figures3/N3-Pick.png?raw=1\" style=\"width:14cm\" alt=\"\" />\n",
    "<figcaption>A humanoid attempting to pick up an object.</figcaption>\n",
    "</figure>\n",
    "\n",
    "Or a robot with an articulated arm (Figure [3](#fig:Pickup))\n",
    "might attempt to pick up an object, but fail. Some objects are easier to grasp than others, and robot grippers are not as dexterous as human hands, so this is not such a rare occurrence."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "feXzV50lnlQc",
   "metadata": {},
   "source": [
    "Similarly, for our vacuum cleaning robot example, a variety of things could go wrong: a particular doorway might be blocked, the robot might get lost, or it might take an action that is simply not available in a particular room - for example executing *move up* in the office.\n",
    "As a reminder, in this chapter we *discretize* time and talk about the state of the robot at discretized times $t_k$, with $k\\geq1$ an integer. Here we don't care too much about the underlying times $t_k$ at which the robot finishes a transition, as long as it is in a reasonable time. For example, the robot control system could time out after several unsuccessful attempts to move to a different room. That is then another way an action can fail."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "GJIO_GtmcP6J",
   "metadata": {},
   "source": [
    "```{index} state transition model, motion model\n",
    "```\n",
    "To model the uncertainty associated with executing an action, we will once again use the language of probability. \n",
    "In particular, we will use the conditional probability $P(X_{k+1}|X_k=x,A=a)$ to define\n",
    "the **state transition model**  model, i.e.,\n",
    "the conditional probability distribution for the next state $X_{k+1}$, \n",
    "given the value $x$ of the current state $X_k$, and the value $a$ of the action $A$. \n",
    "Because the state space in this case involves navigation, we could also call the corresponding conditional distribution \n",
    "$P(X_{k+1}|X_k,A)$ a **motion model**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "en7dzO5uFqYo",
   "metadata": {},
   "source": [
    "The code in Figure [4](#vacuum-motion-model) generates a motion model for moving from state $X_1$ to $X_2$ in the\n",
    "form of a large conditional probability table. In the code, we make use of two new variables (`action_space` and `action_spec`) that were predefined for us but are repeated here in the comment for clarity. The `motion_model` is rendered as a table below the code, showing $P(X_2|X_1,A_1)$ as a row for all possible $(X_1,A_1)$ combinations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "G-qNECPuqoQA",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<p>  <i>P(X2|X1,A1):</i></p>\n",
       "<table class='DiscreteConditional'>\n",
       "  <thead>\n",
       "    <tr><th><i>X1</i></th><th><i>A1</i></th><th>Living Room</th><th>Kitchen</th><th>Office</th><th>Hallway</th><th>Dining Room</th></tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr><th>Living Room</th><th>L</th><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td></tr>\n",
       "    <tr><th>Living Room</th><th>R</th><td>0.2</td><td>0.8</td><td>0</td><td>0</td><td>0</td></tr>\n",
       "    <tr><th>Living Room</th><th>U</th><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td></tr>\n",
       "    <tr><th>Living Room</th><th>D</th><td>0.2</td><td>0</td><td>0</td><td>0.8</td><td>0</td></tr>\n",
       "    <tr><th>Kitchen</th><th>L</th><td>0.8</td><td>0.2</td><td>0</td><td>0</td><td>0</td></tr>\n",
       "    <tr><th>Kitchen</th><th>R</th><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr>\n",
       "    <tr><th>Kitchen</th><th>U</th><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr>\n",
       "    <tr><th>Kitchen</th><th>D</th><td>0</td><td>0.2</td><td>0</td><td>0</td><td>0.8</td></tr>\n",
       "    <tr><th>Office</th><th>L</th><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td></tr>\n",
       "    <tr><th>Office</th><th>R</th><td>0</td><td>0</td><td>0.2</td><td>0.8</td><td>0</td></tr>\n",
       "    <tr><th>Office</th><th>U</th><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td></tr>\n",
       "    <tr><th>Office</th><th>D</th><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td></tr>\n",
       "    <tr><th>Hallway</th><th>L</th><td>0</td><td>0</td><td>0.8</td><td>0.2</td><td>0</td></tr>\n",
       "    <tr><th>Hallway</th><th>R</th><td>0</td><td>0</td><td>0</td><td>0.2</td><td>0.8</td></tr>\n",
       "    <tr><th>Hallway</th><th>U</th><td>0.8</td><td>0</td><td>0</td><td>0.2</td><td>0</td></tr>\n",
       "    <tr><th>Hallway</th><th>D</th><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td></tr>\n",
       "    <tr><th>Dining Room</th><th>L</th><td>0</td><td>0</td><td>0</td><td>0.8</td><td>0.2</td></tr>\n",
       "    <tr><th>Dining Room</th><th>R</th><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr>\n",
       "    <tr><th>Dining Room</th><th>U</th><td>0</td><td>0.8</td><td>0</td><td>0</td><td>0.2</td></tr>\n",
       "    <tr><th>Dining Room</th><th>D</th><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "<gtbook.display.pretty at 0x117b255e0>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: The code for specifying the vacuum cleaner motion model, and the resulting CPT.\n",
    "#| label: vacuum-motion-model\n",
    "# vacuum.action_space = [\"L\",\"R\",\"U\",\"D\",]\n",
    "# vacuum.action_spec is a string with the transition probabilities:\n",
    "#  \"1/0/0/0/0 2/8/0/0/0 1/0/0/0/0 2/0/0/8/0\n",
    "#   8/2/0/0/0 0/1/0/0/0 0/1/0/0/0 0/2/0/0/8\n",
    "#   0/0/1/0/0 0/0/2/8/0 0/0/1/0/0 0/0/1/0/0\n",
    "#   0/0/8/2/0 0/0/0/2/8 8/0/0/2/0 0/0/0/1/0\n",
    "#   0/0/0/8/2 0/0/0/0/1 0/8/0/0/2 0/0/0/0/1\"\n",
    "X = VARIABLES.discrete_series(\"X\", [1, 2, 3], vacuum.rooms) # states for times 1,2 and 3\n",
    "A = VARIABLES.discrete_series(\"A\", [1, 2], vacuum.action_space) # actions for times 1 and 2\n",
    "motion_model = gtsam.DiscreteConditional(X[2], [X[1], A[1]], vacuum.action_spec)\n",
    "pretty(motion_model)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "S-yu_kpzhOZU",
   "metadata": {},
   "source": [
    "It is of course rather tedious to specify this table by hand.\n",
    "In this case, for each of the four actions, we must compute a transition probability from\n",
    "each of the five possible starting rooms to each of the five possible destination rooms:\n",
    "$4*5*5=100$ entries.\n",
    "In the example above, impossible transitions (e.g., moving up from the living room to any other room)\n",
    "are assigned zero probability.\n",
    "Other actions are assumed to have 80% chance of success (e.g., moving right from the living room\n",
    "and arriving to the kitchen is assigned a transition probability of $0.8$).\n",
    "\n",
    "Conditional probability distributions do not *have* to be specified as giant\n",
    "tables. Because the state space is potentially quite large, such a\n",
    "motion model is almost never explicitly specified, but\n",
    "rather exploits the semantics of the states and actions to calculate the conditional distribution at run-time.\n",
    "For example, rather than enumerate every possible action from every possible room, we might\n",
    "determine the probability of successfully moving to an adjacent room is $0.8$, for all\n",
    "rooms and for all actions, and that the probability of failing to do so is $0.2$.\n",
    "If we apply this rule to each combination of action and adjacent rooms, we can\n",
    "construct specific rows the table above on an as-needed basis."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "IUwXQ9Af2UCH",
   "metadata": {},
   "source": [
    "### Exercises\n",
    "\n",
    "1.  Even though the CPT above\n",
    "    has 100 numbers in it, how many *independent* numbers do we\n",
    "    actually have when specifying this CPT?\n",
    "\n",
    "2.  Specify a *parametric* conditional density for the action models for\n",
    "    the vacuuming robot that is somewhat realistic, yet not completely\n",
    "    deterministic.\n",
    "\n",
    "3.  It is possible to create models that do not reflect everyday\n",
    "    physics. For example, how could we model the game “Portal”?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "rra6iSgmQR00",
   "metadata": {},
   "source": [
    "## Understanding Sequences of Actions\n",
    "\n",
    "> From one to many actions.\n",
    "\n",
    "How do we use the above to predict what happens when taking *multiple* actions?\n",
    "Formally, assume we apply a sequence of actions $a_1 \\dots a_k$, and we wish to compute the probability distribution associated with the resulting state $X_{k+1}$.\n",
    "Below, we accomplish this by applying the law of total probability.\n",
    "\n",
    "```{index} law of total probability\n",
    "```\n",
    "The **law of total probability** provides a convenient way to compute the probability of an event by considering all of the different ways the event could occur.\n",
    "Suppose we have a set of events ${\\cal B} = \\{B_1, \\dots , B_n\\}$ such that $B_i \\cap B_j = \\emptyset$ when $i \\neq j$,\n",
    "and with $\\cup B_i = \\Omega$, i.e., the set of events ${\\cal B}$ forms a partition of the sample space.\n",
    "To compute the probability of an event $A$, the law of total probability is given by\n",
    "\\begin{equation}\n",
    "P(A) = \\sum_{i} P(A | B_i ) P(B_i)\n",
    "\\end{equation}\n",
    "We merely sum the conditional probabilities $P(A | B_i)$ for each event $B_i$, weighted by the probability of the event $B_i$.\n",
    "\n",
    "We can use the law of total probability to compute the probability that the robot\n",
    "is in state $x_{k+1}$ at time step $k+1$ by conditioning on the possible states for time step $k$:\n",
    "\\begin{equation}\n",
    "P(X_{k+1} = x_{k+1}) = \\sum_{x_k} P(X_{k+1} = x_{k+1}| X_k = x_k) P(X_k = x_k).\n",
    "\\end{equation}\n",
    "Now, condition every term in the above equation on the sequence of actions $a_1 \\dots a_k$, and we obtain\n",
    "\\begin{equation}\n",
    "P(X_{k+1} | a_1 \\dots a_k) = \\sum_{x_k} P(X_{k+1} | X_k, a_1 \\dots a_k) P(X_k|a_1 \\dots a_k),\n",
    "\\end{equation}\n",
    "where, for brevity's sake, we omit the explicit assignment of values to $X_k$ and $X_{k+1}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "Y0JnoVLi62-p",
   "metadata": {},
   "source": [
    "```{index} posterior\n",
    "```\n",
    "This expression may seem complex, but it can be simplified by making the following observation:\n",
    "*If we know that the robot is in a specific state $x_k$ at time step $k$, then the next state will depend only\n",
    "on the action executed at time step $k$; the previously executed actions will not affect our belief\n",
    "about $X_{k+1}$*.\n",
    "For example, if the robot executes the action *move down* knowing with certainty that it is in the living room at time step $k$,\n",
    "the sequence of actions that brought the robot to the living room (i.e., actions $a_1 \\dots a_{k-1}$) does not affect our belief\n",
    "about whether the robot will arrive to the hallway.\n",
    "Mathematically, we can write this relationship as follows:\n",
    "\\begin{equation}\n",
    "P(X_{k+1} | X_k, a_1 \\dots a_k) = P(X_{k+1} | X_k, a_k)\n",
    "\\end{equation}\n",
    "We can also simplify the term $P(X_k |a_1 \\dots a_k)$.\n",
    "Notice that the action performed at time step $k$ has no affect on the state at time step $k$.\n",
    "For example, if the robot executes the *move down* action\n",
    "in the living room at time step $k$, this actions does not change the fact that the robot was in the living room\n",
    "at time *t*.\n",
    "Therefore, we have\n",
    "\\begin{equation}\n",
    "P(X_k |a_1 \\dots a_k) = P(X_k |a_1 \\dots a_{k-1})\n",
    "\\end{equation}\n",
    "Applying these two simplifications, we obtain the final form for the desired probability distribution $P(X_{k+1} | a_1 \\dots a_k)$:\n",
    "\\begin{equation}\n",
    "P(X_{k+1} | a_1 \\dots a_k) = \\sum_{x_k} P(X_{k+1} | X_k, a_k) P(X_k |a_1 \\dots a_{k-1})\n",
    "\\end{equation}\n",
    "We can think of the terms in this expression as follows:\n",
    "- $P(X_k |a_1 \\dots a_{k-1})$ is the prior over the current state $X_k$;\n",
    "- $P(X_{k+1} | X_k, a_k)$ is the motion model;\n",
    "- $P(X_{k+1} | a_1 \\dots a_k)$ is the **posterior** over the next state $X_{k+1}$.\n",
    "\n",
    "For the initial state, no actions have yet been applied, and the prior is merely \n",
    "the prior $P(X_1)$ over the initial state $X_1$.\n",
    "And then the posterior at time step $k=2$ can be computed as\n",
    "\\begin{equation}\n",
    "P(X_{2}| a_1) = \\sum_{x_1} P(X_{2} | X_1, a_1) P(X_1).\n",
    "\\end{equation}\n",
    "This posterior $P(X_{2}| a_1)$ then becomes the prior in the next step, and so forth... This is one example of computing probability distributions recursively, a scheme which we will encounter many times more.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "LdbH6vi7VnxE",
   "metadata": {},
   "source": [
    "## State Transition Matrices and the Belief State\n",
    "\n",
    "> It's an elementary matrix multiply, my dear Watson.\n",
    "\n",
    "```{index} belief state\n",
    "```\n",
    "In order to specify the complete posterior distribution at time step $k+1$, we would need to perform the calculation above five times, once for each of the possible next states ($L,K,O,H,D$), i.e., all the rooms in the house we could end up in after taking the action sequence.\n",
    "This complete distribution is called the **belief state** $b_{k+1}$, defined as the *row vector*\n",
    "\\begin{equation}\n",
    "b_{k+1} = \\begin{bmatrix}\n",
    "P(X_{k+1} = L | a_{1:k})\\\\\n",
    "P(X_{k+1} = K | a_{1:k})\\\\\n",
    "P(X_{k+1} = O | a_{1:k})\\\\\n",
    "P(X_{k+1} = H | a_{1:k})\\\\\n",
    "P(X_{k+1} = D | a_{1:k})\n",
    "\\end{bmatrix}^T\n",
    "\\end{equation}\n",
    "in which we have simplified notation by using the notation\n",
    "$a_{1:k} \\doteq a_1, \\dots, a_k$.\n",
    "\n",
    "```{index} state transition matrix\n",
    "```\n",
    "We can write the equations for the belief state in a compact form by writing the conditional probability tables as\n",
    "transition matrices.\n",
    "To do so, for each action, we merely gather the corresponding rows from the complete conditional probability\n",
    "table into a state transition matrix.\n",
    "For the action *move right*, this is illustrated below in Figure [5](#fig:TM).\n",
    "\n",
    "<figure id=\"fig:TM\">\n",
    "<img src=\"https://github.com/gtbook/robotics/blob/main/Figures3/S32-transition-matrix.png?raw=1\" style=\"width:20cm\" alt=\"\" />\n",
    "<figcaption>The transition matrix for the action *move right*.\n",
    "</figcaption>\n",
    "</figure>\n",
    "\n",
    "```{index} belief transition function\n",
    "```\n",
    "If we apply the action *move right* to the initial state, by straightforward calculations, we can see that $b_2 = b_1 M_r$, i.e., a simple vector-matrix multiply.\n",
    "This can be generalized to a sequence of actions.\n",
    "If we execute action ${\\cal A}_k$ at time step $k$,\n",
    "the belief state $b_{k+1}$ is given by\n",
    "\\begin{equation}\n",
    "b_{k+1} = b_k M_{{\\cal A}_k}.\n",
    "\\end{equation}\n",
    "Above $M_{\\cal A}$ is the conditional probability matrix for action $\\cal A$ and $b_k$ is the belief state at time step $k$.\n",
    "We refer to this equation as a *belief transition function* -- given the\n",
    "belief at time step $k$ and the action $a_k$, it can be applied to compute the belief at time step $k+1$.\n",
    "This result can be applied recursively to yield\n",
    "\\begin{equation}\n",
    "b_{k+1} = b_1 M_{{\\cal A}_1} \\dots M_{{\\cal A}_k}\n",
    "\\end{equation}\n",
    "\n",
    "### Exercise\n",
    "\n",
    "Implement the above in python and observe how the belief state evolves from various initial belief states."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1hm2Lc39gqR3",
   "metadata": {},
   "source": [
    "## Controlled Markov Chains\n",
    "\n",
    "> Markov chains are everywhere. Actions control them."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "clmN2UowDG_9",
   "metadata": {},
   "source": [
    "```{index} Markov property\n",
    "```\n",
    "In the derivation above of the belief transition function we employed a temporal decoupling property,\n",
    "namely, given the state at time step $k$, all actions that were applied prior to time step $k$ were irrelevant\n",
    "to determining the belief state $b_{k+1}$.\n",
    "This is an example of what is called the **Markov property**.\n",
    "Variations of this property\n",
    "are essential for reducing the amount of computation required to reason probabilistically over long periods of time.\n",
    "\n",
    "```{index} Markov chain\n",
    "```\n",
    "The most common example of this property arises in systems that are called Markov chains.\n",
    "In its simplest form, a **Markov chain** is a sequence of random variables, $X_1, X_2, \\dots $\n",
    "for which, for every $k$, we have\n",
    "\\begin{equation}\n",
    "P(X_{k+1} | X_1 \\dots X_k) = P(X_{k+1} | X_k).\n",
    "\\end{equation}\n",
    "\n",
    "For Markov chains, knowledge of $X_k$ completely decouples the past (i.e., $X_1 \\dots X_{k-1}$) from the future (i.e., $X_{k+1}$).\n",
    "Therefore, when reasoning about future states, we need not perform computations over the entire history of the system: if we know $X_k$, we need only perform computations related to the present when reasoning about the future."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "rWoXZC_lvd6B",
   "metadata": {},
   "source": [
    "Markov chains have a nice graphical representation.\n",
    "Each node corresponds to a random variable,\n",
    "and directed edges specify conditional probabilities.\n",
    "As an application, we can use this simple graphical model to represent\n",
    "the probabilistic transitions between states, and in fact it can be generated in code,\n",
    "as seen in Figure [6](#fig:markov_chain_3)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "mhUUVyjN9_3B",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (0)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"44pt\"\n",
       " viewBox=\"0.00 0.00 206.00 44.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 40)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-40 202,-40 202,4 -4,4\"/>\n",
       "<!-- var6341068275337658369 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>var6341068275337658369</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">X1</text>\n",
       "</g>\n",
       "<!-- var6341068275337658370 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>var6341068275337658370</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">X2</text>\n",
       "</g>\n",
       "<!-- var6341068275337658369&#45;&gt;var6341068275337658370 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>var6341068275337658369&#45;&gt;var6341068275337658370</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M54.22,-18C56.28,-18 58.38,-18 60.5,-18\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"60.23,-21.5 70.23,-18 60.23,-14.5 60.23,-21.5\"/>\n",
       "</g>\n",
       "<!-- var6341068275337658371 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>var6341068275337658371</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">X3</text>\n",
       "</g>\n",
       "<!-- var6341068275337658370&#45;&gt;var6341068275337658371 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>var6341068275337658370&#45;&gt;var6341068275337658371</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.22,-18C128.28,-18 130.38,-18 132.5,-18\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"132.23,-21.5 142.23,-18 132.23,-14.5 132.23,-21.5\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<gtbook.display.show at 0x11121e6a0>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: A simple three state Markov chain.\n",
    "#| label: fig:markov_chain_3\n",
    "N = 3\n",
    "X = VARIABLES.discrete_series(\"X\", range(1, N+1), vacuum.rooms) # states for times 1...N\n",
    "markov_chain = gtsam.DiscreteBayesNet()\n",
    "markov_chain.add(state_prior)\n",
    "for k in range(1, N):\n",
    "    markov_chain.add(X[k+1], [X[k]], \"6/1/1/1/1 1/6/1/1/1 1/1/6/1/1 1/1/6/1/1 1/1/1/1/6\")\n",
    "show(markov_chain, hints={\"X\":1})"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "NjPmgSKsQY_o",
   "metadata": {},
   "source": [
    "Each node in this graph denotes a random variable, and therefore each node has an associated probability distribution.\n",
    "If we know the distribution for the initial state $X_1$, we can recursively compute the distributions for the states $X_k$ for all $k > 1$, by evaluating the conditional distributions associated to the directed edges in the graph."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "R8fVRN-d93mA",
   "metadata": {},
   "source": [
    "```{index} controlled Markov chain\n",
    "```\n",
    "Our robot vacuum cleaner is slightly more sophisticated than this simple Markov chain, since\n",
    "the robot has the ability to execute actions, and these actions affect the propagation\n",
    "of probabilities through the chain.\n",
    "This type of system is called a **controlled Markov chain**, since it incorporates\n",
    "a control input (the actions) into the usual Markov chain."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "n-MtIu8Vq-Dm",
   "metadata": {},
   "source": [
    "Graphically, we can represent such a system by augmenting the graph above to include nodes that denote actions.\n",
    "We use a *box* to denote nodes whose values are known.\n",
    "Since the robot knows which actions it executes, action nodes are denoted by boxes.\n",
    "For our vacuuming robot, we also know the value of the initial state,\n",
    "since the robot always begins in the office.\n",
    "Therefore, we also use a box to denote the initial state in this graph."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "C7EFqJxk9BYj",
   "metadata": {},
   "source": [
    "As an example, the code in Figure [7](#fig:bayes_net_fragment) builds the controlled Markov chain for a single step of our system, i.e., up to time step $k=2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "toDAQ8iXtfJL",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (0)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"134pt\" height=\"116pt\"\n",
       " viewBox=\"0.00 0.00 134.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-112 130,-112 130,4 -4,4\"/>\n",
       "<!-- var4683743612465315841 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>var4683743612465315841</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"54,-108 0,-108 0,-72 54,-72 54,-108\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">A1</text>\n",
       "</g>\n",
       "<!-- var6341068275337658370 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>var6341068275337658370</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">X2</text>\n",
       "</g>\n",
       "<!-- var4683743612465315841&#45;&gt;var6341068275337658370 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>var4683743612465315841&#45;&gt;var6341068275337658370</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M45.17,-71.83C54.54,-62.46 66.07,-50.93 76.05,-40.95\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"78.33,-43.62 82.92,-34.08 73.38,-38.67 78.33,-43.62\"/>\n",
       "</g>\n",
       "<!-- var6341068275337658369 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>var6341068275337658369</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"54,-36 0,-36 0,0 54,0 54,-36\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">X1</text>\n",
       "</g>\n",
       "<!-- var6341068275337658369&#45;&gt;var6341068275337658370 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>var6341068275337658369&#45;&gt;var6341068275337658370</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M54.22,-18C56.28,-18 58.38,-18 60.5,-18\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"60.23,-21.5 70.23,-18 60.23,-14.5 60.23,-21.5\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<gtbook.display.show at 0x117b25bb0>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: A Bayes net fragment modeling the effect of an action on the state.\n",
    "#| label: fig:bayes_net_fragment\n",
    "action_prior = gtsam.DiscreteDistribution(A[1], \"1/1/1/1\")\n",
    "fragment = gtsam.DiscreteBayesNet()\n",
    "fragment.add(motion_model)\n",
    "show(fragment, hints={\"A\": 2, \"X\": 1}, boxes={A[1][0], X[1][0]})"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "BSzxBEwgX3R8",
   "metadata": {},
   "source": [
    "By applying the belief transition equation above, we can compute the posterior probability $P(X_2|a_1)$ over $X_2$,\n",
    "since the action $a_1$ and the initial state $x_1$ are both completely known. \n",
    "Given values for the parent variables $A_1$ and $X_1$, we can examine the corresponding transition probability. \n",
    "\n",
    "The code in Figure [8](#fig:apply_motion_model) shows how to implement this, using the variable `motion_model` we defined early on in this section.\n",
    "In the example, if we start from the $x_1=\\text{Office}$ and attempt to go right, i.e., action $a_1=\\text{R}$, we obtain the probability over the next state $X_2$, showing that we move to the hallway with 80% probability, and stay in the office with 20% probability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "uLHqYw1-8HYB",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<p>  <i>P(X2):</i></p>\n",
       "<div>\n",
       "<table class='DecisionTreeFactor'>\n",
       "  <thead>\n",
       "    <tr><th>X2</th><th>value</th></tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr><th>Living Room</th><td>0</td></tr>\n",
       "    <tr><th>Kitchen</th><td>0</td></tr>\n",
       "    <tr><th>Office</th><td>0.2</td></tr>\n",
       "    <tr><th>Hallway</th><td>0.8</td></tr>\n",
       "    <tr><th>Dining Room</th><td>0</td></tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "<gtbook.display.pretty at 0x117b25af0>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: The result of applying the motion model to a specific state and action.\n",
    "#| label: fig:apply_motion_model\n",
    "values = VARIABLES.assignment({X[1]: \"Office\", A[1]: \"R\"})\n",
    "pretty(motion_model.choose(values))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9Wa-RrjgQrQ8",
   "metadata": {},
   "source": [
    "This idea can be extended to arbitrarily many actions by merely adding action and state nodes for each\n",
    "time step $k$. A code example is shown in code in Figure [9](#fig:controlled_markov_chain), where we create a controlled Markov chain with three states."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "Cnte_Mg6Qy52",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (0)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"116pt\"\n",
       " viewBox=\"0.00 0.00 206.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-112 202,-112 202,4 -4,4\"/>\n",
       "<!-- var4683743612465315841 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>var4683743612465315841</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"54,-108 0,-108 0,-72 54,-72 54,-108\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">A1</text>\n",
       "</g>\n",
       "<!-- var6341068275337658370 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>var6341068275337658370</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">X2</text>\n",
       "</g>\n",
       "<!-- var4683743612465315841&#45;&gt;var6341068275337658370 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>var4683743612465315841&#45;&gt;var6341068275337658370</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M45.17,-71.83C54.54,-62.46 66.07,-50.93 76.05,-40.95\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"78.33,-43.62 82.92,-34.08 73.38,-38.67 78.33,-43.62\"/>\n",
       "</g>\n",
       "<!-- var4683743612465315842 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>var4683743612465315842</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"126,-108 72,-108 72,-72 126,-72 126,-108\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">A2</text>\n",
       "</g>\n",
       "<!-- var6341068275337658371 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>var6341068275337658371</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">X3</text>\n",
       "</g>\n",
       "<!-- var4683743612465315842&#45;&gt;var6341068275337658371 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>var4683743612465315842&#45;&gt;var6341068275337658371</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M117.17,-71.83C126.54,-62.46 138.07,-50.93 148.05,-40.95\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"150.33,-43.62 154.92,-34.08 145.38,-38.67 150.33,-43.62\"/>\n",
       "</g>\n",
       "<!-- var6341068275337658369 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>var6341068275337658369</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">X1</text>\n",
       "</g>\n",
       "<!-- var6341068275337658369&#45;&gt;var6341068275337658370 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>var6341068275337658369&#45;&gt;var6341068275337658370</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M54.22,-18C56.28,-18 58.38,-18 60.5,-18\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"60.23,-21.5 70.23,-18 60.23,-14.5 60.23,-21.5\"/>\n",
       "</g>\n",
       "<!-- var6341068275337658370&#45;&gt;var6341068275337658371 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>var6341068275337658370&#45;&gt;var6341068275337658371</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.22,-18C128.28,-18 130.38,-18 132.5,-18\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"132.23,-21.5 142.23,-18 132.23,-14.5 132.23,-21.5\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<gtbook.display.show at 0x117b25cd0>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: Concatenating Bayes net fragments into a controlled Markov chain.\n",
    "#| label: fig:controlled_markov_chain\n",
    "A = VARIABLES.discrete_series(\"A\", range(1, N), vacuum.action_space) # actions for times 1...N-1\n",
    "bayesNet = gtsam.DiscreteBayesNet()\n",
    "bayesNet.add(state_prior)\n",
    "for k in range(1, N):\n",
    "    bayesNet.add(X[k+1], [X[k], A[k]], vacuum.action_spec) # add creates conditional and adds\n",
    "show(bayesNet, hints={\"A\":2, \"X\":1}, boxes={A[1][0],A[2][0]})"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "-S6oPptgmGTE",
   "metadata": {},
   "source": [
    "The example just shows the graphical model as produced by the three-state code fragment. It is not yet obvious how to obtain the posterior over $X_3$ in this two-step example. We explore that below.\n",
    "\n",
    "### Exercise\n",
    "\n",
    "Try varying the value of $N$ to create other examples."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "plQvgVHN8D20",
   "metadata": {},
   "source": [
    "```{index} forward simulation\n",
    "```\n",
    "```{index} sampling; from Markov chains\n",
    "```\n",
    "## Forward Simulation\n",
    "\n",
    "> Sampling from Markov chains.\n",
    "\n",
    "We can use simulation in a graphical model to explore what a sequence of\n",
    "actions might yield as an outcome. \n",
    "Because the (controlled) Markov chains above are specified as a set of conditional distributions, and we have already seen how to sample from those, we just need to know in what order to sample them.\n",
    "Indeed: to sample from a conditional distribution $p(X|Y)$ we need to make sure we sample the variable $Y$ *beforehand*, and then proceed simply by selecting the appropriate probability distribution,\n",
    "depending on the value of $Y$. We can then\n",
    "proceed as before using the inverse transform sampling method.\n",
    "\n",
    "Forward sampling in a Markov chain simply repeats these steps in\n",
    "succession, proceeding from left to right, because that ensures that we always have the condition before we attempt sampling from the conditional. \n",
    "Simulating a robot *given* an initial state $X_1$ and \n",
    "sequence of actions $a_{1}, a_{2},\\ldots$ is then equivalent to sampling from this Markov chain:\n",
    "\n",
    "1.  Set $k=1$, and we assume $X_1$ is known.\n",
    "\n",
    "2.  Simulate the effect of the next action $A_k$ by sampling the next state\n",
    "    $x_{k+1}$ from \n",
    "    \\begin{equation}\n",
    "    x_{x+1} \\sim P(X_{k+1}|X_k=x_k,A_k=a_k).\n",
    "    \\end{equation}\n",
    "\n",
    "3.  Increment $k$ and return to step $2$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7gM_1TYiDRPY",
   "metadata": {},
   "source": [
    "```{index} rollout\n",
    "```\n",
    "Figure [10](#fig:sample_markov_chain) illustrates how to code this up and shows 4 different **rollouts** by simulating in this way. \n",
    "Rollouts will be discussed in more detail in Section 3.5. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "crDuPAT3IULp",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Office', 'Office', 'Office']\n",
      "['Office', 'Hallway', 'Hallway']\n",
      "['Office', 'Hallway', 'Living Room']\n",
      "['Office', 'Office', 'Office']\n"
     ]
    }
   ],
   "source": [
    "#| caption: A simple example of sampling from a controlled Markov chain.\n",
    "#| label: fig:sample_markov_chain\n",
    "def sample(x1, a1, a2):\n",
    "    values = VARIABLES.assignment({X[1]: x1, A[1]: a1})  # initial state and action\n",
    "    x2 = vacuum.rooms[bayesNet.at(1).sample(values)]\n",
    "    values = VARIABLES.assignment({X[2]: x2, A[2]: a2})  # next state and action\n",
    "    x3 = vacuum.rooms[bayesNet.at(2).sample(values)]\n",
    "    return [x1, x2, x3]\n",
    "\n",
    "\n",
    "for i in range(4):\n",
    "    print(sample(\"Office\", \"R\", \"U\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "RRRMrvFUvqIN",
   "metadata": {},
   "source": [
    "While simple, simulating from a forward model is a rather important\n",
    "technique, and underlies some of the recent successes in deep\n",
    "reinforcement learning, as well as the success of DeepMind in beating\n",
    "the world’s best players of the game of Go {cite:p}`Silver16_alphago`.\n",
    "\n",
    "### Exercises\n",
    "\n",
    "1. Generalize the above forward sampling algorithm to an arbitrary number of actions. Hint: you will have to make sure the variables are defined, and the graphical model is extended properly.\n",
    "2. Empirically estimate the probability distribution of the final state by constructing a\n",
    "histogram over the possible values of the state."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "r1oTGbxDxUKm",
   "metadata": {},
   "source": [
    "```{index} pair: Bayesian network; Bayes net\n",
    "```\n",
    "## Bayesian Networks\n",
    "\n",
    "```{index} generative model\n",
    "```\n",
    ">  Bayes nets provide a graphical language to string together conditional probabilities into a generative world model.\n",
    "\n",
    "```{index} pair: directed acyclic graph; DAG\n",
    "```\n",
    "```{index} factored probability distribution\n",
    "```\n",
    "A Markov chain is a special case of the more general **Bayesian network** or **Bayes net**.\n",
    "A Bayes net is a directed *acyclic* graph (DAG) describing a factored\n",
    "probability distribution over a set of random variables. \n",
    "By the term *factored probability distribution*, we mean that the\n",
    "probability distribution is expressed as a product of factors, \n",
    "which in Bayes nets are always conditional distributions."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "Ym8FdZf-EdLb",
   "metadata": {},
   "source": [
    "The code in Figure [11](#fig:general_bayes_net) uses GTSAM to creates a Bayes net, which we can then display.\n",
    "We formally define Bayes nets below that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "rFUB-kMP2AJY",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (0)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"128pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 128.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 124,-256 124,4 -4,4\"/>\n",
       "<!-- var5 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>var5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">W</text>\n",
       "</g>\n",
       "<!-- var6 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>var6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"55\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"55\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">X</text>\n",
       "</g>\n",
       "<!-- var6&#45;&gt;var5 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>var6&#45;&gt;var5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M48.36,-72.41C45.23,-64.57 41.4,-54.99 37.85,-46.13\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"41.11,-44.86 34.15,-36.88 34.61,-47.46 41.11,-44.86\"/>\n",
       "</g>\n",
       "<!-- var7 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>var7</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"93\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"93\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">Y</text>\n",
       "</g>\n",
       "<!-- var7&#45;&gt;var6 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>var7&#45;&gt;var6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M84.19,-144.76C79.73,-136.55 74.2,-126.37 69.16,-117.09\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.33,-115.6 64.49,-108.48 66.18,-118.94 72.33,-115.6\"/>\n",
       "</g>\n",
       "<!-- var8 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>var8</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"38\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"38\" y=\"-228.95\" font-family=\"Times,serif\" font-size=\"14.00\">Z</text>\n",
       "</g>\n",
       "<!-- var8&#45;&gt;var5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>var8&#45;&gt;var5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.85,-216.12C27.14,-186.86 15.04,-124.76 19,-72 19.6,-63.99 20.71,-55.35 21.91,-47.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"25.35,-48.04 23.51,-37.61 18.45,-46.91 25.35,-48.04\"/>\n",
       "</g>\n",
       "<!-- var8&#45;&gt;var6 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>var8&#45;&gt;var6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M40.08,-215.59C42.95,-191.61 48.16,-148.14 51.6,-119.42\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"55.06,-119.96 52.77,-109.61 48.11,-119.13 55.06,-119.96\"/>\n",
       "</g>\n",
       "<!-- var8&#45;&gt;var7 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>var8&#45;&gt;var7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M50.21,-217.46C57.11,-208.67 65.91,-197.48 73.73,-187.53\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"76.47,-189.71 79.89,-179.68 70.96,-185.38 76.47,-189.71\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<gtbook.display.show at 0x117b34fa0>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: A general Bayes net on four discrete variables.\n",
    "#| label: fig:general_bayes_net\n",
    "wxyz = gtsam.DiscreteBayesNet()\n",
    "W1 = VARIABLES.binary(\"W\")\n",
    "X1 = VARIABLES.binary(\"X\")\n",
    "Y1 = VARIABLES.binary(\"Y\")\n",
    "Z1 = VARIABLES.binary(\"Z\")\n",
    "wxyz.add(W1, [X1, Z1], \"1/1 1/1 1/1 1/1\")\n",
    "wxyz.add(X1, [Y1, Z1], \"1/1 1/1 1/1 1/1\")\n",
    "wxyz.add(Y1, [Z1], \"1/1 1/1\")\n",
    "wxyz.add(Z1, \"1/1\")\n",
    "show(wxyz)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "PCRCCHAEwpvK",
   "metadata": {},
   "source": [
    "The example Bayes net in Figure [11](#fig:general_bayes_net) is simply a graphical representation of which random variables’\n",
    "CPT (conditional probability table) depend on which other variables.\n",
    "Formally, in Bayes nets, the joint probability distribution $P(X_1, \\dots , X_n)$ over a set\n",
    "of random variables $X_1, \\dots, X_n$ can be computed as the product of\n",
    "$n$ conditional probabilities associated with each of the individual variables $X_i$ as\n",
    "```{math}\n",
    ":label: bn_is_product\n",
    "P(X_1, \\dots , X_n) = \\prod_{i=1}^{n} P(X_{i} | \\Pi_{i})\n",
    "```\n",
    "where $n$ is the number of variables, and $\\Pi_{i}$ denotes the set of parents for variable\n",
    "$X_{i}$ in the directed graph.\n",
    "\n",
    "In the example, the joint distribution can then be read off as\n",
    "\\begin{equation}\n",
    "P(W, X, Y, Z) = P(W | X, Z) P(X | Y, Z) P(Y | Z) P(Z).\n",
    "\\end{equation}\n",
    "Note that the order in which\n",
    "we multiply the conditionals does not matter, but we typically prefer to put the parents more towards the right, as above.\n",
    "Finally, note that the above graph has cycles, but the cycles are only in the underlying *undirected* graph, not in the directed graph.\n",
    "Directed cycles, i.e., cycles with a consistent direction, are not allowed."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "vpKgJlg5vmNd",
   "metadata": {},
   "source": [
    "Bayes nets can be very efficient representations of complex\n",
    "probability distributions, as they encode the dependence and especially\n",
    "independence relationships between the variables.\n",
    "The Bayes net above was created assuming binary variables, and hence did not take\n",
    "a lot of effort to specify, but as we saw above, even for relatively small state spaces \n",
    "the complexity of specifying CPTs can be daunting.\n",
    "\n",
    "If we were to construct a full table of probabilities for each possible\n",
    "outcome of the variables $W$, $X$, $Y$, and $Z$, the table could be quite long. \n",
    "For example, if we assume they all have 10 possible values, \n",
    "then the table required to represent the full joint distribution will have $10^{4}$ entries,\n",
    "i.e., $10,000$ unique values. You\n",
    "can save a tiny bit, because they have to sum up to 1, so strictly\n",
    "speaking we need only $9,999$ values. In contrast, we can tally how many\n",
    "entries all four CPT tables have for the Bayes net above. \n",
    "This is shown in the following table:\n",
    "\n",
    "|     CPT     | \\# entries |\n",
    "|-------------|------------|\n",
    "|   *P(Z)*    |      9     |\n",
    "|  *P(Y\\|Z)*  |     90     |\n",
    "| *P(X\\|Y,Z)* |     900    |\n",
    "| *P(W\\|X,Z)* |     900    |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "UBFQ6LCFby-r",
   "metadata": {},
   "source": [
    "For example, $P(X|Y,Z)$ has 900 entries, i.e., 9\n",
    "(independent) entries for each of 100 possible combinations of $Y$ and\n",
    "$Z$. Hence, the total number of parameters we need is only $1,899$,\n",
    "which is significantly less than $9,999$.\n",
    "\n",
    "### Exercise\n",
    "\n",
    "What are the savings for the *binary* version of the graph that we created, i.e., where variables are either `True` or `False`? You should find the savings are much less."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "A8IyEPa9vFSw",
   "metadata": {},
   "source": [
    "## Factored State Representations*\n",
    "\n",
    "> We can save even more by factoring the state.\n",
    "\n",
    "Factored state representations are useful if the state of the robot can\n",
    "be described using features that are relatively independent of each\n",
    "other. Continuing our example, the robot vacuum cleaner might also run\n",
    "out of battery power, so we could associate a different variable with\n",
    "its battery status, e.g., `empty`, `half`, or `full`.\n",
    "The state of the robot would then be specified by the combination of\n",
    "two variables: the room the robot is in, and its battery status. \n",
    "Note that now the total number of possible states\n",
    "is combinatorial: if there are five rooms and three different battery\n",
    "levels, we have a total of 15 possible states for the robot.\n",
    "\n",
    "A possible model for battery life could be the following transition table, which is independent of which action was taken, and will always progress from `full` to `half`, then from `half` to `empty`, and of course once the battery is empty it will stay empty:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "B3OMd8CKZmrI",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<p>  <i>P(B2|B1):</i></p>\n",
       "<table class='DiscreteConditional'>\n",
       "  <thead>\n",
       "    <tr><th><i>B1</i></th><th>full</th><th>half</th><th>empty</th></tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr><th>full</th><td>0.9</td><td>0.1</td><td>0</td></tr>\n",
       "    <tr><th>half</th><td>0</td><td>0.9</td><td>0.1</td></tr>\n",
       "    <tr><th>empty</th><td>0</td><td>0</td><td>1</td></tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "<gtbook.display.pretty at 0x117b349d0>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "battery_states = [\"full\", \"half\", \"empty\"]\n",
    "B = VARIABLES.discrete_series(\"B\", range(1,N+1), battery_states)\n",
    "spec_b = \"9/1/0 0/9/1 0/0/1 \"\n",
    "pretty(gtsam.DiscreteConditional(B[2], [B[1]], spec_b))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "iCryZhsPIdPG",
   "metadata": {},
   "source": [
    "The graphical model approach allows us to easily extend probabilistic\n",
    "actions to factored state representations.\n",
    "The code in Figure [12](#fig:factored_bayes_net) shows one way to do it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "xbIBwGtSaB_Z",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 9.0.0 (0)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"188pt\"\n",
       " viewBox=\"0.00 0.00 206.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 202,-184 202,4 -4,4\"/>\n",
       "<!-- var4683743612465315841 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>var4683743612465315841</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"54,-180 0,-180 0,-144 54,-144 54,-180\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">A1</text>\n",
       "</g>\n",
       "<!-- var4755801206503243778 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>var4755801206503243778</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">B2</text>\n",
       "</g>\n",
       "<!-- var4683743612465315841&#45;&gt;var4755801206503243778 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>var4683743612465315841&#45;&gt;var4755801206503243778</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M36.12,-143.76C48.53,-118.93 70.86,-74.28 85.29,-45.41\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"88.38,-47.06 89.73,-36.55 82.12,-43.93 88.38,-47.06\"/>\n",
       "</g>\n",
       "<!-- var6341068275337658370 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>var6341068275337658370</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">X2</text>\n",
       "</g>\n",
       "<!-- var4683743612465315841&#45;&gt;var6341068275337658370 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>var4683743612465315841&#45;&gt;var6341068275337658370</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M45.17,-143.83C54.54,-134.46 66.07,-122.93 76.05,-112.95\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"78.33,-115.62 82.92,-106.08 73.38,-110.67 78.33,-115.62\"/>\n",
       "</g>\n",
       "<!-- var4683743612465315842 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>var4683743612465315842</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"126,-180 72,-180 72,-144 126,-144 126,-180\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">A2</text>\n",
       "</g>\n",
       "<!-- var4755801206503243779 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>var4755801206503243779</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">B3</text>\n",
       "</g>\n",
       "<!-- var4683743612465315842&#45;&gt;var4755801206503243779 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>var4683743612465315842&#45;&gt;var4755801206503243779</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.12,-143.76C120.53,-118.93 142.86,-74.28 157.29,-45.41\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"160.38,-47.06 161.73,-36.55 154.12,-43.93 160.38,-47.06\"/>\n",
       "</g>\n",
       "<!-- var6341068275337658371 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>var6341068275337658371</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">X3</text>\n",
       "</g>\n",
       "<!-- var4683743612465315842&#45;&gt;var6341068275337658371 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>var4683743612465315842&#45;&gt;var6341068275337658371</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M117.17,-143.83C126.54,-134.46 138.07,-122.93 148.05,-112.95\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"150.33,-115.62 154.92,-106.08 145.38,-110.67 150.33,-115.62\"/>\n",
       "</g>\n",
       "<!-- var4755801206503243777 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>var4755801206503243777</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">B1</text>\n",
       "</g>\n",
       "<!-- var4755801206503243777&#45;&gt;var4755801206503243778 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>var4755801206503243777&#45;&gt;var4755801206503243778</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M54.22,-18C56.28,-18 58.38,-18 60.5,-18\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"60.23,-21.5 70.23,-18 60.23,-14.5 60.23,-21.5\"/>\n",
       "</g>\n",
       "<!-- var4755801206503243778&#45;&gt;var4755801206503243779 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>var4755801206503243778&#45;&gt;var4755801206503243779</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.22,-18C128.28,-18 130.38,-18 132.5,-18\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"132.23,-21.5 142.23,-18 132.23,-14.5 132.23,-21.5\"/>\n",
       "</g>\n",
       "<!-- var6341068275337658369 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>var6341068275337658369</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">X1</text>\n",
       "</g>\n",
       "<!-- var6341068275337658369&#45;&gt;var6341068275337658370 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>var6341068275337658369&#45;&gt;var6341068275337658370</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M54.22,-90C56.28,-90 58.38,-90 60.5,-90\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"60.23,-93.5 70.23,-90 60.23,-86.5 60.23,-93.5\"/>\n",
       "</g>\n",
       "<!-- var6341068275337658370&#45;&gt;var6341068275337658371 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>var6341068275337658370&#45;&gt;var6341068275337658371</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.22,-90C128.28,-90 130.38,-90 132.5,-90\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"132.23,-93.5 142.23,-90 132.23,-86.5 132.23,-93.5\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<gtbook.display.show at 0x11121ed00>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: A factored Bayes net for the vacuum cleaner problem.\n",
    "#| label: fig:factored_bayes_net\n",
    "factored = gtsam.DiscreteBayesNet()\n",
    "factored.add(state_prior)\n",
    "factored.add(B[1], [], \"1/0/0\") # initial battery state\n",
    "for k in range(1, N):\n",
    "    factored.add(X[k+1], [X[k], A[k]], vacuum.action_spec) # motion model for location\n",
    "    factored.add(B[k+1], [A[k], B[k]], \"\".join([spec_b]*4)) # battery evolution model\n",
    "\n",
    "show(factored, hints={\"A\":2, \"X\":1, \"B\":0}, boxes={A[1][0],A[2][0]})"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "CnbTQgetcFfv",
   "metadata": {},
   "source": [
    "You can see that under the transition models chosen, there are now Markov chains, and these are indpendent when the action sequence is *given*."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "yMnLCbLX0p1s",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "Note that the above model makes a number of strong statements about the nature of the world:\n",
    "1. The next battery state does not depend on where we are in the world. This seems like an OK assumption. Still, can you think of situations where this is not a realistic assumption?\n",
    "2. The next state does not depend on the battery life. Maybe this is not so defensible: clearly, if the battery is empty the robot cannot move, and the next state is the same as the previous state. It is worthwhile to think about what you would change above to make a more realistic model of the world."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hMNTpXY3t5lj",
   "metadata": {},
   "source": [
    "## GTSAM 101\n",
    "\n",
    "> The GTSAM concepts used in this section, explained.\n",
    "\n",
    "As in Chapter 2, we once again used a `gtsam.DiscreteConditional`, this time to specify a motion model for the controlled Markov chain above, as shown in Figure [4](#vacuum-motion-model)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1GGXFMgV1VUb",
   "metadata": {},
   "source": [
    "To specify the motion model, we used the `gtsam.DiscreteBayesNet` class, and in particular these methods:\n",
    "\n",
    "- `add(self:, key: Tuple[int, int], parents: List[Tuple[int, int]], spec: str) -> None`: adds a conditional with the same arguments as the `gtsam.DiscreteConditional` constructor.\n",
    "- `at(self, i: int) -> gtsam.DiscreteConditional`: retrieves the $i^{th}$ conditional added."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fmxOt0YIe36N",
   "metadata": {},
   "source": [
    "In the last subsection we used a sleight of hand to extend the battery depletion model to depend on the navigation action.\n",
    "The following is a bit of python code that replicates the battery specification `spec_b` four times:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "YqUj4ECTuivA",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9/1/0 0/9/1 0/0/1 9/1/0 0/9/1 0/0/1 9/1/0 0/9/1 0/0/1 9/1/0 0/9/1 0/0/1 \n"
     ]
    }
   ],
   "source": [
    "# Replicate spec_b 4 times and print the result\n",
    "spec = \"\".join([spec_b]*4)\n",
    "print(spec)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ww_b1Rz40xP",
   "metadata": {},
   "source": [
    "We then made sure to specify the action *before* the previous battery state, so that the string above works out. In Figure [3.18](#fig:replicated_cpt) we pretty-print to  verify that this came out right. Of course, it is entirely possible to make the battery model *dependent* on the action chosen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "6T5VnUVEZtgi",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<p>  <i>P(B2|A2,B1):</i></p>\n",
       "<table class='DiscreteConditional'>\n",
       "  <thead>\n",
       "    <tr><th><i>A2</i></th><th><i>B1</i></th><th>full</th><th>half</th><th>empty</th></tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr><th>L</th><th>full</th><td>0.9</td><td>0.1</td><td>0</td></tr>\n",
       "    <tr><th>L</th><th>half</th><td>0</td><td>0.9</td><td>0.1</td></tr>\n",
       "    <tr><th>L</th><th>empty</th><td>0</td><td>0</td><td>1</td></tr>\n",
       "    <tr><th>R</th><th>full</th><td>0.9</td><td>0.1</td><td>0</td></tr>\n",
       "    <tr><th>R</th><th>half</th><td>0</td><td>0.9</td><td>0.1</td></tr>\n",
       "    <tr><th>R</th><th>empty</th><td>0</td><td>0</td><td>1</td></tr>\n",
       "    <tr><th>U</th><th>full</th><td>0.9</td><td>0.1</td><td>0</td></tr>\n",
       "    <tr><th>U</th><th>half</th><td>0</td><td>0.9</td><td>0.1</td></tr>\n",
       "    <tr><th>U</th><th>empty</th><td>0</td><td>0</td><td>1</td></tr>\n",
       "    <tr><th>D</th><th>full</th><td>0.9</td><td>0.1</td><td>0</td></tr>\n",
       "    <tr><th>D</th><th>half</th><td>0</td><td>0.9</td><td>0.1</td></tr>\n",
       "    <tr><th>D</th><th>empty</th><td>0</td><td>0</td><td>1</td></tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "<gtbook.display.pretty at 0x11121e5b0>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: CPT created by replicated specification.\n",
    "#| label: fig:replicated_cpt\n",
    "pretty(gtsam.DiscreteConditional(B[2], [A[2], B[1]], spec))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22gJu5XkegOn",
   "metadata": {},
   "source": [
    "Finally, a word about the graphs above. You might wonder, why these graphs come out so beautifully positioned, e.g., to indicate time from left to right. This was accomplished with the `hints` argument, which positions variables series at an appropriate height. Similarly, the `boxes` argument (which takes `gtsam.Keys`, not tuples) indicates which variables should considered as given.\n",
    "\n",
    "These arguments are handled in the `gtbook` library {cite:p}`gtbook`, and are passed on in the appropriate format to the underlying GTSAM `dot` methods, which generate graphviz-style graphs{cite:p}`graphviz`."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyOWJ1do7sX2VVOgPTc45upi",
   "include_colab_link": true,
   "name": "S32_vacuum_actions.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "gtbook",
   "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.9.19"
  },
  "latex_metadata": {
   "affiliation": "Georgia Institute of Technology",
   "author": "Frank Dellaert and Seth Hutchinson",
   "title": "Introduction to Robotics"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}