経路探索

経路探索（パスファインディング）とは、コンピュータアプリケーションを用いて2点間の最短経路を探索することです。これは迷路を解く手法のより実用的な応用例と言えます。この研究分野は、重み付きグラフ上で最短経路を見つけるためのダイクストラ法に大きく基づいています。

経路探索は、グラフ理論における最短経路問題と密接に関連しており、大規模ネットワーク内の2点間において、何らかの基準（最短、最安、最速など）を最もよく満たす経路を特定する方法を研究するものである。

パスファインディング手法の本質は、グラフをある頂点から開始し、隣接するノードを探索して目的のノードに到達することです。一般的には、最もコストの低い経路を見つけることを目的としています。幅優先探索などのグラフ探索手法は、十分な時間があれば経路を見つけることができますが、グラフを「探索」する他の手法は、より早く目的に到達する傾向があります。例えるなら、人が部屋を横切って歩く場合です。人は、考えられるすべての経路を事前に調べるのではなく、通常は目的の方向に歩き、障害物を避けるために経路から逸れるだけで、その逸れもできるだけ小さくします。

パスファインディングの主な問題は、（1）グラフ内の2つのノード間のパスを見つけること、および（2）最短パス問題、つまり最適な最短パスを見つけることの2つです。幅優先探索や深さ優先探索などの基本的なアルゴリズムは、すべての可能性を網羅することで最初の問題に対処します。与えられたノードから開始して、目的地のノードに到達するまで、すべての潜在的なパスを反復します。これらのアルゴリズムは、${\displaystyle O(|V|+|E|)}$または線形時間。ここで、Vは頂点の数、Eは頂点間のエッジの数である。

より複雑な問題は、最適な経路を見つけることです。この場合の網羅的なアプローチはベルマン・フォードアルゴリズムとして知られており、その時間計算量は${\displaystyle O(|V||E|)}$、または2乗時間。ただし、最適な経路を見つけるためにすべての可能な経路を調べる必要はありません。A *アルゴリズムやダイクストラ法などのアルゴリズムは、ヒューリスティックまたは動的計画法によって戦略的に経路を排除します。不可能な経路を排除することで、これらのアルゴリズムは、 という低い時間計算量を達成できます。${\displaystyle O(|E|\log(|V|))}$[ ^{1 ]​}

上記のアルゴリズムは、前処理なしでグラフ上で動作する最も優れた汎用アルゴリズムの一部です。しかし、実際の旅行経路システムでは、グラフを前処理してパフォーマンスを向上させるアルゴリズムによって、さらに優れた時間計算量を達成できます。^{[ 2 ]}そのようなアルゴリズムの1つが縮約階層です。

パスファインディングは、動くオブジェクトやNPCが登場するビデオゲームに組み込まれてきた歴史があります。 1982年にクリス・クロフォードは、コンピュータの戦車がU字型の湖の中の陸地に閉じ込められるというTankticsのパスファインディングの問題を解決するために「多くの時間を費やした」と述べています。「多くの無駄な努力の後、より良い解決策を発見しました。マップからU字型の湖を削除することです」と彼は言いました。^{[ 6 ]}

階層的な経路探索

階層的パスファインディングの概念は、ビデオゲーム業界で採用される以前から存在し、古典的な人工知能研究にルーツがあります。最も初期の正式な記述の1つは、1974年のSacerdotiによるABSTRIPS（Abstraction-Based STRIPS）に関する研究^{[ 7 ]}に登場し、論理ベースのプランニングにおける階層的探索戦略を探求しました。HolteらによるHierarchical A*などの後の研究は、探索問題における抽象化階層の理論をさらに発展させました。^{[ 8 ]}

ビデオゲームの分野では、限られたCPU時間で大規模なマップを効率的に計画する必要性から、階層型パスファインディングアルゴリズムが実用化されました。注目すべき進歩は、2004年にBoteaらが発表した階層型パスファインディングA* （HPA*）です。 ^{[ 9 ]} HPA*はマップをクラスタに分割し、隣接するクラスタの入口間の最適なローカルパスを事前に計算します。実行時には、クラスタグラフを通る抽象的なパスを計画し、各クラスタ内でそのパスを洗練します。これにより、探索空間が大幅に削減され、はるかに高速なパフォーマンスでほぼ最適な計画が可能になります。

スターテバントとブロによって開発された部分洗練A*（PRA*）は、同様のアプローチを採用していますが、計画と実行を交互に行うことを重視しています。PRA*は、パス全体を即座に洗練するのではなく、最初の数ステップのみを洗練し、実行中に必要に応じて残りの部分を洗練し続けます。これは、動的な環境で特に有効です。

同様の手法としては、ゲームにおける幾何学的計画に使用されるナビゲーションメッシュ（navmesh）や、複数の輸送手段が関わる巡回セールスマン問題の変形版などにおけるマルチモーダル輸送計画などが挙げられる。

階層型プランナーは、パスファインディングを 2 つのフェーズで実行します。まず、高レベルでクラスタ間を、次に低レベルで個々のクラスタ内をパスファインディングします。^{[ 10 ]}この構造により、ノード数を減らしたガイド付きローカル検索が可能になり、高いパフォーマンスが得られます。主な欠点は、抽象化レイヤーと改良を維持する実装の複雑さです。

例

3000×2000ノードのマップには600万個のタイルが含まれています。最適化されたアルゴリズムを使用しても、この規模で直接パスを計画することは、グラフノードと可能なパスの数が膨大であるため、計算負荷が非常に高くなります。階層的なアプローチでは、マップを300×200ノードのクラスタに分割し、10×10のグリッド（合計100個のクラスタ）を形成します。高レベルの抽象グラフには、わずか100個のノードしか含まれません。これらのクラスタ間でパスを計画しますが、これは計算コストが低くなります。抽象パスが見つかると、パス上の各クラスタを通常のA*プランナーを使用して処理し、その内部の正確な低レベルルートを見つけます。この2段階のプロセスにより、ほぼ最適なパス品質を維持しながら、効率が大幅に向上します。

• ダイクストラ法
• A*探索アルゴリズムは、ダイクストラ法の特殊なケースである。
• D*制約が時間とともに変化する、またはエージェントが最初に経路を計画する時点で制約が完全にはわかっていない問題に対する、増分ヒューリスティック探索アルゴリズムのファミリー
• 任意の角度経路計画アルゴリズムとは、探索グラフのエッジに沿って移動することに限定されない経路を計画するためのアルゴリズム群であり、あらゆる角度を取ることができ、より短く直線的な経路を見つけることができるように設計されています。

マルチエージェント経路探索とは、複数のエージェントが互いに衝突することなく、現在位置から目標位置までの経路を見つけると同時に、すべてのエージェントの経路長の合計などのコスト関数を最適化することです。これは経路探索の一般化です。多くのマルチエージェント経路探索アルゴリズムは、A* から一般化されているか、整数線形計画法などの他のよく研究された問題への還元に基づいています。^{[ 11 ]}しかし、このようなアルゴリズムは通常不完全です。つまり、多項式時間内に解を生成することが証明されていません。Collaborative Diffusionなどの並列アプローチは、マルチエージェント経路探索をセルオートマトンに似たセルなどの計算グリッド構造に展開する、恥ずかしいほど並列なアルゴリズムに基づいています。別のカテゴリのアルゴリズムは、既知のナビゲーションパターン (交通の流れなど) または問題空間のトポロジーを利用することで、最適性を犠牲にしてパフォーマンスを向上させます。^{[ 12 ]}

• あらゆる角度からの経路計画– ユークリッド最短経路を見つけるアルゴリズム 
• 動作計画– 計算上の問題 

• https://melikpehlivanov.github.io/AlgorithmVisualizer
• https://sourceforge.net/projects/argorha
• StraightEdgeは、Javaで開発されたオープンソースの2Dパスファインディング（A *を使用）およびライティングプロジェクトです。アプレットデモも含まれています。
• python-pathfindingオープンソースの Python 2D パスファインディング (ダイクストラ法を使用) およびライティング プロジェクト。
• Daedalus Libはオープンソースソフトウェアです。Daedalus Libは、A*アルゴリズムとファネルアルゴリズムを用いて、完全に動的な三角形分割2D環境モデリングと経路探索を管理します。
• YouTubeの「実際の地図上での経路探索アルゴリズムの可視化」