Bayesscher Filter
n# Bayesscher Filter
Einfache Sprache
Def. Bayessche Filter
Der Bayessche Filter definiert rekursiv, unter Berücksichtigung der vergangenen Beobachtungen $z_i$ und Aktionen $u_i$ mit $i\in[0,t]$, die aktuelle Position Bel$(x_t)$ wie folgt
$$\text{Bel}(x_t) =\eta P(z_t|x_t)\int P(x_t|u_t, x_{t-1})\textrm{Bel}(x_{t-1})dx_{t-1}\;.$$Dabei ist der Teil vor dem Integral der korrigierende Teil, also der Teil der durch Beobachtungen die Sicherheit der aktuellen Position erhöht. Das Integral ist die Vorhersage der Position ausgehen von der aktuellen Position, also der Teil der die Unsicherheit erhört. Unter der Annahme das die Messungen/Wahrnehmungen/Beobachtungen einer Normalverteilung folgen, erhält man den Kalman-Filter.
Herleitung
Von Wahrnehmungen zum Zustand
Zuerst sei festgestellt das $P(x|z)$ schwer zu ermitteln ist, aber $P(z|x)$ einfacher ermitteln. Ersteres wird diagnostisch und letzeres kausal genannt. Wir nutzen den Satz von Bayes und erhalten
$$P(x|z)=\frac{P(z|x)\cdot P(x)}{P(z)}\;.$$Mehrere Wahrnehmungen
Wir nehmen jetzt an das wir 2 Wahrnehmungen $z_1$ und $z_2$ nacheinander haben. Jetzt wollen wir $P(x|z_2,z_1)$ bestimmen. Es ergibt sich wie folgt
$$P(x|z_2,z_1)=\frac{P(z_2|x)P(x|z_1)}{P(z_2|x)P(x|z_1)+P(z_2|\neg x)P(\neg x|z_1)}\;.$$Das berücksichtigen einer weiteren Wahrnehmungen die verändert die aktuellen Belief.
Von Aktion zum Zustand
Um einen neuen Belief zu formen wird eine Aktion zusammen mit dem aktuellen Belief kombiniert. Also $P(x_2|u,x_1)$
Zusammenführung
Beweis
Markov Annahme
Wir nehmen an das System erfüllt die Markov Annahme. Also das die aktuelle Beobachtung $z_t$ nur vom aktuellen Zustand $x_t$ abhängt und die aktuelle Position $x_t$ nur von der letzen Position $x_{t-1}$ und der aktuellen Aktion $u_t$ abhängt. Als Zustandsdiagramm ergibt sich
$$P(z_t|x_0,\ldots,x_t,z_1,\ldots,z_{t-1},u_1\ldots,u_t) = P(z_t|x_t)$$Daraus folgen folgende Gleichnisse für die Wahrscheinlichkeiten von $z_t$ und $x_t$:
und
$$P(x_t|x_0,\ldots,x_{t-1},z_1,\ldots,z_{t-1},u_1\ldots,u_t) = P(x_t|x_{t-1},u_t)\;.$$
Nutzt die
$$\begin{align} & \textrm{Bel}(x_t)\\ =& P(x_t|u_1,z_1,\ldots,u_t,z_t) &\Huge|\normalsize\text{Def. Belief}\\=& \frac{P(z_t|u_1,z_1,\ldots,z_{t-1},u_t,x_t)P(x_t|u_1,z_1,\ldots,z_{t-1},u_t)}{P(z_t|u_1,z_1,\ldots,z_{t-1},u_t)}&\Huge|\normalsize\text{Satz von Bayes}\\=&\eta P(z_t|u_1,z_1,\ldots,z_{t-1},u_t,x_t)P(x_t|u_1,z_1,\ldots,z_{t-1},u_t)&\Huge|\normalsize\text{Eig. $z_i$ als Markov}\\=&\eta P(z_t|x_t)P(x_t|u_1,z_1,\ldots,z_{t-1},u_t)&\Huge|\normalsize\text{$z_t$ hängt nur von $x_t$ ab(Markov)}\\=&\eta P(z_t|x_t)\int P(x_t|u_1,z_1,\ldots,z_{t-1},u_t, x_{t-1})P(x_{t-1}|u_1,z_1,\ldots,u_t)dx_{t-1}&\Huge|\normalsize\text{Law of total probability}\\=&\eta P(z_t|x_t)\int P(x_t|u_t, x_{t-1})P(x_{t-1}|u_1,z_1,\ldots,u_t)dx_{t-1}&\Huge|\normalsize\text{$x_t$ hängt nur von $x_{t-1}$ und $u_t$ ab (Markov)}\\=&\eta P(z_t|x_t)\int P(x_t|u_t, x_{t-1})P(x_{t-1}|u_1,z_1,\ldots,u_{t-1},z_{t-1})dx_{t-1}&\Huge|\normalsize\text{$x_{t-1}$ hängt nicht von $u_{t}$ ab} \\=&\eta P(z_t|x_t)\int P(x_t|u_t, x_{t-1})\textrm{Bel}(x_{t-1})dx_{t-1}&\Huge|\normalsize\text{Def. Bel$(\cdot)$} \\\end{align}$$Algorithmus
Abstrakt wird bei jedem Schritt folgende Berechnung gemacht.
1import numpy as np
2
3def bayesian_filter(belief_prev, u_t, z_t, transition_model, observation_model):
4 """
5 Bayesian Filter implementation
6 Args:
7 belief_prev: Previous belief distribution Bel(x_{t-1})
8 u_t: Action at time t
9 z_t: Observation at time t
10 transition_model: Function p(x_t | u_t, x_{t-1})
11 observation_model: Function p(z_t | x_t)
12 Returns:
13 Updated belief distribution Bel(x_t)
14 """
15 # Prediction step
16 bel_bar = np.zeros_like(belief_prev)
17 for x_t in range(len(bel_bar)):
18 # Integrate over all x_{t-1}
19 integral = 0
20 for x_prev in range(len(belief_prev)):
21 integral += transition_model(x_t, u_t, x_prev) * belief_prev[x_prev]
22 bel_bar[x_t] = integral
23 # Update step
24 belief = np.zeros_like(bel_bar)
25 for x_t in range(len(belief)):
26 belief[x_t] = eta * observation_model(z_t, x_t) * bel_bar[x_t]
27 # calculate eta as the inverse of the sum of belief.
28 eta = 0
29 for x_t in range(len(belief)):
30 eta += belief[x_t]
31 eta = 1.0 / eta
32 # Correct the belief with the eta normalization factor.
33 for x_t in range(len(belief)):
34 belief[x_t] *= eta
35 return belief
Eine konkrete Implementierung kann man hier finden Histogram-Filter > Algorithmus