モーションプランニング

動作計画、または経路計画(ナビゲーション問題またはピアノ移動問題とも呼ばれる) は、オブジェクトをソースから目的地まで移動する有効な構成のシーケンスを見つける計算問題です。この用語は、計算幾何学、コンピュータアニメーション、ロボット工学、コンピュータゲームで使用されます。

たとえば、建物内の移動ロボットを遠くのウェイポイントまで移動させる場合を考えてみましょう。ロボットは壁を避け、階段から落ちないようにしながらこのタスクを実行する必要があります。動作計画アルゴリズムは、これらのタスクの説明を入力として受け取り、ロボットの車輪に送信される速度と回転のコマンドを生成します。動作計画アルゴリズムは、関節の数が多いロボット (産業用マニピュレーターなど)、より複雑なタスク (オブジェクトの操作など)、さまざまな制約 (前進のみ可能な車など)、不確実性 (環境またはロボットの不完全なモデルなど) に対応する可能性があります。

動作計画には、自律性、自動化、CAD ソフトウェアでのロボット設計などのロボット工学への応用がいくつかあるほか、デジタルキャラクターのアニメーション化、ビデオゲーム、建築設計、ロボット手術、生体分子の研究など、他の分野での応用もあります。

コンセプト

基本的な動作計画の問題は、既知の障害物との衝突を回避しながら、開始構成 S と目標構成 G を接続する連続パスを計算することです。ロボットと障害物のジオメトリは 2D または 3Dワークスペースで記述され、動作は (おそらくより高次元の)構成空間内のパスとして表されます。

構成スペース

構成はロボットの姿勢を記述し、構成空間C はすべての可能な構成の集合です。例:

ロボットが 2 次元平面 (作業スペース) 内で移動する単一の点 (サイズ 0) である場合、C は平面であり、構成は 2 つのパラメーター (x、y) を使用して表すことができます。
ロボットが平行移動と回転が可能な 2D 形状の場合、作業空間は依然として 2 次元です。ただし、C は特殊ユークリッド群SE (2) = R ² SO (2) ( SO (2) は2D 回転の特殊直交群) であり、構成は 3 つのパラメータ (x、y、θ) を使用して表すことができます。 $\times$
ロボットが平行移動と回転が可能な立体3D形状の場合、作業空間は3次元ですが、Cは特殊ユークリッド群SE(3) = R ³ SO (3)であり、構成には平行移動用の(x、y、z)とオイラー角(α、β、γ)の6つのパラメータが必要です。 $\times$
ロボットが N 個の回転ジョイント（閉ループなし）を備えた固定ベースマニピュレータである場合、C は N 次元になります。

空きスペース

障害物との衝突を回避する構成の集合は、自由空間 C _{freeと呼ばれます。C における C}_freeの補空間は、障害物または禁止領域と呼ばれます。

_{多くの場合、 C free}の形状を明示的に計算するのは非常に困難です。ただし、特定の構成が C _free内にあるかどうかをテストすることは効率的です。まず、順方向運動学によってロボットのジオメトリの位置が決定され、衝突検出によってロボットのジオメトリが環境のジオメトリと衝突するかどうかがテストされます。

ターゲットスペース

ターゲット空間は、ロボットを移動させたい場所を示す自由空間のサブスペースです。グローバル動作計画では、ターゲット空間はロボットのセンサーによって観測可能です。しかし、ローカル動作計画では、ロボットはいくつかの状態ではターゲット空間を観測できません。この問題を解決するために、ロボットは複数の仮想ターゲット空間を通過します。各仮想ターゲット空間は観測可能領域内 (ロボットの周囲) にあります。仮想ターゲット空間はサブゴールと呼ばれます。

障害物スペース

障害物空間はロボットが移動できない空間です。障害物空間は自由空間の反対ではありません。

アルゴリズム

低次元の問題は、配置空間の上にグリッドを重ねるグリッドベースのアルゴリズム、または C _freeの形状と接続性を計算する幾何学的アルゴリズムを使用して解決できます。

複雑な制約条件の下での高次元システムの正確な動作計画は、計算的に扱いにくい。ポテンシャル場アルゴリズムは効率的だが、局所的最小値の犠牲になる（例外は調和ポテンシャル場）。サンプリングベースのアルゴリズムは局所的最小値の問題を回避し、多くの問題を非常に迅速に解決する。パスが存在しないと判断することはできないが、時間が経つにつれて失敗する確率がゼロに減少する。^[要出典]

サンプリングベースのアルゴリズムは現在、^高次元空間における動作計画の最先端技術と考えられており、数十または数百の次元を持つ問題（ロボットマニピュレータ、生体分子、アニメーションデジタルキャラクター、脚付きロボット）に適用され^てい^ます。

グリッドベースの検索

グリッドベースのアプローチでは、構成空間にグリッドを重ね、各構成がグリッドポイントで識別されると想定します。各グリッドポイントでは、ロボットは、それらの間の線が C _free内に完全に含まれている限り、隣接するグリッドポイントに移動できます(これは衝突検出でテストされます)。これにより、アクションのセットが離散化され、検索アルゴリズム( A*など) を使用して、開始からゴールまでのパスが検索されます。

これらのアプローチでは、グリッド解像度を設定する必要があります。グリッドが粗いほど検索は速くなりますが、アルゴリズムは C _freeの狭い部分を通るパスを見つけることができません。さらに、グリッド上の点の数は配置空間次元で指数関数的に増加するため、高次元の問題には適していません。

従来のグリッドベースのアプローチでは、方向変更が特定の基本角度の倍数に制限されるパスが生成され、多くの場合、最適ではないパスが生成されます。任意角度のパスプランニングアプローチでは、パスをグリッドエッジに制限することなく (短いパスを見つけるため)、グリッドエッジに沿って情報を伝播することで (高速に検索するため)、より短いパスを見つけます。

グリッドベースのアプローチでは、ロボットの構成空間に関する知識が変化した場合や、経路追跡中に構成空間自体が変化した場合など、繰り返し検索する必要があることがよくあります。増分ヒューリスティック検索アルゴリズムは、以前の同様の経路計画問題の経験を使用して、現在の問題の検索を高速化することで、迅速に再計画します。

間隔ベースの検索

これらのアプローチは、グリッドではなく構成空間全体をカバーする舗装を生成することを除いて、グリッドベースの検索アプローチに似ています。^[1]舗装は、 X ⁻ ⊂ C _free ⊂ X ⁺となるボックスで作成された2つのサブ舗装X ⁻、X ^{+に分解されます。C}_{free を}特徴付けることは、集合反転問題を解決することと同じです。したがって、C _{free を}線形不等式で記述できない場合は、保証された囲みを持つために区間解析を使用できます。

したがって、ロボットは X ⁻内を自由に移動できますが、 X ^{+の外に出ることはできません。両方のサブ舗装に対して、近傍グラフが構築され、}ダイクストラやA*などのアルゴリズムを使用してパスを見つけることができます。パスが X ^{−で実行可能な場合、 C}_freeでも実行可能です。1つの初期構成からゴールまでのパスが X ⁺に存在しない場合、 C _freeに実行可能なパスが存在しないことが保証されます。グリッドベースのアプローチと同様に、生成されるボックスの数は構成空間の次元に対して指数関数的に増加するため、間隔アプローチは高次元の問題には適していません。

右側の 3 つの図では、2 つの自由度を持つフックが 2 つの水平方向の小さなセグメントを避けながら左から右に移動する必要があることが示されています。

フックの初期構成 (青) から最終構成への動き。2 つの障害物 (赤のセグメント) を回避します。フックの左下隅は水平線上に留まる必要があるため、フックは 2 つの自由度を持ちます。

配置空間をカバーするボックスによる分解: サブ舗装 X ^{− は}すべての赤いボックスの和集合であり、サブ舗装 X ⁺は赤いボックスと緑のボックスの和集合です。パスは上記で表された動きに対応します。

この図は、上記と同じパスに対応していますが、ボックスの数ははるかに少なくなっています。アルゴリズムは、最終結果に影響を与えない構成空間の部分でボックスを二分することを回避します。

ニコラス・デラヌーは、区間解析を用いた部分舗装による分解によって、連結成分の数を数えるなど、 C_{フリーのトポロジーを特徴付けることも可能になることを示した。}^[2]

幾何学アルゴリズム

多角形の障害物の間をロボットが通る

障害物間のオブジェクトの移動

ミンコフスキー和

建物から脱出する方法を見つける

最も遠い光線追跡

現在の位置の周囲に、壁に当たる長さで分類された光線の束があると、ドアが特定されない限り、ロボットは最も長い光線の方向に移動します。このようなアルゴリズムは、建物からの緊急脱出をモデル化するために使用されました。

人工ポテンシャル場

1 つのアプローチは、ロボットの構成を、目標への引力と障害物からの反発力を組み合わせたポテンシャルフィールド内の点として扱うことです。結果として得られる軌道がパスとして出力されます。このアプローチの利点は、軌道がほとんど計算なしで生成されることです。ただし、ポテンシャルフィールドのローカルミニマムに閉じ込められてパスを見つけられなかったり、最適でないパスが見つかったりする可能性があります。人工ポテンシャルフィールドは、静電ポテンシャルフィールド (ロボットを点電荷のように扱う) に似た連続方程式として扱うことも、フィールド内の動きを一連の言語ルールを使用して離散化することもできます。^[3]ナビゲーション関数^[4]または確率ナビゲーション関数^[5]は、ターゲットポイントを除いて最小点を持たないという特性を持つ人工ポテンシャル関数の一種です。

サンプリングベースのアルゴリズム

サンプリングベースのアルゴリズムは、サンプリングされた構成のロードマップを使用して構成空間を表します。基本的なアルゴリズムは、 C 内の N 個の構成をサンプリングし、 C _{free内の構成を}マイルストーンとして使用するために保持します。次に、線分 PQ が完全に C _free内にある場合、2 つのマイルストーン P と Q を接続するロードマップが構築されます。ここでも、衝突検出を使用して C _{freeに含まれるかどうかをテストします。 S と G を接続するパスを見つけるために、それらをロードマップに追加します。ロードマップ内のパスが S と G にリンクしている場合、プランナーは成功し、そのパスを返します。そうでない場合、理由は明確ではありません。 C}_freeにパスがないか、プランナーが十分なマイルストーンをサンプリングしなかったかのどちらかです。

これらのアルゴリズムは、組み合わせアルゴリズムとは異なり、実行時間が C の次元に (明示的に) 指数関数的に依存しないため、高次元の構成空間に適しています。また、実装も (一般的に) 大幅に簡単です。確率的に完全であるため、時間が経つにつれて、ソリューションが生成される確率は 1 に近づきます。ただし、ソリューションが存在しないかどうかを判断できません。

C _{freeの基本的な}可視性条件を考えると、構成の数 N が大きくなるにつれて、上記のアルゴリズムが解を見つける確率は指数関数的に 1 に近づくことが証明されています。^[6]可視性は C の次元に明示的に依存するわけではありません。つまり、可視性が「良好な」高次元空間や可視性が「不良」な低次元空間が存在する可能性があります。サンプルベースの方法の実験的成功は、最も一般的に見られる空間の可視性が良好であることを示唆しています。

この基本的なスキームには多くのバリエーションがあります。

通常、すべてのマイルストーンのペアではなく、近くのマイルストーンのペア間のセグメントのみをテストする方がはるかに高速です。
非均一なサンプリング分布は、ロードマップの接続性を向上させる領域に、より多くのマイルストーンを配置しようとします。
準ランダムサンプルは通常、疑似ランダムサンプルよりも構成空間をより適切にカバーしますが、最近のいくつかの研究では、ランダム性のソースの影響はサンプリング分布の影響と比較して最小限であると主張しています。
方向性マルコフ連鎖モンテカルロランダムウォークをいくつかのローカル提案分布とともに実行することにより、ローカルサンプリング^{[7]を採用します。}
湾曲した視線を可能にすることで、与えられた問題を解決するために必要なマイルストーンの数を大幅に減らすことが可能です（例えば、2つのマイルストーン間の道を塞ぐ障害物の上を這うことによって^[8]）。
必要な計画クエリが 1 つまたは少数の場合、必ずしも空間全体のロードマップを作成する必要はありません。この場合、ツリー成長バリアントの方が通常は高速です (単一クエリ計画)。同じ空間に対して多数のクエリを実行する場合 (複数クエリ計画)、ロードマップは依然として有用です。

注目すべきアルゴリズムのリスト

完全性とパフォーマンス

モーションプランナーが完全であるとは、プランナーが有限時間内に解を生成するか、解が存在しないことを正しく報告する場合に言えます。完全なアルゴリズムのほとんどは、ジオメトリに基づいています。完全なプランナーのパフォーマンスは、計算の複雑さによって評価されます。この特性を数学的に証明する場合、漸近的限界だけでなく有限時間内に発生することを確認する必要があります。これは特に問題になります。特定の証明手法中に、(限界ケースでのみ収束する) 無限シーケンスが発生した場合、理論的にはアルゴリズムが停止しないからです。直感的な「トリック」(多くの場合、帰納法に基づく) は、通常、収束すると誤って考えられますが、これは無限限界に対してのみ行われます。言い換えると、解は存在しますが、プランナーはそれを報告しません。したがって、この特性はチューリング完全性に関連しており、ほとんどの場合、理論的な基盤/ガイダンスとして役立ちます。ブルートフォースアプローチに基づくプランナーは常に完全ですが、有限で離散的なセットアップでのみ実現可能です。

実際には、アルゴリズムの終了は、最大反復回数のみを許可し、解の有無にかかわらず常に停止するカウンタを使用することによって常に保証できます。リアルタイムシステムの場合、これは通常、プロセスを強制終了するウォッチドッグタイマーを使用することによって実現されます。ウォッチドッグは、すべてのプロセスから独立している必要があります (通常は低レベルの割り込みルーチンによって実現されます)。ただし、前の段落で説明した漸近的なケースには、この方法では到達しません。ウォッチドッグは、これまでに見つかった最良のもの (何もないよりはまし) または何もないことを報告しますが、何もないことを正しく報告することはできません。ウォッチドッグを含むすべての実現は常に不完全です (すべてのケースを有限時間で評価できる場合を除く)。

完全性は、非常に厳密な数学的正しさの証明 (多くの場合、ツールやグラフベースの方法によって支援されます) によってのみ提供され、アプリケーションに安全性コンテンツが含まれている場合にのみ、専門家によって実行される必要があります。一方、完全性の反証は、無限ループを 1 つ見つけるか、間違った結果が 1 つ返されるだけでよいため簡単です。アルゴリズムの形式検証/正しさは、それ自体が研究分野です。これらのテストケースを正しく設定することは、非常に高度なタスクです。

解像度完全性とは、基礎となるグリッドの解像度が十分に高い場合に、プランナーがパスを見つけることが保証されるという特性です。ほとんどの解像度完全プランナーは、グリッドベースまたは間隔ベースです。解像度完全プランナーの計算複雑度は、基礎となるグリッド内のポイントの数に依存し、O(1/h ^d ) です。ここで、h は解像度 (グリッドセルの 1 辺の長さ)、d は構成空間の次元です。

確率的完全性とは、より多くの「作業」が実行されるにつれて、プランナーがパス (存在する場合) を見つけられない確率が漸近的にゼロに近づくという特性です。いくつかのサンプルベースの方法は確率的に完全です。確率的に完全なプランナーのパフォーマンスは、収束率によって測定されます。実際のアプリケーションでは、平均収束時間に基づいてウォッチドッグのタイムアウトを設定できるため、通常この特性が使用されます。

不完全なプランナーは、実行可能なパスが存在する場合でも、必ずしも実行可能なパスを生成するわけではありません (最初の段落を参照)。不完全なプランナーは、保証された時間が経過すると必ず停止し、他のルーチンが引き継ぐことができるため、実際にはうまく機能することがあります。

問題の変種

この基本的な問題のさまざまなバリエーションを処理するために、多くのアルゴリズムが開発されてきました。

差分制約

ホロノミック

マニピュレーターアーム（ダイナミクス付き）

非ホロノミック

ドローン
車
一輪車
飛行機
加速度制限システム
動く障害物（時間は後戻りできない）
ベベルチップステアリングニードル
差動駆動ロボット

最適性制約

ハイブリッドシステム

ハイブリッドシステムとは、離散動作と連続動作を組み合わせたシステムのことです。このようなシステムの例は次のとおりです。

不確実性

動きの不確実性
情報が不足しています
アクティブセンシング
センサーレス計画
ネットワーク制御システム^[9]

環境上の制約

ダイナミクスマップ^[10]

アプリケーション

参照

動くソファ問題- 角を曲がって移動できる最大の 2 次元形状を見つける数学の問題
ジンバルロック– 機械工学における同様の従来の問題
運動力学計画
登山問題
OMPL - オープンモーションプランニングライブラリ
パスファインディング
小石の運動問題- 複数ロボットの運動計画
最短経路問題
速度障害

参考文献

^ Jaulin, L. (2001). 「区間とグラフを使用した経路計画」(PDF) . Reliable Computing . 7 (1).
^ Delanoue, N.; Jaulin, L.; Cottenceau, B. (2006). 「セットの連結コンポーネントの数のカウントとロボットへの応用」。応用並列コンピューティング。科学コンピューティングの最新技術(PDF)。コンピュータサイエンスの講義ノート。 Vol. 3732。 pp. 93–101。CiteSeerX 10.1.1.123.6764。doi :10.1007/11558958_11。ISBN 978-3-540-29067-4。 {{cite book}}:|journal=無視されました (ヘルプ)
^ Wolf, Joerg Christian; Robinson, Paul; Davies, Mansel (2004)。「動的環境における自律ロボットのベクトルフィールドパスプランニングと制御」。Proc . 2004 FIRA Robot World Congress。釜山、韓国: 論文 151。
^ ラヴァル、スティーブン、計画アルゴリズム第8章、2021年4月15日アーカイブ、Wayback Machine
^ Hacohen, Shlomi; Shoval, Shraga; Shvalb, Nir (2019). 「確率的静的環境の確率ナビゲーション関数」.国際制御、オートメーション、システムジャーナル. 17 (8): 2097–2113. doi :10.1007/s12555-018-0563-2. S2CID 164509949.
^ Hsu, D.; JC Latombe, JC ; Motwani, R. (1997). 「拡張構成空間での経路計画」。国際ロボット工学およびオートメーション会議の議事録。第 3 巻。pp. 2719–2726。doi : 10.1109/ ROBOT.1997.619371。ISBN 978-0-7803-3612-4.S2CID 11070889 。
^ Lai, Tin; Morere, Philippe; Ramos, Fabio; Francis, Gilad (2020). 「ベイジアンローカルサンプリングベースの計画」. IEEE Robotics and Automation Letters . 5 (2): 1954–1961. arXiv : 1909.03452 . doi :10.1109/LRA.2020.2969145. ISSN 2377-3766. S2CID 210838739.
^ Shvalb, N.; Ben Moshe, B.; Medina, O. (2013). 「超冗長機構セットのためのリアルタイム動作計画アルゴリズム」. Robotica . 31 (8): 1327–1335. CiteSeerX 10.1.1.473.7966 . doi :10.1017/S0263574713000489. S2CID 17483785.
^ Scordamaglia, V.; Nardi, VA (2021). 「スキッドおよびスリップ現象の影響を受けるネットワーク制御スキッドステア追跡移動ロボットのセットベースの軌道計画アルゴリズム」。Journal of Intelligent & Robotic Systems。101。Springer Nature BV doi :10.1007/s10846-020-01267-0。S2CID 229326435 。
^ Kucner, Tomasz Piotr; Lilienthal, Achim J.; Magnusson, Martin; Palmieri, Luigi; Srinivas Swaminathan, Chittaranjan (2020). 移動ロボットの空間動作パターンの確率的マッピング。認知システムモノグラフ。第40巻。doi :10.1007/ 978-3-030-41808-3。ISBN 978-3-030-41807-6. ISSN 1867-4925. S2CID 52087877.
^ Steven M. LaValle (2006年5月29日). プランニングアルゴリズム. ケンブリッジ大学出版局. ISBN 978-1-139-45517-6。

さらに読む

ラトンブ、ジャン＝クロード（2012）。ロボット動作計画。Springer Science & Business Media。ISBN 978-1-4615-4022-9。
計画アルゴリズム、Steven M. LaValle、2006年、Cambridge University Press、ISBN 0-521-86205-1。
ロボット動作の原理：理論、アルゴリズム、実装、H. Choset、W. Burgard、S. Hutchinson、G. Kantor、LE Kavraki、K. Lynch、および S. Thrun、MIT Press、2005 年 4 月。
マーク・デ・バーグ。マルク・ヴァン・クレベルド。マーク・オーヴァーマースとオトフリード・シュワルツコップ (2000)。計算幾何学(改訂第 2 版)。スプリンガー・フェルラーグ。ISBN 978-3-540-65620-3。第13章: ロボットの動作計画: pp. 267–290。

外部リンク

「オープンロボティクスオートメーション仮想環境」、http://openrave.org/
ジャン＝クロード・ラトンブがロボットと動作計画について語る、2000 年 4 月 5 日
「オープンモーションプランニングライブラリ ( OMPL )」、http://ompl.kavrakilab.org
「モーションストラテジーライブラリ」、http://msl.cs.uiuc.edu/msl/
「モーションプランニングキット」、https://ai.stanford.edu/~mitul/mpk
「Simox」、http://simox.sourceforge.net
「ロボットの動作計画と制御」、http://www.laas.fr/%7Ejpl/book.html

[1] Jaulin, L. (2001). 「区間とグラフを使用した経路計画」(PDF) . Reliable Computing . 7 (1).

[2] Delanoue, N.; Jaulin, L.; Cottenceau, B. (2006). 「セットの連結コンポーネントの数のカウントとロボットへの応用」。応用並列コンピューティング。科学コンピューティングの最新技術(PDF)。コンピュータサイエンスの講義ノート。 Vol. 3732。 pp. 93–101。CiteSeerX 10.1.1.123.6764。doi :10.1007/11558958_11。ISBN 978-3-540-29067-4。 {{cite book}}:|journal=無視されました (ヘルプ)

[3] Wolf, Joerg Christian; Robinson, Paul; Davies, Mansel (2004)。「動的環境における自律ロボットのベクトルフィールドパスプランニングと制御」。Proc . 2004 FIRA Robot World Congress。釜山、韓国: 論文 151。

[4] ラヴァル、スティーブン、計画アルゴリズム第8章、2021年4月15日アーカイブ、Wayback Machine

[5] Hacohen, Shlomi; Shoval, Shraga; Shvalb, Nir (2019). 「確率的静的環境の確率ナビゲーション関数」.国際制御、オートメーション、システムジャーナル. 17 (8): 2097–2113. doi :10.1007/s12555-018-0563-2. S2CID 164509949.

[6] Hsu, D.; JC Latombe, JC ; Motwani, R. (1997). 「拡張構成空間での経路計画」。国際ロボット工学およびオートメーション会議の議事録。第 3 巻。pp. 2719–2726。doi : 10.1109/ ROBOT.1997.619371。ISBN 978-0-7803-3612-4.S2CID 11070889 。

[7] Lai, Tin; Morere, Philippe; Ramos, Fabio; Francis, Gilad (2020). 「ベイジアンローカルサンプリングベースの計画」. IEEE Robotics and Automation Letters . 5 (2): 1954–1961. arXiv : 1909.03452 . doi :10.1109/LRA.2020.2969145. ISSN 2377-3766. S2CID 210838739.

[8] Shvalb, N.; Ben Moshe, B.; Medina, O. (2013). 「超冗長機構セットのためのリアルタイム動作計画アルゴリズム」. Robotica . 31 (8): 1327–1335. CiteSeerX 10.1.1.473.7966 . doi :10.1017/S0263574713000489. S2CID 17483785.

[9] Scordamaglia, V.; Nardi, VA (2021). 「スキッドおよびスリップ現象の影響を受けるネットワーク制御スキッドステア追跡移動ロボットのセットベースの軌道計画アルゴリズム」。Journal of Intelligent & Robotic Systems。101。Springer Nature BV doi :10.1007/s10846-020-01267-0。S2CID 229326435 。

[10] Kucner, Tomasz Piotr; Lilienthal, Achim J.; Magnusson, Martin; Palmieri, Luigi; Srinivas Swaminathan, Chittaranjan (2020). 移動ロボットの空間動作パターンの確率的マッピング。認知システムモノグラフ。第40巻。doi :10.1007/ 978-3-030-41808-3。ISBN 978-3-030-41807-6. ISSN 1867-4925. S2CID 52087877.

[LaValle2006-11] Steven M. LaValle (2006年5月29日). プランニングアルゴリズム. ケンブリッジ大学出版局. ISBN 978-1-139-45517-6。