{"id":696,"date":"2022-02-01T00:01:29","date_gmt":"2022-02-01T05:01:29","guid":{"rendered":"https:\/\/blogs.ams.org\/featurecolumn\/?p=696"},"modified":"2022-10-24T15:53:20","modified_gmt":"2022-10-24T19:53:20","slug":"the-kalman-filter-helping-chickens-cross-the-road","status":"publish","type":"post","link":"https:\/\/mathvoices.ams.org\/featurecolumn\/2022\/02\/01\/the-kalman-filter-helping-chickens-cross-the-road\/","title":{"rendered":"The Kalman Filter. Helping Chickens Cross the Road."},"content":{"rendered":"

The Kalman Filter. Helping Chickens Cross the Road.<\/h1>\n

David Austin
\nGrand Valley State University<\/p>\n

I was running some errands recently when I spied the Chicken Robot <\/a> ambling down the sidewalk, then veering into the bike lane. A local grocery chain needs to transport rotisserie chickens from one of its larger stores to its downtown market. Their solution? A semi-autonomous delivery vehicle that makes the three-mile journey navigating with GPS.<\/p>\n

I was curious how this worked. The locations provided by most GPS systems are only accurate to within a meter or so. How could those juicy chickens know how to stay so carefully in the center of the bike lane?<\/p>\n

A typical solution to problems like this is an elegant algorithm, known as Kalman filtering, that’s embedded in a wide range of technology that most of us frequently either use or benefit from in some way. The algorithm allows us to efficiently combine our expectations about the state of a system, the chickens’ physical location, for instance, with imperfect measurements about the system to develop a highly accurate picture of the system.<\/p>\n

This column will describe some simple versions of Kalman filtering, the main observation that makes it work, and why it’s such a great idea.<\/p>\n


\nA first example
\n<\/span><\/h3>\n

Let’s begin with a simple example. Suppose we would like to determine the weight of some object. Of course, any scale is imperfect so we might weigh it repeatedly on the same scale and find the following weights, perhaps in grams.<\/p>\n\n\n\n
50.4<\/td>\n46.0<\/td>\n46.1<\/td>\n45.1<\/td>\n48.9<\/td>\n42.6<\/td>\n50.7<\/td>\n45.7<\/td>\n47.8<\/td>\n46.7<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

As the result of each weighing is recorded, we update our estimate of the weight as the average of all the measurements we’ve seen so far. That is, after obtaining $z_n$, the $n^{th}$ weight, we could estimate the object’s weight by finding the average $$ x_n = \\frac1n(z_1 + z_2 + \\cdots + z_n). $$ The result is shown below.<\/p>\n

\"\"<\/div>\n

As the next weight $z_{n}$ is recorded, we update our estimate:
\n$$
\n\\begin{aligned}
\nx_{n} & = \\frac1{n}\\left(z_1 + z_2 + \\cdots + z_{n}\\right) \\\\
\nx_{n} & = \\frac1{n}\\left((n-1)x_{n-1} + z_{n}\\right) \\\\
\nx_{n} & = x_{n-1} + \\frac1{n}\\left(z_{n} – x_{n-1}\\right)
\n\\end{aligned}
\n$$<\/p>\n

This expression tells us how each new measurement influences the next estimate. More specifically, the new estimate $x_{n}$ is obtained from the previous estimate $x_{n-1}$ by adding in $\\frac1{n}(z_{n} – x_{n-1})$. Notice that this term is proportional to the difference between the new measurement and the previous estimate with the proportionality constant being $K_n = \\frac1{n}$. We call $K_n$ the Kalman gain;<\/em> the fact that it decreases as we include more measurements reflects our increasing confidence in the estimates $x_n$ so that, as $n$ increases, new measurements have less effect on the updated estimates.<\/p>\n

Suppose now that we have some additional information about the accuracy of our measurements $z_n$. For example, if $z_n$ is the chickens’ location reported by a GPS system, the true location is most likely within a meter or so. More generally, we might imagine that the true value is normally distributed about $z_n$ with standard deviation $\\sigma_{z_n}$.<\/p>\n

Returning to our weighings, we could perhaps estimate $\\sigma_{z_n}$ by repeatedly weighing an object of known weight. The probability that the true value is near $z_n$ is given by the distribution
\n$$
\np_{z_n}(x) =
\n\\frac{1}{\\sqrt{2\\pi\\sigma_{x_n}^2}}
\ne^{-(x-z_n)^2\/(2\\sigma_{z_n}^2)}.
\n$$<\/p>\n

Let’s also suppose that we have some estimate of the uncertainty of our estimates $x_n$. In particular, we’ll assume the probability that the true value is near $x_n$ is given by the normal distribution having mean $x_n$ and standard deviation $\\sigma_{x_n}$:
\n$$
\np_{x_n}(x) =
\n\\frac{1}{\\sqrt{2\\pi\\sigma_{x_n}^2}}
\ne^{-(x-x_n)^2\/(2\\sigma_{x_n}^2)}.
\n$$
\nWe’ll describe how we can estimate $\\sigma_{x_n}$ a bit later.<\/p>\n

These distributions could be as shown below.<\/p>\n

\"\"<\/div>\n

Now here’s the beautiful idea that underlies Kalman’s filtering algorithm. Both distributions $p_{x_n}$ and $p_{z_n}$ describe the location of the true value we seek. We can combine them to obtain a better estimate of the true value by multiplying them. That is, we combine or “fuse” these two distributions using the product
\n$$
\np_{x_n}(x) p_{z_n}(x).
\n$$
\nSince the product of two Gaussians is a new Gaussian, we obtain, after normalizing, a new normal distribution that better reflects the true value. In our example, the product $p_{x_n}p_{z_n}$ is shown in green.<\/p>\n

\"\"<\/div>\n

More specifically, the product of the two distributions is
\n$$
\n\\begin{aligned}
\n& \\exp\\left[-(x-x_n)^2\/(2\\sigma_{x_n}^2)\\right]
\n\\exp\\left[-(x-z_n)^2\/(2\\sigma_{z_n}^2)\\right] \\\\
\n& \\hspace{48pt}=
\n\\exp\\left[-(x-x_n)^2\/(2\\sigma_{x_n})^2-(x-z_n)^2\/
\n(2\\sigma_{z_n}^2)\\right].
\n\\end{aligned}
\n$$
\nExpanding the quadratics in the exponents and recombining leads to the new normal distribution
\n$$
\n\\frac{1}{\\sqrt{2\\pi\\sigma_{x_{n+1}}^2}}
\n\\exp\\left[-(x-x_{n+1})^2\/(2\\sigma_{x_{n+1}}^2)\\right]
\n$$
\nwhere
\n$$
\n\\begin{aligned}
\nx_{n+1} & =
\n\\frac{\\sigma_{z_n}^2}{\\sigma_{x_n}^2+\\sigma_{z_n}^2} x_n +
\n\\frac{\\sigma_{x_n}^2}{\\sigma_{x_n}^2+\\sigma_{z_n}^2} z_n \\\\
\n& = x_n + \\frac{\\sigma_{x_n}^2}{\\sigma_{x_n}^2+\\sigma_{z_n}^2}(z_n –
\nx_n) \\
\n\\end{aligned}
\n$$
\nNotice that this expression is similar to the one we found when we updated our estimates by simply taking the average of all the measurements we have seen up to this point. The Kalman gain is now
\n$$
\nK_n = \\frac{\\sigma_{x_n}^2}{\\sigma_{x_n}^2+\\sigma_{z_n}^2}
\n$$<\/p>\n

In addition, the product of the Gaussians leads to the new standard deviation
\n$$
\n\\sigma_{x_{n+1}}^2 =
\n\\frac{\\sigma_{x_n}^2\\sigma_{z_n}^2}{\\sigma_{x_n}^2+\\sigma_{z_n}^2}
\n= (1-K_n) \\sigma_{x_n}^2
\n$$<\/p>\n

Notice that the Kalman gain satisfies $0\\lt K_n \\lt 1$. In the case that $\\sigma_{x_n} \\ll \\sigma_{z_n}$, we feel much more confident in our estimate $x_n$ than our new measurement $z_n$. Therefore, $K_n\\approx 0$ and so $x_{n+1} \\approx x_n$, reflecting the fact that the new measurement has little influence on our next estimate.<\/p>\n

However, if $\\sigma_{x_n} \\gg \\sigma_{z_n}$, we feel much more confident in our new measurement $z_n$ than in our estimate $x_n$. Then $K_n\\approx 1$ and $x_{n+1}\\approx z_n$.<\/p>\n

In both cases, the uncertainty in our new estimate, as measured by $\\sigma_{x_{n+1}}^2 = (1-K_n)\\sigma_{x_n}^2$, has decreased.<\/p>\n

This leads to the following algorithm:<\/p>\n

    \n
  1. Initialize the first estimate $x_1$ and the uncertainty $\\sigma_{x_1}$. We could use the first measurement as the first estimate or we could simply make a guess for the estimate and choose a large uncertainty.<\/li>\n
  2. Each time a new measurement $z_{n}$ arrives, update the estimate $x_{n+1}$ and uncertainty $\\sigma_{x_{n+1}}$ as follows:\n