More than 3 years have passed since last update.

@tyemiya(Takuma Seimiya)in

株式会社ディー・エヌ・エー

階層化型タスクネットワークを勉強して、ゲームAIのコードを書いてみた

Last updated at 2019-12-16Posted at 2019-12-16

この記事はDeNA20卒内定者エンジニアによるアドベントカレンダーDeNA 20 新卒 Advent Calendar 2019の記事として書かれています。

はじめに

最近ゲームのキャラクターAIに興味があって勉強しているのですが、その中で階層化型タスクネットワーク（Hierarchical Task Network略してHTN）というアルゴリズムについて勉強したことをまとめてみます。
まだ学び始めたばかりなので、間違えてそうなとこ、もっと良くなる点などあればアドバイスいただければ幸いです。

この記事の内容はざっくり、

ゲームAIにおけるHTNの立ち位置
HTNとは何ぞや？という話
実際に自分でHTNを実装してみた感想

の3つを書ければと思っています。

ゲームAIにおけるHTNの立ち位置

〇ゲームAIの種類

ゲーム内におけるキャラクターAIの仕組みを簡潔に言えば、環境から何らかの情報を受け取り、何らかの情報を出力すると言えます。
ここで重要なのは、受け取った環境の情報からアウトプットする上で、どのような意思決定を行うのかという点です。

周りのマップ環境やキャラクターの置かれている状況などの情報をもとに、次に自分がどんな行動をするべきなのかみたいなことを決定するアルゴリズムが必要になります。

その意思決定の手法は、以下のような種類に分けられることが多いです。

ルールベース
ステートベース
ビヘイビアベース
タスクベース
ゴールベース
ユーティリティベース
シミュレーションベース

などなど

それぞれの手法がどのようなものなのかは他の人がたくさん説明してくれているので省略します。こちらの記事が簡潔にまとまっていました。

もっと詳しく知りたい方は、スクエニの三宅陽一郎さんの書かれている本や講演記事などを見るとめちゃめちゃ勉強になります。僕もとてもお世話になっております。
三宅さんが作成するスライドはいつも情報量が半端ないです。ゲームAI入門（前半）

〇最近の流行り

上記の手法の中での最近の主流は、ビヘイビアベースです。
とりあえずキャラクターAIを作るなら、Behavior Treeという、木構造状に定義した振る舞い（ビヘイビア）を環境に合わせて実行していくビヘイビアベースの手法を使うのが一般的ではないかと思います。

その理由としては、僕は以下が挙げられると思ってます。

AIの構造の複雑性に耐えられる
- State Machineなどでは、AIの状態が増えていくとぐちゃぐちゃになって厳しい
保守性が高い
- 他のノードに依存しづらいので、木構造の一部分を取り除いても動く
プランナーさんに優しい
- グラフィカルにAIを作れるので、コーディングできないプランナーでも作れる
- しっかり考えて作れば、プランナーが意図していない行動は取らなくなる

〇HTNの立ち位置

Hierarchical Task Networkという名前にもある通り、HTNはタスクベースのアルゴリズムになります。

タスクベースやゴールベースなどの手法が他の手法と違う点は、プランニング（計画）を行うという点です。
プランニングとは、なにかしらの目的達成のために実行する必要のある行動計画を自動で組み立てるアルゴリズムのことです。

ビヘイビアベースなどは、現在の環境情報に応じて反射的に行動を決定してしまうアルゴリズムです。そのため、その前の行動を参考にしたり、その行動を行った影響などを考慮した上で意思決定することは難しいです。

だんだんとゲームが複雑化、巨大化していく中でより人間らしく、より頭が良いと思われるAIを作成していくには、プランニングの要素も必要となってきます。
やっぱり、ただ反射的に行動している人よりも、何か目的に沿って一連の行動をしているように見える人の方が頭良さそうですよね。

そのため、最近のゲームでは単一の手法だけでキャラクターAIを作らずに、例えば、Behavior TreeとHTNを組み合わせたハイブリッド型のAIというのも増えてきているようです。
ということは、ここらでHTNのようなタスク指向のAIの仕組みを学んでいくというのは結構アリなのでは？と思って、勉強し始めた次第です。

前置きが長くなりましたが、ここからHTNについての話を進めていきます。

HTNとは何ぞ？

基本的にどのHTNの記事も、こちらのGame AI Proに紹介されている内容が元となってます。まずはこれを読むことから始めましょう。

◯HTNの概要

HTNは階層化型タスクネットワークと日本語で表せますので、「タスク」、「ネットワーク」、「階層化型」という順番でHTNとは何かを見ていきましょう。

・「タスク」

上記でも述べたように、HTNはタスクベースのアルゴリズムです。
タスクベースで使用するタスクという単位は、僕の理解では若干曖昧なんですが、一般的に使用してる意味と変わらないのではと思ってます。
ToDoリストとか作成したことあると思うんですが、あれって抽象的なタスク、具体的なタスク、時間軸的に長期間のタスクなどいろいろ粒感がバラバラに混ざってしまうことって多くないですかね？僕だけ？
タスクベースもそれと同じで、大小いろいろなタスクがあります。

・「ネットワーク」

次に、ネットワークについて。タスクベースAIではただタスクを羅列するだけではなくて、タスク同士に関係性を持たせます。
タスクAを実行するには先にタスクBをやる必要がある、とか、タスクCの実行にはタスクD/E/Fのどれかを実行しないといけないみたいな感じです。そうやって考えていくと、それぞれのタスク同士で関係性の線が繋がっていくのがイメージできるでしょうか。
そのようなタスクとタスクが繋がっている空間？のことをタスクネットワークと呼んでいると思っています。

・「階層化型」

上記の2つでタスクネットワークは構築できるのですが、それぞれのタスク間に階層構造を持たせることでより抽象度高く、より効率的にプランニングを行うことができます。
タスクネットワークに階層構造を持たせることで、抽象度の高いタスクから具体的なタスクへのタスクの分割が行いやすくなります。
また、人が行動を計画するときの思考と似ているので、タスクネットワークを構築しやすいことが多いのもメリットです。

〇HTNの構成要素

この画像が、HTNを表す全体像になります。それぞれ、どんなものなのかを見ていきましょう。

Game AI Pro ~Exploring HTN Planners through Example~より

・World State

そのAIから見た世界そのもの。AIのインプットとなる環境情報をまとめたもの。世界すべてを記す必要はなく、AIにとって必要となる情報だけを更新し続ければよい。俗に言う、Blackboardみたいなもの。

・Domain

階層化されたTaskの全体を表した知識群。
ここに問い合わせれば、Taskのことがなんでも分かる場所（という認識）

・Task

HTNの基本的な単位。TaskはPrimitive TaskとCompound Taskの2種類に分けられる。

・Compound Task

複合タスク。階層的に上位のタスク。
複数のMethodを持ち、それらを管理することで様々なタスクの分岐を生む。
保有しているMethod群の中から、現在のWorld Stateの状況に合ったものを探し、そのMethodのSubTaskを後続に流す。

・Method

Compound Taskに保有される。
Methodは以下の2つを持つ。

PreCondition：このMethodを選択するための条件
SubTasks：複数個のTask群（Primitiveでも、Compoundでも）

・Primitive Task

AIが行動を起こす上での最小単位。これ以上小さいタスクはない。
Primitive Taskは以下の3つを持つ。

PreCondition：このPrimitive Taskを実行するための条件
Operator：AIの行動内容
Effects ：このPrimitive Taskを実行した結果、World Stateに与える影響

・Planner

プランニングを行い、プランを管理する本体。
Domainを用いて最適なTaskリスト（Plan）を作成し、現在行うべきTaskを監視する。

Plannerは以下の3つの状態のどれかが起きると、再プランニングを行う。
1. 現在のPlanが完了 or 失敗したとき
2. Planを持っていないとき
3. 外部センサーによって、World Stateの情報が更新されたとき

・Plan Runner

Plannerから受けとったタスクリストの実行と管理を行う。
途中でタスクの実行に失敗するか、全てのタスクをやり切るまで監視する。

結局、何ぞ？

・タスクを2種類に分けることで、タスク同士に階層構造を持たせたタスクベースAI
・タスク同士の関係性をもとにした上で、あるタスクを実行するまでのプラン作成を行う

今回の成果物

GitHubりぽじとり

今回書いたコードは上記になります。最初に断っておきますが、未完成です。泣
キャラクターの行動を実際に実行するところ（Operator周りの実装）まで間に合わず、せっかくUnityで作成していたのにUnityの恩恵を全く受けられていない状態です。悲しい。
また、この記事を書くために再度いろんな記事を読み直して思ったのですが、Domainの実装をミスった感があります。

なので、このままじゃまだまだゲームの使い物にはなりませんが、HTNを実装する上で何かの助けになれば嬉しいです。
今後も実装は続けようと思っているので、長い目で見てやってください。。。

解説

コードに関してはざっくり解説していきます。

Planner

HTNPlanner.cs

public List<TaskBase> Planning(IWorldState currentState, TaskBase rootTask)
    {
        plannerStateHistory.Clear();
        plannerState = new PlannerState(
            currentState.Clone(),
            new List<TaskBase>(),
            new List<TaskBase>() { rootTask },
            0);

　　　　　// 実行予定タスクがなくなるまでプランニングを続ける
        while (plannerState.TaskListToProcess.Count > 0)
        {
            var currentTask = plannerState.TaskListToProcess[0];
            if (currentTask is CompoundTask currentCompoundTask)
            {
                var satisfiedMethod = FindSatisfiedMethod(currentCompoundTask, plannerState);
                if (satisfiedMethod != null)
                {
                    RecordDecompositionOfTask(currentCompoundTask);
                    plannerState.TaskListToProcess.RemoveAt(0);
                    plannerState.TaskListToProcess.InsertRange(0, satisfiedMethod.SubTasks);
                }
                else
                {
                    RestoreToLastDecomposedTask();
                }
            }
            else // PrimitiveTask
            {
                if (currentTask.CheckPreCondition(plannerState.WorkingWS))
                {
                    plannerState.TaskListToProcess.RemoveAt(0);
                    plannerState.FinalPlanList.Add(currentTask);
                    plannerState.WorkingWS = currentTask.ApplyEffects(plannerState.WorkingWS);
                }
                else
                {
                    RestoreToLastDecomposedTask();
                }
            }
        }

        return new List<TaskBase>(plannerState.FinalPlanList);
    }

Plannerクラスの役割は与えられたルートタスク（一番上位のタスク）を元に、タスクリストを作成することです。
ここで説明が必要そうなのはTaskListToProcessですかね。これは、実行可能かを検証する予定のタスクリストみたいなもので、一番最初はルートタスクのみが入ります。

こちらの画像が分かりやすいと思います。
TaskListToProcessに入っているタスクは順番に条件をチェックされ、分解されるかFinal Planに格納されているかのどちらかになります。

Game AI Pro ~Exploring HTN Planners through Example~より

もし途中でTaskListToProcessのタスクの事前条件が成立しなかった場合は、分解される前の直前のCompound Taskの状態まで遡り、違う分解方法を試します。

Task

TaskBase.cs

public enum TaskType
{
    PrimitiveTask,
    CompoundTask
}

public abstract class TaskBase
{
    public TaskType TaskType { get; set;}
    public string TaskName { get; set;}
    public virtual bool CheckPreCondition(IWorldState state) { return true; }
    public virtual IWorldState ApplyEffects(IWorldState state) { return state.Clone(); }
    public virtual bool ExecuteOperator(IWorldState state) { return true; }
}


public abstract class PrimitiveTask<T> : TaskBase where T : IWorldState
{

    // タスクを実行できるかどうかを返す
    public override bool CheckPreCondition(IWorldState state) { return IsSatisfiedPreConditions((T)state); }
    public abstract bool IsSatisfiedPreConditions(T currentState);

    // タスクを実行した場合のWorldStateを返す
    public override IWorldState ApplyEffects(IWorldState state) { return ApplyEffectsToWorldState((T)state); }
    public abstract IWorldState ApplyEffectsToWorldState(T previousState);

    // タスクを実行する
    public override bool ExecuteOperator(IWorldState state) { return Execute((T)state); }
    public abstract bool Execute(T state);
}


public abstract class CompoundTask : TaskBase
{
    public List<Method> Methods = new List<Method>();
}

タスク周りの実装は上記のように行いました。基本的に構成要素で説明した通りの内容です。
これらを継承して、実際のタスクの中身を作ることになります。
たとえば、以下のように移動タスクを作ってみました。

MovoToTargetTask.cs

public class MoveToTask : PrimitiveTask<ExampleWorldState>
{
    public MoveToTask() : base()
    {
        TaskType = TaskType.PrimitiveTask;
        TaskName = "移動する";
    }

    public override bool IsSatisfiedPreConditions(ExampleWorldState currentState)
    {
        return currentState.MoveTarget != null;
    }

    public override IWorldState ApplyEffectsToWorldState(ExampleWorldState previousState)
    {
        var state = (ExampleWorldState)previousState.Clone();
        state.MoveTarget = null;
        return state;
    }

    public override bool Execute(ExampleWorldState state)
    {
        Log.Instance.Printlog(TaskType.ToString() + TaskName + "to" + state.MoveTarget);
        state.MoveTarget = null;
        return true;
    }
}

Compound Taskが保有するMethodはこんな感じ。

Method.cs


public abstract class Method
{
    public List<TaskBase> SubTasks = new List<TaskBase>();
    public List<PreConditionBase> PreConditions = new List<PreConditionBase>();

    public bool CheckPreCondition(IWorldState state)
    {
        foreach(var preCondition in PreConditions)
        {
            if(!preCondition.CheckPreCondition(state))
            {
                return false;
            }
        }
        return true;
    }
}

Plan Runner

PlanRunner.cs


    /// <summary>
    /// 現在のCurrentTaskを実行し、次のTaskがあれば更新する。
    /// その上で、現在のPlanの状態を返す。
    /// </summary>
    private CurrentTaskStatus UpdateCurrentPlanStatus(IWorldState worldState)
    {
        // Taskの実行
        if (currentTask != null)
        {
            if (!currentTask.CheckPreCondition(worldState))
            {
                currentTask = null;
                currentPlan = null;
                return CurrentTaskStatus.PlanFailed;
            }

            if (!currentTask.ExecuteOperator(worldState))
            {
                currentTask = null;
                currentPlan = null;
                return CurrentTaskStatus.PlanFailed;
            }

            worldState = currentTask.ApplyEffects(worldState);
            currentTask = null;
        }

        if (currentPlan == null)
        {
            return CurrentTaskStatus.NoPlan;
        }

PlanRunnerでは、上記のように今行うべきタスクをプランから取得して実行していってます。

今後への課題

いろいろ考えて実装してみたはいいのですが、当方よわよわエンジニアのため、いろいろ漏れてるところがあります。

Domainのあり方
- HTNについて、僕が一番うまく理解できていなかった部分です。タスク同士の関係性などの全ての知識をここに集めることが必要でしたが、僕はリポジトリ的な立ち位置で使用していました。多分、最終的なプランはドメイン層が返してあげられるぐらいまで作りこんでいいのだと思います。Plannerはその補助を行う役割かと。
Operatorの実装
- Operatorはキャラクターの実際の行動部分に当たるのですが、タスクにうまく引数を渡す機構を作らないといけなかったり、行動の状態の監視を行う必要があったりなどいろいろと今の僕には難しいなと思うことが多かったです。ただ、やっぱり文字を出すだけでなく、キャラを動かすまでやって、ゲームAIを作ったって言いたいですね。
非エンジニアへの対応
- ここは若干本題と逸れるかもですが、HTNにもBehavior Treeのようなグラフィカルな操作ができたりしてほしいと感じます、また、コードの自動生成も行えないと同じようなタスクをちまちま作ることになって大変です。