あらゆる角度の経路計画

任意角度パス計画アルゴリズムは、パス内の曲がり角が任意の角度になるようにしながら、グリッドマップ上の 2 点間のユークリッド最短パスを検索するパスファインディングアルゴリズムです。その結果、オープン エリアを直接通過し、曲がり角が比較的少ないパスが作成されます。 ^[1] A*などの従来のパスファインディング アルゴリズムは、パフォーマンスが不足しているか、ギザギザの間接的なパスを生成します。

現実世界や多くのゲーム マップには、直接移動するのがもっとも効率的であるオープン エリアがあります。従来のアルゴリズムでは、これらの問題を解決するのに十分ではありません。

• 8 連結の離散グリッドグラフ(2D、3D トリプルキュービックグラフの場合は 26) を使用した A* は非常に高速ですが、45 度刻みのパスしか調べません。この動作により、2D では平均 8%、3D では 13% の余分なパス長が発生します。^{[2] : 60, 69}後処理の簡単なスムージング手順を使用して、ギザギザの出力をまっすぐにする (したがって短くする) ことができますが、すべての可能なパスを調べるわけではないため、結果が最適になるとは限りません (より具体的には、ブロックされたセルのどちら側を通過するかを変更することはできません)。利点は、ジャンプポイント検索など、グリッド A* のすべての最適化が適用されることです。
• すべてのグリッドポイントを持つ可視性グラフは、 2D空間での最適解をA*で探索することができます。しかし、頂点を持つグラフの辺の数は であるため、パフォーマンスに問題があります。このようなグラフは、3D空間で常に最適解を提供するとは限りません。^[2]${\displaystyle V}$${\displaystyle O(V^{2})}$

任意角度パス プランニング アルゴリズムは、基本的な可視性グラフ アプローチよりも短時間で、最適またはほぼ最適なソリューションを生成することを目的としています。高速な任意角度アルゴリズムの計算時間は、グリッドベースのソリューションとほぼ同じです。

張り詰めた道

パス内のあらゆる方向変更が何らかの障害物をしっかりと「回り込む」パス。均一なグリッドの場合、最適なパスは緊張したパスのみです。

単一ソース

1 つの頂点から始めて、グラフのすべての部分への最短経路を見つけようとする経路検索問題。

これまでに、ヒューリスティック探索アルゴリズムA* ^[3]に基づく5つの主要な任意角度経路計画アルゴリズムが開発されており、それらはすべてグリッドエッジに沿って情報を伝播します。

• フィールドD* ^{[4] [5]} (FD* ^[6] )と3DフィールドD* ^{[7] [8] - 各頂点の拡張中に補間を使用し、}規則的で不均一なコストグリッドを通るほぼ最適なパスを見つけるD*に基づく動的経路探索アルゴリズム。したがって、フィールドD*は加重領域問題^[9]を解決しようとし、3DフィールドD*は対応する3次元問題を解決しようとします。
  • マルチ解像度フィールドD* ^[10] – マルチ解像度グリッド用のフィールドD*の拡張。
• Theta* ^{[6] [11]} - A*と同じメインループを使用しますが、頂点の各拡張に対して、と の後続、 の間に視線チェックがあります。視線がある場合、 から へのパスが使用されます。これは、からおよびへのパスよりも常に少なくとも短いためです。このアルゴリズムは、均一コストのグリッドでのみ機能します。^[6] AP Theta* ^{[6] [11]}は、角度伝播を使用して視線計算の実行コストをO (1)に削減する Theta* の最適化です。 ${\displaystyle s}$${\displaystyle parent(s)}$${\displaystyle s}$${\displaystyle s'}$${\displaystyle parent(s)}$${\displaystyle s'}$${\displaystyle parent(s)}$${\displaystyle s}$${\displaystyle s}$${\displaystyle s'}$
  • Lazy Theta* ^[12]は、Theta*の別の最適化であり、遅延評価を使用して、各ノードの視線計算を探索時から拡張時まで遅らせることで視線計算の数を減らします。3D空間で実行するのに十分な能力があります。
  • インクリメンタルファイ* ^{[13]は、未知の2D環境向けに設計された、}増分的でより効率的なシータ*の変種です。^[2]
  • 厳密なTheta*と再帰的な厳密なTheta* ^[14]は、 ANYAによって導入されたTaut Pathsに探索空間を制限することでTheta*を改良したものです。Theta*と同様に、これは最適に近いパスを返すアルゴリズムです。
• ブロックA* ^[15] - グリッドの小さなセクション上のすべての可能なパスを含むローカル距離データベースを生成します。このデータベースを参照して、任意の角度のパスを部分的に素早く見つけます。
• ANYA ^[16] - 探索空間をタウトパス（経路内のあらゆる方向変更が何らかの障害物の周りをしっかりと「巻き込む」パス）に制限することで、任意の角度の最適なパスを見つけます。ポイントの間隔を単一のポイントではなくノードとして見ます。知られている中で最も高速なオンライン最適手法です。このアルゴリズムは2Dグリッドに制限されています。
• CWave ^{[17] [18]} - 幾何学的プリミティブ（離散的な円弧と線）を使用して、グリッド上の伝播する波面を表します。実用的な地図上の単一ソースのパス計画では、グラフ検索ベースの方法よりも高速であることが実証されています。最適な実装と整数演算の実装があります。

上記のファミリーとは異なる A* ベースのアルゴリズムもあります。

• 可視グラフアプローチのパフォーマンスは、緊張したパスを形成できるエッジのみを考慮するスパースアプローチによって大幅に向上できます。ENLSVGと呼ばれるマルチレベルバージョンはANYAよりも高速であることが知られていますが、前処理なしでしか使用できません。^[19]
• PolyAnyaは、ANYAを一般化して、多角形の障害物がある非グリッドマップでも動作するようにしました。^[20]高速で、前処理を必要とせず（ENLSVGとは異なり）、最適です（RRTとは異なります）。
• 以下に説明するRRTソリューションと同様に、実際の車両を操縦する際にはステアリング制約も考慮する必要があることがよくあります。ハイブリッドA*は、A*の拡張版で、車両の状態を表す2つの追加次元を考慮しているため、実際にパスが可能です。これは、スタンフォードレーシングがDARPAアーバンチャレンジへのエントリーであるジュニアのナビゲーションシステムの一部として作成しました。^[21]より詳細な説明は、Peteritらによって書かれています。^[22]

さらに、高次元の探索空間での検索では、たとえばシステムの構成空間に考慮する必要のある自由度が多く含まれる場合（動作計画を参照）、および/または運動量を考慮する必要がある場合（これにより、探索空間の次元数が実質的に2倍になる可能性があり、運動量を含むこのより大きな空間は位相空間として知られています）には、ますます短い経路を見つけることで（ほぼ確実に）最適経路に収束する、迅速探索ランダムツリー（RRT）^[23]の変種が開発されています。

• 高速探索ランダムグラフ（RRG）とRRT* ^{[24] [25]}
• インフォームドRRT* ^[26]は、 A*がダイクストラのアルゴリズムを改良したのと同様に、ヒューリスティックを導入することでRRT*の収束速度を改善します。

• 確率的ロードマップ

任意角度の経路計画は、より最適な経路が望まれるロボットナビゲーションやリアルタイム戦略ゲームに役立ちます。たとえば、Hybrid A*はDARPAチャレンジへのエントリーとして使用されました。^[21]いくつかの例のステアリング認識特性は、自動運転車にも応用できます。

• モーションプランニング

• Lazy Theta*: より高速なあらゆる角度の経路計画
• A. NashとS. Koenig。「任意の角度の経路計画」人工知能マガジン、34、(4)、85-107、2013年。
• Any Angle Pathfinding、Shunhao Oh のオープンソースデモコード