パスファインディング

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

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

アルゴリズム

基本的に、経路探索法は、1 つの頂点から始めて、目的のノードに到達するまで隣接するノードを探索することでグラフを検索します。通常は、最も安価なルートを見つけることを目的としています。幅優先探索などのグラフ探索法では、十分な時間があればルートが見つかりますが、グラフを「探索」する他の方法の方が、より早く目的地に到達する傾向があります。例えとして、部屋を横切って歩く人が挙げられます。人は、事前にすべての可能なルートを調べるのではなく、通常は目的地の方向に歩き、障害物を避けるためだけにパスから外れ、できるだけ外れないようにします。

経路探索における 2 つの主な問題は、(1)グラフ内の 2 つのノード間の経路を見つけることと、(2)最短経路問題(最適な最短経路を見つけること)です。幅優先探索や深さ優先探索などの基本的なアルゴリズムは、すべての可能性を尽くすことで最初の問題に対処します。つまり、指定されたノードから始めて、目的のノードに到達するまですべての可能性のある経路を反復します。これらのアルゴリズムは、つまり線形時間で実行されます。ここで、V は頂点の数、E は頂点間の辺の数です。 $O(|V|+|E|)$

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

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

ダイクストラのアルゴリズム

グラフベースの経路探索アルゴリズムの一般的な例としては、ダイクストラのアルゴリズムがあります。^[3]このアルゴリズムは、開始ノードと候補ノードの「オープンセット」から始まります。各ステップで、開始からの距離が最も短いオープンセットのノードが調べられます。ノードは「閉じた」とマークされ、そのノードに隣接するすべてのノードがまだ調べられていない場合はオープンセットに追加されます。このプロセスは、目的地への経路が見つかるまで繰り返されます。距離が最も短いノードが最初に調べられるため、目的地が最初に見つかったときは、そこへの経路が最短経路になります。^[4]

ダイクストラのアルゴリズムは、負のエッジウェイトがある場合には失敗します。ノード A、B、C がエッジ AB = 3、AC = 4、BC = -2 で接続された無向グラフを形成するという仮想的な状況では、A から C への最適パスのコストは 1 で、A から B への最適パスのコストは 2 です。ダイクストラのアルゴリズムは A から開始し、最も近い B を最初に調べます。それにコスト 3 を割り当て、閉じたものとしてマークします。つまり、そのコストは再評価されません。したがって、ダイクストラは負のエッジウェイトを評価できません。ただし、多くの実用的な目的では負のエッジウェイトは決して存在しないため、ダイクストラのアルゴリズムはパスファインディングの目的にほぼ適しています。

A*アルゴリズム

A*は、ダイクストラのアルゴリズムのバリエーションで、さまざまな用途に使用できます。A* は、各オープンノードに、そのノードへのエッジの重みとそのノードと終了点の間のおおよその距離を加えた重みを割り当てます。このおおよその距離はヒューリスティックによって検出され、そのノードと終了点の間の最小距離を表します。これにより、最初のパスが見つかると、より長いパスを除外できます。開始点と終了点の間に長さ x のパスがあり、ノードと終了点の間の最小距離が x より大きい場合、そのノードを調べる必要はありません。^[5]

A* はこのヒューリスティックを使用して、ダイクストラのアルゴリズムに対する動作を改善します。ヒューリスティックがゼロに評価されると、A* はダイクストラのアルゴリズムと同等になります。ヒューリスティック推定値が増加して実際の距離に近づくと、A* は引き続き最適なパスを見つけますが、実行速度が速くなります (検査するノードの数が少なくなるため)。ヒューリスティックの値が実際の距離とまったく同じ場合、A* は最も少ないノードを調べます。(ただし、常に実際の距離を計算するヒューリスティック関数を記述することは一般に非現実的です。これは、同じ比較結果が、より単純な計算 (たとえば、2 次元空間でユークリッド距離ではなくチェビシェフ距離を使用するなど) を使用して到達できることが多いためです。) ヒューリスティックの値が増加すると、A* が検査するノードの数が少なくなりますが、最適なパスは保証されなくなります。多くのアプリケーション (ビデオゲームなど) では、アルゴリズムを高速に実行し続けるために、これは許容可能であり、望ましいことでもあります。

ビデオゲームでは

パスファインディングは、移動する物体やNPCが登場するビデオゲームに取り入れられてきた歴史がある。 1982年にクリス・クロフォードは、タンクティクスのパスファインディングの問題を解決するために「多大な時間を費やした」と述べている。タンクティクスでは、コンピュータの戦車がU字型の湖の中に閉じ込められてしまう。「多くの無駄な努力の末、より良い解決策を見つけた。地図からU字型の湖を削除するのだ」と彼は語った。^[6]

階層的経路探索

このアイデアは、 CPU時間を少なくして大きなマップを計画する必要があったビデオゲーム業界によって最初に説明されました。抽象化とヒューリスティックを使用するという概念は古く、ABSTRIPS（Abstraction-Based STRIPS）^[7]という名前で最初に言及されました。これは、ロジックゲームの状態空間を効率的に検索するために使用されました。^[8]同様の手法に、ゲームでの幾何学的計画に使用されるナビゲーションメッシュ（navmesh）や、複数の輸送車両を使用する巡回セールスマン問題で利用されるマルチモーダル輸送計画があります。

マップはクラスターに分割されます。高レベルレイヤーでは、クラスター間のパスが計画されます。計画が見つかった後、2番目のパスが下位レベルのクラスター内で計画されます。^[9]つまり、計画は元の空間でのガイド付きローカル検索である2段階で行われます。利点は、ノードの数が少なく、アルゴリズムのパフォーマンスが非常に優れていることです。欠点は、階層型パスプランナーの実装が難しいことです。^[10]

例

マップのサイズは 3000x2000 ノードです。ノードベースでパスを計画するには、非常に長い時間がかかります。効率的なアルゴリズムでも、多くの可能なグラフを計算する必要があります。その理由は、このようなマップには全体で 600 万のノードが含まれ、幾何学的空間を探索する可能性が非常に大きいためです。階層パスプランナーの最初のステップは、マップを小さなサブマップに分割することです。各クラスターのサイズは 300x200 ノードです。全体のクラスター数は 10x10=100 です。新しく作成されたグラフではノードの数が少ないため、100 個のクラスター間を移動できますが、詳細マップ内では移動できません。高レベルグラフで有効なパスが見つかった場合、次のステップは各クラスター内でパスを計画することです。サブマップには 300x200 ノードがあり、通常のA* パスプランナーで簡単に処理できます。

経路探索に使用されるアルゴリズム

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

マルチエージェント経路探索

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

参照

参考文献

^ 「7.2.1 単一ソース最短経路問題: ダイクストラのアルゴリズム」。2016年3月4日時点のオリジナルよりアーカイブ。2012年5月18日閲覧。
^ Delling, D.; Sanders, P. ; Schultes, D.; Wagner, D. (2009). 「エンジニアリングルート計画アルゴリズム」.大規模で複雑なネットワークのアルゴリズム: 設計、分析、シミュレーション. コンピュータサイエンスの講義ノート. Vol. 5515. Springer. pp. 117–139. CiteSeerX 10.1.1.164.8916 . doi :10.1007/978-3-642-02094-0_7. ISBN 978-3-642-02093-3。
^ ダイクストラ、EW (1959 年 12 月)。「グラフに関連した 2 つの問題についてのメモ」。数学数学。1 (1): 269–271。土井：10.1007/BF01386390。
^ 「5.7.1 ダイクストラアルゴリズム」。
^ 「A* パスファインディング入門」。
^ Crawford, Chris (1982 年 12 月). 「コンピュータゲームのデザイン手法とアイデア」. BYTE . p. 96. 2013 年10 月 19 日閲覧。
^ Sacerdoti, Earl D (1974). 「抽象化空間の階層における計画」(PDF) .人工知能. 5 (2): 115–135. doi :10.1016/0004-3702(74)90026-5.
^ Holte, Robert C、Perez, MB、Zimmer, RM、MacDonald, AJ (1995)。階層的 a*。抽象化、再定式化、近似に関するシンポジウム。{{cite conference}}: CS1 maint: multiple names: authors list (link)
^ Pelechano, Nuria および Fuentes, Carlos (2016). 「ナビゲーションメッシュの階層的経路探索 (HNA⁎)」(PDF) . Computers & Graphics . 59 : 68–78. doi :10.1016/j.cag.2016.05.023. hdl : 2117/98738 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
^ Botea, Adi、Muller, Martin、 Schaeffer , Jonathan (2004) 。「ほぼ最適な階層的パス探索」。ゲーム開発ジャーナル。1 :7–28。CiteSeerX 10.1.1.479.4675。 {{cite journal}}: CS1 maint: multiple names: authors list (link)
^ Hang Ma、Sven Koenig、Nora Ayanian、Liron Cohen、Wolfgang Hoenig、TK Satish Kumar、Tansel Uras、Hong Xu、Craig Tovey、Guni Sharon。概要：マルチエージェント経路探索の現実世界のシナリオへの一般化。第25回国際人工知能合同会議（IJCAI）マルチエージェント経路探索ワークショップ。2016年。
^ Khorshid, Mokhtar (2011). 「非最適マルチエージェント経路探索のための多項式時間アルゴリズム」SOCS。

外部リンク

https://melikpehlivanov.github.io/AlgorithmVisualizer
http://sourceforge.net/projects/argorha
StraightEdge オープンソース Java 2D パス検索 (A* を使用) および照明プロジェクト。アプレットデモが含まれています。
python-pathfinding オープンソースの Python 2D パス検索 (ダイクストラアルゴリズムを使用) およびライティングプロジェクト。
Daedalus Lib オープンソース。Daedalus Lib は、A* およびファンネルアルゴリズムを通じて、完全に動的な三角形の 2D 環境モデリングとパスファインディングを管理します。

[1] 「7.2.1 単一ソース最短経路問題: ダイクストラのアルゴリズム」。2016年3月4日時点のオリジナルよりアーカイブ。2012年5月18日閲覧。

[2] Delling, D.; Sanders, P. ; Schultes, D.; Wagner, D. (2009). 「エンジニアリングルート計画アルゴリズム」.大規模で複雑なネットワークのアルゴリズム: 設計、分析、シミュレーション. コンピュータサイエンスの講義ノート. Vol. 5515. Springer. pp. 117–139. CiteSeerX 10.1.1.164.8916 . doi :10.1007/978-3-642-02094-0_7. ISBN 978-3-642-02093-3。

[3] ダイクストラ、EW (1959 年 12 月)。「グラフに関連した 2 つの問題についてのメモ」。数学数学。1 (1): 269–271。土井：10.1007/BF01386390。

[4] 「5.7.1 ダイクストラアルゴリズム」。

[5] 「A* パスファインディング入門」。

[crawford198212-6] Crawford, Chris (1982 年 12 月). 「コンピュータゲームのデザイン手法とアイデア」. BYTE . p. 96. 2013 年10 月 19 日閲覧。

[7] Sacerdoti, Earl D (1974). 「抽象化空間の階層における計画」(PDF) .人工知能. 5 (2): 115–135. doi :10.1016/0004-3702(74)90026-5.

[8] Holte, Robert C、Perez, MB、Zimmer, RM、MacDonald, AJ (1995)。階層的 a*。抽象化、再定式化、近似に関するシンポジウム。{{cite conference}}: CS1 maint: multiple names: authors list (link)

[9] Pelechano, Nuria および Fuentes, Carlos (2016). 「ナビゲーションメッシュの階層的経路探索 (HNA⁎)」(PDF) . Computers & Graphics . 59 : 68–78. doi :10.1016/j.cag.2016.05.023. hdl : 2117/98738 .{{cite journal}}: CS1 maint: multiple names: authors list (link)

[10] ^ Botea, Adi、Muller, Martin、 Schaeffer , Jonathan (2004) 。「ほぼ最適な階層的パス探索」。ゲーム開発ジャーナル。1 :7–28。CiteSeerX 10.1.1.479.4675。 {{cite journal}}: CS1 maint: multiple names: authors list (link)

[11] Hang Ma、Sven Koenig、Nora Ayanian、Liron Cohen、Wolfgang Hoenig、TK Satish Kumar、Tansel Uras、Hong Xu、Craig Tovey、Guni Sharon。概要：マルチエージェント経路探索の現実世界のシナリオへの一般化。第25回国際人工知能合同会議（IJCAI）マルチエージェント経路探索ワークショップ。2016年。

[12] Khorshid, Mokhtar (2011). 「非最適マルチエージェント経路探索のための多項式時間アルゴリズム」SOCS。