この記事は、 LINE Engineering Blog 「夏休みの自由研究 -Summer Homework-」 の 15 日目の記事です。
私は夏休みの宿題を最後の週に慌ててやる派でした。@overlastです。
小学生のうちに夏休みの序盤に宿題をすべて終わらせる大切さを実感する必要があったな、と後悔しきれない後悔をしております。
さて。私は Clova センターという部署に所属しており、Clova を構成するシステムのうち NLU(Natural Language Understanding / 自然言語理解)と呼ばれるパートに関するサーバーサイドの開発をしています。
先日、三宅陽一郎さんと対談する機会を頂きまして、その対談中に考えていたのですが、ゲーム業界においてキャラクター AI などを作成する用途で頻繁に使われている Behavior Tree(ビヘイビアツリー)というモデルを私は一回も使ったことが無かったんです。
話しているうちに「これは良い機会だな〜」と思いましたので Behavior Tree 自体や既存実装の使用感を確認し、夏休みの宿題としてまとめてみることにしました。
Behavior Tree について
まずは Wikipedia を見てみる
手始めにWikipediaでBehavior Treeに関するページを読んでみましょう。
すると、冒頭から "Behavior trees are a formal, graphical modeling language .. " と書いてあり、「言語? えっ、Behavior Tree ってデータ構造かモデルじゃないの?」という気持ちになれます。これはかなり焦りました。
戸惑いつつ更に読むと、Behavior Tree(AI、ロボティクスと制御)はコチラ、と曖昧性解消のためのリンクが、ページの冒頭にあったので、慌ててそちらを開いて読み始めると "A Behavior Tree (BT) is a mathematical model of plan execution ..." と書いてあります。
よかった。今度はモデルです。うっかり気付かないで読んでいたら、別の Behavior Tree を使おうとして奮闘していたかもしれません。危ない。
Behavior Tree の概要まとめ
モデルとしての Behavior Tree の解説は、本気できっちり書くととても長くなり辛いので、以下に端的な理解に必要な要素を箇条書きでまとめます。
- AI分野においてReactive Planning から発生
- 2004に発売された Halo 2 はこの時期に Reactive Planning を導入したゲームのひとつ
- ゲーム制作におけるAIを効率よく実装するために実用例が豊富
- 挙動(Behavior)を木構造で記述
- ひとまとまりのタスクが部分木になっている
- サブタスク、サブツリーやブロックと呼ばれることがある
- 木を構成するための節が大まかに3タイプあり、以下のように分類できる
- root node: 根
- control flow node: 根でも葉でもない
- execution node: 葉ノード。タスクとも呼ばれる
- 評価時に各nodeは深さ優先探索される
- 探索した結果として子ノードから親ノードに状態が返ってくる
- Success: 実行成功
- Failure: 実行失敗
- Running(Continue): 実行中。次回にRunningを返したノードが再度呼ばれる
- すべてのノードには評価可能かを示すactive/inactive状態を設定できる
というような感じです。
Behavior Tree を使って AI 的な動作を実現するためには、control flow node と execution node の役割と、それらをどう使えば良いかを調べれば良さそうです。
control flow node
各 control flow node の役割はそのノード以下の部分木(ブランチと呼ばれる)によって表現される挙動(サブタスク)を制御することです。
既存の実装を観察すると、異なる実現方法や命名方法がありますが、あらゆる実装に共通して存在しているノードは以下の2種類です。
Selector
子ノードのうちいずれか1つを実行するためのノードです。評価を開始すると Selector の子ノードを左から右(優先度が高い方から低い方)へ順に深さ優先探索で評価します。
Selector の子ノードのうちどれかが Success か Running を返した場合、Selector は即座に Success か Running を親ノードに返します。Selector のすべての子ノードがfailureを返した場合、Selector も failure を親ノードに返します。
Sequence
子ノードを順番に実行するためのノードです。評価を開始すると Sequence の子ノードを左から右(優先度が高い方から低い方)へ順に深さ優先探索で評価します。
Sequence の子ノードのうちどれかが Failure か Running を返した場合、 Selector は即座に Failure か Running を親ノードに返します。Selector のすべての子ノードが Success を返した場合、Selector も Success を親ノード返します。
Composite
上記の2種類のノードに共通する特徴は、ブランチの Root になることです。
またデザインパターンの Composite パターン的な動作を実現するので、Composite とタイプ分けされることがあります。
実用上は Selector と Sequence のそれぞれにランダム性や確率の導入が必要と感じましたし、Selector と Sequence 以外にも、部分木を Behavior Tree として並列評価(親のBehavior Treeが終了したら強制終了)するための Parallel 処理系のノードや、過去に実行していない子ノードのみを評価するためのノードが必要になるでしょう。
しかしこれだけでは、if 文や while 文などのプログラミング言語でよく使う制御文を control flow node として表現できません。
Decorator
制御文を実現するためのノードはデザインパターンの Decorator パターン的な動作を実現するので、Decorator とタイプ分けされることがあります。Call や Condition としてタイプ分けされることもあります。
以下に、Behavior Tree の既存実装で実現されている、または実現できる代表的な条件式を以下に挙げます。
While(Conditional Loop)
条件との合致を評価する関数が True を返す限り、子ノードの評価を繰り返す。条件との合致を示す関数が Failure を返したら、While も Failure を親ノードに返します。
If
条件との合致を評価する関数が True を戻した場合、現在アクティブな子ノードを呼び出してその結果を返します。 それ以外の場合は、子ノードを呼び出すことなく Failure を親ノードに返します。
Repeat(Loop)
子ノードを評価した回数があらかじめ設定した回数に達したら、Success を親ノードに返します。それ以外は Running を親ノードに返します。
その他のノード
上記があれば if文、while文、for文 を実現できますけど、その他にも処理の中断や割り込みをするためのノードも欲しいです。
さらに各ノードの実行結果を必要に応じて記憶する Behavior Tree 内でノードをまたいで共有できるメモリ領域と、そのメモリ領域に格納されたデータを使った制御を実現するノードは、アクションの結果を活用する手段として必要になります。
execution node
execution node はアクションとも呼ばれます。アクションは葉ノードとして書き、Behavior Tree 外に実装された具体的な関数を呼びます。
その関数の戻り値に基づいて実行結果の状態(Success / Failure / ...)を判定して、その戻り値を親ノードに返します。
具体例から Behavior Tree に変換してみる
ここまで説明してきたを使って、「所持金と気分に応じて周囲の自販機で飲み物を買う」という挙動を Behavior Tree で書いた結果を図1に示します。
この Behavior Tree を評価する関数は、入力される引数に所持金の情報が含まれている必要があります。
所持金が0円と300円のときにどの様に挙動が変わるかを、簡単に確認してみます。
場合1: 所持金が0円のとき => ドリンク購入失敗
まずは所持金0円の場合の各Stepにおける挙動を以下に書き、結果を図2でも示します。
- Step1: Rootからスタート
- Step2: Sequence に遷移。以降、深さ優先探索を継続する
- Step3: Action1 に遷移。椅子から立ち上がることに成功し Success を返す
- Step4: If の Decorator に遷移。所持金が0なので Failure を返す
- Step5: Sequence に再び遷移。Failure が返ってきたので、探索を終わり Failure を返す
- Step6: Behavior Tree の更新結果として Failure を返して、終了
Step5でサブタスクの逐次実行に失敗したSequenceが探索を終わってしましいました。お金がないのでは自販機に行く意味がありません。では所持金が300のときはどうでしょう。
場合2: 所持金が300円のとき => ドリンク購入成功
次に所持金300円の場合の各Stepにおける挙動を以下に書き、結果を図3でも示します。
- Step1: Rootからスタート
- Step2: Sequence に遷移。以降、深さ優先探索を継続する
- Step3: Action1 に遷移。椅子から立ち上がることに成功し Successを返す
- Step4: If の Decorator に遷移。所持金が300なので If の Decorator に設定たれた条件を満たした
- Step5: Action2 に遷移。自販機に移動することに成功し Successを返す
- Step6: If の Decorator に以下の再び遷移。子ノードのstateである Success を返す
- Step7: ランダムな Selector に遷移。いずれかの子ノードに遷移する
- Step8: Action4 にたまたま遷移。水を買うことに成功し Successを返す
- Step9: Selector に遷移。Successが返ってきたので探索を終わり Success を返す
- Step10: Action5 に遷移。自席に移動することに成功し Success を返す
- Step11: Action6 に遷移。自席に移動することに成功し Successを返す
- Step12: Sequence に遷移。すべての子ノードが Success を返したので、Success を返す
- Step13: Root に遷移。Behavior Treeの更新結果として Success を返して、終了
かなり省略しているのですが、それでも所持金0のときに比べて倍以上のStep数です。
この例では Selector のサブタスクの選択方法をランダムにする必然性は無いのですが、実際にAIの行動を実行のたびに変化させるためには、優先度順の以外の試行方法が必要そうですね。
Behavior Tree のゲームAIへの応用
ゲーム上の AI 実装はこのような Behavior Tree を tick と呼ばれる更新処理が走るたびに評価されます。その点を考慮し滑らかに動作する様に、また選択される挙動が不必要に収束しない様に Behavior Tree の構成を工夫する必要があります。
たとえば図1の例の様に素朴な Behavior Tree だと、何回かの更新処理によってお金を使い果たした後、更新処理のたびに所持金0の場合と同じ動作をする様になり、以降は自席の椅子の前で立っているだけになります。
ゲームだと NPC や敵キャラなどが滑らかで知的に動いている様に見せたいので、更新処理は1〜数フレームごとに行う必要があり、更新頻度がとても頻繁です。そのため Running 状態が欠かせません。
Behavior Tree のライブラリはグラフィカルな開発ツールが充実していて驚きます。いろいろな理由がありそうですけど、ゲーム業界で使われているライブラリは開発効率がとても大切なので、視覚的で扱いやすい開発ツールが充実しやすいのかもしれません。
Behavior Tree の対話システムへの応用について
他方で多くの対話システムでは、AIは会話が1言進むごとにBehavior Treeを更新できたら、一旦は十分です。サーバサイドで Behavior Tree が暗黙的に頻繁に更新されると、人間の話者は AI の発言についていけなくなってしまうでしょう。
また、対話中にタスクがずっと Running 状態になってしまうと、会話が止まってしまうので、ある程度の時間が経過した Running 状態のタスクは停止する必要がありそうです。
私もまだチュートリアルをベースに簡単な Behavior Tree を実装した程度なので、それを公開しても単なる自己満足になってしまいます。参考文献にあるチュートリアルをお試しください。
今回ご紹介した Behavior Tree は仕事で活用できるはずなので、今後また続きをご紹介できると思っていますし、開発成果の一部は OSS として公開したいと思っています。
弊社エンジニアによる様々な夏休みの宿題をご覧いただき、どうもありがとうございました(アーカイブはこちらからご覧ください)。
そして、この記事が最後になります。お楽しみ頂けましたか? もう夏も終盤ですね。個人的に今年の夏は時間の経過が速すぎてとても残念です。なんとかかんとかして、諸々やり残しが無いように秋を迎えたいものです。
そして、私達は今年の12月には LINE Advent Calendar 2018 を公開できる(はず)と思いますので、また冬に逢いましょう。ではでは。
参考文献
- GDC 2005 における Halo 2 の AI に関する解説記事
- いろいろな呼び方のひとつに "a behavior tree" というフレーズが出てくる
- UNREAL ENGINE の Behavior Tree のチュートリアル
- Unity の Behavior Tree のマニュアル
- The Behavior Tree Starter Kit, Alex J. Champandard, Philip Dunstan, Game AI Pro, 2013
- aigamedev/btsk(Behavior Tree Starter Kit in C++)
- miccol/Behavior Trees Library in C++
- arvidsson/BrainTree - A C++ behavior tree header-only library