見出し画像

多分木グラフでロボットに指示を出す　ビヘイビアツリー入門

tks

この記事はビヘイビアツリーの解説記事です。

ビヘイビアツリーの特徴や各ノードの意味、Navigation2におけるデフォルトコードの仕様等を説明していきます。


ビヘイビアツリーとは？

ビヘイビアツリーとは、ロボットのAIの行動や判断を多分木グラフで表現した計算モデルの一種です。

ロボットの指示の仕組みとして「有限状態機械 (FSM) 」というモデルも存在しますが、ビヘイビアツリーはFSMよりシンプルな構造となっており、バグ発生時に原因が特定しやすいなど扱いやすい特徴を持っています。

ROSのロボット自律システムであるNavigation2では、ロボットへの指示を行う際にビヘイビアツリーを使って行動や判断を設定していきます。

ビヘイビアツリーの記述

ビヘイビアツリーはXML形式で木構造を記述します。

例えばロボットに「1m走行するごとに最適経路を再計算しながらゴールへと向かう」という機能を実装したい場合、以下のようなシンプルな木構造となります。

木構造の各ノードを<ノード名>のXMLタグ形式で表現します。

これらのノードひとつひとつがロボットの行動や判断を行うための指示となっています。例えば「DistanceController」ノードはロボットが一定距離進むごとに子ノードを実行、「ComputePathToPose」はゴールまでの経路を計算するという意味を持ちます。

そして子ノードを親ノードの開始タグと終了タグで挟むことにより、親ノード・子ノードの関係を表現します。

<親ノード>
    <子ノード>
</親ノード>

例えば、上記の木構造のグラフをXMLで記述すると以下のようになります。

<root main_tree_to_execute="MainTree">
  <BehaviorTree ID="MainTree">
    <PipelineSequence name="NavigateWithReplanning">
      <DistanceController distance="1.0">
        <ComputePathToPose goal="{goal}" path="{path}"/>
      </DistanceController>
      <FollowPath path="{path}"/>
    </PipelineSequence>
  </BehaviorTree>
</root>


ビヘイビアツリーを構成する各種ノード

ビヘイビアツリーは様々な機能を持つノードの多分木構造で構成されます。

各ノードは「Success（成功）」「Failure（失敗）」「Running（実行中）」の3つの結果を返し、親ノードは子ノードの結果によって行動を変更することで複雑な機能をもったAIを作成することができます。

ビヘイビアツリーのノードは「Action Nodes」「Condition Nodes」「Control Nodes」「Decorator Nodes」の4つに類別されます。

Action Nodes

ロボットに対し具体的な行動を指示するノードです。

例えば「○○m前に進む」「○度回転する」「目的地までのルートを計算する」など行動を指示し、その行動を実行できたか否かによって成功・失敗の判定を行います。

  • 対象のアクションを正常に実行した（とサーバー側が認識した）⇒ 成功

  • 対象のアクションを実行中の場合 ⇒ 実行中

  • 上記以外の場合（アクションを異常終了した場合）⇒ 失敗

Condition Nodes

ロボットの状態を判定するノードです。

例えば「初期位置に移動したか」「目的地に着いたか」「バッテリーが一定電圧以下になったか」など条件を設定し、指定された条件を満たしているか否かによって成功・失敗の判定を行います。

  • ロボットが指定された条件を満たしている場合 ⇒ 成功

  • ロボットが指定された条件を満たしていない場合 ⇒ 失敗
    ※Condition Nodesでは「実行中」を返すことはありません。

Control Nodes

子ノードを複数持ち、実行順序を制御しているノードです。

成功、失敗、実行中判定は子ノードたちの結果によって左右されます。

例えば「Sequence」というControl Nodesでは子ノードを上から順番に実行し、以下のように判定を行います。

  • 子ノードが一つでも実行中 ⇒ 実行中

  • 子ノードが一つでも失敗 ⇒ 失敗

  • すべての子ノードが完了したときに全ノードが成功 ⇒ 成功

Decorator Nodes

一定条件で子ノードを実行するノードです。

例えば「一定距離を走行するごとに実行」「一定時間が経過するごとに実行」「速度に応じて実行頻度を変更する」などの機能が存在します。

成功、失敗、実行中判定はノードごとに異なります。

例：Navigation2における基本アルゴリズム

Navigation2におけるデフォルトのビヘイビアツリーは以下の形になっています。

このビヘイビアツリーは二つのサブツリーに分割することができます。

  • 左側：ナビゲーションツリー ＝ 経路の計算・走行を行うツリー

  • 右側：リカバリーツリー＝ナビゲーションツリー実行が失敗時に復帰動作を行うツリー

ナビゲーションツリーの仕様

ナビゲーションツリーは経路の計算を行う「ComputePathToPose」と、計算した経路上の移動を行う「FollowPath」の2つのツリーから成り立っています。

これら2つのツリーの根元を「PipelineSequence」というControl Nodesで結合します。

【PipelineSequenceの仕様】
			
子ノードを先頭から順に（樹形図だと左から順に）実行していく。
Sequenceと違い、K番目の子ノードを実行する際、同時に1～K-1番目のノードも再実行する。

子ノードが一つでも実行中　⇒　実行中
再実行も含め1回でも失敗　⇒　失敗
すべてのノードが完了したときに全ノードが成功　⇒　成功

このPipelineSequenceを使うことにより、

  • ComputePathToPoseの後にFollowPathを実行する（経路を計算してから移動を行う）

  • FollowPathを実行中にComputePathToPoseを再実行する（経路上を移動しながら経路の再計算を行う）

という２つの動きをシンプルな木構造で表現することができます。

PipelineSequenceより下には、ComputePathToPoseツリーとFollowPathツリーという2つのツリーが並列することになるのですが、これらのツリーは並べてみるとほぼ同じ構造を持っています。

  1. 指定した行動（経路の計算または経路上の走行）を実行。

  2. 指定した行動が失敗した場合、復帰動作を実行。
    復帰できた場合、指定アクションを再度実行する。

木構造に「実行したいアクション」だけでなく簡易な「復帰動作」を追加することで、通行人や障害物といった予期せぬアクシデントにも対応できるようになります。

ただし、この簡易の復帰動作でも対応できない大きな問題に遭遇した場合、ナビゲーションツリーをいったん止め、右側のリカバリーツリーに移行します。

リカバリーツリーの仕様

ComputePathToPoseおよびFollowPath内の回復動作で元の動作に復帰ができなかった場合、ナビゲーションツリーのノードは「失敗」を返し、リカバリーツリーを実行します。


リカバリーツリーでは不具合の発生したゴール目標をいったんクリアし、不具合のない新しいゴール目標を定めることで走行復帰を目指します。

そこで、新しいゴール目標が設定されるまでRoundRobinノードによって以下の4動作を順番に実行します。

  • コストマップ（ローカル、グローバル両方）の初期化

  • 90度の旋回

  • 5秒の待機

  • 0.15mの後退

【RoundRobinノードの仕様】
	
初めてこのRoundRobinノードに入った場合、
子ノードを上から順に（樹形図だと左から順に）実行していく。

そして、このRoundRobinノードに入るのが2回目以降の場合、
前回の最後に実行した子ノードの次のノードから順に実行していく。


子ノードが一つでも実行中 ⇒ 実行中
途中一つでも成功 ⇒ 成功（RoundRobin処理を途中離脱する）
すべてのノードが完了したときに全ノードが失敗 ⇒ 失敗を返す。

参考文献

いいなと思ったら応援しよう！

この記事が参加している募集

#AIとやってみた

37,626件