目次
- 目次
- はじめに
- 経路計画 (Path Planning or Motion Planning)の各アルゴリズム
- 各経路生成アルゴリズムの利点と欠点
- 参考資料
- MyEnigma Supporters
はじめに
ロボットの自律移動技術の中で、
重要なものの一つに、
経路計画(Path planning and Motion planning)があります。
(その他の自律移動技術に関しては下記を参照ください
今回の記事では、
ロボットの経路計画問題における代表的な技術の分類と
その詳細やサンプルコードの記事のリンクをまとめておきます。
加えて、それぞれの技術の利点と欠点を
あるサーベイ論文を元にまとめました。
経路計画 (Path Planning or Motion Planning)の各アルゴリズム
経路計画は，
自己位置推定で得られた位置姿勢と
作成した周辺環境の地図情報を用いて，
どの経路を走行すれば，安全で，走行距離が短く，
そしてロボットの運動モデルに沿った走行ができるかを
ロボット自身が判断することです．
つまり，最もロボットにとって最適な経路を計算する技術とも言えます。
加えて、周辺環境の変化に応じて
生成する経路も更新される必要があるため、
経路計画において計算コストも重要な要素になります。
ロボットでよく使用される経路生成のアルゴリズムは
大きくわけて、下記のように分類されます。
Geometric Analytic Approach
Geometric Analytic Approachは、
幾何学的な関係を用いて、
ロボットのコースを生成するアルゴリズム群です。
主に、CADの技術である曲線生成アルゴリズムを利用します。
下記が代表的なアルゴリズムです。
アルゴリズムの詳細や特徴などはそれぞれの記事を参照ください。
Spline Planning
Voronoi Diagram Planning
Dubins Path Planning
Reed-sheep Planning
Graph Search Approach
Graph Search Approachは
ロボットの走行箇所を
グラフやグリッドで表し、
その中でグラフ理論のアルゴリズムを利用して、
経路探索を実施する手法です。
代表的なアルゴリズムとして下記のアルゴリズムがあります。
アルゴリズムの詳細や特徴などはそれぞれの記事を参照ください。
ダイクストラ法
A*
Dynamic Window Approach
Dynamic Window Approachは、
ある一定時刻、入力を一定だと仮定して
その中でロボットの運動モデルを使って
入力の取りうる範囲(Window)を計算し、
そのWindowの中で最もコストが低い制御入力を選択します。
アルゴリズムの詳細や特徴などは下記の記事を参照ください。
State Lattice Approach
State Lattice Approachは、
ある二点間のパスを車両モデルと入力モデルに基いて、
最適化で計算する技術と、
周辺環境の情報から効率的に目標点をサンプリングする技術を
組み合わせた経路計画技術です。
アルゴリズムの詳細や特徴などは下記のそれぞれの記事を参照ください。
Model Predictive Trajectory Optimization
State Lattice Local planning
Randomized Approach
Randomized Approachは、
ランダムにサンプリングした点を元に、
経路を徐々に探索していく経路計画アルゴリズムです。
一般的にRRTと呼ばれます。
コースの評価の仕方などでいくつか手法があるのですが、
アルゴリズムの詳細や特徴などは下記のそれぞれの記事を参照ください。
RRT
RRT *
Closed RRT
Model Predictive Control
Model Predictive Controlは、
ロボットのモデルと最適化技術を使って
最適な各時刻の入力と軌跡を計算する経路計画手法です。
アルゴリズムの詳細や特徴などはそれぞれの記事を参照ください。
各経路生成アルゴリズムの利点と欠点
下記の論文で議論されている内容をベースに
各経路生成アルゴリズムの利点と欠点をまとめておきます。
A Review of Motion Planning Techniques for Automated Vehicles - IEEE Journals & Magazine
| アルゴリズム種類 | 利点 | 欠点 |
|---|---|---|
| スプライン補間 | 計算コストが低い。曲率の連続性 | コースの最適性が考慮されない。障害物などの境界条件が考慮できない |
| クロソイド曲線 | 曲率が線形で連続になる | パスの生成が積分を必要とするために、計算時間が若干多い。曲率は連続だがスムーズではない。単体では複雑な形状のコースを生成できない。 |
| Dubins and Reed-sheep Path | 計算コストが低い。実装が容易。ステアリング型のロボットでは最も短いパスが生成される | コースの曲率が連続ではない。単独では複雑な形状のコースを生成できない。 |
| 多項式近似 | 計算コストが低い。複雑な形状のコースを生成できる。 | ４次元以上の多項式で近似したい場合、解を求めるのが難しい。 |
| ベジェ曲線 | 計算コストが低い。複雑な形状のコースを生成できる。コントロールポイントを使って、簡単にコースを変形できる。 | コントロールポイントが増えると計算時間が増大し、解を求めるのも難しくなる。 |
| Dynamic Window Approach | ロボットの未来の動きを予想しながらパスが引ける。実装が容易。計算コストが低い。 | 入力が一定であるという仮定があるため、複雑な走行ができない。 |
| ダイクストラ法 | ノードやグリッドで表現された空間において最短コースを生成できる。大域経路生成に向いている | ヒューリスティックを使わないため、ノードが増えると計算量が大きくなる。コースが連続ではない。リアルタイムのアプリケーションには向かない |
| A* (と関連する技術) | ダイクストラ法と同じ利点を持つ。ヒューリスティックを使うため、ダイクストラ法よりも計算が早い | コースが連続ではない。正しいヒューリスティック関数を決めるのが難しい |
| State Lattice Planner | 多次元(位置、速度、加速度、時間など)を考慮したコースが生成できる。局所的経路生成や、動的環境にあっている | 計算コストが事前のlookup tableに依存する。目標地点がState Latticeの解像度に依存する。 |
| RRT(と関連技術) | 多次元の空間において、高速に解を計算することができる。時間が与えらればたいていの問題の解を得ることができる。大域的にも局所的にもパスを生成できる | 通常のRRTではパスがjerkyになってしまう。RRT*では最適なパスを生成できるが利用できる計算時間による |
| MPC | 車両のモデルや周辺環境などの制約条件を考慮したパスが生成できる。コスト関数に応じて最適なパスを生成できる。 | 計算コストが大きい。制約条件が厳しい場合に解が求まらない場合がある。 |
参考資料
MyEnigma Supporters
もしこの記事が参考になり、
ブログをサポートしたいと思われた方は、
こちらからよろしくお願いします。
