プログラマ専用SNS ミクプラ

現代のAI技術を学ぶため、とにかく資料を読まなきゃ始まりませんが、
残念なことに日本語の資料はほとんどありません。てなわけで英語を訳します。


今回はこれ。「DHPA* and SHPA*: Efficient Hierarchical Pathfinding in Dynamic and Static Game Worlds」
動的そして静的なゲーム世界における効率的な階層的経路探索：DHPA*とSHPA*。
http://aaai.org/ocs/index.php/AIIDE/AII ... /view/2131

抜粋は次のように書かれています。

In 2004, Botea et al. published the HPA* algorithm (Hierarchical Pathfinding A*), which is the first detailed study of hierarchical pathfinding in games.
2004年、Botea氏他数人は、HPA*(階層的経路探索A*)を発表しました。そしてそれは、ゲームにおける階層的経路探索の最初の詳細な研究でした。

However, HPA* can be optimized. In this paper, we introduce the DHPA* and SHPA* hierarchical pathfinding algorithms, along with a metric for comparing the dynamic performance of pathfinding algorithms in games.
一方、HPA*は最適化が可能です。この紙面では、DHPA*とSHPA*という階層的経路探索アルゴリズムを、ゲームにおける経路探索の動的なパフォーマンスと比較するための指標とともに紹介します。

We show that DHPA* searches up to an order of magnitude faster than HPA*, but consumes significantly more memory and produces slightly less optimal paths.
DHPA*は大量の要求に至ってもHPA*より高速に探索可能です、その反面、著しくメモリを消費し、わずかに不正確な経路をもたらします。

The SHPA* algorithm searches up to five times faster than HPA* and consumes less memory, but it also produces slightly less optimal paths, and is only fit for static environments.
SHPA*はHPA*の5倍高速に探索できます、そしてメモリもより節約できます、しかしながら、これもまた若干不正確な経路をもたらし、また、静的な環境にしか適しません。

When comparing the algorithms in dynamic environments, our results show that DHPA* often outperforms HPA*.
動的な環境で比較したとき、その結果から、DHPA*はHPA*よりもたいてい高性能であるということが明らかになっています。

Unlike many other hierarchical pathfinding algorithms, both solutions presented in this paper maintain a read-only terrain representation during search, which simplifies programming and debugging, and improves multithreaded performance.
他の多くの階層的経路探索アルゴリズムと異なって、この紙面で述べられている両方の解決法は、探索中、読み込みのみの地形データを持ちます。そうすることによって、プログラミング・デバッグが簡単になり、マルチスレッドの効率を向上させることができるのです。

本文はこれから訳していき…ます

【紹介】 現代のビデオゲームでは、広大で常に変化し続ける環境を動きまわる、大量のエージェントを補助するための、効率的な経路探索が要求されます。
Warhammer 40000: Dawn of War 2、Splinter Cell: Conviction、この最新のゲームの両方は、障害物が動的に地形を変化させるような巨大な世界をもちます。
地形を階層的に表現すれば、経路探索をより小さな空間にとどめ、地形の変化をマップの単位部分に制限することによって、
経路探索のパフォーマンスを向上させることができます。
ビデオゲームに適用できる多くの階層的経路探索アルゴリズムが学界で研究されてきました。
(例えば、1996年にHolte氏ら、2004年にBotea氏ら、2005年にSturtevant氏とBuro氏、2006年にDemyen氏とBuro氏、2009年にBulitko氏とBjörnsson氏の発表など)
ほぼ間違いなく、ビデオゲームにとっての最も適切な階層的経路探索解決法はHPA*です。
HPA*アルゴリズムはシンプルに理解でき、簡単に実装でき、そして効率的です。ビデオゲームに対する最も適当な候補となります。
他の多くの階層的経路探索アルゴリズムのように、HPA*は「構築アルゴリズム」と「探索アルゴリズム」から成ります。
構築アルゴリズムは、グラフの一連を通じて階層を定義します、そこで、それぞれのグラフはより高レベルな分解グラフを抽出します。
複数の抽象レベルでHPA*が動いている間、私たちはもっぱら単一の抽象レベルにおけるHPA*について検討します、
なぜなら、複数のレベルにまたがると、実装が難しくなり、パフォーマンス増加が減少するです(Botea氏ら,2004年)
階層が作成されたあと、探索アルゴリズムは最も高いレベルで経路を探します、
そして、その経路を最も低いレベルに沿った部分的な経路が連続したものに洗練します。
Botea氏ら(Botea氏、Müller氏、Schaeffer氏：2004年)はグリッド上で使用するHPA*を提供しました。
もっとも、例えばナビゲーションメッシュのような他の地形構造に適用することも可能です。
HPA*の構築アルゴリズムは2つのオフラインなタスクを実行します。
最初に、地形を互いにばらばらなクラスターの集まりに分解します。
[※クラスター … 塊や集合体、ここでは複数のグリッド(ノード/エッジ)の集合]
そこでは、それぞれのクラスターは低レベルなノードの一定数をカバーし、
それよりも少ない数の抽象ノード(高レベルノード)をカバーしています。
つぎに、構築アルゴリズムはエッジ重みのキャッシュを作成します。
キャッシュは各対の接続された抽象ノード間の重みを蓄えます。
そこでは、その重みが、先ほどの抽象ノード間における、低レベルグラフ上の経路での長さに等しくなるようにします。
したがって、その重みをもとに抽象グラフ探索における移動コストを決定することができます。
実行時、構築アルゴリズムは地形が変化するときにグラフを更新する必要があります。
そのような状況では、構築アルゴリズムは影響を受けたクラスターで集中的にはたらき、
抽象ノードと、影響を受けたクラスターに対応するようなキャッシュの一部をつくり直すことになります。
HAP*はビデオゲームによく適すだけでなく、非常に汎用的です。
実際問題、グラフ階層がよりよく用意されているような静的世界においては、
HPA*はとっても効率的にできますし、典型的な動的世界においても、
頻発する地形変化を処理できるように改良することも出来るでしょう。
この文書でははじめに静的な地形においての経路探索に有効なSHPA*と、動的な地形で有効なDHPA*を紹介します。
セクション２では、SHPA*とDHPA*アルゴリズムについて詳しく記述します。
セクション３では、動的なパフォーマンス計量を示します。
セクション４では、SHPA*、DHPA*そしてHPA*を比較した実証的な分析結果を示します。
そして、最終的にセクション５では、結論を要約し、今後可能であると思われる研究方向について示します。

（section1 おわり）

DHPA*とSHPA*は両方とも構築アルゴリズムと(改良された)探索アルゴリズムから成ります。
大雑把に言えば、DHPA*は構築アルゴリズムに多くのメモリと時間を使い、
探索アルゴリズムに費やす時間を減らすことで、HPA*の実行時間を減らします。
それとは対照的に、SHPA*はパフォーマンスを改善するだけでなく、メモリの使用量も減らします。
どちらのアルゴリズムも探索中に変化する地形には適用できません、
プログラミングを楽にして、マルチスレッド性能を高めるためなのです。

セクション2-続く
→DHPA*構築アルゴリズム
→DHPA*探索アルゴリズム
→SHPA*構築アルゴリズム
→SHPA*探索アルゴリズム
→Shared Properties