ビヘイビアツリーは、 コンピュータサイエンス 、ロボット工学 、制御システム 、ビデオゲームで使用される プラン 実行の数学的モデル です。有限個のタスク間の切り替えをモジュール方式で記述します。その強みは、単純なタスクの実装方法を気にすることなく、単純なタスクで構成される非常に複雑なタスクを作成できることにあります。ビヘイビアツリーは階層型ステートマシン といくつかの類似点がありますが、ビヘイビアの主要な構成要素が状態ではなくタスクであるという重要な違いがあります。人間が理解しやすいため、ビヘイビアツリーはエラーが発生しにくく、ゲーム開発者コミュニティで非常に人気があります。ビヘイビアツリーは、他のいくつかの制御アーキテクチャにも一般化できることが示されています。[ 1 ] [ 2 ]
背景 2本腕ロボットの探索および把持計画をモデル化したビヘイビアツリー 行動ベースの制御構造は、ロドニー・ブルックス が「移動ロボットのための堅牢な階層型制御システム」という論文で最初に提案しました。最初の提案では、行動のリストが互いに代替として機能することができました。その後、このアプローチは拡張され、行動のツリー状の組織に一般化され、ノンプレイヤーキャラクター （NPC）の行動をモデル化する ための強力なツールとしてゲーム業界で広く応用されています。[ 3 ] [ 4 ] [ 5 ] [ 6 ] これらは、 Halo 、Bioshock 、Spore などの有名なビデオゲームで広く使用されています。最近の研究では、 UAV 、複雑なロボット、ロボットマニピュレーション、マルチロボットシステムのためのマルチミッション制御フレームワークとして行動ツリーが提案されています。[ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] Unity（ゲームエンジン） やUnreal Engine などの汎用ゲーム環境でも扱われています（下記のリンクを参照）。
ビヘイビアツリーは、その開発パラダイムによって人気を博しました。NPCのアクションをプログラミングし、その後、リーフノードがアクション、内部ノードがNPCの意思決定を決定するツリー構造を設計する（通常はドラッグ＆ドロップ で）だけで、複雑な動作を作成できるからです。ビヘイビアツリーは視覚的に直感的で、設計、テスト、デバッグが容易であり、他の動作作成方法よりもモジュール性、拡張性、再利用性に優れています。
長年にわたり、さまざまなビヘイビアツリーの実装は、業界の要求を満たすために効率と機能の両面で改善を続け、最終的にイベント駆動型 ビヘイビアツリーへと進化しました。[ 15 ] [ 5 ]
主要概念 ビヘイビアツリーは、ノードがルート、制御フローノード、または実行ノード（タスク）に分類される有向 ツリー としてグラフィカルに表現されます。接続されたノードの各ペアについて、出力ノードは親、入力ノードは子と呼ばれます。ルートには親がなく、ちょうど1つの子があり、制御フローノードには1つの親と少なくとも1つの子があり、実行ノードには1つの親と子がありません。グラフィカルには、制御フローノードの子は、左から右の順にその下に配置されます。[ 16 ]
ビヘイビアツリーの実行は、ルートノードから始まり、ルートノードは一定の頻度で子ノードにティック信号を送信します。ティック信号は、子ノードの実行を許可する有効化信号です。ビヘイビアツリー内のノードの実行が許可されると、実行が完了していない場合は実行中、目的が達成されている場合は 成功 、それ以外の場合は失敗という ステータスを親ノードに返します。
制御フローノード 制御フローノードは、それを構成するサブタスクを制御するために使用されます。制御フローノードは、セレクタ（フォールバック）ノードまたはシーケンスノードのいずれかです。これらは、それぞれのサブタスクを順番に実行します。サブタスクが完了し、そのステータス（成功または失敗）が返されると、制御フローノードは次のサブタスクを実行するかどうかを決定します。
図1. N個のタスクからなるフォールバック構成の図解。 フォールバックノードは、失敗しない最初の子ノードを見つけて実行するために使用されます。フォールバックノードは、子ノードのいずれかが成功または実行中を返すと、すぐに成功または実行中のステータスコードを返します（図Iおよび以下の擬似コード を参照）。子ノードは、左から右へ重要度順にチェックされます。
擬似コードで表すと、フォールバック合成のアルゴリズムは次のようになります。
1 i から nまで 繰り返す 2 子ステータス ← Tick(子(i)) 3. childstatus = running の場合 4 リターン ランニング 5 else if childstatus = success 6 成功を返す 7終了 8リターン 失敗
シーケンスノード 図II．N個のタスクのシーケンス構成の図解。 シーケンスノードは、まだ成功していない最初の子ノードを見つけて実行するために使用されます。シーケンスノードは、子ノードのいずれかが失敗または実行状態を返した時点で、直ちに失敗または実行状態のステータスコードを返します（図IIおよび以下の擬似コードを参照）。子ノードは左から右の順にチェックされます。
擬似コードで表すと、シーケンス合成のアルゴリズムは次のようになります。
1 i から nまで 繰り返す 2 子ステータス ← Tick(子(i)) 3. childstatus = running の場合 4 リターン ランニング 5 else if childstatus = failure 6 リターン 失敗 7終了 8成功を返す
数学的状態空間の定義 制御理論のツールをビヘイビアツリーの分析に適用するために、それらは3タプルとして定義することができる。[ 17 ]
T 私 = { f 私 、 r 私 、 Δ t } 、 {\displaystyle T_{i}=\{f_{i},r_{i},\Delta t\},}
どこ私 ∈ N {\displaystyle i\in \mathbb {N} } f 私 : R n → R n {\displaystyle f_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}} Δ t {\displaystyle \Delta t} r 私 : R n → { R 私 、 S 私 、 F 私 } {\displaystyle r_{i}:\mathbb {R} ^{n}\rightarrow \{R_{i},S_{i},F_{i}\}} R 私 {\displaystyle R_{i}} S 私 {\displaystyle S_{i}} F 私 {\displaystyle F_{i}}
注 ：タスクとは、親も子も持たない退化したビヘイビアツリーのことです。
ビヘイビアツリーの実行 ビヘイビアツリーの実行は、以下の標準的な差分方程式によって記述されます。
x k + 1 （ t k + 1 ） = f 私 （ x k （ t k ） ） {\displaystyle x_{k+1}(t_{k+1})=f_{i}(x_{k}(t_{k}))}
t k + 1 = t k + Δ t {\displaystyle t_{k+1}=t_{k}+\Delta t}
どこk ∈ N {\displaystyle k\in \mathbb {N} } x ∈ R n {\displaystyle x\in \mathbb {R} ^{n}}
参考文献 ↑ Colledanchise, Michele; Ögren, Petter (2017). "How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees" . IEEE Transactions on Robotics . 33 (2): 372–389 . doi : 10.1109/TRO.2016.2633567 . S2CID 9518238 . ↑ コレダンチャイセ、ミケーレ。ペッター・オーグレン（2018）。 ロボット工学と AI の動作ツリー: はじめに 。 CRCプレス。 arXiv : 1709.00084 。 土井 ： 10.1201/9780429489105 。 ISBN 978-1-138-59373-2 . S2CID 27470659 . ↑ Isla, D. (2005). "Halo 2 AI における複雑性の処理" . ゲーム開発者会議 (Vol. 12) . 2012 年 5 月 11 日の オリジナル からアーカイブ済み。 ↑ Isla, D. (2008). Halo 3 - より良い戦いの構築 。 1 2 Agis, Ramiro A.; Gottifredi, Sebastian; García, Alejandro J. (2020). "ビデオゲームにおける非プレイヤーマルチエージェントの協調を促進するためのイベント駆動型ビヘイビアツリー拡張" (PDF) . Expert Systems with Applications . 155 (1) 113457. doi : 10.1016/j.eswa.2020.113457 . S2CID 218995637 . ↑ Lim, CU; Baumgarten, R.; Colton, S. (2010). "商用ゲーム DEFCON のための進化するビヘイビアツリー" (PDF) . 進化計算の応用 . コンピュータサイエンス講義ノート. 第 6024 巻. ベルリン: Springer. pp. 100–110 . doi : 10.1007/978-3-642-12239-2_11 . ISBN 978-3-642-12238-5 2020年7月14日にオリジナル（PDF） からアーカイブされました。2020年7月14日 に取得 。↑ Ögren, Petter (2012). 「コンピュータゲームのビヘイビアツリーを使用したUAV制御システムのモジュール性の向上」 (PDF) . AIAA誘導・航法・制御会議、ミネソタ州ミネアポリス . pp. 13–16 . ↑ Colledanchise, Michele; Marzinotto, Alejandro; Ögren, Petter (2014). "確率的挙動ツリーの性能分析" (PDF) . 2014 IEEE International Conference on Robotics and Automation (ICRA) . pp. 3265–3272 . doi : 10.1109/ICRA.2014.6907328 . ISBN 978-1-4799-3685-4 . S2CID 14719083 . ↑ Marzinotto, Alejandro; Colledanchise, Michele; Smith, Christian; Ögren, Petter (2014). "Towards a Unified BTs Framework for Robot Control" (PDF) . Robotics and Automation (ICRA), 2014 IEEE International Conference on . ↑ Klöckner, Andreas. 「記述論理を用いたBTと世界とのインターフェース」 AIAA誘導・航法・制御会議、ボストン、マサチューセッツ州、2013年。 ↑ アンドレアス、クレックナー (2013)。 「UAV ミッション管理のための動作ツリー」。 GI ジャーレスタグング 。 57～ 68ページ 。 ↑ Bagnell, J. Andrew; Cavalcanti, Felipe; Cui, Lei; et al. (2012). "自律ロボット操作のための統合システム" (PDF) . Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on . IEEE. pp. 2955–2962 . doi : 10.1109/IROS.2012.6385888 . hdl : 20.500.11937/14608 . ISBN 978-1-4673-1736-8 . S2CID 419179 . ↑ ミリントン、ファンジ（2009）。ゲームの ため の人工知能 。CRC Press。ISBN 978-0-12-374731-0 。↑ Rabin, S. (2014). Game AI Pro . CRC Press. ISBN 978-1-4665-6596-8 。↑ Champandard, Alex J.; Dunstan, Philip (2012). "The Behavior Tree Starter Kit" (PDF) . Game AI Pro: Collected Wisdom of Game AI Professionals . pp. 72–92 . ↑ craft ai (2015). "BT 101 – ビヘイビアツリーの文法の基礎" . 2021年9月20日に オリジナルからアーカイブ済み 。 2021年7月28日 に取得。 ↑ Colledanchise, Michele; Ögren, Petter (2014). "How Behavior Trees Modularize Robustness and Safety in Hybrid Systems" (PDF) . In Intelligent Robots and Systems (IROS), 2014 IEEE/RSJ International Conference on . IEEE.
外部リンク ROSビヘイビアツリーライブラリ Unreal Engine 4 ビヘイビアツリーのドキュメント AIにおけるビヘイビアツリー：その仕組み ビヘイビアツリー：ロボットのためのシンプルながら強力なAI（ 2020年2月25日にWayback Machine に アーカイブ済み） ビヘイビアツリーに関するビデオ講義 
