Cooperative Pathfinding - Githubissues

Drunkar / papers

0 stars 0 forks source link

Cooperative Pathfinding #4

Open Drunkar opened 5 years ago

Drunkar commented 5 years ago

一言でいうと

A*アルゴリズムを応用したマルチエージェントのpath findingアルゴリズムのうち、Cooperative A* [CA*]、Hierarchical Cooperative A* [HCA*]とWindowed Hierarchical Cooperative A* [WHCA*]の3つを到達エージェントの割合、平均経路上cycle数、平均経路長、初期化時間、総計算時間で比較し、WHCA* (window size 32)が比較的どれも良い結果となった。ベースラインはLocal Repair A* (ゲーム業界でのスタンダードなアルゴリズムとのこと)。
WHCA*の紹介

論文リンク

著者/所属機関

David Silver: University of Alberta

投稿日付(yyyy/MM/dd)

2005/06/01

掲載誌・学会等

AIIDE'05 Proceedings of the First AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment Pages 117-122

先行研究と比べてどこがすごい？

WHCA*の紹介 (発明?)

技術や手法のキモはどこ？

Local Repair A*

各エージェントは、現在の近傍以外のエージェントを無視して物理空間上でA*による経路計算をする
衝突が発生する直前まで、各エージェントは計算した経路に沿って進む
衝突しそうになったら、再び近傍以外のエージェントを無視して経路を再計算する

Cooperative A* [CA*]

各エージェントは物理空間 x 時間の空間をA*で探索する。ただし、すでに計算された他エージェントの経路はreservation tableとして保存され、経路計算を行うエージェントからはobstaclesとみなされる。

Hierarchical Cooperative A* [HCA*]

CA*での各エージェントの経路探索をより効率化するために情報を参照する方式。hierarchical とはより抽象度の高い情報(物理空間のみ、など)を参照しているという意味。
CA*では各エージェントが物理空間 x 時間の空間を探索しなければならないので計算量が大きくなる。より効率的な計算をするために、物理空間上で、reservation tableを無視した距離を計算して都度参照しながら経路を決定する？元論文を読む必要がある。

Windowed Hierarchical Cooperative A* [WHCA*]

HCA*でも、各エージェントが物理空間 x 時間という広大な空間を探索しなければならないことは変わらないので、数ステップ分を検索-> 実行の繰り返しに分解する。
ただし、正しい方向に向かっていることを保証するために、抽象空間での探索は全期間で行う。
結果的には、window sizeを変えることによってCA* (高コストだがより堅実)とHCA* (低コストだがよりアグレッシブ)の間を選ぶことができる感じ。

どうやって有効だと検証した？

32 x 32グリッドの2次元空間で、侵入不可能なピクセルをランダムに配置。
エージェントの数だけ出発点、到着点をランダムに設置。

議論や検証がまだ必要なところはある？

CA*のようなヒューリスティクスでは、あるエージェントの到達点が別のエージェントの経路を塞いでしまうようなときに、到達点に達する経路を見つけられないエージェントが発生してしまう。これを回避するためには、出発点と到達点の割当を適切に行う必要がある。
探索物理空間 x 時間のサイズを考慮しなければならないので、3次元空間でエージェントが増えたときの計算時間や消費メモリ、feasibility (すべてのエージェントに経路が見つけられるか) がどの程度になるか不明。

次に読むべき論文は？

A*: Hart, P.; Nilsson, N. J.; and Raphael, B. 1968. A for-mal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cyber-netics 4:100–107.
CA*: ? 記載なし
HCA*: Holte, R. C.; Perez, M. B.; Zimmer, R. M.; and MacDon-ald, A. J. 1996. Hierarchical A*: Searching abstraction hierarchies efficiently. In AAAI/IAAI, Vol. 1, 530–535.

コメント

Drunkar commented 5 years ago

multi-agent path planningタスクの分類

Centralised planning takes: 全エージェントの可能な経路を(衝突等を考慮しながら)同時に計算し、可能な経路を列挙するタスク。
The decoupled or dis-tributed approach: 各エージェントの独立した、または部分的に独立した経路問題として解く。

前者はPSPACE-hardらしい(Hopcroft, J.; Schwartz, J.; and Sharir, M. 1984. On the complexity of motion planning for multiple independent objects: PSPACE-hardness of the warehouseman’s prob-lem. International Journal of Robotics Research 3(4). )