戦場における作戦行動には、作戦エリアに関する地形情報にくわえて、敵部隊の規模と種類、位置と時間、配備された装備など、リアルタイムに変化していく動的な情報を収集、逐次更新するための隠密偵察、威力偵察、またはその両方が欠かせません。敵に察知されないよう情報収集に徹する隠密偵察に対して、威力偵察とはあえて敵と交戦することで対象の位置や装備を把握する行動を指します。
こうした動的環境における長期的な意思決定は、ゲームAI開発における大きな課題のひとつです。7月19日から7月24日までオンラインで開催された「Game Developers Conference 2021」（GDC 2021）にて、スクウェア・エニックスのAIエンジニア、並木幸介氏と森寅嘉氏による「階層型タスクネットワークを使った動的環境におけるプランニングへの新たなアプローチ」というセッションを取材しました。
このセッションでは、武装した巨大ロボットを操縦して戦場を駆け巡るアクションゲームを使って、AIプレイヤーが威力偵察における索敵、交戦、撤退を自らの判断で実行するための新たなプランニング手法が提案されました。偵察中に発見した撃破可能なターゲットを排除しつつ、強敵の出現によって危険な状況に転じた場合は煙幕を張って撤退を開始。その際に切り札となる強力な兵器を使って強敵を破壊するか、あるいは敵に追撃を断念させることを行います。なお、攻撃の際には敵からの被弾を最小限に抑えるために稜線射撃に徹すること。これらをすべてAIの判断で実行させることが最終目的です。
近年のゲームAI開発は、有限状態機械（FSM、Finite State Machine）やビヘイビアツリー（Behavior Tree）、GOAP（Goal Oriented Action Planning）、階層型タスクネットワーク（HTN：Hierarchical Task Network）といった異なる種類の意思決定モデルによって支えられています。それぞれに長所と短所があり、目的に応じて使い分けたり、複数のモデルを組み合わせたりして、ゲームデザインに最適なゲームAIが構築されていきます。
今回のセッションで扱うHTNとは、読んで字のごとし。複数のタスクによるネットワークを階層型に構築することで、行動計画を立てるタスクベースのアルゴリズムを意味します。長期的な行動計画の実装に適しており、特に配送最適化問題のような静的環境におけるプランニングに優れています。
すべてのタスクは、行動の最小単位であるプリミティブタスクと、それらを組み合わせたコンパウンドタスクの2種類に分別されます。この時、前者は階層的に下位、後者は上位という関係にあります。たとえば、「歩行」や「射撃」がプリミティブタスクだとすれば、長期的な行動目標である「威力偵察」は多くのプリミティブタスクを複合させた階層的に最上位のコンパウンドタスクであると考えられます。
こうしたコンパウンドタスクを複数のタスクへ分解し、下層タスクから順に実行できるようプランニングするのが、HTNの役割です。プランニングの際に最小単位まで分解されたタスクは、1本の鎖のように並べられた後、ひとつずつ順番に実行されます。このタスクチェーンは、すべてのタスクが実行されるまで変更できません。そのため、途中で環境に変化が生じた場合、HTNは既存の計画をすべて破棄して新しいプランを作ろうとします。
その性質上、プレイヤーの挙動によって環境が常に変化するビデオゲームでは、リプランニングの頻度が増えるほど、AIは長期的な思考能力を失ってしまいます。結果として、短期的な意思決定しかできない即応的なAIが出来上がってしまうというわけです。そこで、ビデオゲームのような動的な環境で長期的な行動を実現するために、スクウェア・エニックスはHTNを改良した「ART-HTN」という新たなプランニング手法を提案しています。
「ART-HTN」（Advanced Realtime Hierarchical Task Network）には、「マルチシナリオ・プラン」「シミュレーション・プランナー」「プラン・エグゼキュータ」という3つの特徴があります。簡単に説明すると、マルチシナリオ・プランが複数のシナリオを想定することでリアルタイムに起こる状況の変化に対応し、シミュレーション・プランナーが簡易的なシミュレーションの生成でプラン精度を向上させることでリプランニングの回数を減らし、プラン・エグゼキュータというプラン生成とは別の実行権限を設けることで柔軟なプランの制御を可能にするという仕組みです。
マルチシナリオ・プランは、環境の変化によって本来は破棄されていたタスクチェーンを、サブプランとして再利用するために機能させます。タスクとシチュエーションという2種類のデータで構成されており、シチュエーションにはキャラクターの位置情報や残りHP、敵AIの内部ステートIDといった簡略化されたゲームワールドの情報がふくまれています。それぞれのシチュエーションが前後のシチュエーションを参照することで、「Situation-Task ネットワーク」（ST-Network）というグラフ構造を形成します。これにより、プランの探索中に発見した中間状態をタスクチェーンの分岐点として含められるというわけです。
「ART-HTN」では、プリコンディション（事前条件）とシミュレート関数を持つプリミティブタスクのほかに、前述したコンパウンドタスクと同様に複数のタスクから構成されるコンポジットタスクを扱います。セッションでは、コンポジットタスクの例として「FSMタスク」と「ステップタスク」が紹介されました。FSMタスクは、後述するシミュレーション・プランナーが敵の行動を予測するために用いられ、ステップタスクは、タスク実行の際に少数のループや限定された数の分岐を持たせるために使われるということです。
シミュレーション・プランナーは、前述したST-Networkの生成やシチュエーションの終端ノードを展開する役割を担っています。この際、敵の行動モデルをシミュレートすることで、それぞれのシチュエーションにおける分岐も生成しています。終端ノードを展開する際には、意思決定システムが各キャラクターに対してプリコンディションを満たしたタスクをアサインします。くわえて、コンポジットタスクが許可した場合は、現在のコンポジットタスクを展開することも可能ということでした。
例えば、あるシチュエーションにおけるFSMタスクが「ステートa」「ステートb」「ステートc」へ遷移する場合、このFSMタスクはそれぞれのコピーインスタンスへと展開します。この時、FSMタスクにふくまれるすべてのデータがコピーされます。その後、ステートの遷移が実行されて、異なる3つのタスク・インスタンスが生成されるという流れです。
このプロセスは、すべてのエージェントの意思決定システムによって実行されるので、結果としてST-Networkは膨大なノード数を持つことになります。このサイズを縮小するために、展開処理に確率閾値を設定できるようにデザインしたということです。乱数がこの閾値を越えた場合に限って、タスクが展開されるという仕組みです。
キャラクターの行動はタスクによって定義されていますが、タスクそのものはゲーム環境で実行できるフォーマットではありません。そこでプラン・エグゼキュータの出番です。プラン・エグゼキュータは、ST-Networksのシチュエーションノードからもっとも評価値の高いタスクを選択した後、そのタスクを分解してゲーム内で実行可能なオペレータへと変換してくれます。それらを順番に実行することでゲームキャラクターが動き出します。
セッションの最後には、地形の等高線データに基づいた丘陵検出アルゴリズムを活用した稜線射撃デモと、冒頭で記述した長期的な行動計画をすべて実行させた威力偵察デモが披露されました。今回の技術検証によって、ART-HTNが動的環境に適応できることが確認できたということでした。将来、人間のように長期的な思考能力を有したゲームAIが実現できれば、ゲーム体験の価値そのものが大きく変化することでしょう。
Writer：Ritsuko Kawai / 河合律子
