{ "cells": [ { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github", "tags": [ "no-tex" ] }, "source": [ "\"Open" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "id": "w-CIikP0ZZnm", "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 -q -U gtbook" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "id": "uef6Kglzcrha", "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "from gtbook.discrete import Variables\n", "from gtbook.display import pretty\n", "\n", "import numpy as np\n", "import pandas as pd\n", "import gtsam\n", "\n", "import plotly.express as px\n", "try:\n", " import google.colab\n", "except:\n", " import plotly.io as pio\n", " pio.renderers.default = \"png\"\n", "\n", "import gtbook\n", "VARIABLES = Variables()\n", "def pretty(obj): \n", " return gtbook.display.pretty(obj, VARIABLES)" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "TP6jRdj2ccW1" }, "source": [ "```{index} action; discrete actions\n", "```\n", "\n", "# Actions for Sorting Trash\n", "\n", ">Robots change the world through their actions. Action models capture their salient aspects.\n", "\n", "\n", "\"Splash" ] }, { "cell_type": "markdown", "metadata": { "id": "kh41s6J2ccW2" }, "source": [ "Robots decide how to act in the world by reasoning about how their actions can be used to achieve their goals, given the current state of the world.\n", "At a high level, actions can be represented by symbolic descriptions of their effects (changes that will occur in the world state when the action is executed)\n", "and by their preconditions (things that must be true in the current state in order to execute the action).\n", "The robot's goals can be encoded as a symbolic description of the desired world state, or, as we will do now,\n", "by assigning a cost executing an action in a particular world state.\n", "Note that assigning a cost to an action is equivalent to assigning a reward (merely multiply the cost by -1 to obtain a reward).\n", "If we use a cost-based approach, we generally frame the planning problem as a decision problem: choose the action that minimizes cost.\n", "If we are interested in long time horizons, we would choose the sequence of actions that minimize cost over the chosen time period.\n", "If there are uncertainties, either in the world state or in the effects of actions, we would minimize the expected value of the cost.\n", "\n", "In this section, we will consider only the problem of evaluating\n", "the cost of a single action based on limited knowledge of the world.\n", "In particular, we will assume that the robot has only the prior probability distribution\n", "on categories described in the previous section.\n", "We will address the more general problem of planning (i.e., choosing which actions to apply in the\n", "current context) later in the chapter." ] }, { "cell_type": "markdown", "metadata": { "id": "5_gRa4NQZsD4" }, "source": [ "## Modeling Actions and Their Effects\n", "\n", "> For a trash sorting robot, the destination bin is the most important aspect of an action.\n", "\n", "For our trash sorting robot, we will define four actions, each of which can be executed when\n", "there is an item of trash in the work space (i.e., there are no preconditions for the actions).\n", "The first three actions use the robot manipulator to move an item of trash\n", "to one of three bins: glass, metal, or mixed paper.\n", "The fourth action is a nop,\n", "which corresponds to the robot simply allowing the item to\n", "pass through the work space, to be processed, for example, by a human worker\n", "(note that \"nop\" is a shorthand used in many programming languages\n", "to denote \"no operation\").\n", "\n", "We assign labels to these actions as follows:\n", "\n", "* $a_1$: put in glass bin\n", "* $a_2$: put in metal bin\n", "* $a_3$: put in mixed paper bin\n", "* $a_4$: nop (let the object continue, unsorted)\n", "\n", "and each of these actions can be applied at any stage of execution.\n", "\n", "If the robot had perfect knowledge of the world state (i.e., if the robot always knew\n", "exactly the category of the item in the work space), choosing an action would be simple:\n", "place paper and scrap cardboard in the paper bin; place cans and scrap metal in the metal bin;\n", "place bottles in the glass bin. The nop action would never be used.\n", "But what if the robot's knowledge of the world state is uncertain?\n", "Suppose, for example, that it sometimes mistakes scrap metal for cardboard.\n", "Placing scrap metal in the paper bin could lead to significant damage to\n", "trash processing equipment, possibly requiring the facility to shut down completely\n", "while repairs are made.\n", "In contrast, if the robot places paper into the metal bin, serious damage is unlikely, and the cost of this wrong decision would likely be much smaller.\n", "\n", "In order to make informed decisions about which action to take,\n", "the robot needs to have some quantitative way to evaluate the cost of\n", "executing the wrong actions.\n", "This begins by assigning a cost to each action, depending on the world\n", "state when the action is executed.\n", "\n", "For this example, we will assign zero cost when the robot executes the correct action,\n", "and positive value costs when wrong actions are executed, depending on the severity\n", "of the consequence. We can encode these costs into a table using the following code." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 175 }, "id": "wVPAl8gdccW3", "outputId": "e0da3179-ed58-4c17-c195-8c5921bffba5" }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
cardboardpapercanscrap metalbottle
glass bin22460
metal bin11002
paper bin005103
nop11111
\n", "
" ], "text/plain": [ " cardboard paper can scrap metal bottle\n", "glass bin 2 2 4 6 0\n", "metal bin 1 1 0 0 2\n", "paper bin 0 0 5 10 3\n", "nop 1 1 1 1 1" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "categories = [\"cardboard\", \"paper\", \"can\", \"scrap metal\", \"bottle\"]\n", "actions = [\"glass bin\", \"metal bin\", \"paper bin\", \"nop\"]\n", "cost = np.array([[2, 2, 4, 6, 0],\n", " [1, 1, 0, 0, 2],\n", " [0, 0, 5, 10, 3],\n", " [1, 1, 1, 1, 1]])\n", "pd.DataFrame(cost, index=actions, columns=categories)\n" ] }, { "cell_type": "markdown", "metadata": { "id": "5DPv9ncuccW4" }, "source": [ "Note that the cost of making the correct decision (e.g., placing cardboard into the paper bin) is zero, and the cost of wrong decisions is a positive number that reflects the damage done to processing machinery for the specific cases. Furthermore, we have assigned a unit cost to executing the nop action (i.e., letting the trash item pass, unsorted). This latter cost assignment depends, of course, of what happens at the downstream sorting stages, but we ignore such effects here.\n", "\n", "If the robot knew the state of the world with certainty, planning would amount to merely choosing at each\n", "moment the action that minimizes the cost. For our trash sorting problem, this approach would uniquely\n", "define which action to take as a function of the world state.\n", "When the state of the world is uncertain, we can use probability theory\n", "to define a solution strategy." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "4tK1Vdi8R28c" }, "source": [ "## Discrete Random Variables\n", "\n", "> If the category is not known with certainty, then the cost of an action will be a random variable.\n", "\n", "Suppose the robot takes the naive decision to always place trash in the paper bin.\n", "What can we say about the cost associated to this action?\n", "We can immediately conclude that the cost will take its value from the set\n", "$\\{ 0, 3, 5, 10\\}$, since these are the only values that appear in the table of costs\n", "for this action.\n", "In the absence of any other information, this is really all that can be said about the\n", "cost that will be incurred by placing a newly arrived item of trash in the paper bin.\n", "But in our case, we have additional information in the form of the prior distribution\n", "on trash categories.\n", "Thus, we can view the cost of moving an item to the paper bin as a random quantity\n", "that takes its values from a finite set of numbers.\n", "\n", "We can compute the probabilities for the various values of cost by examining the outcomes\n", "that lead to those costs.\n", "The probability of paper is 0.2 and the probability of cardboard is 0.3. In each of these cases,\n", "the cost is zero. Therefore, we can conclude that the probability of zero cost is 0.5.\n", "Similarly, since the probability of a can is 0.25, the probability is 0.25 that the cost will be 5;\n", "the probability that the cost will be 10 is 0.2; and the probability that the cost will be 3\n", "is 0.05. And voilà, we have determined the complete probability distribution on cost, given\n", "that the robot always places items in the paper bin!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "```{index} random variable\n", "```\n", "\n", "In probability theory, a **random variable** is defined as a mapping from the sample space\n", "to real numbers, $X : \\Omega \\rightarrow \\mathbb{R}$.\n", "We typically use upper case letters to denote random variables, and we typically\n", "write $X$ instead of $X(\\omega)$.\n", "In this way, we deal directly with $X$, treating $X$ as a random quantity\n", "whose probability distribution is induced by the probability distribution on $\\Omega$.\n", "This is exactly what we did above, when we used the probability distribution on\n", "categories to infer the distribution on costs.\n", "\n", "```{index} random variable; discrete random variable\n", "```\n", "\n", "```{index} pair: probability mass function; PMF\n", "```\n", "\n", "A **discrete random variable** is defined as a random variable that takes values \n", "from a finite (or even countably infinite) set. The probability distribution\n", "for a discrete random variable is called a **probability mass function** or **PMF**.\n", "The pmf for random variable $X$ is typically denoted by $p_X$ or simply by $p$\n", "when the context makes clear the random variable under consideration. Discrete random variables\n", "and pmf's are key concepts in the development of probability theory,\n", "and they will be key in our treatment of uncertainty for robotics applications.\n", "\n", "Let us denote by $X$ the cost of moving an item of trash to the paper bin.\n", "We use lower case letters to denote values that can be taken by random variables;\n", "in this case $x$ denotes a value taken by the random variable $X$.\n", "The pmf $p_X$ can be represented in tabular form as follows:\n", "\n", "| $x$ | $p_X(x)$ |\n", "|----------------|:------:|\n", "| 0 | 0.50 |\n", "| 3 | 0.05 |\n", "| 5 | 0.25 |\n", "| 10 | 0.20 |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We could apply this same approach for each of the possible actions, and then use the resulting\n", "PMFs to make decisions about which actions to apply. We will discuss such an approach\n", "to planning a bit later in this chapter." ] }, { "cell_type": "markdown", "metadata": { "id": "wTjUvyLVcb7v" }, "source": [ "```{index} expectation, expected value\n", "```\n", "## Expectation\n", "\n", "For many robotics applications, we hope that the robot will operate for a long period of time.\n", "We might hope for our trash sorting robot to operate for weeks, months, or longer, placing many pieces\n", "of trash into bins over the course of its operation.\n", "Suppose again that the robot merely always chooses to place trash in the paper bin.\n", "What can we say about the cost that will accrue over the robot's lifetime?\n", "With probability theory, we are unable to say anything definitive about a particular outcome;\n", "however, we *can* say things about average behavior over many trials.\n", "This is the concept of **expectation** in probability theory.\n", "\n", "Suppose that the random variable $X$ takes its values from a finite set,\n", "$X \\in \\{ x_1, \\dots , x_n \\}$.\n", "The **expected value** of $X$, which we denote by $E[X]$ is defined\n", "by\n", "\n", "$$E[X] = \\sum_{i=1}^n x_i p_X(x_i)$$\n", "\n", "For the example above, the expected value of cost, $E[X]$, is given by\n", "\n", "$E[X] = (0 \\times 0.2) + (0 \\times 0.3) + (5 \\times 0.25) + (10 \\times 0.2) + (3 \\times 0.05) = 3.4$\n", "\n", "Note that we never really *expect* to see the cost $3.4$. The term *expected value* is a technical term,\n", "defined by the equation above. The expected value is related to what we would\n", "expect to see if we took the average over many trials. \n", "As an example, if we roll a fair, six-sided die\n", "and let $X$ denote the number of dots on the top face, it is easy to show that $E[X] = 3.5$. Of course\n", "we will never roll a $3.5$, but if we roll the die 100 times and take the average of those rolls, we would expect that average to be near $3.5$.\n", "We will discuss this in more detail below.\n" ] }, { "cell_type": "markdown", "metadata": { "id": "H01bqJfbR28f" }, "source": [ "In python, we can compute the expected cost for each action by merely multiplying the $4\\times5$ cost matrix with the $5\\times1$ PMF:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "

P(Category):

\n", "
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Categoryvalue
cardboard0.2
paper0.3
can0.25
scrap metal0.2
bottle0.05
\n", "
" ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Category = VARIABLES.discrete(\"Category\", categories)\n", "category_prior = gtsam.DiscreteDistribution(Category, \"200/300/250/200/50\")\n", "pretty(category_prior)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "L38Db44xR28f", "outputId": "e7716cb8-bcf6-4911-c400-1365b26bf3eb" }, "outputs": [ { "data": { "text/plain": [ "array([3.2, 0.6, 3.4, 1. ])" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cost @ category_prior.pmf()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The result is an array in which each entry corresponds to the expected cost for a specific action.\n", "Thus, this array encapsulates everything we know about the expected costs of applying the four possible\n", "actions. We will use this later in the chapter to form a basis for simple planning.\n", "\n", "If it is not clear to you why this works, write out the expression for the matrix multiplication\n", "described above, and compare to the equations for the expected cost of each action." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Simulation by Sampling\n", "\n", "> It is easy to demonstrate the relationship between expectation and the average\n", "over many trials - simply sample and average!\n", "\n", "The code below computes the average cost over $N$ samples for a specified action.\n", "Try various values for $N$, and notice that as $N$ increases, the average tends\n", "to be an increasingly better approximation of the expected cost." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3.36\n" ] } ], "source": [ "# Sample N times, and evaluate the cost of executing the given action:\n", "total_cost = 0\n", "N = 100\n", "action = 0\n", "for i in range(N):\n", " category = category_prior.sample()\n", " total_cost += cost[action, category]\n", "print(total_cost/N)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For example, one experiment with $100$ samples yielded:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "cost_estimate = [3.14, 0.6, 4.01, 1.0]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "```{index} Probability theory\n", "```\n", "## Probability Theory vs. Statistics\n", "\n", "> Probability theory is the study of certain mathematical functions, while statistics are functions of data. The two are related, but different.\n", "\n", "Probability theory and statistics seem to be concerned with the same kinds of ideas, but they are two very\n", "different fields of study.\n", "\n", "**Probability theory** is the study of a certain class of mathematical functions (probability distributions).\n", "The modern, axiomatic approach to probability theory begins with three axioms, from which\n", "all other properties are derived:\n", "- For $A\\subseteq \\Omega$, $P(A) \\geq 0$\n", "- $P(\\Omega) = 1$\n", "- For $A_i, A_j \\subseteq \\Omega$, if $A_i \\cap A_j = \\emptyset$, then $P(A_i \\cup A_j) = P(A_i) + P(A_j)$.\n", "\n", " Probability theory does not consider the problem of how one might obtain the probability distribution $P$.\n", " Probability theorists take this as a given, along with the axioms.\n", " \n", " Expectation is a property of a probability distribution.\n", " For a discrete random variable $X$ with $\\Omega = \\{ x_1 \\dots x_n\\}$,\n", " $E[X]$ (also called the mean, and often denoted by $\\mu$)\n", " can be computed as above\n", "\n", "$$\\mu = E[X] = \\sum_{i=1}^n x_i p_X(x_i)$$\n", "\n", "The variance of a *random variable*,\n", "typically denoted by $\\sigma^2$, is merely the expected value of the squared difference between\n", "the random variable $X$ and the mean. The variance is also a property of probability distributions, and it can\n", "be computed as\n", "\n", "$$\\sigma^2 = E[(X-\\mu)^2] = \\sum_{i=1}^n p_X(x_i) (x_i - \\mu)^2 $$\n", "\n", "Note that the expressions for $\\mu$ and $\\sigma^2$ depend only on the probability distribution (in this case,\n", "the pmf $p_X$) and the values taken by the random variable $X$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "```{index} statistic, weak law of large numbers\n", "```\n", "A **statistic** is any function of data (including the identity function). \n", "Consider a set of measurements $\\{ z_1, \\dots z_N \\}$.\n", "The average of these values, often denoted by $\\bar{z}$, is a statistic, and it can be computed as\n", " \n", "$$\\bar{z} = \\frac{1}{N} \\sum_{i=1}^{N} z_i$$\n", "\n", "Likewise, the variance of the *data*, often denoted by $\\hat{\\sigma}^2$ can be computed as\n", "\n", "$$\\hat{\\sigma}^2 = \\frac{1}{N-1} \\sum_{i=1}^{N} (z_i- \\bar{z})^2$$\n", " \n", "Note that the definitions of $\\bar{z}$ and $\\hat{\\sigma}^2$ depend *only* on the data itself.\n", "\n", "Certain similarities are immediately obvious between these two sets of definitions.\n", "The mean of a random variable seems similar to the average of a data set.\n", "The variance of a random variable seems similar to the variance of a data set.\n", "\n", "In fact, if it happens that certain probability distributions do a good job of describing how the world behaves,\n", "then probability theory can provide a rigorous basis for a system of inference about data.\n", "As an example, if the data we observe behave according to the probability distribution $p_X$,\n", "then the average of the data will tend toward the expected value of $X$.\n", "This property can be written formally as the **weak law of large numbers**, which\n", "states that for any $\\epsilon > 0$, if $\\bar{z}_N$ denotes the average of a data set of size $N$,\n", "then\n", "\n", "$$\\lim_{N \\rightarrow \\infty} P( \\mid \\bar{z}_N - \\mu \\mid < \\epsilon ) = 1 $$\n", "\n", "i.e., the average of $N$ data points will become arbitrarily close to $\\mu$ as $N$ becomes\n", "large. This occurs with probability one, a nuance that we will not discuss here.\n", "This is one explanation for why simulation by sampling works, and why the results tend\n", "to improve with an increasing number of samples.\n", "\n", " The weak law of large numbers is only the first of many theorems that formalize the connections\n", " between probability theory and statistics, but most all of these theorems express variations\n", " on a simple concept: *as the size of a data set becomes large, the statistics of that data\n", " set will become increasingly good approximations for various properties of\n", " the underlying probability distribution from which the data set was generated.*\n", " Therefore, using probability theory to reason about distributions can serve as a basis\n", " for inferential reasoning about the real world.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Summary\n", "\n", "In ths section we considered the foundational concept of robot *actions*, focusing on how robot systems can use actions to intervene in the physical world. For our very abstracted world state, we considered discrete, symbolic actions, and introduced probability theory to model the uncertain outcomes associated with each action. We introduced the notion of *expectation* to think about the average outcome of actions over time. And, we ended by contrasting probability theory with statistics, and how the weak law of large numbers bridges the gap between these two formalisms." ] } ], "metadata": { "colab": { "include_colab_link": true, "name": "S22_sorter_actions.ipynb", "provenance": [] }, "interpreter": { "hash": "c6e4e9f98eb68ad3b7c296f83d20e6de614cb42e90992a65aa266555a3137d0d" }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.8.12" }, "latex_metadata": { "affiliation": "Georgia Institute of Technology", "author": "Frank Dellaert and Seth Hutchinson", "title": "Introduction to Robotics" } }, "nbformat": 4, "nbformat_minor": 1 }