Control
障害物の表現 (ベクトルと格子) と膨張
障害物を図形 (多角形・円) で持つか占有格子で持つか。図形で持つときの膨張はミンコフスキー和で、角を長方形のまま広げると r(√2−1) 余計に大きくなる
要点: 形が既知の静的な場では、障害物を図形 (多角形・円) で持ち、可視グラフ で厳密な最短経路を出す。膨張はミンコフスキー和で、角は丸くなる。長方形のまま四方に r 広げると、角で 余計に大きくなる。
ベクトルと格子
| ベクトル (図形) | 占有格子 | |
|---|---|---|
| 精度 | 座標の精度そのまま | 格子の解像度 |
| 計画 | 可視グラフで厳密 | A* / Dijkstra で近似 |
| 膨張 | ミンコフスキー和 (図形演算) | 距離変換 |
| 更新 | 数値を書き換える | 再ラスタライズ |
| 得意 | 寸法が決まっている構造物 | センサの生データ、形が不定の物 |
膨張: ミンコフスキー和
機体を半径 r の円で包むと、機体の中心が入ってはいけない領域は「障害物 ⊕ 半径 r の円」。凸多角形なら、各辺を外へ r 平行移動し、頂点を半径 r の円弧でつないだ形になる。
角の円弧を多角形で近似したときの余計な張り出し (頂点の角が 90° の場合):
| 近似 | 余計な張り出し | r = 0.43 m のとき |
|---|---|---|
| 長方形のまま (四方に r) | 0.178 m | |
| 八角形 (45° で面取り) | 0.035 m | |
| 16 角形 | 0.008 m |
外接側の多角形で近似すると安全側 (正しい膨張を必ず含む)。張り出しが通路の余裕に比べて大きいと、通れる経路を通れないと判断する。
動く障害物
相手機・置かれた物体は円や多角形として実行中に足し、グラフを作り直す。頂点が数十個なら作り直しは ms 単位。
ポテンシャル法 (ベクトル場) との違い
障害物の反発とゴールの引力のベクトルを足して進む方法 (Khatib 1986) は、図形で障害物を持つことと別物。
| 問題 | 内容 |
|---|---|
| 局所最小 | 反発と引力がつり合う点 (凹形状の前など) で止まる |
| 振動 | 狭い通路で両側の反発に挟まれる |
| 経路の保証 | 計画した曲線・速度割り付けを通らない |
大域の経路には使わず、近接時の減速・停止など局所の層に限るのが一般的。
関連
最終更新: