\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",
"

\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": [
"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",
"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 (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": [
"## 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": [
"cardboard | paper | can | scrap metal | bottle | |
---|---|---|---|---|---|

glass bin | 2 | 2 | 4 | 6 | 0 |

metal bin | 1 | 1 | 0 | 0 | 2 |

paper bin | 0 | 0 | 5 | 10 | 3 |

nop | 1 | 1 | 1 | 1 | 1 |

\n",
""
]
},
"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": [
"## 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": [
"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
}

*P(Category):*

\n",
"\n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
"

\n",
"

"
],
"text/plain": [
"Category | value |
---|---|

cardboard | 0.2 |

paper | 0.3 |

can | 0.25 |

scrap metal | 0.2 |

bottle | 0.05 |