本記事は『戦略ゲームAI 解体新書 ストラテジー＆シミュレーションゲームから学ぶ最先端アルゴリズム』（三宅陽一郎）の「第4章 指揮官としての人工知能─「メンバーやユニットを指揮するゲーム」」から「4.4 時間の階層化」を抜粋したものです。掲載にあたって一部を編集しています。
前編「ストラテジーゲームにおける指揮官としての人工知能、制御の要となる「チームと空間の階層化」を解説」はこちらから読めます。
時間の階層化
「時間の階層化」と言ってもぴんと来ないかもしれません。しかし、人間も、この時間はだいたい書類仕事をして、この時間はだいたい調べものをして、この時間は休憩して、とだいたい決めておいて、その時が来たら、さらにそれぞれの時間の中で細かくすることを決める、ということがあると思います。これが「時間の階層化」です。
この人間の「するべきこと」は人工知能では「タスク」と言います。大きなタスクを中くらいのタスク、小さいタスクに分割していくことで、計画の全容を決めていきます。このような大きなタスクをより小さなタスクへ分割しつつ接続していく意思決定の方法を「階層型タスクネットワーク」（Hierarchical Task Network、HTN）と言います。
階層型タスクネットワーク
「階層型タスクネットワーク」は、タスクそれ自体に知的機能を持たせることによって階層的に命令を自動的に作り出していく手法です。「タスク」とは何か、を明確に定義しておきます。
タスクとは、以下のように定義できます。
（1）「明確に範囲と行動が指定された仕事」（ドメイン）
（2）「状況によっていくつかのより小さなタスクに分解される」（メソッド）
（3）「実行のための前提条件がある」（プリコンディション）
たとえば「お皿を机から流しに運ぶ」「積み木Aを積み木Bの上に置く」というタスクの場合、ドメインとは「お皿、机、流し」「積み木」であり、それ以外の情報は考慮に入れません。ストラテジーゲームの場合は「敵Aと砂漠で交戦する」などです。
また各タスクには各タスクの「実行のための前提条件」（precondition）が存在します。たとえば「味方を助けに行く」というタスクの前提条件は「30秒以内にたどり着く場所にいること」、「味方をかばう」というタスクの前提条件は「十分な体力が残存していること」です。
タスクは「コンポジット・タスク」（合成タスク）と「プリミティブ・タスク」（原初タスク）に分かれます。「コンポジット・タスク」はさらにそれ以下のタスクに分解されるタスクのことであり、より小さなタスク（サブタスク）への分解の仕方である「メソッド」を持っています。
たとえば「クリームソーダを作る」はコンポジット・タスクであり、これは「ソーダを作る」「アイスを乗せる」というタスクにメソッドによって分解されます。「ソーダを作る」「アイスを乗せる」はこれ以上、分解できませんので「プリミティブ・タスク」となります（図4.5）。特に大切なのは、この2つのタスクに順番がある、ということです。
このような階層図は図4.6のようなタスクネットワークを生み出します。タスクは順序構造を持ち、順序がなく並列に実行して良い場所は並列に並べられます。いったん、このようなタスクネットワークができると、実行器（Executor）にこのネットワークが渡され実行されることになります。
ここまでの解説を読まれると、それでは最初から図4.5のようなツリー構造を作っておけば良いのでは、と考えられる方もおられると思います。階層型タスクネットワークの多様性はメソッドの状況によるさまざまな分解の方法によってもたらされます。上記はメソッドによる一通りの分解の仕方しか示しませんでしたが、実際、メソッドは条件によって他の分解の仕方もありますので、これとまったく違った分解の仕方を定義しておけば、また違ったタスクネットワークができます。
「アイスを作る器具がない場合」「スプーンが近くにない場合」には、異なる分解の仕方を行うようにメソッドに記述しておけば、図4.7のように「アイスを買いに行く」「アイス専用ストローを持ってくる」タスクネットワークとなります。このように状況によって、さまざまな分解のされ方が起こり、その組み合わせによって、さまざまなタスクネットワークが生成されるところに、階層型タスクネットワークの真骨頂があるのです。
MEMO 参考文献
「階層型タスクネットワーク」については、以下の文献を参考にしました。
長谷川誠、『【GDM37】ゲームAI における意思決定と地形表現～『LEFT ALIVE』を事例に紹介』、GDM、2019
応用例
たとえば、魔法部隊が2つあり、指揮官の人工知能から指示を出すとします。敵モンスター部隊も3つの部隊がありますが、最後の1つがとても大きな部隊であり、戦力をまとめて戦う必要があったとします（図4.8）。
この場合、2つの魔法部隊は最初の戦いが終わってから、もう一方の部隊と合流して戦う必要があります。すると、指揮官としては、まず各部隊のリーダー（サブリーダー）には、まずそれぞれの部隊に戦うように命令します。そして、その次に2つの部隊を合流させ、3つ目の敵に一緒に向かわせる、という命令をしたいわけです。
こういった命令を人工知能の指揮官にさせたい場合には、今回の例では「戦闘」して、「合流」して、という大きなタスクのシークエンスがあります。このタスクのシークエンスは、今回は固定にしておきます。それぞれのタスクにはさらに細かいタスクがあります。たとえば、序盤の「戦闘」では、それぞれのチームに戦闘を割り当てます。次に合流ではそれぞれのチームに合流ポイントに来るように指示を出します。さらに最後の「戦闘」では敵をどちらから攻めるかを指定します。
この場合、「戦闘」タスクは「敵チームに対して味方のチームを割り当てて戦わせる」という機能を持たせます。つまり味方A、Bの周囲にいる敵X、Y、Zを選択し、A、Bにターゲットとして割り当てる、という機能です。この「戦闘」タスクは、呼び出された状況に応じてさまざまな分解の仕方をすることになります。この指揮官のタスクネットワークは図4.9のようになります。ここで近い方ではなく、戦力が拮抗するように割り当てる、という分解の仕方も入れておけば、場合によっては味方Aを敵Yに、味方Bを敵Xに割り当てる、ということも起こり得ます。
ここで、新しい仕様を追加します。これまではあらかじめすべてのタスクを分解しておきましたが、それでは状況の変化が起こった場合、プランのミスマッチが起こるかもしれません。そこで、それぞれのタスクは、それを実行するタイミングで分解を行うことにします。つまり、最初は「戦闘する」「合流する」「戦闘する」という第1階層のタスクだけを準備しておきます。
まずゲーム開始時に最初の「戦闘する」タスクを分解メソッドによって分解します。すると2つのプリミティブ・タスクに分解されます。次に敵を倒したら「合流する」を分解します。指揮官AIが「合流する」を指示する場合、メソッドによる分解の仕方は2通りあり、合流地点を指示して集合させるメソッドもあれば、お互いがお互いへ向かわせるメソッドもあります。今回は後者のメソッドを選択したとしましょう。合流したら最後の「戦闘する」を分解します。すると2つのプリミティブ・タスクに分解されます。タスクをつないでいく（ネットワークする）と、2つのタスクの流れが形成されます（図4.10）。
このようなとりあえずのプラン（第1階層）を作っておいて、詳細なプラン（第2階層のプラン）は適時、実行する段階で分解によって生成する手法を実行時分解（Lazy Evaluation）と言います。この手法を使うと、ある程度の堅牢なプランを立てながらも、ゲームの状況に合わせて変化させることができます。
たとえば、もし敵Dがいきなり現れたとしたら、最後の「戦闘する」タスクは「味方Aに敵Cと戦うように指示する」「味方Bに敵Dと戦うように指示する」ように分解されることになります。このように同じタスクでも状況によって異なる分解のされ方があるところに本手法の多様性があります。
MEMO 参考文献
HTNとLazy Evaluationについては、以下の文献を参考にしました。
Troy Humphreys, "Exploring HTN Planners through Example GAME AI PRO, Chapter 12, pp.149-167", A K Peters/CRC Press, 2013
輸送問題
今度は味方魔法チームA、B、そして召喚モンスターで、敵モンスター本拠地を占拠する、という場合を考えてみましょう。敵モンスター拠点の前には森があって、この森で自分の魔法チームの体制を整えたいとします（図4.11）。
ところで、ここに魔法輸送船があって、1チームを輸送することができるとします。魔法輸送船は道路に沿ってしか動くことができません。魔法チームは徒歩ですので森の中も歩けるとします。あなたが指揮官であるなら、「敵本拠地制覇」のためにどのように作戦を立てるでしょうか？
まず大きくは、「敵本拠地攻撃」「敵本拠地占拠」にタスクを分けることができます。ここで「敵本拠地攻撃」は敵本拠地にいる敵を倒すことであり、「敵本拠地占拠」は敵本拠地に居座り周囲の敵を倒すことで占領することを意味します。「敵本拠地攻撃」というタスクはさらに小さな「チーム移動」「チーム攻撃」というタスクに分解することができます（図4.12）。
ここで「チーム移動」はフォーメーション領域（図4.11に明記）までの移動です。「敵本拠地占拠」はさらに「チーム移動」「敵本拠地防衛」（籠城して周囲の敵を追い払う）に分解することができます。ここでの移動は敵本拠地に集合することを意味しています。
さて、ここで「チーム移動」ですが、2つのチームA、Bがあるので、「どちらか一方を魔法輸送船で目的地まで輸送すること」（T）ができます。そこでチームA、Bの進行状況に応じて「チーム移動」を分けることができます。召喚モンスターは歩いていくしかないので、ここでは考慮に入れる必要がありません。
まず、チームA、Bがすでに目的地の近くまで来ている場合にはチームA、Bを輸送する必要はなく、輸送船が単独で領域に向かえばいいわけです。次にチームAとチームBを比べて領域まで離れている方を輸送します。この3通りがあるわけです。メソッドとしては、チームA、Bと領域との距離を判定し割り振ります。「チーム移動」だけで図4.13のような分解になります。
また、魔法輸送船は道路に沿って移動しますので「場所1」か「場所2」のいずれかに止まる必要があります。このような割り当てもメソッド内で行うことで、どの場所に輸送船を止めるかを決定します。ここで「輸送移動」のタスクを分解する必要があります。輸送船XがチームYを乗せて場所Nまで移動する、というタスクにしておけば、このタスクはさまざまな場合に使うことができます。この輸送移動は図4.14のように分解することができます。
さて、このように分解メソッドを重ねていくと、分解のメソッドごとに、生成されるバージョンが増えますので、掛け算で作られるタスクネットワークの種類が増えていきます。ここではチーム攻撃と敵本拠地防衛のメソッドを省略しましたが、たとえば、生成されるタスクネットワークの1つは図4.15のようになります。
たとえばゲーム開始時ではチームBが遅れているとします。魔法輸送船はチームBを輸送します。次にフォーメーション領域から、それぞれが攻撃を始めたあと、敵本拠地へ集合するときは、チームAが遅れたために魔法輸送船はチームAを輸送する、というネットワークになっています。これも実行時評価によって結果的に得られたタスクネットワークということになります。
このような技術は『ArmA/Arma2』（Armed Assault, 2006, 2009, Bohemia Interactive Studio）における『Planned Assault』というミッションジェネレーターとして応用されています。上記の解説もこのミッションジェネレーターの実装を参考に考案しました。
MEMO 参考文献
全体を通じては、以下の文献を参考にしました。
William van der Sterren, "Multi-Unit Planning with HTN and A*", AIGameDev.com's Paris game AI conference, 2009
特に「輸送問題」については、以下の文献を参考にしました。
William van der Sterren, "Hierarchical Plan-Space Planning for Multi-unit Combat Maneuvers", GAME AI PRO, Chapter 13, pp.169-183, A K Peters/CRC Press, 2013
