The exact same algorithm works beautifully for planning the shortest path
to a single mission goal from any possible start location,
and the only difference here is in this graph over here of an actual road graph
we are also incorporating the heading direction as measure of distance.
Green corresponds to nearby to large values, red to far away.
The reason why the area below the mission goal is green is because we expect
the car to point up, to point north, at the time it reached the mission.
So if it came from the north, it would point in the wrong direction.
The state space is augmented correspondingly.
Where if it comes from over here, it points in the correct direction.
If you look at the circle over here, it's interesting.
If we came from the left side over here, it could do a right turn,
but over here it's forced on this one-way circle to do the entire loop to go around,
and that increases the value as it comes over here.
This is value iteration applied to the road graph where we keep track of heading
and where the circle over here is a one-way circle.
まったく同じアルゴリズムが
1つのゴールと複数の初期位置で
最短経路を計画する問題に対しても美しく働きます
ここでの唯一の違いはこのグラフでは
ここは実際の道だということです
向きについても距離の指標に入れました
緑は近い場所で赤が遠い場所です
この場所が緑なのはこの場所で車は
上つまり北を向いていると考えているからです
もし北から来れば違う方向を向いています
状態空間はともに増大しています
ここから来た場合正しい方向を向いています
この円を見れば興味深いと感じるはずです
左から来た場合右へ曲がれますが
ここからは強制的に
一方通行の円を回る必要があります
それによってここからの値は増加しています
これは向きを一定にする必要のある
道のグラフに値の反復があり
円が一方通行に出会った場合です