「今日のメシどうする？」問題から学ぶ、階層型タスクネットワーク

株式会社ディー・エヌ・エーは、エンジニア向けの勉強会「GDM vol.37 エンジニア向け勉強会　ゲームAIにおける意思決定と地形表現〜『LEFT ALIVE』を事例に紹介〜」を開催しました。講師として迎えられたのは、スクウェア・エニックスの長谷川誠氏です。

サバイバルアクションゲーム『LEFT ALIVE』（2019年、スクウェア・エニックス）は、複雑な手順のアクションを実行するAIが求められるため、キャラクターAIの意思決定にHTN（階層型タスクネットワーク）を採用し、長いスパンの行動計画の生成に対応できるようにしました。

今回はHTNを採用した背景と、ご飯を用意して食べるという身近な生活にたとえたHTNの具体的な説明、実際に『LEFT ALIVE』でどのようにHTNの実装をしたかなどについて解説がされました。

HTNを採用した背景

『LEFT ALIVE』は、シリコンスタジオのゲームエンジンOROCHIを採用。ゲームAIの機能もあったものの、『LEFT ALIVE』の複雑さに耐えらないと判断したため、AIのアーキテクチャを自作することにしました。

候補として挙がったのは、

• ビヘイビア・ツリー
• 階層型ゴール思考
• HTN
• GOAP

この4つのアーキテクチャでした。この中から企画の細かい要望に対しつつ複雑な状態を捉えられてノード数を爆発させて扱いきれなくなることは避けられる方法を選びました。

ビヘイビア・ツリーはアンリアルエンジンにも標準搭載されており、採用事例も多くて手堅い選択肢のように思われました。しかし、ノード数が増えすぎる懸念があったためこのときは選択肢から外されました。GOAPはノード数を減らせるものの、企画の局所的な部分における細かい対応が十分にできないため、こちらも今回の選択肢から外したとのことです。

最終的に『LEFT ALIVE』の開発では、すでに長谷川氏も開発経験のある「階層型ゴール思考」と、局所的な対応ができてノード数も増えすぎない「HTN」を採用しました。

両者は、HTNは抽象度の大きいタスクを分解する際に使い、階層型ゴール思考は、抽象度の低いものに使用するという形で使い分けました。

HTNに関わる各用語の解説

HTNはHierarchical Task Networkの略で日本語では階層型タスクネットワークと呼ばれています。これはネットワーク状につながっている多くのタスクに処理を加えることで、自動的に目的に沿ったタスクのリストにする機能です。

HTNの構成要素は大きく分けて「ワールドステート」、「タスク」、「プラナー」の3つがあります。タスクは「プリミティブタスク」と「コンパウンドタスク」に分かれ、それぞれの要素があります。これらをまとめて「ドメイン」と呼んでいます。

ワールドステート

ワールドステートは、自分の状態もふくめたゲームの世界全体の状態です。『LEFT ALIVE』には、ワールドステートが143種類あります。

プリミティブタスク

プリミティブタスクは、世界に影響を与える行動を表すもので、次の3つの要素でできています。

• プリコンディション
• オペレータ
• エフェクト

プリコンディションは、タスクを実行するために必要な条件で、オペレータは実際に行う行動。エフェクトはオペレータの行動でワールドステートどのように変わるかが記述されているものです。

コンパウンドタスク

コンパウンドタスクは、タスクが達成すべき結果に至る方法を記述した「メソッド」を複数持ちます。メソッドは、自分が選ばれるための条件となる「コンディション」と、選ばれたときのタスクのリストを持っています。コンパウンドタスクにはメソッドが複数ありますが、どれを選んでもコンパウンドタスクが求める結果（この場合は「ご飯を食べる」）になるようにメソッドを記述しておきます。

ドメイン

プリミティブタスクやコンパウンドタスクが入っているフレームをドメインと呼びます。

プラナー

ワールドステートを参照・編集しながら、ドメインをタスクのリストに変えていく機能がプラナーです。

ご飯どうする？から学ぶHTN

次に長谷川氏はプランニングのアルゴリズムについて、「ご飯を食べる」というタスクを実行するためのドメインを例にHTNの仕組みを解説しました。まずコンパウンドタスクとして「食事する」というタスクを設定。メソッドを2つ用意しました。

メソッド1：「ご飯がある」という条件を満たせば「ご飯を食べる」

メソッド2：条件が「常に真（どんな状態でも選ばれる）」。「ご飯を買いに行く」、「食事する」というコンパウンドタスクが存在。

つまりここには「ごはんを食べる」というプリミティブタスクと、「ごはんを買いに行く」というプリミティブタスクがあるということです。

プランスタックは、プランを作るにあたって必要な機能を分解していく過程を積んでおく場所です。プランニング中のワールドステートは現在の状態を表しています。

この状態からプランニングを開始します。

ケース1：すでにあるご飯を食べる

初期状態の「ご飯ある」という状態を用意した上で、「食事する」というタスクを分解していくことでタスクのリストを作ります。

まずはプランスタックに入っている、「食事をする」というタスクを取り出します。取り出したら、メソッドに付随するプリコンディンションを確認し、現在の状態である「ご飯ある」と一致するメソッドを探します。この場合、メソッド1を採用します。

採用したら、メソッド1にある「ごはんを食べる」というタスクを、プランスタック（黄色い箱）に積みます。

この状態から、またさらにプランスタックに積まれている「ご飯を食べる」というタスクを取り出して、「食べる」というオペレータプランリスト（黒い箱）に追加します。それを実行することでエフェクトをワールドステートに適応させることができます。その結果、プランスタックが空になり、ワールドステートが「ご飯なし」「お腹いっぱい」という状態になるので、プランニングは終了します。

ケース2：買ってきたご飯を食べる

次にワールドステートの初期状態を「ご飯なし」「お金ある」に変更した上で「食事する」というタスクを分解していきます。

先ほどと同様に、プランスタックから「食事する」というタスクを取り出します。今度は「ご飯がある」というプリコンディションに対応できないので、メソッド2の「常に真」が採用されます。採用されたら、サブタスクのリスト「ご飯を買う」「食事する」をプランスタックに積みます。

するとこの状態になります。その次に「ご飯を買う」というタスクを取り出します。この時は「お金あり」の条件を満たしており、このプリミティブタスクが実行できるため、「ご飯を買う」というタスクがプランリストに追加されます。

無事買い物ができたので、「ご飯がある」、「お金なし」というエフェクトをワールドステートに適用します。

そうすると、この状態になります。

プランスタックにある「食事する」を取り出します。今度は「ご飯がある」のプリコンディションのメソッド1を採用できるため、「ご飯を食べる」がプランスタックに追加されます。ケース1の展開と同様に、「ご飯を食べる」が取り出されて追加され、「お腹いっぱい」「ご飯なし」になります。これでプランスタックが空になるので、プランニングは終了です。

失敗するケース

こちらのケースはプランニングが失敗して、最終的にご飯を食べられないケースです。ワールドステートは「ご飯なし」「お金なし」です。まず「食事する」を取り出します。このとき「ご飯がある」が対応していないので、「常に真」のメソッド2を採用してプランスタックに積みます。本来なら「ご飯を買う」が実行されるはずですが、ワールドステートを見ると「お金なし」なので、このタスクは実行できずに失敗します。

プリコンディションで失敗した場合は、最後にコンパウンドタスクを展開する前の状態に戻します。今回の場合は、プランスタックに「食事をする」というタスクが積まれている状態まで戻します。その上で失敗するのが分かっているメソッド（この場合はメソッド2）を選択対象にしないようにします。

そうなると、今度は今のワールドステートは「ご飯がある」に対応できるものではないので、メソッド1も採用できません。結局すべてのメソッドが採用されずに終わります。

全順序タスクと半順序タスク

タスクには「全順序タスク」と「半順序タスク」の2種類があります。全順序タスクは一つひとつ順番に実行しなくてはならず、同時平行で処理できないタスクです。例えば、お湯を沸かして、カップラーメンにお湯を注いで、3分待つという3つのタスクは必ず順番に実行しなければなりません。お湯を沸かしながらカップラーメンにお湯を注ぐことは、お湯がそもそもないのでできませんし、3分待つのを実行するタイミングも順番を変えるとおかしなことになります。

一方で、同時平行で処理できるタスクのことを半順序タスクと呼びます。ごはんを炊きながらカレーのルーを作ることは同時にできます。このように同時並行でできるタスクを半順序タスクといいます。

ここまでのまとめ：HTNを活用することで、ワールドステートをプリミティブタスクのエフェクトを使って仮想的に変更しつつ、将来に向かって一貫性のあるプランを立てることができます。また、ビヘイビア・ツリーのようなツリー形ではないため、比較的柔軟な組み方が可能です。

『LEFT ALIVE』に実装されたHTN

『LEFT ALIVE』のHTNリストは『Game AI Pro』の12章に掲載されたHTNの説明を参考に実装されました。

Exploring HTN Planners through Example｜Game AI Pro

この時は半順序タスクは扱わない、タスクは引数を取らない、プランの良し悪しはメソッドが並んでいる順番並、というシンプルな形で実装しました。とはいえ、そのままでは実用に不十分だったため、『LEFT ALIVE』に最適化するためにHTNの機能の拡張を行ったとのことです。そのプロセスにおける課題と解決をそれぞれ解説されました。

オペレータ並列実行

当初は半順序タスクを扱わないHTNを実装したため、例えばシールドを構えながら移動をするなど、「〇〇しながら××」というタスクが処理できないという問題が生じました。そこで、プリミティブタスクに複数のオペレータを登録して同時に実行できるようにしました。移動というオペレータ、射撃というオペレータ、リロードというオペレータはすべて別々にあり、これらをドメイン上で組み合わせることで複数の動作を同時並行で実行しているように見せることに成功しました。

成功コンディション

10メートル以内まで敵に近づくのと、自分から敵が見えるまで敵に近づくのはほぼ同じタスクです。このように同じようなプリミティブタスクのオペレータを共通の実装にしたいという課題もありました。解決策としては、成功終了する条件をプリミティブタスクに持たせることで、複数のオペレータを用意しなくても組み合わせで実行できるようにしました。

成功タイムアウト／失敗タイムアウト

旋回速度が遅く、なかなか正面にとらえられないため、諦めて次のアクションを実行する（タスクが成功して次に行く）。近づいて攻撃したいけれど、なかなか近づけないので、攻撃をやめる（タスクの失敗）といったタイムアウトの処理をオペレータごとに実装するのも煩雑で手間のかかる作業です。この課題については、プリミティブタスクのデフォルトの機能として実装することで解決しました。

プリミティブタスクのクールタイム

強力なボスの攻撃を連続で実行させたり牽制のグレードや強い攻撃を連発させないように、プリミティブタスクのクールタイムをデフォルト機能として設定しました。1回実行したプリミティブタスクはヒートアップの状態になるので、クールダウンしている最中にはプリコンディションが常に「false」の状態になります。

優先実行時間

ボスのガトリング攻撃は、まず攻撃態勢の動きをしてから、ある一定のループ時間を経て、最後に終了のモーションで終わるという比較的長めのモーションを再生します。これは、ある間合いに入ると再生されますが、その間合いから外れるとモーションを停止してしまいます。そのためプレイヤーが頻繁に動き回ると、再生と停止が頻繁に発生して不自然な演出になってしまいます。それを避けるために、1回モーションの再生を実行したら、ある程度の時間は裏側で作成されるリプランを行わない機能を実装しました。

リプランニング

優先実行時間に関わるのがプランのリプランニングです。ゲームの状態は常に変化し続けるので、プランを立てた瞬間から、そのプランを実行する環境が変化してしまうため、プランを実行している最中に常にバックグラウンドで優先度の高いプランを立て続けます。リプランニングの周期は、部隊のエージェントに関しては0.5秒おき、部隊に関しては2秒おきにリプランニングをかけていきます。

このように実行中のプランがあり、優先度の高いプランができたら次々に置き換えます。プランの優先度は、コンパウンドタスク内のメソッドの若い番号順です。

優先度の高いプランへの置き換えをする場合、単純にそのまま入れ替えてよい場合と、現在実行中のプランと上手くマージしなければならない場合があります。例えばここでは「ラーメンを作る」というタスクを実行している次に「フォークで食べる」が置かれてしまっています。しかし優先度が高いのは「ラーメンを作る」の次に「箸で食べる」のタスクが待機しているプランです。

ここを入れ替えたいなど、何かしらの理由でプランを置き換えるとき、分岐点が現在実行中のタスクより上位のメソッドの場合は、現プランを全部破棄して新しいプランに置き換えます。抽象度の高いところで分岐しているということは、実行しようとしている内容自体が変わっているので全部置き換えても問題ないはずです。下位のメソッドで分岐している場合は、現在実行中のタスクをそのまま実行して、未実行のタスク部分だけを置き換えます。

「食事する」「食べる」という簡単なドメインがあって、現在実行中のプランは「ケーキを買う」だとします。その次に「フォークで食べる」というタスクが控えています。このとき例えばケーキを買いに行く途中でカップラーメンを発見した場合、新しいプランが立てられます。

その場合、「ラーメンを調理する」「箸で食べる」の方がメソッドの順番的には優先度が高くなります。このときに「ケーキを買う」から展開するメソッド自体が変わるため、当初のプランをすべて捨てて入れ替えます。

次に、今度は「ラーメンを調理する」「フォークで食べる」の順で実行しようとしていたところ箸を入手したので、フォークではなく箸で食べようと次のプランが立てられます。「ラーメンを調理する」はそのまま実行し、下位の分岐で「フォークで食べる」を「箸で食べる」に入れ替えます。

この場合はコンテクストの一部を入れ替える処理で済みましたが、すべてのプランを入れ替えなければならないケースもあります。例えばゲームの中で非戦闘状態から戦闘状態に変わる、ターゲットが変わるなどで、そもそもやろうとしていること自体が変わってしまったケースです。

プリミティブタスクの実行をしている最中に起きたアクシデントへの対応についても解説がありました。例えばラーメンを作って箸で食べている最中に箸を落としてしまったとします。このときにすべてのタスクをリプランニングし直すのは負荷がかかる上に、何をやっていたかも破棄されて全然関係ないプランが立てられてしまう可能性もあります。

この場合、「箸で食べる」のタスクをふくむメソッドを選択対象外とし、すでにあるプラン「フォークで食べる」と差し替える形で、部分的にプランニングをかけます。

つまり「ラーメンを調理する」をすでに実行されていて「箸で食べる」も実行されていたとき、何かしらの理由で箸が使えなくなったら、「箸で食べる」というメソッドをふくんでいたコンパウンドタスクを、ルートタスクとして部分的にプランをし直します。そして「フォークで食べる」を失敗した部分と差し替えて、既存のコンテキストをできるだけ維持した形で再度プランを組み立てます。さらに失敗履歴を取っておき、差し替わったプランがすべて正常終了するまでそれを保持し続けることで、失敗したメソッドが選ばれないようにします。

HTNは必ずしも銀の弾丸ではない

ここまでがHTNの概要と実装の事例についての解説でしたが、HTNは必ずしも万能ではありません。実際に導入するにあたり、さまざまな課題や失敗があったとのことです。例えば、HTN用のツールがないことで、あるプランをなぜ採用したか（あるいは採用しなかったか）のログを追いづらいため、デバッグなどの精度を上げにくいという課題があります。「HTNをやるのであれば、あるドメインからプランが生成される過程がグラフィカルに見られる環境でないとかなり厳しいです」と長谷川氏は指摘します。

HTNを開発できる人材の不足も大きな課題です。アンリアルエンジンでデファクトスタンダードになっているビヘイビア・ツリーとは異なり、お金を使って人材を確保することも、そもそもの人材が不足しているためできません。現状としては、HTNを採用するのであれば、ビヘイビア・ツリーとのハイブリッドシステムで柔軟に人員配置をできる環境にしておかないと難しいと長谷川氏は語ります。

HTN自体をシンプルにしすぎたことで生じた問題もありました。前述の『Game AI Pro』12章を参考に実装したHTNは、ごくシンプルであるがゆえに複雑なことをしたい場合は自力でドメインを書く他ありません。そのため『LEFT ALIVE』のプリミティブタスク数は通常兵士だけでも300を超えてしまいました。HTNを採用するのであれば、タスクに引数を渡せるシステムは必須とのことでした。

HTNだけで頑張ろうとせず、ビヘイビア・ツリーと組み合わせることで負荷を減らせるというのも実際に採用したことで得た発見だといいます。『LEFT ALIVE』のドメインの上位部分は、HTNである必要のない構成で、ビヘイビア・ツリーのプライオリティノードとまったく同じことをしています。さらにビヘイビア・ツリーの方が動作が軽く、必要のないワールドステートが増えることも防げます。従ってHTNは、指向の一番上から一番下ではなく、真ん中部分に採用するのが合理的です。最上位にあるビヘイビア・ツリーやUtilityが何をしたいかを決定し、その後にHTNが走って実際に何をどういう順番で行うかを決めた後に、細かいタスクの実装をビヘイビア・ツリーが行う構成が一番良いとのことでした。

このようにHTNは一貫性のあるプランを立てることができるものの、採用するにあたってツールや環境、人材面で非常に高いハードルがあります。とはいえ使う場所を選ぶことで、他のアーキテクチャで実行しようとすると煩雑になる作業を比較的小さいノード数で組むことができます。長谷川氏がHTNの導入に最適なタイトルとして挙げたのがシェフとなり、客からの注文に応じて食材や食器などの在庫を管理しながら料理を出すゲーム『Overcooked』（2016年、Ghost Town Games）です。サブタスクと複雑な依存関係があるタスクを処理しなければならず、かつタスクの順番が必ずしも固定されていないためHTNを活用したプランニングが向いているとのことでした。

Editor：高橋ミレイ