| 講演者：
| Vadim Bulitko |
| 題目：
| Dynamic Control in Real-time Heuristic Search
実時間ヒューリスティック探索における動的制御 |
概要：
| Real-time heuristic search is a challenging type of agent-centered search because the agent's planning time per action is bounded by a constant independent of problem size. A common problem that imposes such restrictions is pathfinding in modern computer games where a large number of units must plan their paths simultaneously over large maps. Common search algorithms (e.g., A*, IDA*, D*, ARA*, AD*) are inherently not real-time and may lose completeness when a constant bound is imposed on per-action planning time. Real-time search algorithms retain completeness but frequently produce unacceptably suboptimal solutions. In this paper, we extend classic and modern real-time search algorithms with an automated mechanism for dynamic depth and subgoal selection. The new algorithms remain real-time and complete. On large computer game maps, they find paths within 7% of optimal while on average expanding roughly a single state per action. This is nearly a three-fold improvement in suboptimality over the existing state-of-the-art algorithms and, at the same time, a 15-fold improvement in the amount of planning per action.
実時間ヒューリスティック探索は, エージェント中心探索の一種であるが, 各回の動作選択 (プランニング)時間が制約が課されている点で困難な部類にあたる. この様な制約は, 最新のコンピュータゲームにおいて見られる. 登場する多数の
ユニットが大規模な地図上で同時に経路プランニングを行うことから, ユニット個々のプランニング時間は必然的に制限を受ける. よく使われるヒューリスティック探索アルゴリズム (A*, 反復深化A*, D*, ARA*, AD*) は, 本質的に実時間性を考慮しておらず, プランニング時間に制約を課すと完全性 (目標に必ず到達するという性質) が失われてしまう. 実時間探索は, このような状況でも完全性を持
つが, しばしば非常に悪いプランが作成される欠点がある. 本講演では, 古典的/最新の実時間探索アルゴリズムを拡張し, プランニングの先読み深さと副目標を動的に決定する. この結果得られる新しいアルゴリズムは, 実時間性と完全性を
保つ. 大規模なコンピュータゲーム用地図に適用したところ, 平均して最適経路の7%以内の準最適経路を発見することができ, 動作ごとの平均拡張状態数はほぼ1に過ぎなかった. これは, 既存のアルゴリズムに比べて, 解の質に関しては3倍, 動作ごとのプランニング量に関しては15倍もの向上である.
|
|