<![CDATA[
---
# ナビゲーション
---
## 経路計画とナビゲーション
ローカリゼーションを使って*どこにいるか*という問題を解決しました。
次は*目的地までどうやって行くか*という点について考えましょう。
- ロボットの周りには一般的に、障害物や物体がありますので、衝突を回避しなければなりません。
- 以前の演習でロボットの移動制御を実装しましたが、その時は障害物を無視していました（障害物がない環境でした）。
<img src="./v6_media/path_planning_problem.png" alt="" style="width: 27%;"/>
⇒
<img src="./v6_media/path_planning_problem1.png" alt="" style="width: 27%;"/>
---
## 古典的なナビゲーション構造
ナビゲーションの問題を解決する一般的なアプローチは、ナビゲーションを2つの課題に分割することです。
- グローバル計画
- ローカル計画
---
#### グローバル計画
= 現在位置から目的地までの障害物を考慮した経路を計画します
- 目的地まで行くにはどの道が一番いいか？
- 比較的低い頻度で更新する（数秒に一回）
#### ローカル計画
= 障害物を回避しながらグローバル経路に沿って進むための速度を決定します
- 周りの障害物にぶつかることなく、目的地の方向へ進む、または計画された経路をたどる
- 比較的高い頻度で更新する（一秒に数回）
<img src="./v6_media/four_layer_arch.png" alt="" style="width: 40%;"/>
<img src="./v6_media/two_layer_arch.png" alt="" style="width: 55%;"/>
---
# 経路計画
経路計画手法は様々ですが、よく使われているのはグラフ探索です
2つのステップ
1． スペースを分解する
- どのように分解するか？
2． グラフ探索アルゴリズムを使用して経路を計算する
- どのアルゴリズムを使うか？
## スペースの分解
スペースには、ロボットが通過できる空き部分と障害物がある部分が含まれています。
空きスペースを分割します。
- 正確な分解
- おおよその分解
- 正確な分解よりも構築が簡単
---
### おおよその分解
固定サイズのセグメントのグリッドに分解します。
<img src="./v6_media/grid_decomp_path.png" alt="" style="width: 45%;"/>
- 簡単ですが、セグメントが多い
- 一方、グリッド地図はローカリゼーションにも使用するので、地図構築で作った占有グリッド地図がそのまま使えます！
### コストマップ
計画アルゴリズムを使うと、障害物の近くを通過する経路を得ることが多いです。
- ローカリゼーションエラーが発生した場合はぶつかる可能性があります
⇒ 障害物がさらに拡張されます
<img src="./v6_media/map_noblur.png" alt="" style="width: 35%; display: inline-block;"/>
⇒
<img src="./v6_media/map_blur.png" alt="" style="width: 35%; display: inline-block;"/>
---
## グラフ探索アルゴリズム
「人工知能」からの復習
- 知識を用いない探索
- 幅優先探索
- 深さ優先探索
- 均一コスト探索（ダイクストラ法）、など
- 知識を用いた探索
- A*アルゴリズム、など
幅・深さ優先探索 ⇒ ノードからノードへの移動コストを無視するので、コストマップ上の探索に使用できません
---
### 均一コスト探索
⇒ あるグラフノードから隣接ノードへの移動の「コスト」を考慮します（コストはコストマップから得られます）
- 次にチェックするノードは、合計コストが最も低いノードを選択します
- 得られる経路は最適です（最短コスト）
例：
<img src="./v6_media/Dijkstras_progress_animation.gif" alt="" style="width: 35%;"/>
---
### A*
⇒ グラフのあるノードから隣接するノードへの移動のコストに加え、残りのパスの推定コストも考慮します
- 検索するノードが少ないため、より効率的です ⇒ よく使われます
- 得られる経路は必ずしも最適ではありません
例：
<img src="./v6_media/Astar_progress_animation.gif" alt="" style="width: 35%;"/>
---
---
# 障害物回避
= ローカル計画
障害物との衝突を避けながら、グローバルに計画された経路にできるだけ従うように、制御コマンド（速度命令）を決定します。
- グローバル計画との接続方法
- グローバル経路を可能な限り追跡する
- グローバル経路上のロボットの少し前のポイントを選んで、それを「ローカルの目的地」として使う。ローカルの目的地に向かって移動するように速度を選択する
---
## 障害物回避アルゴリズム
一般的に使用されるアルゴリズムの1つは「ダイナミックウィンドウ方式」です。
（他にはVector field histogram、Velocity obstacle、Elastic bandなどがあります。）
### ダイナミックウィンドウ方式
Dynamic Window Approach (DWA) [Fox, Burgard, Thrun, 1997]
- ロボットは円弧を描いて移動すると想定されています (v, ω)
- [2輪差動駆動のロボット](./v2_intro.html)（例えばTurtleBot3） のナビゲーションに適したアルゴリズム
<img src="./v6_media/dwa_situation.png" alt="" style="width: 45%;"/>
---
以下の図を見てください。
<img src="./v6_media/dwa0.png" alt="" style="width: 45%;"/>
Vs = 速度 v と角速度 ω のすべての可能な組み合わせの空間
Va = ロボットが次のステップで移動し、障害物に衝突する前に停止できる速度のすべての組み合わせ
---
- 各ステップで、*ダイナミックウィンドウ* Vd を考慮します
Vd = ロボットの現在の速度と最大加速度を考慮して、このステップで達成できるすべての速度のセット
<img src="./v6_media/eq_dwa_vd.png" alt="" style="width: 40%;"/>
<img src="./v6_media/dwa1.png" alt="" style="width: 50%;"/>
速度の最適な組み合わせを探しているスペース：
<img src="./v6_media/eq_dwa_vr.png" alt="" style="width: 15%;"/>
---
Vrで速度の最適な組み合わせ (v, ω) を選択する方法は？
- いくつかの要素を組み合わせた目標関数を最大化します
<img src="./v6_media/dwa_equation.png" alt="" style="width: 40%;"/>
**方向** ⇒ ローカルターゲットへの方向を測定します。ステップの終わりにより良い方向を与える組み合わせが好ましいです。
**目的地** ⇒ ターゲットまでの距離;ステップの最後にロボットが（ローカル）ターゲットに近い組み合わせが推奨されます。
**速度** ⇒ 高速が推奨されます。
α、β、γ はパラメータです。
---
#### 一つのステップの例
<img src="./v6_media/dwa_step.png" alt="" style="width: 60%;"/>
- (vc, ωc) - 現在の速度
- 青い線 - 障害物との衝突を引き起こす組み合わせ
- 緑の線 - 許可された組み合わせ
---
利点
- 障害物と衝突しない、障害物の変化に反応が早い
- 簡易な計算
- 多くの実際のアプリケーションですでに使用されている
欠点
- 選ばれる移動経路が最適でない場合がある
---
→ [実習](v6_1.html)
↑ [ホームページ](index.html)
]]>