【Unity】階層型タスクネットワークを実装してみた【ゲームAI】

概要

　Unityによって階層型タスクネットワークを実装し、以下のデモのようにプランニングと実行をできるようにします。

　Unityのバージョンは2020.2.0f1です。
　プロジェクトはGitHubに上げておきます。
　https://github.com/saragai/SimpleHTN
（イラストの再配布を防ぐために画像がMissingになっています）

階層型タスクネットワークとは

　英語ではHierarchical Task Networkと呼ばれます。以下HTNと呼びます。
　HTNはその名の通り、タスクを階層的に組み合わせて作られるネットワークのことです。
　HTNはゲームAIのプランニングに用いられます。

プランニングとは

　プランニングとは、何らかの目標に対して、どの行動をどの順序で行うべきかをあらかじめ考えることです。

　例えば、現在家にいて、「新宿駅へ行く」という目標を立てたとします。
　この目標は、最寄り駅が池袋駅だとすると

• 「家を出る → 池袋駅まで歩く → 電車に乗る」

のような方法で実現できるとします。
　しかし、電車で行くとするとお金が必要ですが、お金が手元にないとしたらどうでしょうか。その場合は,

• 「家を出る → 銀行まで歩く -> お金を下ろす -> 池袋駅まで歩く → 電車に乗る」

とする必要があります。また、足を骨折していた場合は

• 「タクシーを呼ぶ -> 家を出る -> 池袋駅までタクシーで行く → 電車に乗る」

のような方法をとる必要があり、この場合はさらにお金が多く必要になります。

　ゲームAIとしてよく用いられるFSMやBehaviorTreeなどは、行動を決定する際に現在の状況しか見ることができません。
　しかし、上の例のようにどのようなルートを通るかで、必要なお金は変わります。その場合、「お金が足りるか」という条件を確かめるだけでも今から行うであろう行動を想定して手動で設定しなければならず、条件分岐が大量に必要になります。

　しかし、目標達成までに行うべき行動をあらかじめ列挙(=プランニング)できれば、「お金が足りるか」はおのずとわかるはずです。
　ここで、プランニングを行う際には、その行動に必要な条件と行動の影響がわかっている必要があります。例えば、電車に乗るのであれば、必要な条件は「運賃260円を持っている」であり、行動の影響は「所持金が260円減る・自分のいる場所が池袋から新宿にかわる」です。
　これらの条件を行動自体と合わせてまとめたものを、タスクと呼びます。

タスクとは

　改めてまとめます。HTNにおいて、タスクは以下の情報を持ちます。

• 必要な条件
• 実際にする行動
• 行動した際の影響

　必要な条件と行動した際の影響がまさにプランニングに必要な要素です。この情報のおかげで実際に行動しなくても仮想的に行動の結果がわかってシミュレーションが可能になります。
　この二つは、どちらもWorldStateと呼ばれる世界の状態を参照します。
　プランニングの際は、現在のWorldStateのコピーを作成し、仮想的にタスクを実行してWorldStateのコピーを更新していくことでシミュレーションを行います。

階層的とは

　タスクには様々な粒度があります。
　先ほどの例のように「新宿駅へ行く」はタスクですが、これは「家を出る」「池袋駅まで行く」「電車に乗る」などのタスクに分解できます。さらに「家を出る」は「靴を履く」「ドアを開ける」「鍵を閉める」へと分解できるでしょう。
　逆に言うと、「靴を履く」というような細かい具体的なタスクをまとめることによって「新宿駅へ行く」という抽象的なタスクにして扱いやすくできるのです。

　また、抽象的なタスクには複数の表現方法があることも述べました。

• 「タクシーを呼ぶ -> 家を出る -> 池袋駅までタクシーで行く → 電車に乗る」
• 「家を出る → 銀行まで歩く -> お金を下ろす -> 池袋駅まで歩く → 電車に乗る」

　この二つの方法の内容に差異はありますが、どちらの分解方法を選んだとしても最終的に目的は達成できるため、同一のタスクとして扱われるべきです。

　このような前提から上で述べたタスクをまとめた複合タスクを考えることができます。
　複合タスクは、「目的を達成するための一連のタスク」と「一連のタスクを選ぶための条件」のセットを複数持つものとします。
　この『「目的を達成するための一連のタスク」と「一連のタスクを選ぶための条件」のセット』はMethodと呼ばれます。

　この複合タスクも、以下のように確かにタスクの要件を満たすため、タスクと同様に扱うことが可能になっています。

• 必要な条件：Methodを選ぶための条件と、選ばれたMethodが持つ一連のタスクに必要な条件
• 実際にする行動：選ばれたMethodの持つ一連のタスクの実際にする行動
• 行動した際の影響：選ばれたMethodの持つ一連のタスクを実行したときの影響

　この複合タスクを導入することによって、タスクを階層的に扱うことができるようになります。

用語

　ここまででHTNに必要な一通りの要素を解説しました。実装に移る前に用語を整理しておきます。

• Primitive Task: 最も基本的なタスクのこと

  • Condition: 必要な条件のこと
  • Operator: 実際にする行動のこと
  • Effect: 行動したときの影響のこと

• Compound Task: 複合タスクのこと

  • Method: Conditionと一連のタスクのセット
    • Sub Task: 一連のタスク

• World State: 世界の状態。タスクの条件や影響で参照される

• Planner: タスクを一つ設定し、プランニングして実行する行動の順列を割り出すひと

  • Root Task: プランニングしたいタスク

• Plan Runner: プランを実行するひと

実装

一般的な実装

　HTNを解説している記事はたくさんありますが、どれもGame AI Pro 12を参考にしているようです。
　以下に疑似コードを引用します。

WorkingWS = CurrentWorldState
TasksToProcess.Push(RootTask)
while TasksToProcess.NotEmpty
{
    CurrentTask = TasksToProcess.Pop()
    if CurrentTask.Type == CompoundTask
    {
        SatisfiedMethod = CurrentTask.FindSatisfiedMethod(WorkingWS) 
        if SatisfiedMethod != null
        {
            RecordDecompositionOfTask(CurrentTask, FinalPlan, DecompHistory) 
            TasksToProcess.InsertTop(SatisfiedMethod.SubTasks) 
        }
        else
        {
            RestoreToLastDecomposedTask() 
        }
    }
    else//Primitive Task
    {
        if PrimitiveConditionMet(CurrentTask)
        {
            WorkingWS.ApplyEffects(CurrentTask.Effects)
            FinalPlan.PushBack(CurrentTask)
        }
        else
        {
            RestoreToLastDecomposedTask()
        }
    }
}

　これについて軽く解説をします。
　はじめに処理スタックにRootTaskを積み、以下の処理を処理スタックが空になるまで繰り返します。

• 処理スタックに乗っているタスクを取り出して、CompoundTaskかPrimitiveTaskかで場合分ける
  • CompoundTaskであれば、実行できるMethodがあるか確認して、あればSubTasksを再び処理スタックに積む
  • PrimitiveTaskであれば、実行できるか確認して、実行できるならプランにそのタスクを加える
• どちらの場合でも、失敗したら最後にCompoundTaskを展開したときまで状態を差し戻す

……なんかちょっと気になりませんか？
　気になるポイントは二点あります

• CompoundTaskかPrimitiveTaskかで場合分けしているのが気持ち悪い
• 最後に展開したときまで状態を差し戻すというのが分かりづらく、今何をしているのか混乱する

　個人的な理解としてはCompoundTaskはPrimitiveTaskの拡張なので、同じインターフェースによって統一的に扱えるのではないかと思いました。また、スタックに新たなタスクがどんどん積まれていく中で、「最後にCompoundTaskを展開した時まで戻す」がどういう挙動になるのかちょっと想像しにくい気がしました。

　もちろんそのまま組んで悪いことは全然ないのですが、そのままの実装については他の記事でもたくさん実装例があるのでちょっと変えてみようと思います。
　気になるポイントへの対処としてはそれぞれ、

• Taskをインターフェースで扱って、CompoundTaskとPrimitiveTaskの処理の違いはそれぞれのTask側に実装する
• スタックではなく再帰によって階層を実現する

です。

インターフェース & 再帰による実装

　CompoundTaskとPrimitiveTaskはともにITaskインターフェースを実装します。

public interface ITask
{
    bool TryPlanTask(WorldState state, ref Plan plan);
}

　唯一のメソッドTryPlanTask()は、WorldStateを受け取ってタスクを実行できるか確認し、実行できるならPlanに追加していきます。このメソッドの中でWorldStateも更新していくことにします。

　また、本筋ではないですが、Unityを使った開発ではTaskの設定のためにScriptableOjectを使うのではないかと思うので、ScriptableOjectを継承した抽象クラスも間に挟みます。

public abstract class Task : ScriptableObject, ITask
{
    public abstract bool TryPlanTask(WorldState state, ref Plan plan);
}

それぞれ、以下のように実装します。

Primitive Taskの実装

　これは何のひねりもなく、ただConditionを満たしていたらWorldStateをEffectで更新し、プランにOperatorを加えているだけです。

[CreateAssetMenu(fileName ="primitive_task.asset", menuName = "Primitive Task", order = 0)]
public class PrimitiveTask : Task
{
    [SerializeField] List<Condition> m_Preconditions;
    [SerializeField] Operator.Operator m_Operator;
    [SerializeField] List<Effect> m_Effects;

    public override bool TryPlanTask(WorldState state, ref Plan plan)
    {
        foreach (var condition in m_Preconditions)
        {
            if (!condition.Match(state))
                return false;
        }

        foreach(var effect in m_Effects)
            effect.ApplyTo(state);

        plan.Enqueue(m_Operator);

        return true;
    }
}

Compound Taskの実装

　ここで再帰が出てきます。
　階層はCompoundTaskがMethodを介してサブタスクのTryPlanTask()を呼んで再帰することで実現しています。
　再帰で実装すると、「現在の状況を保存する場所」と「その状況に戻す場所」が近く、二つの対応が一目でわかるようになります。

[CreateAssetMenu(fileName ="compound_task.asset", menuName = "Compound Task", order = 1)]
public class CompoundTask : Task
{
    [SerializeField] List<Method> m_Methods;

    public override bool TryPlanTask(WorldState state, ref Plan plan)
    {
        foreach (var method in m_Methods)
        {
            // 実行するタスクを見つける
            if (!method.Match(state))
            {
                continue;
            }

            // 現在のplanを保存
            var currentPlan = new Plan(plan);

            // サブタスクを行う
            if(!method.TryPlanSubTasks(state, ref plan))
            {
                // 失敗したときplanを元に戻す
                plan = currentPlan;
                continue;
            }

            // サブタスクが全て完了したので成功
            return true;
        }

        // 条件を満たすメソッドがなかったので失敗
        return false;
    }
}

Methodの実装

[System.Serializable]
public class Method
{
    [SerializeField] List<Condition> m_Conditions;
    [SerializeField] List<Task> m_SubTasks;

    public bool Match(WorldState state)
    {
        foreach (var condition in m_Conditions)
        {
            if (!condition.Match(state))
                return false;
        }

        return true;
    }

    public bool TryPlanSubTasks(WorldState state, ref Plan plan)
    {
        foreach(var task in m_SubTasks)
        {
            if(!task.TryPlanTask(state, ref plan))
            {
                return false;
            }
        }

        return true;
    }
}

　このようにすることでPlannerのコードはとてもシンプルになります。

Plannerの実装

public class HTNPlanner : MonoBehaviour
{
    [SerializeField]
    WorldStateHolder m_WorldStateHolder;

    Plan m_Plan;

    public void Awake()
    {
        m_Plan = new Plan();
    }

    public Plan DoPlan(ITask rootTask)
    {
        m_Plan.Clear();

        // WorldStateのコピーを取って自由に書き換えられるようにする
        var tmpState = m_WorldStateHolder.WorldState.CreateCopy();
        rootTask.TryPlanTask(tmpState, ref m_Plan);

        return m_Plan;
    }
}

　ここでWorldStateではなくWorldStateHolderを介しているのは、WorldStateをMonoBehaviourにしたくないからです。WorldStateをMonoBehaviorにしてしまうとコピーを気軽にInstantiateできなくなってしまいます。

Planの実装

Operatorを表すインターフェースIOperatorを要素とするQueueの簡素なラッパークラスになっています。

public class Plan
{
    Queue<IOperator> m_Operators;

    public IEnumerable<IOperator> Operators => m_Operators;

    public Plan()
    {
        m_Operators = new Queue<IOperator>();
    }

    public Plan(Plan other)
    {
        m_Operators = new Queue<IOperator>(other.m_Operators);
    }

    public void Clear()
    {
        m_Operators.Clear();
    }

    public void Enqueue(IOperator @operator)
    {
        m_Operators.Enqueue(@operator);
    }
}

デモの実装

ここからはデモ用の実装をしながら、ここまで解説なしで出していたクラスについても説明します。
そのため、少し具体的な実装になってしまっています。本来はまだもっと抽象化すべきだと思うのですが、デモを兼ねているということで少し手を抜きました。

デモの状況

状態の種類とタスクについてはこのスライドを参考にしています
https://www.slideshare.net/dena_genom/gdm37aileft-alive

WorldStateの種類はenumで指定、値はboolのみとします。
ここでは状態は

• 空腹か
• 金を持っているか
• 食べ物を持っているか

のみとします。

Primitive Taskは

• 働く（金を得る）
• 食べ物を買う（金を使って食べ物を得る）
• 食べ物を食べる（食べ物を使って空腹を満たす）

Compound Taskは

• 食事をする

として、どのような状況でも食べ物を食べるまで行きつくようにMethodを設定します。

Operatorで指定される実際の行動は、移動のみとします。

WorldStateの実装

[System.Serializable]
public class WorldState
{
    /// 状態の種類
    public enum TYPE
    {
        IsHungry,
        HaveMoney,
        HaveMeal,

        MaxCount,
    }
    public static int NumStates => (int)TYPE.MaxCount;

    [SerializeField]
    private bool[] m_States;

    /// コンストラクタ
    public WorldState()
    {
        m_States = new bool[(int)TYPE.MaxCount];
    }

    /// 種類と値を指定して状態を設定
    public void Set(TYPE type, bool value)
    {
        m_States[(int)type] = value;
    }

    /// 種類を指定して状態の値を取得
    public bool Get(TYPE type)
    {
        return m_States[(int)type];
    }

    /// 自身を複製する（プランニングの際に必要）
    public WorldState CreateCopy()
    {
        var copy = new WorldState();
        for (int i = 0; i < NumStates; i++)
        {
            copy.m_States[i] = m_States[i];
        }
        return copy;
    }
}

Conditionは、WorldStateの種類を指定して、その真偽を問い合わせます。
Effectは、WorldStateの種類を指定して、その真偽を設定します。

Conditionの実装

[System.Serializable]
public class Condition
{
    [SerializeField] WorldState.TYPE m_Type;
    [SerializeField] bool m_Value;

    /// 状態を指定して条件を満たすか判断する
    public bool Match(WorldState state)
    {
        return state.Get(m_Type) == m_Value;
    }
}

Effectの実装

[System.Serializable]
public class Effect
{
    [SerializeField] WorldState.TYPE m_Type;
    [SerializeField] bool m_Value;

    /// 状態を指定して、新たな状態を設定する
    public void ApplyTo(WorldState state)
    {
        state.Set(m_Type, m_Value);
    }
}

Operatorの実装

　Operatorは、用途を考えると多種多様なものが必要になりそうなものなので、少し抽象化します。

　OperatorをPlan Runnerが実行するとき、個々のOperatorが何をするかを考えたくはありません。しかし、Operatorには実行対象を渡さないといけないため、実行時はIOperatableというインターフェースを引数で渡すことにします。

　また、OperatorはPlannerにおいてはプランニングのキューに入るだけですが、Plan Runnerが実行するときに実際に実行するときはある程度時間がかかるものが多いと思います。そのため、コルーチンで実装します。

// 操作対象
public interface IOperatable
{
    Transform Transform { get; }
}

// 操作
public interface IOperator
{
    string OperatorName { get; }
    IEnumerator Execute(IOperatable operatable);
}

public abstract class Operator : ScriptableObject, IOperator
{
    [SerializeField] string m_OperatorName;
    public string OperatorName => m_OperatorName;

    /// 操作を実行
    public abstract IEnumerator Execute(IOperatable operatable);
}

Move To Operator (Operatorの具象クラス）

　行きたい場所を指定してそこまで直進するOperatorとします。
　場所はとりあえずPlaceManagerというシングルトンを作ってそこから取っていますが、細かいところなので適当です。

[CreateAssetMenu(fileName ="move_to_operator.asset", menuName = "Operator/Move To", order = 0)]
public class MoveToOperator: Operator
{
    [SerializeField] PlaceManager.PLACE m_Place;
    [SerializeField] float m_Velocity = 1f;

    public override IEnumerator Execute(IOperatable operatable)
    {
        var targetPos = PlaceManager.GetPosition(m_Place);

        while (true)
        {
            var transform = operatable.Transform;
            var dir = targetPos - (Vector2)transform.position;

            if(dir.magnitude < 0.1f)
            {
                yield break;
            }

            dir.Normalize();

            // 動かす
            transform.position += (Vector3)( m_Velocity * dir * Time.deltaTime);
            yield return null;
        }
    }
}

Plan Runnerの実装

PlannerにRoot Taskを渡して、受け取ったIOperatorのキューに入っているExecuteを順番に呼んでいきます。

public class HTNPlanRunner : MonoBehaviour
{
    [SerializeField] HTNPlanner m_Planner;
    [SerializeField] Operatable m_Operatable;

    [SerializeField] Task m_Task;

    [SerializeField] float m_ReplanningInterval = 1f;

    List<IEnumerator> m_RunningCoroutines;

    // Start is called before the first frame update
    void Start()
    {
        m_RunningCoroutines = new List<IEnumerator>();
        StartCoroutine(SetTaskRoutine(m_Task));
    }

    IEnumerator SetTaskRoutine(ITask task)
    {
        while (true)
        {
            // 一定時間ごとにリプランニング
            SetTask(task);
            yield return new WaitForSeconds(m_ReplanningInterval);
        }
    }

    public void SetTask(ITask task)
    {
        StopCoroutine();

        var plan = m_Planner.DoPlan(task);
        StartPlan(plan);
    }

    /// プランの実行を開始
    void StartPlan(Plan plan)
    {
        var coroutine = Execute(plan.Operators);
        m_RunningCoroutines.Add(coroutine);

        StartCoroutine(coroutine);
    }

    /// 進行中のコルーチンを止める
    void StopCoroutine()
    {
        foreach (var coroutine in m_RunningCoroutines)
        {
            StopCoroutine(coroutine);
        }
        m_RunningCoroutines.Clear();
    }

    IEnumerator Execute(IEnumerable<IOperator> operators)
    {
        foreach (var @operator in operators)
        {
            var action = Execute(@operator);
            m_RunningCoroutines.Add(action);
            yield return StartCoroutine(action);
        }
    }

    IEnumerator Execute(IOperator @operator)
    {
        var action = @operator.Execute(m_Operatable);
        m_RunningCoroutines.Add(action);
        yield return StartCoroutine(action);
    }
}

デモの設定

　上でPrimitive Taskは

• 働く（金を得る）
• 食べ物を買う（金を使って食べ物を得る）
• 食べ物を食べる（食べ物を使って空腹を満たす）

の3つと言いました。それぞれ以下のように設定します。
・働く

・食べ物を買う

・食べ物を食べる

　全て、実際の行動は指定の場所に行くこととしています。

　余談ですが、Unity2020.2からリストがデフォルトでReorderableListになっています。便利です。
　参考：https://zenn.dev/ohbashunsuke/articles/1134c1615efc2b636769

Compound Taskの食事をするは以下のように設定します。

これは3つのMethodからできており、それぞれ

• 食べ物を持っているなら、食べ物を食べる
• 金を持っているなら、食べ物を買ってから再度食事タスクをする
• （条件なしで）働いて再度食事タスクをする

となっており、これが上から順に評価されて実行されます。

デモの結果

　初めに貼ったgifの挙動になります。

課題

　実は今、無限再帰を防ぐための処理を全くしていません。
　例えば、CompoundTaskにおいて、条件は常に真でSubTaskとして自分自身を指定すると無限ループが起きます。
　無限再帰を防ぐために、「同じ条件で同じタスクを与えられたときはスキップする」というような処理が必要です。

　そのほかにも、デモでは本当に単純なことしかやっていないので実際にゲーム内で使用するともっと課題が出てくると思います。そのような課題はこちらのスライドなどが詳しいです。

おわりに

　HTNの解説は以前から見聞きしていましたし、Qiitaにもいくつか記事があります。

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

　ですので完全に後追いなのですが、単純に自分で実装してみたかったことと、自分なりの解釈を書いておくことで誰かの理解の助けになればよいなと思ったので記事を書くことにしました。
　HTNのような綺麗な概念の実装は、ログを出して確認するだけだとすぐでも、実際使うことを考えると、どういうクラス構造にするか、データは誰が持つか、という複雑さがあるので、デモが動くところまで出来て良かったです。

　ここはもっとこうした方がよい、のような意見があればコメントで教えていただけるとありがたいです。
　ご拝読ありがとうございました。

参考文献

• はじめての階層型タスクネットワーク
• 階層化型タスクネットワークを勉強して、ゲームAIのコードを書いてみた
• 【UE4】HTNを実装してみた
  
• プレイヤーに反応するだけのAIはもう古い！ゲームAIへのプランニング技術の導入
• 【GDM37】ゲームAIにおける意思決定と地形表現～『LEFT ALIVE』を事例に紹介～
• Exploring HTN Planners through Example (GameAiPro, Chapter12)