Hello, and welcome to the fourth Office Hours.
We've had a lot of really good discussion in the forums and some great questions.
Let's start with a question from Michael.
He asks, "In the last office hours, you mentioned something
about the possibility of a project at the end of the class.
What are your thoughts on the students building a robotic car?"
I just recorded the final class, and I actually spent some time putting everything together
into a simulation of a car at the level we've been operating--not a real car.
Honestly, it took me a whole day to put this all together.
It's substantial work, because at the surface these pieces fit together nicely,
but when you put them together, you realize that what the planner generates is not quite
isn't quite exactly what the controller really wants.
Tuning those parameters was actually a challenge,
but what I've done is for the final class, I'm giving you the environment first
and saying solve the problem of driving a car from A to B.
If you're really so inclined, you can go out and really try it,
but as the class goes on I give you most of my implementation, leaving bits and pieces out.
Then you can go and plug those bits and pieces and and hopefully make it work.
Unfortunately, I can't really give you a real car. That's the real fun thing.
As we'll see in the final example, the methods that we discussed are the core methods.
They give you a good path, but they won't give you a path good enough for actual driving.
There's a lot of work that goes beyond this class that could be done
to make things smoother and more elegant. Perfect.
Tangled asked, "In the Unit 4.14 video, you mentioned something about the other cars honking."
He wants to know if Junior can here.
Does he have a microphone sensor that affects his actions, and can he honk himself?
[Sebastian:] None of our cars hear, and none of our cars honk.
I know in certain parts of the world that's a recipe for not driving confidently and safely in traffic,
but we chose not to make audio communication part of that experiment.
George asked, "While it's possible to constantly re-plan
if enough computational power is available,
A-star assumes a static and deterministic world."
Can you comment on some of the possible pitfalls of using A-star?
And what are some of the alternatives to this algorithm?
Those are great and really deep questions,
to which I've dedicated a number or research years, it turns out,
and I've graduated a number of PhD students on that very topic.
A-star gives you a taste of how cool planning can be,
but there are many, many opens problems.
For example, A-star cannot deal with branching outcomes where you flip a coin,
and you have to pursue both outcomes. It just doesn't work.
It cannot deal with information gathering.
Sometimes in planning what you want to do is take
a specific action just for the sake of a reducing uncertainty.
For example, if I am going to a grocery store, and I don't know whether I have money with me,
I might just check, do I have my money here, and this checking action
has no other bearing than informing me that my money is in my pocket.
That is completely not doable with A-star now.
The dynamic programming stuff that I discussed has that flavor.
You can actually pursue multiple outcomes and bring them together.
It is computationally very inefficient, so you have to basically go over the entire state space.
The fact that we wrote the universal plans is just
a side effect of pursuing every possible combination.
The moment the state space gets very large, dynamic programming doesn't scale.
It's a big, open issue.
Now, if you go to something like Google Maps, what you'll find is
that you can do instant path planning between two points.
What Google has been doing is pre-caching a lot of the principal sub-plans,
so the remaining planning problem of finding the shortest path becomes mostly a table lookup.
They've done this in a way that's actually optimal.
They can prove it's optimal for path planning.
It's really an amazing achievement that's way beyond A-star.
The planning field is much more interesting than the lecture alluded.
I just want to get your juices flowing to have you use one.
Now, we did use A-star in our world,
and the way we addressed re-planning in the current environment
is that we just plan really, really fast.
We had a version of A-star that was super fast.
If we saw something new, it would just re-plan, and that was just fine for us.
You mentioned something about dynamic programming just now,
and a student had a very good question about that.
How large is the planning policy for Junior?
In Junior's case and the Google self-driving car cases,
we don't do that much planning.
We basically plan only within the visual horizon of the vehicle horizon of the vehicle itself.
We don't address the problem of how to get from here to Paris or what streets to take
We assume that's solved by Google Maps.
We assume a fixed route in all our driving, but once the fixed route is speced out,
all the planning that takes place is within the visual range of the robot.
They are typically 3-dimensional state spaces.
They're typically x, y, and orientation.
Now, in some of our experiments we also use velocity as a state variable,
because sometimes you want to take a little detour so you can straighten and be faster,
but they are relatively low-dimensional spaces.
Okay. Another question from George was about prohibitively expensive left turns.
Are the costs of actions--are these a dynamic variable
that's constantly being updated or are they static within the car?
The way we've handled the cost of action is we have a version that looks
at the global picture--like go from A to B and find the cost there--
then zooming back to the local picture.
And the local picture variable is to actually consider cars right now at this moment
whereas in the global picture we assume a static world,
and we make a fixed cost for left turns.
Now, as we go to the local picture, we do a lot of local roll outs,
local look-ahead plans--not dissimilar from A-star--
and then fill in the actual cost of left turns and replace them with the assume cost.
That's sometimes needs a different action.
There situations where we are planning to do a lane shift but we can't
because it's just too expensive right now.
We'd rather endure being stuck behind a slower car until the lane shift is cleared.
There's an interplay between two levels of planning going on.
A student wants to know about multi-goal environments.
An obvious example of a multi-goal environment would be a parking lot.
I want to get to an empty parking spot.
That's a great question I should've asked you the students,
because it has a really nice and obvious answer, which is--here's the answer.
In A-star, you can certainly designate multiple states to be goal states.
Nothing prohibits this. You just have to make sure your heuristic is admissible.
It takes a value that is underestimating or at least estimating correctly
the distance to any of those goal states. Then it's just fine.
The same is true for dynamic programming. You can certainly have multiple goal states there.
Nothing in the formulation is a problem.
Talking about heuristic functions, a student had a question,
and I think a lot of people are wondering,
since this is really where A-star gets its speed in the choice of the heuristic function,
are they deduced algorithmically or are they just done with intuition or trial and error?
How do we decide?
That's a fantastic question.
That's actually a really deep question as well.
In the car domain, we actually calculate heuristic function,
and we have two heuristic functions we kind of superimpose.
Both of them get at the gist of the problem, but are much easier to compute.
Suppose we have an environment with obstacles,
and your planning space is 3-dimensional--your x, your y, and your orientation.
One way to do your heuristic is to ignore the rotational degree of freedom
and assume you're moving a disk in any direction.
Obviously, moving a robot in any direction is easier
than being constrained by the filters or the car.
This becomes now a 2-dimensional problem, and by going from 3 dimensions to 2 dimensions,
we can solve the entire problem in no time.
We plan in 2D and use the 2D planning result as a heuristic for the 3D planner.
The reason why it works is because 2D planning is so much faster than 3D planning.
That's on that is basically ignoring the physical constraints of the car
and going to a simpler car model which can move in any direction any time.
The second heuristic we're using looks at the 3D problem but without obstacles.
We can pre-plan the optimal action of a 3D robot that has turning constraints
in the 3D space--x, y, and orientation--to any goal location in advance--
we do this once and it's true forever--without any obstacles.
What this gets us is that sometimes to get in a certain target orientation,
you have to take a certain turn, and that turn has to be taken no matter what,
and obstacles will only make it worse.
If you compute this obstacle-free heuristic,
you sort of get an underestimate that gets only worse with obstacles.
You have an admissible heuristic.
We toss both of their heuristics in as heuristics in A-star,
and we get a speed-up of a planner easily of a factor of 10^10 in practice.
That's very interesting. Great.
So it's actually--I'm giving this as an example.
I don't want you to really implement those right now, but that shows you how deep this question really is.
If you can come up with good ways of cheating and solving
the problem by lessening constraint and do it much faster,
that tends to be a great heuristic for A-star.
All right. Thanks a lot. We had a lot of great questions.
I'm sure we'll have a lot next week.
Can you give us a little preview of what's coming in Units 5 and 6?
Yes, first I want to thank you for these questions.
I really appreciate how deep they are, and how much you connect with the material.
I think that's great.
I honestly personally much prefer them over questions
such as, "When can I buy my next self-driving car?"
I think is really deep material I'm trying to teach you,
and I love the fact that many of you are diving in and really deeply,
because that's what I want to enable you to do, to apply it in a deep way.
So keep these questions coming.
In Unit 5 and 6 I'll dive into control.
Control is now the art of turning these abstract, discrete, and chucky paths
into actual steering motion.
It's a continuous thing, because your steering is continuous, and time is continuous.
We're going to go away from the discrete world and into the continuous world.
In Unit 6 I try to toss everything together.
In Unit 6 we program, hopefully, a robotic car with my help
where we go all the way to localization at the same time
and path planning at the same time and control
and hopefully generate some actual trajectories by our simulated car.
Can't wait. I'm sure the students feel the same way. Thanks a lot.
See you in class.
こんにちは 第4回オフィスアワーへようこそ
フォーラムではいい議論と質問が
いろいろありました
まずマイトゥールの質問から紹介します
前回のオフィスアワーでは講義終了時に
課題プロジェクトを出す話がありましたが
実際にロボットカーは作りますか?
実は最終講義を撮り終えたばかりで
車のシミュレーションのまとめに
多くの時間を割きました
しかし残念ながら実際の車ではありません
内容をすべてまとめるには丸一日かかりました
表面上はすべての要素をうまく組み合わせますが
プランナが作り出すものとコントローラが
必要とするものが違うことに気づきます
実はパラメータを調整することが難題でしたが
最終講義では先に環境を与えて車をAからBまで
運転させる問題を解いてもらいます
実際に現場で試してもらってもかまいません
講義が進むにつれ
私の実装のほとんどをお教えしますので
それが動作するように細部を入力してください
残念ながら本物の車を
皆さんに提供することはできませんが
最終の例題からも分かるように
講義してきたのは中核となる方法です
方向性は与えてくれますが
実際の運転に十分な方法ではありません
この講義の内容をさらに深めていけば
よりスムーズで簡潔に実現できるでしょう
タングルドの質問です レッスン4ー14で車の
クラクションの話題が出ましたが
ジュニアはクラクションを聞き分けられますか?
またマイクロホンセンサにより音の影響を受けたり
自動でクラクションを鳴らしたりしますか?
ジュニアはどちらもできません
自信を持って安全に運転するにはクラクションが
必要だという国や地域もあります
しかし私たちは音声通信を
実験に取り入れないことに決めました
次はジョージからの質問です
十分な計算能力があるなら
何度も再計画することが可能ですが
A*は静的で決定論的な世界を仮定します
A*を使用する際に陥りやすい点はありますか?
またその代わりとなるアルゴリズムは何ですか?
非常に深くて すばらしい質問です
私はその研究に何年も捧げましたし
何人もの博士課程の学生に
その主題で学位を与えました
A*は計画のすばらしさを体験できますが
未解決の問題点も多くあります
たとえばコイン投げをして
両方の結果を追求するような
分岐結果には対応できないのです
情報収集にも対応できません
計画においてやるべきことは
不確実性を減らすためにある動作を取ることです
たとえば食料品店に行く時
お金があるか分からないとします
私は財布があるか確認するでしょう
この確認動作はポケットに財布があるという情報を
もたらす以外に影響はありません
そして今のところA*では
このようなことはまったくできません
私が以前に話したダイナミック・プログラミングは
実際に複数の結果を追求して
まとめることができます
計算上では低効率なので
全状態空間を確認する必要があります
ユニバーサル計画を書いたことは
すべての可能な組み合わせを
追求する上での副産物でした
状態空間が拡大すると
ダイナミック・プログラミングはスケールしません
これも大きな未解決問題です
さてGoogleマップなどを使うと
二点間の経路計画を即座に作成できます
Googleが行っていたのは主な代替案を
事前にキャッシュに格納することです
計画問題で最短経路を見つけることは
テーブルを参照することです
実に最適な方法で行われました
経路計画において最適であることを証明できます
これはA*をはるかに超えたすばらしい成果です
計画分野は講座で触れた内容より
さらに面白いので皆さんに興味を持ってほしいです
私たちがA*を使い現在の環境でいかに
再計画に取り組んだかというと
非常に早く計画を行いました
高速のA*バージョンがありましたので
新しいものがあれば
再計画を行うだけでよかったのです
ダイナミック・プログラミングについて
触れましたが
ジュニアの計画ポリシーの大きさは?
という関連した質問がありました
ジュニアやGoogle自動運転車の場合は
あまり計画を行いません
基本的に車両そのものの視覚地平線以内の
計画を行ないます
ここからパリへの経路や
どの道路を使うかの問題には取り組みません
Googleマップで解決済みと仮定しています
すべての自動運転において固定進路を仮定し
詳細が決まれば
計画はすべて
ロボットの視覚範囲内で行われます
一般的な三次元状態空間でxとyと方向です
また一部の実験には速度を状態変数として使います
状況の改善や速度を上げるために
少し回り道をしたくなるかもしれません
ですが比較的 低次元空間です
コストのかかる左折について
もう1点質問があります
動作のコストは動的変数として
絶えず更新されていますか?
それとも固定ですか?
動作のコストに取り組む方法として
全体像を見ます
たとえばAからB地点までのコストを調べて
局所像へ戻ります
この局所像変数は
今この時点で車を考慮するためで
逆に全体像では静止した世界を仮定します
そして左折用に固定のコストを作ります
局所像では局所的に展開しA*と
相違のない局所先読み計画もします
そして左折の想定したコストを
実際のコストで置き換えます
時には車線変更を計画しても
違う動作をする場合がありますが
その時点でのコストが高すぎるからです
車線が空くまで遅い車の後ろについて
我慢する方を選びます
2つの計画レベルの間に相互作用があります
次は多目的環境とは?という質問です
多目的環境の分かりやすい例は
駐車場で空いている場所に駐車する場合です
いい問題ですし明確な答えがあるので
皆さんに課題として出すべきでした
A*において確かに多目的状態を
ゴール状態として指定することができます
ただヒューリスティック関数が許容できるかを
確かめなければいけません
いずれかのゴール状態への距離を
低く見積もるか
または正しく見積もった値が必要です
ダイナミック・プログラミングも同様に
多目的状態が可能で
定式化において何の問題もありません
ヒューリスティック関数についても質問があります
皆さんが知りたいと思っているのは
選択するヒューリスティック関数によっては
A*は早くなるのですが
アルゴリズムで推定するのか
それとも直感や試行錯誤で行われるのか
どうやって決めるのですか?
すばらしい質問ですね 実に深い問題です
車の領域では実際に
ヒューリスティック関数を計算し
2つのヒューリスティック関数を重ね合わせます
両者とも問題の要点に取り組みますが
より簡単に計算できます
障害がある環境があるとしましょう
計画空間がx、y、方向といった
三次元だとします
ヒューリスティックを働かせる1つの方法は
回転自由度を無視して
あらゆる方向へ車輪を移動できると仮定します
当然ながらロボットを
あらゆる方向へ移動することは
フィルタや車で制約されるよりも簡単です
今は二次元問題になり
三次元から二次元へ行くことによって
問題全体を即座に解決できます
二次元で計画し二次元計画の結果を
三次元プランナで
ヒューリスティック関数として使います
二次元のほうが三次元計画より
はるかに早いので成功します
車の物理的制約条件を無視することにより
どんな時でもあらゆる方向へ移動できる
単純な車モデルを選びます
2つ目のヒューリスティック関数は
障害のない三次元の問題についてです
x、y、方向という三次元空間で
回転制約がある三次元ロボットの
ゴール位置への最適動作を
事前に計画できます
1回行えばその値は永遠に正解で障害はありません
つまりある目標方向を得るために時には
ある回転が何が何でも必要で
障害はそれをさらに悪化させます
障害なしヒューリスティック関数を計算すれば
過小評価に至り障害があると悪化しますが
許容できるヒューリスティック関数です
これらの2つのヒューリスティック関数を
A*に投入すれば
実際に10から100倍プランナを加速します
とても面白いですね
今のは例として挙げただけです
すぐに実装しなくてかまいません
質問がいかに深いかということです
制約を減らし近道をして問題を解決する
よい方法を考えることができれば
A*において
よいヒューリスティック関数になるはずです
今回はいい質問が多く寄せられました
また次回も期待しています
ではレッスン5と6の概要をお願いします
その前に皆さんからの質問に感謝します
質問の深さや内容の理解をうれしく思いました
すばらしいことです
いつ自動運転車を買えますか?という質問より
うれしい疑問が多く寄せられました
講義の内容は本当に奥が深いと思います
そして皆さんにはさらに深く応用できるように
なってほしいと考えています
ですからどんどん質問をしてください
レッスン5と6では制御について学びます
制御というのは
抽象的で離散的なブツ切りのコースを
実際の運転動作へ変える技術です
運転や時間と同様に制御も連続性があります
つまり離散世界から離れて連続的世界を学ぶのです
レッスン6ではすべてをまとめます
そして私も手伝いながら
ロボットカーをプログラミングし
同時に位置推定や
経路計画や制御を行います
できればシミュレートした車で
実際の軌道を出力します
生徒の皆さんも楽しみにしていると思います
また講義でお会いしましょう