Control
可視グラフ (visibility graph)
2 次元・多角形の障害物の間の最短経路を厳密に求めるグラフ。頂点同士を「見える」なら辺で結び、Dijkstra / A* で解く (Lozano-Pérez & Wesley 1979)
要点: スタート・ゴール・障害物の全頂点をノードにし、2 点を結ぶ線分が障害物の内部を通らなければ辺で結ぶ (重み = 長さ)。このグラフの最短経路が、平面上で多角形の障害物を避ける最短経路そのものになる (Lozano-Pérez & Wesley, CACM 1979)。
手順
- ノード: スタート、ゴール、(膨張後の) 障害物の多角形の全頂点
- 辺: 2 ノードを結ぶ線分が障害物の内部と交わらなければ張る。重みはユークリッド距離
- 探索: Dijkstra または A* (ヒューリスティック = 直線距離)
厳密な理由
多角形の障害物を避ける平面上の最短経路は、障害物の頂点でだけ折れる折れ線になる。頂点以外の場所で折れていれば、その点の付近を直線に置き換えて短くできるから。したがって候補を頂点に限っても最短経路を落とさない。
計算量
| 作り方 | 計算量 (n = 頂点数) |
|---|---|
| 全ペア × 全辺の交差判定 | |
| 回転掃引 (rotational sweep) | |
| 縮約可視グラフ (支持線・二重接線の辺だけ残す) | 辺の数を減らせる。最短経路は保たれる |
他の手法との比較
| 可視グラフ | グリッド A* | RRT* | |
|---|---|---|---|
| 最適性 | 厳密 | 格子の解像度の分だけ近似 | 漸近的に最適 (試行数 → ∞) |
| 決定性 | 決定的 | 決定的 | 乱数に依存 |
| 向く場面 | 2 次元・多角形・障害物が少ない | 地図がラスタ / コストマップ | 高次元 (アーム等) |
使うときの注意
- 膨張: 最短経路は障害物の角に接する。先に障害物を機体の外接半径 + 余裕だけ膨らませる (Minkowski 和)。円で膨らませた角は多角形で近似する
- 平滑化: 出力は折れ線で、角で速度 0 にしない限り走れない。Bスプライン等で丸め、TOPP-RA で速度を割り付ける。丸めた曲線が膨張の外に出ないかは別に確かめる
- 2 次元限定: 3 次元の多面体の間の最短経路は辺の途中を通り、問題は NP 困難 (Canny & Reif 1987)
- 動的な障害物: グラフを作り直すか、静的経路 + 局所回避で扱う
関連
最終更新: