ご無沙汰しております。ちょびえです。前回の私の記事は「Electronでゲームの設定ツール作ってみた」でしたね。
あれからElectronは幾度かversion upしておりますが、安定して使えているので程よくつかえるツール環境だなぁ、なんて思ってたりします。

はてさて、今日はAIの話。はじめての階層化型タスクネットワークということで、Hierarchical Task Network略してHTNについて書いてみたいと思います。

本記事ではArtificial Intelligenceの中でもプランニング（意思決定）に使われる仕組みのお話です。

階層型タスクネットワークの概念（ざっくり）

階層化型タスクネットワークはざっくりいうと既知の問題解決のための行動の定義を領域ごとに細分化したグループを用い、特定問題を解決するため集合を定義します。
そこから条件にあったプランを返していく、というのが大まかな流れです。

Web系の人にはChefのBookやRecipeだったり、ワークフローエンジンみたいなもんだと思ってもらえれば、うーん、そこまで大きくは間違ってないかと。

あくまで既知の問題をどうやって解決する、というルールベースのプランニングAIです。

HTNを構成する要素

ページ下部の参考にあるExploring HTN Planners through Example：Troy Humphreysの説明を使い、HTNを構成する要素について書いてみます。

• World: Blackboardみたいなもん。計画をすすめる上で変更されていきます。
• Domain: 特定領域の知識表現を束ねたもの。CompoundTask(この場合RootTaskと呼びます)の集合を持ちます。
• CompoundTask： Methodの集合をもちます。
• Method: CompoundTaskやPrimtiveTaskの集合を持ちます。
• PrimitveTask: Operatorの集合を持ちます。
• Operator: 実際の処理を行う単一のActionです。

設計思想によって多少変わったりはしますが大まかにはこのような分割です。

タスクの集合を条件に照らし合わせてアクションプランを探していくのは階層型プランニングと同様ですが、最終結果のプランをPlanner制約によって順序を「いい感じ」に変更していくというのがHTNの特色みたいです。
各種ノードには前提条件や事後効果などをもたせるといろいろ塩梅が良いです。

大まかなプランニングの流れとしてはPlannerは上位ノードから条件にマッチしたノードの事前効果をWorldに適用しつつ深さ優先探索していき最後のノードまで処理を行ってマッチしたプランを返します。各ノードを通る際にWorldの状態とタスクの事前条件を判定して通過できれば事後効果をWorldに適用していきシミュレーションを進めます。

基本的にはプランニングをするだけなので、実行するのは別の処理になります。
（遅延評価などを入れたい場合はタスクなどにそういった情報を仕込んでいったりします）

という感じで、ゲームAIにはよくある構成なので実装に関してとっつきやすいと思います。

タスクの再順列化

階層型プランニングの一番の理解が難しい所がタスクの再順列化（ReOrder）です。

おそらく殆どのゲーム向け実装ではきっと簡略化されていると思います。そんな都合もあり、解釈が難しい（すくなくともぼくには）
（というかゲームで使われるAIという都合上、AIデザイナが指定した順序で動いてくれたほうが都合が良いという気が。）

再順列化については、実際のゲームで考えるよりも、馴染みのある事象、そうですね、今回は味噌汁づくりで考えてみたいと思います。

それでは、味噌汁を作る上での作業単位で洗い出しを行います。
色々作り方に突っ込みどころはあるかと思いますが、説明という事でご容赦いただければ。
Methodは一つのみとして省略しています。

テキストで前提条件、事後効果も合わせて書いてみます。（今回の味噌汁づくりでは、場合分けなどはないので、あまり効果はありませんが）

調理ドメイン☆味噌汁をつくる

と、まぁこんなところでしょうか。
前提条件はタスクを実行するための制約。
（豆腐の準備ができていないのに鍋にいれられないのでそういった制約をつけていきます）
事後効果はタスクをやったことで発生する効果としておきます。
（豆腐切ったら豆腐準備オッケー、みたいな）

今回は特に場合分けがないので素直にタスクを出会った順でもっていけばプランの完成です。
（雑に場合分け増やすなら時間がなければインスタント味噌汁にするタスクを追加、時間があればほどよい味噌汁にする、みたいな感じになるかと）

図の左から順番にやっていけばたしかに味噌汁作れそうですね。

とはいえ、この順序は味噌汁を作れるだけであって工程にはまだ最適化の余地がありそうです。沸騰待つ間にまったりしているのも時間の無駄です。
それではタスクの再順列化を考えてみましょう。

今回は人の手で最順列化をやるので多少あいまいではありますが、味噌汁づくりの経験をかみしつつ、前提条件が満たせるように適当に組み替えてみました。
再順列の流れは基本的には前提条件を満たしているものをやれるならやってしまう、と思っておけばよいと思います。（もちろん再順列制約、並列化制約によって変わります）
このような順序の仕組みを半順序プランニングと呼ぶそうです。
（こういう再順列するには、作業に必要とされる時間や効用の評価、作業中暇を持て余すか、といったメタ情報が必要になりますがHTN自体とはまた話がちょっと変わってくるので割愛します）

出来上がったプランを見る限りでは火つけてる間に具材の準備をしているので全体としての時間は減っていそうな気がしますね。

こんな具合にプランナーの制約や実装によって再順列化の詳細は変わってきます。

何をどの程度解きたいかでヒントの量を調整したり、メタデータを調整してプロダクトにあったものを作っていけばいいかとおもいます。

まとめ

人間は経験と環境から工程を最適化できますが、どうしても中～大規模の工程最適化は難しくなってしまいます。階層型タスクネットワークが使えるとこういった処理が半機械的にできるのが良いと思います。
HTN自体は階層型FSMともみなせるので、BehaviourTreeとやれることは似通っていますが、どちらも得手不得手あるので目的にあった方を使うのが良いです。
（今回の例のような味噌汁づくりの工程を再順列する、みたいなのはBehaviourTree無理ですしね。）

ぼく自身もまだ階層型タスクネットワークは全て理解しきれていないので間違っているところなどがあればご指摘いただけると幸いです。
（自分たちのゲーム向けに簡略/都合の良い解釈してつくるのであってるか、といわれるとそんなに自信なかったり。まーまー動いてくれればおっけー！）

今回はHTN Plannerが得意とするビルド系のプランニングで解説しましたが勿論キャラクターAIなどでも有用で目的を持った行動をさせやすくなります。

とまぁ、AIの意思決定手法は数あれど、解決したい問題に対して違うアプローチで取り組むことによってもっと簡単に量産や問題解決が出来ることがあります。
一つの手法にこだわらず、このアルゴリズムであればこういった問題を解決できる！なんて考えていくのは楽しいですね。

おわりに、AI情報をわかりやすく資料として残してくださった皆様に感謝を申し上げます。

ではでは、たのしいゲーム開発を

参考

• 迷路を解くＡＩを使ってゲームを作る （ゲームＡＩ連続セミナー第３回付録Ｉ）：三宅 陽一郎
• GDC における海外のゲーム関連技術についての調査：三宅 陽一郎
• 人工知能の作り方 ――「おもしろい」ゲームAIはいかにして動くのか：三宅 陽一郎
• 「00年代から10年代へゲームＡＩとプロシージャル手法の進化」：三宅 陽一郎
• プレイヤーに反応するだけのAIはもう古い！ゲームAIへのプランニング技術の導入：長谷 洋平
• Exploring HTN Planners through Example：Troy Humphreys