State Estimation & Recursive Bayesian Updating
State Estimation
Consider that we want to determine whether a door is open or closed:
- A robot obtains measurement $z$ from its sensor
We need to determine:
\[P(\text{open}\mid z)\]Diagnostic vs. Causal
- $P(\text{open}\mid z)$ is diagnostic:
- What is the state of the door given the evidence?
- $P(z\mid\text{open})$ is causal:
- What is the evidence if the door is open?
This type of knowledge can be easily obtained by sampling sensors in a particular situation.
We can use causal knowledge to generate diagnostic knowledge by using Bayes:
\[P(\text{open}\mid z)=\frac{P(z\mid\text{open})P(\text{open})}{P(z)}\]Probability Distribution Function
Assume we measure a number of sensor samples:
- When the door was closed.
- When the door was open.
This gives us the probability distribution function (PDF) for some sensor when the door is open.
In this example we can assume:
- $P(z\mid \text{open}) = 0.6$
- $P(z\mid\neg\text{open})=0.3$
As we don’t know if the door is open or not, we assume uniform distribution for the prior:
\[P(\text{open})=P(\neg\text{open})=0.5\]State Estimation Example
Given that:
- $P(z\mid\text{open})=0.6$
- $P(z\mid\neg\text{open})=0.3$
- $P(\text{open})=P(\neg\text{open}) =0.5$
We have:
\[\begin{aligned} P(\text{open}\mid z)&=\frac{P(z\mid\text{open})P(\text{open})}{P(z\mid\text{open})P(\text{open})+P(z\mid\neg\text{open})P(\neg\text{open})}\\ &=\frac{0.6\times0.5}{(0.6\times0.5)+(0.3\times0.5)}\\ &=0.67 \end{aligned}\]Recursive Bayesian Updating
Suppose we have additional sensors ($z_1,\ldots,z_n$) we want to inform our estimation with. We want to estimate:
\[P(x\mid z_1,\ldots,z_n)\]We can estimate $x$ given observations $z_1,\ldots,z_n$:
\[P(x\mid z_1,\ldots,z_n) = \frac{P(z_n\mid x,z_1,\ldots,z_{n-1})P(x\mid z_1,\ldots,z_{n-1})}{P(z_n\mid z_1,\ldots,z_{n-1})}\]To simplify this:
- We have the recursive term $P(x\mid z_1,\ldots,z_{n-1}$ in the numerator.
- We also know we can handle the denominator with normalisation.
- We can use the Markov assumption on the term $P(z_n\mid x, z_1,\ldots,z_{n-1})$:
- This term refers to the likelihood of a measurement givent that I know what the state of the door is ($x$) and I know all my previous measurements.
- If we only have the priors $z_1,\ldots,z_{n-1}$ then $z_n$ woudl be depentent by the priors.
- However, we know the current state $x$, so $z_n$ is independent of $z_1,\ldots,z_{n-1}$. Hence the Markov assumption.
Maximum a Posteriori Estimation
This simplification is called maximum a posteriori estimation and it is written like so:
\[\begin{align} P(x\mid z_1,\ldots,z_n) &= \frac{P(z_n\mid x,z_1,\ldots,z_{n-1})P(x\mid z_1,\ldots,z_{n-1})}{P(z_n\mid z_1,\ldots,z_{n-1})}\\ &=\frac{P(z_n\mid x)P(x\mid z_1,\ldots,z_{n-1})}{P(z_n\mid z_1,\ldots,z_{n-1})}\tag{Markov Assumption}\\ &=\eta P(z_n\mid x)P(x\mid z_1,\ldots,z_{n-1})\tag{Normalisation}\\ &=\eta_{1\ldots n}\left[\prod_{i=1\ldots n}P(z_i\mid x)\right]P(x)\tag{Recursive Term} \end{align}\]State Estimation with Multiple Sensors Example
Given that:
- $P(z\mid\text{open})=0.6$
- $P(z\mid\neg\text{open})=0.3$
- $P(\text{open})=P(\neg\text{open}) =0.5$
- $P(\text{open}\mid z_1) = 0.67$
- This was calculated at State Estimation Example
- $P(\neg\text{open}\mid z_1) = 1-P(\text{open}\mid z_1) = 0.33$
- $P(z_2\mid \text{open}) = 0.5$
- $P(z_2\mid\neg\text{open}) = 0.6$
We have:
\[\begin{aligned} P(\text{open}\mid z_2,z_1) &= \frac{P(z_2\mid\text{open})P(\text{open}\mid z_1)}{P(z_2\mid\text{open})P(\text{open}\mid z_1)+P(z_2\mid\neg\text{open})P(\neg\text{open}\mid z_1)}\\ &=\frac{\frac12\times\frac23}{(\frac12\times\frac23)+(\frac35\times\frac13)}\\ &=\frac58=0.625 \end{aligned}\]