Rust製 Behavior Treeライブラリ作ってみた
はじめに
Behavior tree というものがあります。
簡単に言うと有限状態マシン (Finite State Machine) をツリー状に拡張したものです。
ロボティクスやゲームのAIの開発に使われています。
もともとは BehaviorTreeCPP という C++ 実装があり、他の言語にもちらほら移植されています。
もちろん、筆者は Rust に移植しました。
ただ、元の実装がかなり冗長に感じたので、必要最小限の機能に削減しました。
これは rusty-behavior-tree-lite という名前で公開していますが、まだまだ実験段階なので本番では使わないでください。
この記事では rusty-behavior-tree-lite を実装するうえでの C++ との違いや、思考プロセスを記録しておこうと思います。
何の役に立つのか？
Behavior という名前のついていることからもわかるように、AI [1] の挙動の定義に非常に重宝します。
詳しい説明は BehaviorTreeCPP の公式サイト に譲りますが、状態遷移の記述にとても役に立ちます。
例えば、ドアを開くという人間にとっては簡単な作業を、ロボットにさせるにはどうしたらいいか考えてみましょう。
ロボットが考えることはこんな感じになると思います。
しかし、このロジックをどのように記述すればいいのでしょうか。普通に考えたら次のように関数が書けないかと思います。
fn run_ai(&mut self) {
self.ドアノブの位置を認識する();
self.ドアノブに手を伸ばす();
self.ドアノブを握る();
while !self.ロックが解除される() {
self.ドアノブを回す();
}
self.ドアノブを引く();
}
しかし普通のコードではこのように書けません。なぜならば関数は一度呼び出されればリターンするまで他のことはできないからです。ロボットは他にもセンサーの情報を読み取ったりモーターを制御したりさまざまな仕事を同時にしています。この一連の作業が終わるまで他のことが全くできないのでは、ロボットとして機能しません。
このように「他の仕事を合間にする」ようにロジックを記述するのによく使われるのが有限状態マシン [2] です。
上記のロジックは下記のように書き換えられます。
enum State {
ドアノブの位置を認識する,
ドアノブに手を伸ばす,
ドアノブを握る,
ドアノブを回す,
ドアノブを引く,
}
fn run_ai(&mut self) {
use State::*;
match self.state {
ドアノブの位置を認識する => self.state = ドアノブに手を伸ばす,
ドアノブに手を伸ばす => self.state = ドアノブを握る,
ドアノブを握る => self.state = ドアノブを回す,
ドアノブを回す => {
if self.ロックが解除される() {
self.state = ドアノブを引く;
}
}
ドアノブを引く => (),
}
}
run_ai が呼び出されるたびに、「進捗」が少しずつ更新されていきます。一度にすべてを実行しなくても良いので、呼び出し元では他の仕事も平行に進めることができます。
しかし、これではめちゃくちゃ読みにくいですね。これを助けるためにさまざまな手法が考案されていますが、その一つがのが Behavior tree です。独自の状態遷移ルールを記述する XML フォーマットを使ってロジックの記述を楽にしています。さらにツリー状に状態を構造化することもでき、複雑なロジックになっても保守性が保てます。
少し脱線になりますが、このように「他の仕事も並行に進める」ことができる性質を並行処理 (concurrency) や非同期(asynchronous) [3] といい、 Rust にも async/await というキーワードでサポートされています。しかし、 async/await は主に I/O 非同期 API のために使われます。 I/O というのはディスクやネットワークソケットなどの読み書きに時間のかかるデバイスです。より一般に並行処理を記述するロジックをコルーチン (coroutine) と呼びます。
コルーチンは軽量版スレッドとでも言うべきもので、 OS のスレッドリソースを使わなくても実装できることと、実際には並列 (parallel) ではないのでスレッド間の同期処理が必要ないことが利点です。
並行性 (Concurrency) と並列性 (Parallelism) は、しばしば誤解の元になる用語です。
これをちゃんと解説しようとするとそれだけで記事になりそうなので、ここでは前に描いた絵でなんとなくイメージだけ伝えます。
- 並行性 (Concurrency) は、多数の仕事を同時にする性質です。
- 並列性 (Parallelism) は、複数の CPU やコアが同時に処理を行う性質です。
コルーチンの最大の欠点は、普通のコンピュータでは直接記述できないことです。過去には Windows が Fiber という名で実装を試みたりしたことがありますが、うまくいきませんでした。 ネイティブコンパイル言語ではコルーチンのサポートは非常に困難で、 Rust でも一般的なコルーチンはまだ使用できません(async/awaitやgeneratorなどの特別な形でのコルーチンのサポートは徐々に広がっています)。 C++20 ではコルーチンの構文は定義されましたが、なんとランタイムは自分で実装するか、ライブラリを使わないといけません。
そんなわけで、有限状態マシンや Behavior tree はまだ使われているわけです。
Rust 特有の困難 - 借用チェッカー
Behavior tree の特徴の一つは、ロジック記述言語を使って実行時にツリーを構築することができることです。つまり再コンパイルなしにある程度の挙動のカスタマイズができます。
これは有限状態マシンの代わりという意味ではそれほど本質的な特徴ではなく、どちらかというと副産物ですが、便利であることは確かです。
動的な記述言語を静的にするのは簡単です(逆はそうではないですが)。 Rust では外部ファイルを文字列としてソースコードに埋め込むことができます。
include_str!("test_global_nav.txt")
しかし、動的であるということの代償は、コード上での静的チェックと相性が悪いということです。
まず明らかなのが黒板変数 (blackboard variable) が動的型になるということです。
Behavior tree には黒板変数という概念があり、これは埋め込む C++ や Rust の変数とは異なり、 Behavior tree のインスタンス自体が管理する変数です。
ユーザがどんな型を黒板変数に保管したいか、ライブラリでは事前にはわからないので、 std::any::Any で型消去することになります。
すなわち、 downcast や downcast_ref が具体的な型を取得するのに必要になります。
実際には Context がジェネリックメソッドを ctx.get::<YourType>("name") のような構文で取得できるようにしています。
より具体的には以下のような感じです。
struct PrintStringNode;
impl BehaviorNode for PrintStringNode {
fn provided_ports(&self) -> Vec<PortSpec> {
vec![PortSpec::new_in("input")]
}
fn tick(&mut self, _arg: BehaviorCallback, ctx: &mut Context) -> BehaviorResult {
static INPUT: Lazy<Symbol> = Lazy::new(|| "input".into());
if let Some(s) = ctx.get::<String>(*INPUT) {
println!("PrintStringNode: {}", s);
} else {
println!("PrintStringNode: didn't get string");
}
BehaviorResult::Success
}
}
ここまでの話は C++ にも当てはまりますが、 Rust の場合はもう一段階厄介な問題があります。
Behavior tree を使う時、外部との変数のやり取りをしなくて済むということはほとんどなく、ノードの中から外部環境への何らかの作用が必要になることが多いです。前述の例では、ロボットのセンサーの信号を読み取ったり、アクチュエータの駆動信号を送ったり、などです。
最初は、 Context のメンバにそのための "user pointer" のようなものを置こうとしたのですが、 std::any::Any は 'static ライフタイムに拘束されているということが最大の問題でした。
外部のオブジェクトは、動的に生成されることが多いですので(たとえがゲームの敵AIを考えてみると、敵は倒されれば消滅し、また新たにスポーンしますので、 'static にはなりえません)、このライフタイム拘束だとほとんど何も渡せません。
他にも生ポインタを unsafe でやりくりしたり、 mpsc で通信したりする策も考えられますが、同じプロセス、同じスレッド内でのデータの受け渡しでそんなものを使うのも "軽量" を謳うライブラリとしてはいまいちです。
結局、解決策としては、 tick メソッドに外部との通信用のコールバックを渡すことにしました。
tick メソッドの第２引数の型は次のような型エイリアスです。
pub type BehaviorCallback<'a> = &'a mut dyn FnMut(&dyn Any) -> Option<Box<dyn Any>>;
つまり Any を受け取り、 Box<dyn Any> を返す関数オブジェクトです。
返り値が Boxed なのは、 dyn Any のサイズがコンパイル時にはわからないからです。
関数の引数のライフタイムは、暗黙に関数の実行期間よりも長いことが強制されますので、関数から見たら 'static です。つまり Any も渡せることになります。
具体的な使い方は、例えば tick されるたびに環境に bool 変数を送り、それを Vec<bool> に追加していくようなことをするなら、まずは結果を保持する変数 res とそれに追加するクロージャ append を次のように定義します。
let mut res = vec![];
let mut append = |v: &dyn std::any::Any| {
res.push(*v.downcast_ref::<bool>().unwrap());
None
};
コールバックに bool を渡す Behavior node を次のように定義します。
struct Append<const V: bool = true>;
impl<const V: bool> BehaviorNode for Append<V> {
fn tick(&mut self, arg: BehaviorCallback, _ctx: &mut Context) -> BehaviorResult {
arg(&V);
BehaviorResult::Success
}
}
ツリーに Append ノードを追加します。
let mut tree = SequenceNode::default();
tree.add_child(Box::new(Append::<true>), BBMap::new())
.unwrap();
tree.add_child(Box::new(Append::<false>), BBMap::new())
.unwrap();
そして tick を append を引数に指定して呼び出します。
tree.tick(&mut append, &mut Context::default());
すると結果が res に追加されます。
assert_eq!(res, vec![true, false]);
実際のコードでは、全てのノードが同じコールバックを呼び出すので、それを区別するためにイベントごとの型を定義して downcast_ref で識別するような形になります。
let mut process = |f: &dyn std::any::Any| {
if let Some(com) = f.downcast_ref::<DriveCommand>() {
command = Some(Command::Drive(*com));
return MotionResult::as_drive(&self.last_motion_result);
} else if let Some(com) = f.downcast_ref::<MoveToCommand>() {
command = Some(Command::MoveTo(*com));
return MotionResult::as_move_to(&self.last_motion_result);
} else if f.downcast_ref::<FindEnemyCommand>().is_some() {
// println!("FindEnemy process");
self.find_enemy(entities)
} else if f.downcast_ref::<HasPathNode>().is_some() {
return Some(Box::new(!self.path.is_empty()));
} else if f.downcast_ref::<ClearPathNode>().is_some() {
let ret = !self.path.is_empty();
self.path.clear();
return Some(Box::new(ret));
} else if f.downcast_ref::<TargetPosCommand>().is_some() {
...
};
tree.0.tick(&mut process, &mut ctx);
あまり美しくは見えないですが、実際に使ってみるとそれほど悪くはありません。特に型チェックが常に行われているので、少なくとも間違うことは稀です。
またコールバックはただの関数呼び出しなのでオーバーヘッドも少ないです。返り値がある場合は Box に包まなければいけないのが少し気になりますが、必要なければ None を返せばヒープメモリは使いません。
ロジック記述言語
rusty-behavior-tree-lite は、軽量化を目標に掲げています。
BehaviorTreeCPP では、ロジックの記述に XML を使いますが、これがまた非常に冗長で人間の目に優しくないです[4]。一例をあげると以下のようなものです。
<BehaviorTree ID="main">
<IfThenElse>
<Decorator ID="Inverter">
<Condition ID="HasTarget" target="{target}"/>
</Decorator>
<Action ID="FindEnemy"/>
</IfThenElse>
<IfThenElse>
<Decorator ID="not">
<Condition ID="HasPath" has_path="{has_path}"/>
</Decorator>
<Action ID="FindPath"/>
</IfThenElse>
<IfThenElse>
<Condition ID="HasPath" has_path="{has_path}"/>
<Fallback>
<Action ID="FindPath"/>
<ReactiveSequence>
<Action ID="Move" direction="backward"/>
<Action ID="Timeout" time="20"/>
<Action ID="FindPath"/>
</ReactiveSequence>
</Fallback>
</IfThenElse>
</BehaviorTree>
同じロジックを behavior-tree-lite のフォーマットで記述すると次のようになります。
tree main = Sequence {
if (!HasTarget (target <- target)) {
FindEnemy
}
if (!HasPath (has_path <- has_path)) {
FindPath
}
if (HasPath (has_path <- has_path)) {
Fallback {
FindPath
ReactiveSequence {
Move (direction <- "backward")
Timeout (time <- "20")
FindPath
}
}
}
}
何だか、プログラミング言語っぽいですね。実際、プログラムというのはある種の有限状態マシンなので、プログラミング言語と言っても間違いではないです。
実は、コルーチンはスクリプト言語の得意とするところです。 Python や JavaScript では async/await やジェネレータはかなり早い段階でサポートされていましたが、それは実装が簡単だからです。スクリプト言語では実行ランタイムを言語設計者が提供するので、ネイティブコードのような制約を受けずにコードを状態マシンに変換することができます。というよりも、スクリプト言語のランタイムは状態マシンそのものです。
その意味では、並行処理を楽に記述することを突き詰めた結果、スクリプト言語ができてしまうことはおかしくはないです。スクリプト言語っぽいのであれば、いっそのことスクリプト言語にしてしまえ、ということで、構文は XML のような静的構造化文書よりも、思いっきりプログラミング言語に寄せています。
もう一つの設計指針が、驚き最小の原則 (Principle of least astonishment) です。
Behavior tree を使う場面では、自前でノードの実装を行うため、ユーザーは少なくとも C++ か Rust のコードに慣れていると考えられます。そのようなプログラマが見て一目でおおよそ何をやっているのか理解できるような構文が望ましいところです。
例えば、何らかの条件 Condition が満たされたときにだけ実行するアクション Action があったとします。これを純粋な Behavior tree で実装すると次のようになります。
Sequence {
Condition
Action
}
しかし、このような「慣用句」は慣れていないと読みにくくて仕方がありません。その点、次のコードはどうでしょうか。
if (Condition) {
Action
}
この意味がわからないプログラマはいないでしょう。
この構文は実は構文糖衣で、実体としては、組み込みのノード if を使った次のようなツリーが構築され、実行モデルは Behavior tree に変わりありません。
if {
Condition
Then
Else
}
せっかくなのでプログラミング言語らしく構文ハイライトの VSCode 拡張も作りました。
他の言語での実装例 - JavaScript の例
ちなみに、 JavaScript 製 Behavior tree 実装である Behavior Tree の記述言語はこんな構文です。
?
| ->
| | (Ghost Close)
| | ?
| | | ->
| | | | !(Ghost Scared)
| | | | (Power Pill Close)
| | | | [Eat Power Pill]
| | | ->
| | | | (Ghost Scared)
| | | | [Chase Ghost]
| | | [Avoid Ghost]
| =1
| | [Eat Pills]
| | [Eat Fruit]
……正直、あまり読みやすいとは言えません。まず、 SequenceNode や FallbackNode を示すのに ? や -> といったシンボルを使っていて、これは behavior tree の原論文の公式シンボルではあるのですが、覚えられる人はいるのでしょうか。
そして、ツリーの子ノードをネストするのに縦棒 (|) を使ってインデントしているのですが、これってネストのレベルが増えたら書きにくくないですか？
また、原論文には Condition node と Action node という区別があり、このライブラリでもノード名を囲む () か [] で区別しているのですが、私にはこれを構文レベルで区別する意味が分かりません。個人的には「関数」と「手続き」の区別と同じぐらい意味がないと思います。
behavior-tree-lite では子ノードのネストは波括弧 {} を使うことにしています。これはほとんどのエディタでプログラミング言語の構文のグループ化に使われると認識され、自動インデントや対応する括弧のハイライトの機能が使えるからです。
構文解析の実装方法
このフォーマットの構文解析には nom を使っています。
nom はパーサコンビネータライブラリで、再帰下降パーサを効率的に書くことができます。
実装は単なる再帰下降パーサなので、他の言語でも実装できるはずです。
この言語はチューリング完全か？
これは非常に興味深い疑問です。おそらく答えは、実装するノードによるが、この言語自体ではチューリング完全にはならない……と思います。多分。
チューリング完全であることの証明は、万能チューリングマシンでしか実装できないアルゴリズムを一つでも実装すればできますが、チューリング完全でないことの証明は、どんなに頑張ってもそのような実装ができないことを示さなくてはいけないので、悪魔の証明になります。
この言語には条件分岐 if や繰り返し Repeat, Retry といった構造がありますが、数値演算やスタックなどのデータ構造を構築するための機能は、ノードで提供しない限りないので、チューリングマシンに相当しないと思うのですが、あまり自信はありません。
ひとつ面白いのは、この言語では再帰呼び出しができないということです。
この言語ではサブツリーという概念があり (BehaviorTreeCPPにも存在する概念です)、サブルーチンのような役割を担っているのですが、自分自身や、自分自身を含むサブツリーをノードとして持つことはできません。つまり次のようなコードはエラーになります (LessThan や Decrement といったノードは提供すると仮定します)。
tree main = Sequence {
recurse (n <- "10")
}
tree recurse(in n) = Sequence {
if LessThan (lhs <- "0", rhs <- n) {
Decrement (input <- n, output -> n)
recurse (n)
}
}
この理由は割愛しますが、再帰呼び出しを使ってループに相当するロジックを実装することはできないということです。
本当に役に立つのか？
本当に役に立つのかを確かめるには、ある程度の規模のプロジェクトで実際に試してみるしかありません。
というわけで、もう一つのプロジェクト、 swarm-rs で rusty-behavior-tree-lite を使っています。
このプロジェクトは複数のエージェントが自律的に行動するシミュレーションゲームです。それぞれのエージェントが独立した behavior tree を持ちます。
ある程度複雑な挙動が実現されているのが分かると思います。まだあまり賢いとは言えませんが……
ちなみにこのエージェントの挙動をロジック記述言語で書くと次のようになります。同じことを状態マシンで実装することを想像したらぞっとしますね。
tree main = Sequence {
if (!HasTarget (target <- target)) {
FindEnemy
}
Fallback {
Sequence {
IsTargetVisible (target <- target)
FaceToTarget (target <- target)
Shoot
}
FollowPathAndAvoid
}
}
tree FollowPathAndAvoid = Sequence {
if (!HasPath) {
TargetPos (pos -> target)
FindPath (target <- target)
}
if (HasPath) {
if (!FollowPath) {
ReactiveSequence {
Drive (direction <- "backward")
Randomize (max <- "20", value -> timeoutValue)
Timeout (time <- timeoutValue)
}
if (PathNextNode (output -> pathNext)) {
Randomize (min <- "20", max <- "100", value -> timeoutValue)
ReactiveFallback {
Avoidance (goal <- pathNext)
ForceFailure {
Timeout (time <- timeoutValue)
}
ClearAvoidance
}
}
}
Shoot
}
}
-
最近は AI というとディープラーニングなど機械学習をベースにしたものを意味することが多いですが、ここでは伝統的な意味での、人間によってデザインされた決定論的なアルゴリズムで、知能っぽいことを再現することを指します。 ↩︎
-
日本語では有限状態機械、有限オートマトンなどと呼ばれることもありますが、 FSM と略されることが多いようです。 ↩︎
-
もっと細かいことを言うと非同期 (asynchronous) は形容詞で、非同期な性質そのものを表す名詞形は非同期性で、英語では asynchrony ですが、誰もそんな呼び方はしないので asynchronous で押し通します。 ↩︎
-
公平のために付け加えておくと、 BehaviorTreeCPP の思想としては、この記述言語は人間が手で記述するのではなく、 Groot というグラフィカルエディタで編集することになっているので、構文だけ見て難しさを判断するのはフェアとはいえません。しかし、 Groot も大規模なツリーになってくると使いづらくなってくるので、普段 C++ を書いているようなプログラマにとっては、結局はテキスト形式が一番保守しやすいフォーマットになりがちです。 ↩︎
Discussion
いいねこれ! 使いやすい!!!