LoginSignup
18
15

More than 3 years have passed since last update.

Unreal Engine 4 (UE4) #2Advent Calendar 2019Day 18
@Dv7Pavilion(Pavilion DV7)

【UE4】HTNを実装してみた

Last updated at Posted at 2019-12-17

はじめに

この記事はUnreal Engine 4 (UE4) Advent Calendar 2019 その２の18日目の記事です。そしてUE4アドカレ「勉強してみましたシリーズ」の最終回です。
GOAPの記事を書いた勢いでHTNについても勉強してみたのでここでまとめてみようと思います。

HTNとは

Hierarchical
Task
Network
の頭文字を取ってHTNです。日本語では「階層型タスクネットワーク」と（HTNプランナーとも）呼ばれます。

この技術は意思決定アルゴリズムの内、タスクベースに該当します。タスクベースはある抽象的なタスクからどんどんタスクを分解していき最終的に具体的な小さなタスクを求め、そこから一連のアクションを導き出します。この時、抽象的なタスクをコンポジットタスク（Composite Task）と呼び、具体的なタスクをプリミティブタスク（Primitive Taskも）と呼びます。

HTNで登場する用語たち

HTNの詳細な説明に入る前にHTNで頻出する重要な用語を紹介します。ここで出てくるいくつかの単語はGOAPの記事でも出てきます。

  • World State（世界の状態）

    • 文字通り世界の状態を表すデータ。例えば＜状態名、真理値＞と表される。（＜HasOre, True＞は（AIは）鉱石を持っていると同義）
    • 有名なホラーFPS：F.E.A.R.では真理値の部分を列挙型であったりオブジェクトのポインタだったりする。
    • この世界という言葉は第三者からみたゲーム世界とAI本人から見たゲーム世界のどちらの意味でも使われる。

  • Preconditions（前提条件）

    • あるタスクを実行するために満たしておくべき条件
    • 例：プレイヤーのもとへ移動する場合の前提条件として「プレイヤーを視認している」必要がある

  • Effects（効果）

    • 世界に与える状態のこと
    • 例：鉱石を拾うタスクの効果として＜HasOre、True＞をWorld Stateへ与える

  • Primitive Task（プリミティブタスク）

    • HTNで登場する2つのタスクの１つ。最も具体的なタスクでありAIが実行するアクションを持つ。
    • Primitive Taskは他のタスクを持つことは出来ない。
    • ツリー構造でいう葉に該当する。
    • 役割としてはGOAPのアクションと同じ。よってタスクを実行するための前提条件、効果を持つ。（しかし前提条件の実装は必須ではない）
    • GOAPのアクションと異なる点としてOperatorと呼ばれるアクションを持つ。（Operatorについては後述する）
    • 例：AからBへの移動、他オブジェクトへの攻撃、防御、等々
// 擬似コード（Exploring HTN Planners through Example より）
Primitive Task [TaskName(term1, term2,...)]
    Preconditions [Condition1, Condition2, …]//有っても、無くてもよい
    Operator [OperatorName(term1, term2,...)]
    Effects [WorldState op value, WorldState = value, WorldState += value]//optional

// 少し具体的な例
Primitive Task [SprintToEnemy] // エネミーに向かって走る
    Preconditions [WsHasEnemy == true] // 前提条件は「敵を認知しているか？」
    Operator [NavigateTo(EnemyLoc, Speed_Fast)] // 実際の行動（Enemy LocにSpeed_Fastの速さで移動する）
    Effects [WsLocation = EnemyLoc, WsIsTired = true] // 現在地はEnemy Locであり疲れている状態を世界に与える
  • Composite Task（複合タスク）
    • Hierarchical（階層）と名を持つ所以。Composite TaskやPrimitive Taskを持つことができる。（これらをSubtasks（詳細は後述）と呼ぶ）
    • ツリー構造でいう枝に該当する
    • Methodsと呼ばれるComposite Taskの分解ルートを決める条件を持つ
    • 例：プレイヤーを倒すComposite Taskの場合、サブタスクとして「プレイヤーへの移動」「プレイヤーへの攻撃」を持つ
// 擬似コード（Exploring HTN Planners through Example より）
Compound Task [TaskName(term1, term2,...)]
    Method 0 [Condition1, Condition2,...]
        Subtasks [task1(term1, term2,...). task2(term1,term2,...),...]
    Method 1 [Condition1, Condition2,...]
        Subtasks [task1(term1, term2,...). task2(term1,term2,...),...]

// 少し具体的な例
Compound Task [AttackEnemy]  // 敵を攻撃する
    Method 0 [WsHasTreeTrunk == true] // 前提条件「木の棍棒を所持しているか？」
        Subtasks [NavigateTo(EnemyLoc). DoTrunkSlam()] // 前提条件を満たしている時に展開できるサブタスク（「EnemyLocに移動」して、「攻撃」する）
    Method 1 [WsHasTreeTrunk == false] // 前提条件「木の棍棒は未所持か？」
        Subtasks [LiftBoulderFromGround(). ThrowBoulderAt(EnemyLoc)] // 「丸石を拾う」「EnemyLocに丸石を投げる」
  • Methods
    • Composite Taskの分解ルートを示す。
    • 例：の場合、Subtasks_Aを展開。条件を満たさない場合はSubtasks_Bを展開。

  • Operator（オペレータ）

    • 実際にAIが行うアクション。Primitive TaskはこのOperatorを実行してAIを世界で行動させる。
    • 例：実際にAI Move Toノードを定義したMove To等

  • Subtasks

    • Composite Taskが持つ他の（もしくは自身の）Composite TaskやPrimitive Taskのリスト
    • Methodsに沿ってComposite Taskを分解していきSubtasksを得る

  • Domain（ドメイン）

    • Composite TaskやPrimitive Taskを保持する。

HTNプランニングの外観

HTNプランニングの全体のイメージとしてはExploring HTN Planners through Exampleにある図が非常にわかりやすいです。

World StateはAIが持つSensors（UE4でいうAI PerceptionやPawn Sensingコンポーネントのこと）によって常に更新されます。PlannerはDomainに保持されている各Composite TaskをMethodsによって分解し、分解するべきComposite Taskが無くなった時点でのPrimitive Taskを一連のアクションとして返します。Plan Runner（ここではAI自身）は一連のアクションを実行しPrimitive Taskが持つEffectをWorld Stateへ適用します。

GOAPとの違い

HTNについてのひと通りの説明が終わったところで、もう１つのプランニングを用いた意思決定アルゴリズムであるGOAPとの違いを紹介していきます。

GOAPによるプランニング

GOAPでのプランニングはA＊による経路探索によって実現されます。
HTNでいうところの「Primitive Task」と「Operator」両方の機能を備えたActionを定義しDomainに放り込まれ、A＊によって各アクションの前提条件と効果を連鎖的につなぎ合わせることで一連のアクションを導き出します。

HTN

HTNでのプランニングは深さ優先探索（Depth First Search, DFS）による経路探索によって実現されます。
Composite TaskをMethodに基づいて分解を行い、Primitive Taskが出現するとそのPrimitive Taskが持つ効果をWorld Stateへと適用し実行リストへと格納されます。この時点で未だ分解されていないComposite Taskがあれば再び分解を行います。これを未分解のComposite Taskが無くなるまで繰り返します。
このComposite Taskの分解と出現したPrimitive Taskが持つ効果の適用を繰り返し、必要なComposite Taskを分解し尽くしたときに目標を達成するための一連のアクションが手に入ります。

以下の画像ではSubtasksの数字順にPrimitive Taskが出現します。Composite TaskであるPickup Oreの目標を達成するには
MoveTo(ToolStorage) -> Pickup(Tool) -> MoveTo(Mine) -> Pickup(Ore)
という順番にタスクを実行すれば良いことになります。

もう1つ分かりやすい図としてExploring HTN Planners through Exampleにある図も載せておきます。

プロジェクトはこちら

いつものようにOneDriveにてプロジェクトを配布しています。Unreal C++を使用しているのでVisual Studioの導入が必要だと思われます。

UE4バージョン：4.23.1
Visual Studio Community 2019 - Version 16.1.3
https://1drv.ms/u/s!Au-8FqgREBKZiTZ2QD6o4Z4FE0Ss?e=CBCrxs

プログラム解説

ここの実装は@yhaseさんのlua_plannerとExploring HTN Planners through Exampleを参考にしました。

C++側

HTNBaseTasks.h/cpp

これらのファイルにはHTNに必要な各タスクが定義されています。最初にPrimitive Taskのクラスから見ていきます。

Primitive Taskは前提条件と2種類の効果を持ちます。Expected Effectsは「プランニング時にのみ考慮される効果」、つまり「このタスクを実行するときはこういう状態になっていて欲しいな～」という期待を込めた効果を表します。Effectsは「実世界に影響を与える効果」を表します。このように効果を2種類に分けることによりOperator実行中に何らかの理由によって世界の状態が変化した場合に再プランニングで対処することが出来るようになります。（2種類の効果の実装はExploring HTN Planners through Exampleを参考にしました）

プロジェクトの実装ではPrimitive Taskが所持できるOperatorは１つのみです。『LEFT ALIVE』で採用されたHTNを用いたゲームAIとは？で紹介されているプロジェクトでは複数のOperatorを設定でき同時に実行できるようにしていますがUE4ではBP側にSequenceという並行処理のノードがあるのでこれで代用出来るのではと思いOperator１つのみの実装としました。

UCLASS(Blueprintable)
class HTNPLANNINGEXAMPLE_API UHTNPrimitiveTask : public UHTNTaskBase
{
    GENERATED_BODY()
private:
protected:
    UPROPERTY(EditDefaultsOnly, Category = "HTN")
        TSubclassOf<UHTNOperator> OperatorClasses;
    UPROPERTY(EditDefaultsOnly, Category = "HTN")
        FHTNWorldState Preconditions;
    UPROPERTY(EditDefaultsOnly, Category = "HTN")
        FHTNWorldState ExpectedEffects;

    UPROPERTY()
        UHTNOperator* Operator;         // 実際のアクション
    UPROPERTY()
        FHTNWorldState Effects;

    // 実世界に影響を与える効果はBP側で定義する。（「何個集めたときにTRUEにする」みたいなことをしたいので）
    UFUNCTION(BlueprintImplementableEvent, BlueprintCallable, Category = "HTN")
        void DefineEffects(FHTNWorldState& WS, class AAIController* OwnerController, APawn* ControlledPawn);

public:
    virtual void Initialize() override;
    // Expected EffectsをWorld Stateに適用する。（プランニング時にのみ呼ばれる）
    virtual void ApplyExpectedEffects(FHTNWorldState& WS) { WS.Update(ExpectedEffects); }

    // EffectsをWorld Stateに適用する（Operator実行後に呼ばれる）
    virtual void ApplyEffects(FHTNWorldState& WS, class AAIController* OwnerController, APawn* ControlledPawn) 
    { 
        DefineEffects(Effects, OwnerController, ControlledPawn);  
        WS.Update(Effects); 
    }

    // 前提条件のチェック
    virtual bool CheckPreconditions(const FHTNWorldState& WS);

    UHTNOperator* GetOperator() const { return Operator; }
};

Composite Taskはほとんどやることが無くComposite Taskを分解するためのMethodや分解した結果を保持するSubtasks配列を持つくらいです。

UCLASS(Blueprintable)
class HTNPLANNINGEXAMPLE_API UHTNCompositeTask : public UHTNTaskBase
{
    GENERATED_BODY()
private:
    void ClearSubtasks() { Subtasks.Empty(); }
protected:
    UPROPERTY(EditDefaultsOnly, Category = "HTN")
        TArray<TSubclassOf<UHTNMethod>> MethodClasses;

    UPROPERTY()
        TArray<UHTNMethod*> Methods;
    UPROPERTY()
        TArray<FString> Subtasks;
public:
    virtual void Initialize() override;

    // StartIndex番目のMethodを実行し、Composite Taskを分解する
    bool FindSatisfiedMethod(const FHTNWorldState& WS, int StartIndex = 0);

    const TArray<FString>& GetSubtasks() const { return Subtasks; }
};

HTNMethodsOperators.h/cpp

ここではComposite Taskの分解ルートを示すMethodクラスと実際にAIの振る舞いが定義されるOperatorクラスが定義されます。MethodクラスはBP側の実装が肝なのでここでは省略します。

OperatorクラスはAIが実際にゲーム世界での振る舞いを定義する場所なので多くの機能がBP側に公開されています。このクラスの実装はBehavior TreeのTaskノードの実装を参考にしました。
ReceiveExecuteActionには実際の振る舞いを定義します。よってMove Toノード等を配置する場所はこの関数内（BP側でイベントとして定義）になります。Behavior TreeのTaskノードと同様にReceiveExecuteActionでアクションを実行し終えたタイミングでFinishExecute関数を呼ぶ必要があります。これによってOperationの実行は成功、失敗、何らかの理由で中断されたかを知ることが出来ます。この結果はアクターにアタッチするHTNComponentで活用されます。（FInishExecute関数が呼ばれなかったときは「実行中」と判断されます）

enum class EOperationResult
{
    Success,
    Failed,
    Aborted,
    InProgress,
};

UCLASS(Blueprintable)
class HTNPLANNINGEXAMPLE_API UHTNOperator : public UObject
{
    GENERATED_BODY()
private:
protected:
    EOperationResult Result;
    bool bActive;
    UFUNCTION(BlueprintImplementableEvent, Category = "HTN")
        void ReceiveInitializeAction(class AAIController* OwnerController, class APawn* ControlledPawn);
    UFUNCTION(BlueprintImplementableEvent, Category = "HTN")
        void ReceiveExecuteAction(class AAIController* OwnerController, class APawn* ControlledPawn);
    UFUNCTION(BlueprintCallable, Category = "HTN")
        void FinishExecute(bool bSuccess) { Result = bSuccess ? EOperationResult::Success : EOperationResult::Failed; }
    UFUNCTION(BlueprintCallable, Category = "HTN")
        void FinishAbort() { Result = EOperationResult::Aborted; }
public:
    UHTNOperator()
    {
        Result = EOperationResult::InProgress;
    }

    void Initialize(class AAIController* OwnerController, class APawn* ControlledPawn)
    {
        bActive = true;
        Result = EOperationResult::InProgress;
        ReceiveInitializeAction(OwnerController, ControlledPawn);
    }

    void Execute(class AAIController* OwnerController, class APawn* ControlledPawn)
    {
        Result = EOperationResult::InProgress;
        ReceiveExecuteAction(OwnerController, ControlledPawn);
    }

    void Terminate() { bActive = false; }
    EOperationResult GetResult() const { return Result; }
    bool IsActivated()const { return bActive; }
};

HTNPlanner.h/cpp

HTNによるプランニングはこれらのファイルで実装されます。DomainについてはPrimitive TaskやComposite Taskを保持するだけのクラスなので説明は省略します。

UHTNPlannerはプラン生成の他に深さ優先探索で用いられるバックトラックのための機能がいくつか備わっています。
PSがプランナーの探索状態を表し、ResorePointsがバックトラックに用いるスタックです。RecordDecompositionOfTask関数で現在のプランナーの状態のコピーを取りスタックへ格納します。RestoreToLastMethodIndexAndTasksToProcess関数とRestoreToLastDecomposedTask関数はどちらもプランナーの状態を過去へと戻します。

UCLASS()
class HTNPLANNINGEXAMPLE_API UHTNPlanner : public UObject
{
    GENERATED_BODY()
private:

private:
    UPROPERTY()
        TArray<FPlannerState> RestorePoints;
    UPROPERTY()
        FPlannerState PS;

    // 復元ポイントを作成＆スタックにプッシュ
    void RecordDecompositionOfTask() { RestorePoints.Add(PS); }
    // Method IndexとTasks To Processのデータのみ復元
    void RestoreToLastMethodIndexAndTasksToProcess()
    {
        // Pop()で末尾要素を取り出して削除
        FPlannerState RestorePS = RestorePoints.Pop();
        PS.CurrentTask = RestorePS.CurrentTask;
        PS.MethodIndex = RestorePS.MethodIndex;
        PS.TasksToProcess = RestorePS.TasksToProcess;
    }
    // プランナーの状態を全て復元
    void RestoreToLastDecomposedTask() { PS = RestorePoints.Pop(); }
    // 復元できるかチェック
    bool CanRollBack() const { return RestorePoints.Num() > 0; }

protected:
public:
    void GeneratePlan(const FHTNWorldState& InitialState, const UHTNDomain* Domain, FString RootTaskName,  TArray<UHTNPrimitiveTask*>& OutPrimitiveActions);

};

プランを生成するGeneratePlan関数を見ていきます。全てのコードを一度に載っけると少々長めなので分割しながら説明します。

タスクを探索中のタスクを表すTasksToProcessから取り出した直後のコードです。こちらでは取り出したタスクがComposite Taskかをチェックします。
Composite Taskだった場合、FindSatisfiedMethod関数を実行してWorld StateとMethod Indexに応じたSubtasksがBP側にて生成されます。返り値がTRUE、つまり無事にSubtasksが生成された場合、その時点でのプランナーの状態をスタックへ保存します。ここがアクション経路の分岐点なので進んだルートの先でプランが成立しなかった場合はバックトラックによりこの時点に戻ることが出来ます。

        // 取り出したタスクは「Composite」？
        UHTNCompositeTask* const Composite = Domain->GetComposite(PS.CurrentTask);
        if (Composite)
        {
            // MethodIndexに応じたMethodを実行して分解する。
            if (Composite->FindSatisfiedMethod(PS.WorldState, PS.MethodIndex))
            {
                RecordDecompositionOfTask();
                PS.MethodIndex = 0;
                // 分解した結果を取得
                TArray<FString> Subtasks = Composite->GetSubtasks();
                // 取得したSubtasksは探索中のタスクリストの先頭に挿入される
                PS.TasksToProcess.Insert(Subtasks, 0);
            }
            // 「条件が合わずに分解出来なかった」 or 「実行するMethodが無かった」場合はバックトラックする
            else if (CanRollBack())
            {
                RestoreToLastMethodIndexAndTasksToProcess();
                PS.MethodIndex++;
                PS.TasksToProcess.Insert(PS.CurrentTask, 0);
            }
            continue;
        }

取り出したタスクがPrimitive Taskの場合、現時点でのWorld Stateで前提条件のチェックを行います。前提条件をクリアした場合、ApplyExpectedEffectsによりプランニング時にのみ適用される効果をWorld Stateへ適用し出力されるプランへと組み込まれます。前提条件をクリアできなかった場合はバックトラックが実行されます。

        // 取り出したタスクは「Primitive」？
        UHTNPrimitiveTask* const Primitive = Domain->GetPrimitive(PS.CurrentTask);
        if (Primitive)
        {
            // 前提条件のチェック
            if (Primitive->CheckPreconditions(PS.WorldState))
            {
                // World Stateに適用（実世界には影響しない）
                Primitive->ApplyExpectedEffects(PS.WorldState);
                // 最終的なプランに加える
                PS.FinalPrimitives.Add(Primitive);
            }
            // バックトラックします
            else if (CanRollBack())
            {
                RestoreToLastDecomposedTask();
                PS.TasksToProcess.Add(PS.CurrentTask);
            }
            continue;
        }

Composite TaskやPrimitive Taskを取り出したときの動作を繰り返し、探索中のタスクのリストであるTasksToProcessが空っぽになったら「プランが無事に生成できた」となり出力されます。

BP側

BP_Composite_ホニャララ

UHTNCompositeTaskの派生BPはかなり単純で使用するMethodのクラスとタスク名を指定するだけです。

BP_Primitive_ホニャララ

UHTNPrimitiveTaskの派生BPでは実際の振る舞いを定義したOperatorクラス、期待される効果であるExpected Effects、タスク名、実世界に適用するEffectsを定義しています。

BP_Primitive_DropOreでは条件を用いてWorld Stateの値を設定しています。

BP_Operator_ホニャララ

以下の図はBP_Operator_MoveToでの処理です。名前が表す通りAIの移動処理を実装しています。
Receive Execute Actionでは移動処理を実行していますが目的に到達する前に次のタスクへ遷移してしまわないようにFinish Executeを呼んでいません。よってこのOperatorはInProgressを返すので次のTickでもこのOperatorが呼ばれます。
Receive Initialize ActionでHTNComponentを所持するPawnの参照からイベントディスパッチャを取り出しバインドします。このイベントディスパッチャは移動が終了したときに呼び出されますのでバインドしたイベントではFinish Executeを呼び出し引数にTrueを与えます。ここで初めてこのOperatorは処理を完全に終了することが出来ます。

BP_Method_ホニャララ

以下の図はBP_Method_CorrectOreの一部を切り取ったものです。
World StateによってSubtasksに与えられる内容が異なります。Has ToolがFalseの場合は採掘道具を取得するComposite TaskがSubtasksとして与えられますがその他にもCompositeCorrectOreが指定されています。CompositeCorrectOreはBP_Method_CorrectOreを持つBP_Composite_CorrectOreのことですのでこれは再帰を意味しています。

図では枠で囲まれて右上に数字が書かれていますが、これはSubtasksに分解される順番を示しています。
Has ToolがFalseの場合はCompositePickupToolの中身が分解されPrimitive TaskであるPickupToolが出現するので、このPickupToolのExpected Effectsを適用します。CompositeCorrectOreがあるので再びCompositeCorrectOreが分解されますが、今度はHas ToolがTrueになっているので一段下のHas OreがFalseの場合の分解に移ります。

以下の図はBP_Method_CorrectOreの全分解ルートを示したものです。

HTNのいいところ

プロジェクトの説明をひと通り終えたところでHTNの利点を紹介します。

  • 直感的な記述が可能

    • 大きなタスクを分解して小さなタスクの集合とする考えは人間にとっても非常に自然で馴染み深い意思決定方法。
    • Behavior Treeと比べるとAIの行動についての表現力は高いと言える。

  • 実装は結構シンプル

    • HTNプランニングシステム自体はそれほど複雑な作りではないので組み込みやすい。

  • 実行速度が早い

    • 急激な環境の変化が無い場合は一度のプラン生成をするだけなので意思決定時の負荷は低いと言える。
    • プランニング自体もソートを用いるA＊アルゴリズムと比べると処理速度が早い。（もちろんComposite Taskの複雑さによる）

おわりに

UE4アドカレ「勉強してみましたシリーズ」最終回でした。
HTNは思っていた以上に実装しやすくGOAPと比べると直感的にAIの振る舞いを記述出来るのでサンプル作成は結構楽しかったです。ですがUE4にビルトインされているBehavior Treeと比べるとグラフィカルなツールが無いので全体の見通しは少し悪いですね。あとデバッグもしづらいです。
しかしプレイヤーに反応するだけのAIはもう古い！ゲームAIへのプランニング技術の導入で解説されているようにHTNプランニングによって生成されたプランをBehavior Treeとして出力する方法もあるようです。これならグラフィカルなツールが無い＆デバッグしづらい問題も一気に解決できそうな気がします。

余談：UE4にはHTNの公式プラグインがあるよ

UE4には標準でHTNを実装したプラグインが備わっています。
Epic GamesのAI Tech LeadのMieszko Zielinskiさんのツイートでは「フォートナイト：世界を救え」や「Paragon」でも使われたようです。

公式プラグイン版HTNですが
C:\Program Files\Epic Games\UE_バージョン名\Engine\Plugins\AI\HTNPlanner
にあります。
UE4.23.1をインストール自分の環境では
C:\Program Files\Epic Games\UE_4.23\Engine\Plugins\AI\HTNPlanner
にありました。

しかし上記にあるHTNプラグインはHTNの実装は確認出来ますが使い方については特に書かれていません。GitHubにてダウンロードできるUE4のソースコード内ではHTNプラグインの自動化テストが記述されているのでそちらからある程度使い方について見当が付くと思います。
GitHub上では
リリース版ブランチ/Engine/Plugins/AI/HTNPlanner/Source/HTNTestSuite/Private/HTNTest.cpp
にて自動化テストが記述されています。

もしクローンしたUE4をお持ちの場合UE4 VisualStudioを使ってエンジンをデバッグするを参考にエンジンをデバッグ出来る状態にしたプロジェクトをC++テンプレートで作成します。上記の自動化テストが記述されたファイルのどこかにブレークポイントを配置しPluginの
「Built-In -> AI -> HTN Plunner」「Built-In -> Testing -> EditorTests」
を有効にします。続いてSession FrontendのAutomationタブを開きHTNの自動化テストを実行すればブレークポイントで停止するので自由にステップ実行で処理を確認することが出来ます。

参考資料

18
15
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
18
15