Online SLAM - Artificial Intelligence for RoboticsYouTube↗  IA↗(long shot)
Education  11.6K views 59 likes 0 dislikes   23 Feb 2015
Udacity 651K subscribers United States YouTube↗


Please select the problem
You must specify your email and describe the problem in detail
Describe your problem in detail if it's not obvious

Click to Play Video Click to Play Video
[Narrator] I now want to ask you the really challenging question over here,
今回はとても難易度の高い問題を 出したいと思います
and it goes as follows: one of the weaknesses of slam is
SLAMの短所の1つはこれらのランドマークを見て
as we move along and map a world by seeing these landmarks,
移動しながら世界の地図を作成することです
the matrix omega which is the big thing here and of course the vector C
行列Ωは大規模なものでありベクトルξはもちろん
grow linearly with the length of the path.
経路の長さと共に線形的に増加します
Now this means if you go to your local supermarket and buy a robot,
例えば近くのスーパーでロボットを買うとします
and that robot lives for a long time, say a year or a decade,
そのロボットが1年または10年という長い間 存在する場合
then this thing here, the path will be a really, really large even though the environment
例えロボットが動作する環境の地図が 固定サイズであったとしても
in which it might operate, the map might be of a fixed size,
経路は非常に膨大になるのです
and that means a robot programmed by graph SLAM
またGraph SLAMでプログラミングされたロボットは
will eventually stop working because it gets slower and slower.
だんだん遅くなって 最終的には動作が停止するでしょう
Now, we all know computer operating systems that have that property.
コンピュータオペレーティングシステムは この特徴を有していて
The older they are the slower they are, but we're not talking about how to fix operating systems.
古いほど処理速度は遅くなりますが ここで話しているのは
We're just talking about how to fix SLAM.
SLAMを修正する方法についてです
The crucial idea that I want to tell you about and I want you to implement from scratch in our software
ソフトウェアに実装してほしい 重要な考えはこうです
is the following: we can actually reduce the map we maintain
私たちは保守する地図を縮小することができます
to one that only contains the most recent position in the path,
経路における最新の位置だけを持つ 地図にするのです
and all of the stuff over here can be safely erased when we build our map.
また地図を作成する時に すべての情報を安全に消去できます
You don't know how to do it, but let me tell you.
その方法はこれからお話しします
Suppose we have a robot position and we have a matrix omega
ロボットの位置1つと 1つの位置に関連する情報だけを含む
that only contains the information pertaining to 1 position.
行列Ωがあります
If the position is 1 dimensional, it's just 1 row and 1 column.
位置が一次元の場合は行列は1×1です
Whereas, you might have many different entries for the map.
一方では地図に対して多種多様のエントリを 持っているかもしれません
Suppose the robot moves to a new position; let's call it XT+1.
ロボットが新しい位置に移動するとします Xt+1としましょう
Then, we'd do exactly the following: we'd grow the matrix in the vector
次に行うのはすでによくご存じですが
by using the expand function that you're already familiar with
expand関数を使って ベクトル内の行列を増やすことです
such that we now have space for our new position.
新しい位置のためのスペースができました
The new area we added are these rows over here.
追加した新しい領域はこれらの行です
It's a single row of numbers of a position 1 dimensional. It's 2 rows of number of a position that is 2 dimensional,
一次元の位置の場合は1行、 二次元の位置の場合は2行
and it's this column, again, is just a single column if our position is 1 dimensional;
この列も一次元の位置の場合は1列で 二次元の場合は2列です
otherwise, it is 2 column, and we initialize those all by 0,
そしてそれらすべてをゼロで初期化します
and then we can apply our regular motion update,
次に通常の動作更新を適用します
that as you know adds 1 or some number like 1 to the main diagonal
1または1に近い値を対角要素に追加し
and -1s off diagonal, and the same on the right side for the vector C.
－1を非対角要素に追加します 右側のベクトルξも同様です
That is just a motion update but that runs the risk that our path increases.
これは単なる動作更新ですが 経路が増えるリスクがあります
Now we go back to a form like this.
こちらのフォームに戻りましょう
We make X2+1 survive.
Xt＋1にします
Simplified speaking, you might think about doing this by just cutting out the new sub-matrix that starts over here, and the sub-vector that starts over here; however, if you do this as you can easily verify, that sub-matrix doesn't give you the correct answer,
簡単に言えば ここから始まる新しい部分行列と ここから始まるサブベクトルを切り取ればいいと 考えるかもしれません しかしそうだとしても容易に検証できるように この部分行列は正しい答えを出力しません
and here is where the meat is.
要点はこうです
We now cut out 3 sub-matrices or values from the full matrix on the right side.
私たちは右側の完全な行列から 3つの部分行列つまり値を切り取りました
One sits here, that one I will call A.
ここにある1つをAと呼びます
One is over here; it's a single element for a 1D robot,
こちらの1つは一次元のロボットの場合は 1つの要素ですが
but is a 2 x 2 matrix for a robot in 2D coordinates,
二次元の座標にいるロボットの場合は2×2行列です
and one that I'll call C, and it's obvious to see that this thing over here
そして1つをCと呼びます これが切り取りたいものであることは明らかですが
that you want to cut out is called A-1.
切り取ったものをA⁻¹としましょう
These values carry a lot of importance.
これらの値はかなり重要です
We can't just erase them, but we can forward them back into the surviving matrix
単純に消去することはできませんが 次のシンプルな操作によって
by the following simple operation:
残りの行列に移動することができます
we take the surviving matrix to be called omega prime
残りの行列をΩ´と呼びましょう
and the surviving vector to be called X prime,
そして残りのベクトルをξ´と呼びます
and you can get omega prime and X prime by using the function take that is in your own matrix library.
Ω´とξ´は行列ライブラリにある take関数を使用して取得できます
You have to look into how to make take take exactly those elements over here,
まずこれらの要素を正確に取得する方法を 検討する必要があります
and then if we modify X prime and C prime with the following piece of math.
Ω´とξ´を計算式で変更する場合は
We subtract from omega prime A transpose times B to the -1, the inverse, times A.
Ω´から AのT乗×B⁻¹×Aを引きます
If we implement this correctly this gives you a matrix of the same size as sigma prime,
これを正しく実装すれば σ´と同じサイズの行列が得られます
and that's what you subtract to arrive at our reduced sigma.
引いたのは縮約したσを得るためです
Similarly you do the same for C.
ξについても同様に計算します
You subtract A prime minus B to the -1 times C.
ξ´からAのT乗×B⁻¹×Cを引きます
This tends to be the same as Gaussian where we technically do away
これはガウス分布と同じになる傾向があります 変数X₁を厳密に排除する
or we call it integrate away the variable X1,
あるいは変数X₁を 先に実行してしまうことに相当します
and I don't want to go into detail why that's correct.
これが正しいという詳しい説明は省略します
My book has a multi-page proof of that simple equation.
私の著書ではこの単純な方程式の証明に 何ページも割いています
I just want to give you intuition here, which is these values do carry importance,
ここではこれらの値が重要であるということを 直感で理解してください
and to get rid of those you have to redistribute them into the remaining variables
また残りの変数に再分布する必要性を 排除するために
and that over here happens to be the math.
ここでは計算を行っています
It's A transpose times B times A that you subtract from the remaining omega prime,
AT×B×Aを残りのΩ´から引きます
and the same for C over here.
Cに対しても同様に計算します
When you do this, you are now left with a matrix of the same original dimension
この計算を行うと 元の次元と同じ次元の行列が残ります
because we first added the post and then we subtracted one,
最初に位置を追加してから引いたからです
and as you can see when you do this many, many times
そして何度もご覧になって分かるとおり
the final dimension of the matrix is only determined based on the size of the map
行列の最終的な次元は地図のサイズに
plus, well, a single entry which in the 1D case is 1 row and 1 column.
一次元の場合は1×1の行列の単一のエントリを 二次元の場合は
In the 2D case is 2 of those corresponding to the robot position.
ロボットの位置に対応する2×2の行列の 2エントリをそれぞれ足して決定します
That means SLAM scales to really large environments
これはSLAMが実に大規模な環境に 拡張できることを意味します
because we can do the trick every single time a robot moves.
ロボットが動作する度に 目的を達成することができるからです
You asked for a challenging program assignment.
ここでは難しいプログラムの課題を出します
I promise you, you will be busy with it for awhile.
しばらく考え込んでしまうでしょう
I'm giving you now my piece of code in which I implemented SLAM for you.
SLAMを実装した私のコードの一部がこれで
You're familiar with this.
皆さんがよくご存じのものです
You have all of that, and then I run SLAM with 3 landmarks,
ランドマークは3つでSLAMを実行します
3 time steps, a world size of 100, and a measurement range of 100.
時間ステップ数は3、世界のサイズは100 観測範囲は100です
I make data at random as you're familiar with and you'll complete the result,
いつものようにランダムにデータを作成するので 結果を入力してください
and the result in this case contains a vector of omega C and U concatenated.
この場合の結果には連結された Ω、Xi、μのベクトルが含まれます
Then what I might get out looks as follows:
次は出力内容です
there's 3 landmarks.
ランドマークが3つあります
There's a sequence of estimated positions leading up to the actual robot position.
実際のロボットの位置につながる 推定位置が続いています
They're both correct, and then there's estimates for where landmarks are.
どちらも正しくて ランドマークの推定位置があります
Every time I run it, I get a different answer because my landmarks and my world is different every time.
実行する度に異なる結果が得られるのは 私のランドマークと世界が 毎回 異なるからです
Now I also implemented and that's your task now
また私が実装した関数と課題でもある関数を
a function called online SLAM. It does exactly what I told you to do.
オンラインSLAMといいます これは私が話した処理そのものを行います
It resizes the matrix every time a new motion occurs
これは新しい動作が起こるたびに 行列のサイズを変更します
and then goes back to the original size,
それから元のサイズに戻り
and I've printed out here as an example the information matrix omega
例として私が取得した行列Ωと ベクトルξの情報を出力しています
and in the vector C that I obtained, and I also printed out the final result.
さらに最終的な結果も出力しています
In the final result, we get exactly the same estimated pose as for the full SLAM algorithm
完全なSLAMアルゴリズムの場合と まったく同じ推定位置を取得しています
which is 86.0 and 33.7.
86．0と33．7です
I go down, these are exactly the same number for the estimated pose; that's how you can verify this.
下の方には推定位置とまったく同じ数値があり このようにして検証できます
The same is true for the estimated landmark.
ランドマークの推定位置についても同じです
Those coordinates are identical despite the fact that I reduce the size of omega and C,
これらの座標は Ωとξのサイズを縮約したにもかかわらず 一致しますが
but when I print omega and C, we find that the dimensionality is reduced.
Ωとξを出力すると 次元が削減されていることに気づきます
It's an 8 x 8 matrix omega, and the number 8 comes because there's 6 coordinates for the landmarks and 1 final robot pose.
8×8の行列Ωの8という数字は ランドマークの座標が6つ、 ロボットの最終位置が1つあることによります
That is substantially smaller than the matrix I would obtain
完全なSLAMの場合に取得する行列よりも 大幅に小さくなります
for the full SLAM case, and the same is true for the information vector of size 8; here's an example.
サイズ8の情報ベクトルの場合も 同じことが言えます　これが例です
What you are asked to do is to fill the entire online SLAM routine and to do this,
この課題では オンラインSLAMルーチンを完成させてください
every time you get a new pose, you want to expand to grow the matrix by inserting something right behind the existing pose.
新しい位置を取得する度に 既存の位置の後ろに挿入することによって 行列を拡張します
You then run take to take out the sub-matrix.
次に部分行列を取り出すtakeを実行します
You also calculate A, B, and for the information vector C,
そしてA、Bと 情報ベクトルCを計算したあとに
and then as before your reduced omega is obtained with this equation,
縮約したΩをこれまでのようにこの式で取得します
and your reduced C is obtained with this equation.
縮約したξはこの式で取得します
If you make no mistake, then you get exactly the same area as you had before,
間違いがなければ 前の領域とまったく同じ領域が得られて
and you can test your routine and arbitrary maps and arbitrary data sets, and it'll just be fine.
ルーチンと任意の地図とデータセットを テストすることができます
So, good luck; this is a wonderful programming assignment
これはすばらしいプログラミングの問題で
because it gives you the first really scalable SLAM algorithm
拡張性の高いSLAMアルゴリズムを習得できる 初めての機会です
and when you implement it, it's actually a major achievement.
これを実装すれば大きな実績になります
I can tell you it took the scientific feat of SLAM easily 15 years to really discover this form,
この形式を発見するまでには 15年を超すSLAMの科学的功績がありました
and ever since what was really complex and involved lots of common failures,
そのあとも実に複雑なカルマンフィルタの 問題などが多くありましたが
and I can tell you lots of headaches, became amazingly easy.
今ではそういったことは驚くほど簡単になりました
So, implement it and you can call yourself a robotic mapper.
これを実装できれば ロボットの地図作成者だと名乗ることができます
Similar videos:

Expansion Grid - Artificial Intelligence for Robotics
Udacity
10.4K views 2 likes 0 dislikes 29 May 2012100% match

Parameter Update 2 - Artificial Intelligence for Robotics
Udacity
13.2K views 1 likes 0 dislikes 29 May 2012100% match

Two Coin Quiz - Artificial Intelligence for Robotics
Udacity
12.3K views 7 likes 0 dislikes 19 Feb 2012100% match

Uniform Probability Quiz - Artificial Intelligence for Robotics
Udacity
44.5K views 32 likes 0 dislikes 19 Feb 2012100% match

Print Path - Artificial Intelligence for Robotics
Udacity
10.2K views 3 likes 0 dislikes 29 May 2012100% match

Tracking Intro - Artificial Intelligence for Robotics
Udacity
31.9K views 44 likes 0 dislikes 02 Mar 2012100% match

PID Control - Artificial Intelligence for Robotics
Udacity
23.3K views 32 likes 4 dislikes 18 Mar 2012100% match

Add Noise - Artificial Intelligence for Robotics
Udacity
11.4K views 6 likes 0 dislikes 29 May 2012100% match

Left Turn Policy - Artificial Intelligence for Robotics
Udacity
9.3K views 4 likes 0 dislikes 30 May 2012100% match

Kalman Prediction - Artificial Intelligence for Robotics
Udacity
10.5K views 6 likes 1 dislikes 29 May 2012100% match

Formal Definition of Probability 1 - Artificial Intelligence for Robotics
Udacity
13K views 9 likes 2 dislikes 19 Feb 2012100% match

Maze - Artificial Intelligence for Robotics
Udacity
9.9K views 4 likes 0 dislikes 29 May 2012100% match

Kalman Filter Prediction - Artificial Intelligence for Robotics
Udacity
18.2K views 10 likes 7 dislikes 29 May 2012100% match

Coin Flip Quiz - Artificial Intelligence for Robotics
Udacity
21K views 13 likes 0 dislikes 19 Feb 2012100% match

Total Probability - Artificial Intelligence for Robotics
Udacity
17.6K views 128 likes 5 dislikes 19 Feb 2012100% match


Sensing - Artificial Intelligence for Robotics
Udacity
6.4K views 1 likes 0 dislikes 23 Feb 2015100% match

Graph SLAM - Artificial Intelligence for Robotics
Udacity
39.1K views 196 likes 9 dislikes 31 May 2012100% match

Planning Solution - Artificial Intelligence for Robotics
Udacity
620 views 0 likes 0 dislikes 16 Mar 2012100% match

Formal Definition of Probability 3 - Artificial Intelligence for Robotics
Udacity
11.5K views 5 likes 0 dislikes 19 Feb 2012100% match

Implement P Controller - Artificial Intelligence for Robotics
Udacity
13.7K views 7 likes 0 dislikes 30 May 2012100% match

Separated Gaussians - Artificial Intelligence for Robotics
Udacity
22.9K views 13 likes 0 dislikes 29 May 2012100% match

Admissible Heuristic - Artificial Intelligence for Robotics
Udacity
21.9K views 25 likes 57 dislikes 23 Feb 2015100% match

pHit and pMiss - Artificial Intelligence for Robotics
Udacity
21.4K views 6 likes 2 dislikes 19 Feb 2012100% match


Sense and Move 2 - Artificial Intelligence for Robotics
Udacity
14.5K views 7 likes 0 dislikes 19 Feb 2012100% match

Gaussian Motion - Artificial Intelligence for Robotics
Udacity
15.5K views 8 likes 0 dislikes 29 May 2012100% match

Importance Weight - Artificial Intelligence for Robotics
Udacity
14.8K views 12 likes 1 dislikes 29 May 2012100% match

New Mean and Variance - Artificial Intelligence for Robotics
Udacity
15.9K views 4 likes 0 dislikes 29 May 2012100% match

Sum of Probabilities - Artificial Intelligence for Robotics
Udacity
18.2K views 6 likes 0 dislikes 19 Feb 2012100% match

Resampling - Artificial Intelligence for Robotics
Udacity
7.2K views 11 likes 0 dislikes 29 May 2012100% match

Compute Sum - Artificial Intelligence for Robotics
Udacity
30.2K views 12 likes 0 dislikes 19 Feb 201265% match



Settings Privacy About Contact Donate