- 追加された行はこの色です。
- 削除された行はこの色です。
[[FrontPage]]
[[ドキュメント/制御]]
<comments />
== 目次==
== 概要==
EKF(Extended Kalman Filter)の立式方法について。<br />
導出は完全に抜きにして、とにかく動くものができるようにすることを目的とした文書である。<br />
また、パラメータチューニングに関するTipsも載せるつもりである。
== 製作者==
[[若田部]]
== カルマンフィルタとは==
カルマンフィルタは、状態量の平均値と分散共分散行列を推定するフィルタである<br />
確率密度はガウス分布によって表現されるので、平均値は最尤値（=一番それっぽい値）に一致する。<br />
また、分散共分散行列はガウス分布の確率密度の広がりを表し、これは平均値の確からしさを表す。<br />
== 用語==
カルマンフィルタを理解するために必要な用語を記述する。<br />
状態量: 推定する目的の確率変数のベクトル。<math>x</math>で表す。<br />
平均値: この文書の文脈では、状態量の平均。<math>\mu</math>で表す。<br />
分散共分散行列: このページの文脈では、状態量の分散共分散行列。<math>\Sigma</math>で表す。<br />
<br />
制御量: 状態量の速度の観測に関する、確率変数のこと。<math>u</math>で表す。<br />
状態遷移関数: ある制御量が新しく入力された時、以前の平均値とその制御量によって、どの平均値に移るかを推定するベクトル関数。<math>\mu_t = g(\mu_{t-1}, u)</math>で表す。<br />
予測段: カルマンフィルタは二つのステップに完全に独立に分かれている。その内、制御量を用いて、平均値と分散共分散を更新するステップ。<br />
<br />
観測量: センサによる観測に関する、確率変数のこと。<math>z</math>で表す。<br />
観測関数: 平均値と何らかモデルを入力にして、理想的な観測を計算するための関数。<math>h(\mu)</math>で表す。モデルを明示する場合は、<math>h(\mu, m)</math>とすることもある。<br />
観測段: カルマンフィルタは二つのステップに完全に独立に分かれている。その内、観測量を用いて、平均値と分散共分散行列を更新するステップ。<br />
== イメージ==
状態量: ロボットの位置(x, y, theta)の確率変数<br />
平均値: ロボットの自己位置の中で最も尤もらしい場所。これがいわゆるオドメトリとして扱われる。<br />
分散共分散行列: ロボットの自己位置の不確かさ。例えば、ロボットが「自分は大体x方向に関して標準偏差5cmくらいはずれてるかも…」とか思ってることを表現している。<br />
<br />
制御量: エンコーダの情報。確かにこれらはx, y, thetaの速度を司る。<br />
状態遷移関数: オドメトリ更新式。これは、「一つ前のオドメトリとエンコーダ」を入力に、「直後のオドメトリ」を得るベクトル関数である。<br />
予測段: エンコーダによる更新。平均値と分散共分散行列の更新の2本の式に依るが、今までの更新式はまさに平均値の更新にあたる。<br />
<br />
観測量: 測距センサによる観測や、カメラや測域センサによるランドマーク検出などによる距離情報や角度情報。<br />
観測関数: オドメトリと測距センサがついている位置から、センサの出力の理想的な出力を計算するための関数。<br />
観測段: 測距、カメラ、測域などによる情報を組みこむ更新。<br />
== 予測段==
予測段では、状態量の速度に関する情報を更新に組みます。
=== 時間の添え字について===
更新前の状態量: <math>\mu_{t-1}</math><br />
更新後の状態量: <math>\mu_t</math><br />
更新に使う制御量: <math>u_t</math><br />
時刻tで得られた制御量によって、時刻t-1の状態量が、時刻tの状態量に更新される、というイメージです。
=== 式===
式は以下のとおりです。<br />
G: <math>\mu_{t-1}</math>に関するヤコビ行列。<math>G = \frac{\partial \mu_t}{\partial \mu_{t-1}}</math><br />
R: <math>\mu_t</math>の分散共分散行列。その1回の予測により、どれくらい状態量の不確かさが増加するのか、を表す。<br />
<br />
<math>\mu_t = g(\mu_{t-1}, u)</math><br />
<math>\Sigma_t = G \Sigma_{t-1} G^t + R</math> …(1)<br />
=== 例: 二輪ロボットのオドメトリ===
参考:<br />
[[File:https://robotich.ath.cx/ppssww/pukiwiki.php?plugin=attach&refer=%A5%C9%A5%AD%A5%E5%A5%E1%A5%F3%A5%C8%2F%C0%A9%B8%E6%2F%A5%EA%A5%CB%A5%A2%A5%A8%A5%F3%A5%B3%A1%BC%A5%C0%A4%CB%A4%E8%A4%EB%B1%DF%B8%CC%B6%E1%BB%F7%C6%F3%CE%D8%B7%CF%B9%B4%C2%AB%A5%AA%A5%C9%A5%E1%A5%C8%A5%EA&openfile=odme_map.pdf]]<br />
<br />
状態量と制御量を以下のように設定します。<br />
<math>\mu_t = \begin{pmatrix} x_t \\ y_t \\ \theta_t \end{pmatrix}</math><br />
<math>u_t = \begin{pmatrix} v_t \\ \omega_t \end{pmatrix}</math><br />
<br />
gを資料から読み解きます。<br />
<math>\begin{pmatrix} x_t \\ y_t \\ \theta_t \end{pmatrix} = \begin{pmatrix} x_{t-1} + v_t \Delta t \cos(\omega_t \Delta t / 2 + \theta_{t-1}) \\ y_{t-1} + v_t \Delta t \sin(\omega_t \Delta t / 2 + \theta_{t-1}) \\ \theta_{t-1} + \omega \Delta t \end{pmatrix} </math><br />
<br />
Gを、gを<math>x_{t-1}</math>で偏微分することで求めます。<br />
<math>G = \begin{pmatrix} 1 & 0 & - v_t \Delta t \sin(\omega_t \Delta t / 2 + \theta_{t-1}) \\ 0 & 1 & v_t \Delta t \cos(\omega_t \Delta t / 2 + \theta_{t-1}) \\ 0 & 0 & 1 \end{pmatrix}</math><br />
<br />
Rに相当する行列を求めます。<br />
ロボットの場合、一回の予測ステップの不確かさを生みだすのは、制御量に他ならないので、制御量の分散共分散行列Mを仮定し、それをヤコビ行列によって状態量の分散共分散行列に射影します。<br />
制御量による状態量の分散共分散行列は、状態量の制御量に関するヤコビ行列<math>V = \frac{\partial \mu_t}{\partial u_t}</math>を用いて、<math>V M V^t</math>と表されます。…(2)<br />
<math>M = \begin{pmatrix} \alpha_1 v_t^2 + \alpha_2 \omega_t^2 & 0 \\ 0 & \alpha_3 v_t^2 + \alpha_4 \omega_t^2 \end{pmatrix}</math><br />
<math>V = \begin{pmatrix} \Delta t cos(\omega_t \Delta t / 2 + \theta_{t-1}) & - v_t \Delta t ^ 2 / 2 sin(\omega_t \Delta t / 2 + \theta_{t-1}) \\ \Delta t sin(\omega_t \Delta t / 2 + \theta_{t-1}) & v_t \Delta t ^ 2 / 2 cos(\omega_t \Delta t / 2 + \theta_{t-1}) \\ 0 & 1 \end{pmatrix}</math><br />
<math>R = V M V^t</math><br />
<br />
以上から、予測段は以下のように立式されます。<br />
<math>\begin{pmatrix} x_t \\ y_t \\ \theta_t \end{pmatrix} = \begin{pmatrix} x_{t-1} + v_t \Delta t \cos(\omega_t \Delta t / 2 + \theta_{t-1}) \\ y_{t-1} + v_t \Delta t \sin(\omega_t \Delta t / 2 + \theta_{t-1}) \\ \theta_{t-1} + \omega_t \Delta t \end{pmatrix} </math><br />
<math>\Sigma_t = G \Sigma_t G^t + V M V^t</math>…(3)<br />
=== Tips===
==== 分散の線形射影====
(1), (2)では以下の事実を利用しています。<br />
<br />
線形空間Xのある正規分布が、平均<math>\mu_X</math>分散共分散行列を<math>\Sigma_X</math><br />
線形空間Yが存在する。<br />
XからYへの線形変換行列Aが存在する。<br />
Xの正規分布をAによって射影した時の、Yの正規分布は、平均<math>\mu_Y</math>分散共分散行列を<math>\Sigma_Y</math>とする。<br />
この時、<br />
<math>\mu_Y = A \mu_X</math><br />
<math>\Sigma_Y = A \Sigma_X A^t</math><br />
である。<br />
*証明[[Image:ドキュメント_制御_ExtendedKalmanFilterの立式方法_project_variance.pdf]] [#e5df8368]
==== 分散の和====
(3)は以下のような事実から本当は明らかです。<br />
関数gが射影しうる分散は、(x, y, theta, v, omega)から来るはずです。<br />
「Tips/分散の線形射影」を用いれば、本当ならばAは5*5の行列になるはずです。
<br />
これは「ひとつ前の状態量の分散共分散行列と、今の制御量の分散共分散行列は独立である。」という仮定により分解されています。<br />
つまり、状態の分散共分散と、状態の速度の分散共分散に関係があるわけがない、という信念により、カルマンフィルタのもとの式でもRは別扱いされているのです。
==== 予測段は簡単====
予測段は僕でも導出できるくらいに簡単なものです。<br />
カルマンフィルタの真骨頂は観測段にあります。<br />
== 観測段==
観測段では、「状態量にとって意味のある観測」を更新に組みます。<br />
=== 状態量にとって意味のある観測===
まず、「状態量にとって意味のある観測」とは何か、ということについて書きます。<br />
「状態量にとって意味のある観測」とは、「状態量とモデルから、理想的な観測量が計算できる」という意味です。…(4)<br />
<br />
例えば、<br />
四角い枠に囲まれたフィールドにロボットがいます。<br />
ある壁に対して、測距センサで距離を測ったとします。<br />
この場合、ロボットのオドメトリと測距センサが付いている位置によって、当然理想的な観測量は計算可能できるはずです。…(5)<br />
=== 時間の添え字について===
更新前の状態量: <math>\mu_{t-1}</math><br />
更新後の状態量: <math>\mu_t</math><br />
更新に使う観測量: <math>z_t</math><br />
時刻tで得られた観測量によって、時刻t-1の状態量が、時刻tの状態量に更新される、というイメージです。
=== 式===
以上のことを踏まえて、式を記述します。<br />
H: hの<math>\mu_{t-1}</math>に関する偏微分。<math>\frac{\partial h}{\partial \mu_{t-1}}</math><br />
Q: <math>z_t - h(\mu_{t-1})</math>の分散共分散行列<br />
<math>K=\Sigma_{t-1} H^t (H \Sigma_{t-1} H^t + Q)^{-1}</math><br />
<math>\mu_t = \mu_{t-1} + K (z - h(\mu_{t-1}))</math><br />
<math>\Sigma_t = (I - K H) \Sigma_{t-1}</math><br />
<br />
Kは一般に「カルマンゲイン」と呼ばれています。<br />
式を見れば、これは「状態量からの理想的な観測量と、実際の観測量の差分」を反映させた、フィードバックゲインとなっていることがわかります。<br />
=== 例: 点ランドマークベースの更新===
状態量と実観測量と理想観測量を以下のように設定します。<br />
<math>\mu = \begin{pmatrix} x \\ y \\ \theta \end{pmatrix}</math><br />
<math>
m_x, m_y</math>: フィールド座標での点ランドマークの実際のx, y。<br />
<math>z = \begin{pmatrix} r \\ \phi \end{pmatrix}</math>: 観測された、マシン中心から見た点ランドマークとの距離と角度。<br />
<math>\hat{z} = h(\mu_{t-1})</math>: 状態量から算出された理想的な、マシン中心から見た点ランドマークとの距離と角度。<br />
<br />
hを立式します。<br />
<math>q = (m_x - x_{t-1})^2 + (m_y - y_{t-1})^2</math> <br />
<math>\hat{z} = h(\mu_{t-1}) = \begin{pmatrix} \sqrt{q} \\ norm(atan2(m_y - y_{t-1}, m_x - x_{t-1}) - \theta_{t-1}) \end{pmatrix}</math><br />
ただしnormは、角度を[-pi, pi]に丸める関数。<br />
<br />
Hをhを<math>\mu_{t-1}</math>で偏微分して求めます。<br />
<math>H = \frac{\partial h}{\partial \mu_{t-1}} = \begin{pmatrix} -(m_x - x_{t-1}) / \sqrt{q} & -(m_y - y_{t-1}) / \sqrt{q} & 0 \\ (m_y - y_{t-1}) / q & -(m_x - x_{t-1}) / q & 1 \end{pmatrix}</math><br />
<br />
Qを設定します。<math>r, \phi</math>は互いに独立だと仮定して、ランドマークの観測と理想位置とのズレの分散共分散行列は、<br />
<math>Q = \begin{pmatrix} Q_r & 0 \\ 0 & Q_\theta \end{pmatrix}</math><br />
<br />
以上より、観測段の更新式は、<br />
<math>K=\Sigma_{t-1} H^t (H \Sigma_{t-1} H^t + Q)^{-1}</math><br />
<math>\mu_t = \mu_{t-1} + K (z - h(\mu_{t-1}))</math><br />
<math>\Sigma_t = (I - K H) \Sigma_{t-1}</math><br />
=== Tips===
==== 状態量にとって意味のある観測の数学的な記述====
(4)について、直感的な説明だけにとどめたかったので厳密さに欠くことを書きましたが、実際には、
*観測量=f(状態量, モデル)、ただし状態量について一階偏微分可能 [#vb14f913]
を良く近似するfが存在することが条件となります。
==== 状態量にとって意味のない観測の例====
(5)について、意味のない観測の例は下らないのでTipsに。<br />
<br />
四角い枠に囲まれたフィールドにロボットがいます。<br />
この時、工学部二号館8階の自動ドアの測距センサが、床もしくは通行人との距離を測ったとします。<br />
この場合、ロボットのオドメトリと自動ドアの測距センサが付いている位置によって、当然自動ドアの理想的な計算量を推定することはできません。<br />
==== 点ランドマークが同時に複数見つかった場合====
上記の場合では、点ランドマークが一つしか見つかっていない状況しか想定していません。<br />
もしLRFなどで複数のランドマークが同時に見つかった場合は、「それぞれ別々に」上記の更新を行えばよいです。<br />
つまり、3つランドマークが見つかったのならば、3回カルマンゲインを更新して、3回更新をかけることになります。<br />
== Tips==
=== ヤコビ行列===
ベクトル関数のベクトルによる偏微分係数をヤコビ行列と呼びます。<br />
ベクトル関数のベクトルによる偏微分係数の定義を知らない人のために、以下に定義を書きます。<br />
<br />
x: n次元実数ベクトル変数<br />
f: n次元実数ベクトルからm次元実数ベクトルへのベクトル関数<br />
<math>\frac{\partial f}{\partial x} = \begin{pmatrix} \frac{\partial f_1}{\partial x_1} & \cdots & \frac{\partial f_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial f_m}{\partial x_1} & \cdots & \frac{\partial f_m}{\partial x_n} \end{pmatrix}</math><br />
== 観測偏差の分散共分散行列のチューニング方法==
=== 基本===
*チューニングパラメータは以下である。 [#h4b7713e]
**理想観測と実観測の差分(=観測偏差)の分散共分散行列 [#t43f344a]
*同定にあたって重要なパラメータは、<math>\Delta z_t = z_t - \hat{z}_t, \Delta \mu = K \Delta z_t</math>である。 [#j50479e5]
**これらはすぐに確認してplotできるような環境を整えてください。 [#mb2e64e0]
=== 方法===
*<math>\Delta z_t</math>をプロットし、その最小値と最大値の半分が1SDになるように分散共分散行列を構成する。 [#geda0cb1]
**例えば、理想ランドマーク位置までが100mm, 測域センサによる観測が94-108mmだったとする。 [#h5e88cc0]
**すると、1SDを(108-94)/2= 14 mmなので、分散は14^2 = 196 mm^2に設定すればよい。 [#x5f5b1ea]
*なぜ半分を1SDにするのか？ [#f9e02a7c]
**本当であれば最大値と最小値を3SD (=99%域)にセットしても良いはずである。 [#x33726a5]
**実際のデータはこの観測から大きく外れることが想定される。 [#h2b57923]
***中央値がずれる可能性もある、外れ値が出る可能性もある。 [#f9aecd0d]
**その上、この設定した分散が大きすぎてもパフォーマンスが下がるだけだが、小さすぎると暴走・振動する可能性がある。 [#ud788b0d]
***基本的にロボットって振動して欲しくない。 [#p4ff5426]
**なので、安全線として1SDとするのが良いと思う。 [#k6df4544]
***もっとパフォーマンスをあげようとか思った時に、ちょっとずつ分散共分散行列を下げていけば良い。 [#n23f6c3c]
== 初期状態の分散共分散行列==
=== 基本===
*大きいと観測による補正がかかりやすくなる [#g0767f40]
**これは、自分の位置がよくわからないから、比較的観測を信用することを意味する。 [#vc6f1c34]
**極端に大きいと(Σ=∞)、藁にもすがるように、自分の位置を完全に無視して観測ばかり反映することになる。 [#o2ef4ecf]
*小さいと観測による補正がかかりにくくなる。 [#p40fd8c5]
**これは、自分の位置を信用していて、観測にぶれない自分を持っていることを意味する。 [#rd9477b2]
**極端に小さいと(Σ=0)、自分が絶対的に正しいと思っているので、どんな観測がきてもその補正量は0となり無視される。 [#ib1c8f6c]
=== 方法===
==== 補正の信頼性が比較的高い場合====
*測域など [#uda8d35a]
*基本的にはありえないくらいに大きく。 [#e00df75a]
**例えば、ロボットの初期位置だったら1SD=±1mとか。 [#c9e4e193]
**初期位置なんて1cmもずれるわけないが、これくらいに設定しておく。 [#x73de8f9]
*すると、はじめの観測をほぼ信頼して、ロボットの位置が補正される。 [#m4fe6be6]
==== 補正の信頼度が比較的低い場合====
*測距など [#cdee232e]
*ロボットの初期位置の人間の手によるズレのうち、考えられる最小と最大の差の1/2を1SDとするような分散共分散行列にする。 [#q809d628]
**例えば、人間の手でリトライをかけるときに、±(10 mm, 10 mm, 5 mrad)の誤差が考えられるとする。 [#afbbb17b]
**そうしたら、Var = (100 mm^2, 100 mm^2, 25 mrad^2)のように初期状態を設定する。 [#z2b4ea38]
==== 初期状態を大きくしたら暴走する場合====
**初期状態をいくら大きくしたら暴走するのかを確認する [#d6637cb8]
**理論上は、観測関数の線形化がうまく行っていれば、いくら大きくしても暴走することはないはず [#e7a83787]
**このような状態になることはほぼありえないので、パラメータチューニングとは別の要因を探すべき [#n7db538f]
***例えば更新にかかる計算時間が遅く、up to dateな更新がかけられていないとか→高速化する [#sa780d9a]
***1つだけでは不定性のある観測をやたら信頼して更新をかけているとか→2つ見えた時にだけ更新をかける [#w4bc4086]
== 参考資料==
確率ロボティクスのExtended Kalman Filterの欄。
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
