[Narrator] So, here's my implementation of the resampling step,
and it follows the same logic that I gave you in the diagram
We're creating a new set of particles called P3; it's an empty set in the beginning,
and inside this routine, every time I resample,
I add a particle from the previous particle set with the index index.
So, that's the main loop over here, and at the end I assign P3 back to P.
So, that's the resampling step.
My very first index is drawn at random.
This is a uniform random sampler of all the indices,
and then I had this running variable beta that I set to 0.0,
and I cache away the max of W just to be slightly faster.
You don't have to do this; they come in over here.
Doesn't really matter if we have max over here,
but then I go and produce exactly N particles, and the way I do this
I add to beta a uniform random that is twice as large
and maximum in the range as my max weight W.
Now, 2 times max weight W will be a very large step,
but by adding a random variable that sits between 0 and 1,
I have uniformity in 0 and 2 times MW,
and then while this beta variable is larger than the weight of the current index,
I subtract this weight from my beta value
and I increment index by 1 modulo N
the total number of particles, and when it's smaller I'm done.
I can just take that particle, add it, append it, and repeat.
So, this entire procedure over here is somewhat involved
if you got that right I'm impressed.
I hope you learn something from doing it.
It happens to be really easy to program once you know what to do,
and every time we write a particle filter you can just reuse it.
You never have to think about it again because there's nothing
domain specific in this specific procedure over here.
So, let's run it; if I run it nothing happens to that empty set.
So, let me print out the resulting set of particles.
So, now I have a print P over here.
Let me run it, and of course, I'm going to get 1000 particles, right?
A lot of particles but let's look through them.
If you just look at the first value over here, they are all about the same.
They are all between 76 and 82.
The second one--they're all about 42, 44, 43, 41, 39, 38.
So, what you've gotten here is a set of particles
that are all co-located .
So, instead of having a complete random set of particles, like we had before,
the resampling step--we can see this already gives me particles
of very similar X and Y positions.
Now it turns out the orientations are not very similar.
They jump like crazy, and the reason is--
--well, if you think about it, we only have 1 location so far,
our distances to landmarks are independent of the orientation.
Such as that our orientation plays no role in the projected measurement,
and therefore has no role in the selection.
Let me make the point, again; here's our 4 landmarks,
and we measure the distances to those.
A robot facing this direction has a certain set of distances.
A robot facing a different direction, like this one,
has the exact same set of distances.
Therefore, in our particle future, the heading direction plays no role.
これが再サンプリングステップの実装で
先ほどの図と同じロジックです
P3と呼ばれる新しい粒子の集合を作ります
最初は空の集合です
このルーチンの中で再サンプリングする度に
前の粒子の集合からindexに粒子を加えます
メインループがこれで
最後にP3をPに戻して割り当てます
これが再サンプリングステップです
一番最初のインデックスは無作為に抽出されます
これがすべてのインデックスについての
均一なランダムサンプリングステップです
0.0にセットして実行し変数βを得ました
少しだけ速くするために
Wの最大値は置いておきます
最大値がここでは重要ではありません
しかしN値の粒子を作りたいので
方法としてはβに
2倍の均一な乱数を加えます
最大重みWはその範囲で最大となります
最大重みWを2倍すると
とても大きなステップになるでしょう
しかし0から1の間にある
ランダム変数を加えることで
0と2×MWに一様性があります
変数βが
現在のインデックスの重みよりも大きいうちに
βの値からこの重みを引きます
そして指数を1ずつ足してNで割り
粒子の総数が小さくなれば終わりです
ただ粒子を選び出して、足して、
そして追加してを繰り返します
このすべてのプロシージャはやや複雑なので
正しく理解できたら感心です
学ぶものが何かあればうれしいです
一度理解すればプログラミングが簡単になり
粒子フィルタを書く度に利用できます
このプロシージャに特定のドメインはないので
再考する必要はありません
さて実行すると空の集合には何も起こりません
そこで得られた粒子の集合を出力します
ここにprint Pがあります
これを実行すると1,000個の粒子を得ますね
数は多いですがよく見てみましょう
この1番目の値を見てみると
ほとんど同じで76から82の間です
2つ目は42、44、43、41、39、38です
ここで得た粒子の集合は
すべて同じ場所にあります
先ほどのように
完全無作為の粒子の集合を持つ代わりに
再サンプリングステップで
xとyの位置によく似ている粒子が
得られることがわかります
方向とはそれほど似ていません
勢いよくジャンプする理由ですが
今のところ1ヵ所しかないので
ランドマークまでの距離は
方向とは無関係だからです
保護された観測では方向は影響を及ぼさないので
選択においては何の役割も果たしません
もう一度4つのランドマークで点をとり
そこまでの距離を測ります
この方向を向いているロボットは
特定の距離の組み合わせを持っています
このように別の方向を向いているロボットは
同じ距離の組み合わせがあるので
粒子の未来において
進行方向には何の役割もありません