1 of 21

Behavior Trees

Github repo for mr_bt: https://github.com/campusrover/mr_bt

The goal behind the MRBT project was to create a efficient, modular, and user-friendly solution for programming complex behaviors into the Turtlebot3 robot stack. Our solution came in the form of a popular method in the videogaming industry for programming behaviors into NPCs (Non-Playable Characters in videogames; think enemies in HALO or Bioshock). With the use of behavior trees, we are now able to program complex behaviors using a simple tree definition in a JSON file, and we can partition a behavior into multiple different subtrees which can then be used elsewhere or standalone.

Installation

Requires ROS Noetic, Ubuntu 20.04, and a catkin workspace
cd into your catkin_ws/src directory
Run git clone https://github.com/campusrover/mr_bt.git
Run cd ../ && catkin_make

Usage

To run one of the example behavior trees you must use a Turtlebot3 robot connected to ROS.
Run the example roslaunch mr_bt btree.launch tree:=move_to_position
If you want to run any example in the folder mr_bt/src/tree_jsons/, pass in the name of the example folder containing a root.json as the tree argument for the launch script.

Key Components of the Behavior Tree

Any complex behavior tree can be broken down into a few key components which highlight the overall logical structure of how they operate.

Blackboard

The Blackboard is the main storage component for data accessible to nodes in the behavior tree. It is stored as a Python dictionary and its reference is passed down to each node in the behavior tree from the root node. The effect of this is that each node in the tree is able to change and share data through the Blackboard. Additionally, data that is sent from the sensors on the robot, including camera data, lidar data, etc, is accessable from each node in the tree.

Nodes

A behavior tree is a tree-shaped data structure consisting of nodes, each of which contain a logical method which executes code. The behavor tree is evaluated recursively starting at the root node. Each node has the abilility to execute code which will either run a script, or execute all of its children. Each node will also return one of 3 outputs to its parent: "success", "failure", or "running". There are two main types of nodes: the control-flow (parent nodes) nodes and the leaf nodes.

Control-Flow Nodes

Selector
- The Selector executes its children sequentially from left to right.
- If one of its children returns either "success" or "running", it will halt execution of its children and it will return the result of the child it stopped on.
- If all of its children return "failure", the Selector will also return "failure".
Sequencer
- The Sequencer executes its children sequentially from left to right.
- The Sequencer will not halt execution of its children unless one of them returns "failure" or "running", in which case it will also return "failure" or "running".
- If all children return "success" the Sequencer will return "success"
Multitasker
- The Multitasker runs all of its children concurrently, each in a separate thread.
- The Multitasker will return "success" only if all of it's children return "success".
- If any of its children return "running" but none return "failure", the Multitasker will return "running".
- If any of its children return "failure", the Multitasker will return "failure".

Leaf Nodes

Action Nodes
- Action nodes send ROS topic messages from the behavior tree to the robot.
- Often the type of message sent from an Action node is a cmd_vel message which encodes movement instructions for the robot.
Update Nodes
- Update nodes are designated for updating data in the blackboard.
- Often times the types of data updates performed by Update nodes include preprocessing or processing of message data from the robot.
Conditional Nodes
- Conditional nodes will return either "success" or "failure", corresponding to the boolean values "true" and "false" respectively
- Conditional nodes will access data in the blackboard and return one of the two values listed above based on if a particular condition is met within the data.

Nodes

Control-Flow Nodes

Selector
- The Selector executes its children sequentially from left to right.
- If one of its children returns either "success" or "running", it will halt execution of its children and it will return the result of the child it stopped on.
- If all of its children return "failure", the Selector will also return "failure".
Sequencer
- The Sequencer executes its children sequentially from left to right.
- The Sequencer will not halt execution of its children unless one of them returns "failure" or "running", in which case it will also return "failure" or "running".
- If all children return "success" the Sequencer will return "success"
Multitasker
- The Multitasker runs all of its children concurrently, each in a separate thread.
- The Multitasker will return "success" only if all of it's children return "success".
- If any of its children return "running" but none return "failure", the Multitasker will return "running".
- If any of its children return "failure", the Multitasker will return "failure".

Leaf Nodes

Action Nodes
- Action nodes send ROS topic messages from the behavior tree to the robot.
- Often the type of message sent from an Action node is a cmd_vel message which encodes movement instructions for the robot.
Update Nodes
- Update nodes are designated for updating data in the blackboard.
- Often times the types of data updates performed by Update nodes include preprocessing or processing of message data from the robot.
Conditional Nodes
- Conditional nodes will return either "success" or "failure", corresponding to the boolean values "true" and "false" respectively
- Conditional nodes will access data in the blackboard and return one of the two values listed above based on if a particular condition is met within the data.

Visualization of the behavior Tree

Each tree that you build will be able to be visualized as a ROS Image topic under the topic name /btree

Once your behavior tree is executed with roslaunch mr_bt btree.launch tree:=my_tree the /btree topic will begin to be published and updated according to the state of your tree in real time.

The nodes which have not been run will appear white, those which have been run and returned "failure" will appear red, those which have been run and returned "success" will appear green, and those which returned "running" will appear yellow.

Since the image is updated in real time, you will be able to get feedback on which state your tree is in at any given moment, and also debug any issues.

Using RVIZ to visualize the Behavior Tree

You can run rviz to open up the program and add the /btree topic as an image to visualize the tree.

Logging the Blackboard

You can log the values in the blackboard by using the log argument when running the mr_bt launch file: roslaunch mr_bt btree.launch tree:=my_tree log:=true

The blackboard will then be printed in the terminal where you run the launch file in the ROS log.

Because some blackboard variables will be two large to print, not all of the variables will show up in the output. Strings, floats, ints, and booleans will be printed, as well as the first 5 elements of any lists or arrays. If the full value of a variable is not printed, its data type will be printed instead.

basic_movement.md

The 3 nodes classified as "basic movement" nodes are the fundamental building blocks needed in order to make a robotics behavior tree application.

LinearAngularStatic

When this node is activated, it will publish a cmd_vel message including the linear and angular velocities specified during its construction:

Example:

{
    "name":"my_node",
    "type":"LinearAngularStatic",
    "lin_vel":0.5,
    "ang_vel":1
}

Stop

A special case of LinearAngularStatic; upon activation the Stop node will publish a cmd_vel message with all velocity values set to 0.

Example:

{
    "name":"my_node",
    "type":"Stop"
}

LinearAngularDynamic

This node is similar to LinearAngularStatic how,ever instead of providing velocities during construction, you provide names of blackboard topics which correspond to the linear and angular velocities that the node will publish in cmd_vel when activated. This allows for velocities to be updated by update nodes and then have one LinearAngularDynamic node providing dynamic movements.

Example:

{
    "name":"my_node",
    "type":"LinearAngularDynamic",
    "linear_var_name":"my_linear_vel",
    "angular_var_name":"my_angular_vel",
    "blackboard":{
        "my_angular_vel":null,
        "my_linear_vel":null
    }
}

build

The mr_bt project allows users to define behavior trees as JSON files. Each node in the behavior tree is a JSON dictionary object, for example:

{
    "name":"goal_pid",
    "type":"Multitasker",
    "children":[
        
        {
            "name":"Calculate angular velocity necessary to face towards the position",
            "type":"PathCorrection",
            "correction_var_name":"angular_goal_pid",
            "goal_value_var_name":"goal_rotation",
            "current_value_var_name":"rotation",
            "max_vel":1.5
          },
          {
            "name":"Calculate linear velocity to get to position",
            "type":"PathCorrection",
            "correction_var_name":"linear_goal_pid",
            "goal_value_var_name":"dist",
            "current_value_var_name":"dummy_current_value",
            "max_vel":0.1,
            "offset":0
          }
    ],
    "blackboard":{
        "angular_goal_pid":null,
        "linear_goal_pid":null,
        "dummy_current_value":0,
        "dist":null
    },
    "blackbox":true
}

Folder structure

When building a new project create a new folder with the name of your project in mr_bt/src/tree_jsons.

Each behavior tree project must have a root JSON file named root.json. This file will define the root node of your behavior tree and must be unique in your project folder. For example if you want to make a new project named my_new_bt_project, your folder structure should look something like this:

mr_bt/src/tree_jsons/
  my_new_bt_project/
    root.json
    action1.json
    action2.json

defining_blackboard.md

The blackboard is the main data storage component of the behavior tree in mr_bt which contains ROS messages, and other variables vital to the function of your program. The variables in the blackboard will be defined in your tree JSON or throughout multiple tree JSONs in your project.

The blackboard is, at its core, just a referece to a python dictionary that gets passed down through each node recursively in your tree. All nodes called in your tree have access to the same python dictionary so they can share information.

Populating variables in the Blackboard

Let's start off with defining a blackboard that has two input variables: max_speed and goal_position. You want to define these two variables yourself at the root of your tree, so your tree JSON root.json should look something like this:

{
    "name":"move_to_position",
    "type":"Selector",
    "children":[
        ...
    ],
    "blackboard":{
        "max_speed":0.5,
        "goal_position":[1, 1]
    }
}

You can see that the blackboard is defined within the node with the keyword "blackboard" and the value being another JSON dictionary containing the key, value pairs of the blackboard variables.

Initializing variables in the blackboard

Let's say you want a few variables in your blackboard to keep track of where your robot is, and whether it has reached a certain position. You want your variables to be called current_position and reached_position.

The various nodes within your tree will update these variables with the correct information when the tree is executed, however you don't want to populate them yourself. In this case, you can simply define the blackboard as so:

{
	...
	"blackboard":{
		"current_position":null,
		"reached_position":null
	}
}

Since your other nodes will populate these values upon execution of the tree, you can initialize them as null.

ROS messages in the Blackboard

You'll likely need to subscribe to ROS messages coming from either your robot, or other ros programs in your behavior tree. In order to program your behavior tree to subscribe to these messages, you must define them in the blackboard as a special case.

For example, let's say you need want to use the GetPosition node to populate the current_position variable from the previous example. The GetPosition node uses an Odometry message to get the current positionof the robot, so your blackboard should look like this:

{
	"name":"Get my robot's position",
	"type":"GetPosition",
	"position_var_name":"current_position",
	"blackboard":{
		"current_position":null,
		"/odom":"Odometry"
	}
}

You'll notice that in the special case of subscribing to a ROS topic in the blackboard, the name of the variable is preceded with a /, and the value is the name of the ROS message type. This will be the case for any ROS topic subscription in your behavior tree.

Defining the blackboard in multiple JSONs

Likely you will split your project up into multiple different files, and it will be difficult to consolidate all of the required blackboard variables and ROS topic subscriptions into one blackboard definition. Luckily, you don't need to do that.

You can define different sections of the blackboard in different JSON files, and all of the different blackboard definitions will be combined into one upon compilation of your tree.

For example, if you have two files in your tree each with a different blackboard definition such as:

{
	...
	"blackboard":{
		"current_position":null,
		"/odom":"Odometry"
	}
}

And then

{
	...
	"blackboard":{
		"max_speed":0.5,
		"goal_position":[1, 1]
	}
}

The final functional blackboard will be

"blackboard":{
	"current_position":null,
	"/odom":"Odometry",
	"max_speed":0.5,
	"goal_position":[1, 1]
}

defining_nodes.md

Working with Leaf Nodes in Tree JSON

The usage of the included nodes can be generalized to a few rules.

All of the included nodes exist within python files inside the folder mr_bt/src/nodes/. The files themselves are using the snake naming convention, for example: my_bt_node. The classes inside each file uses the CapWords naming convention conversion of the file name, for example: class MyBtNode:. When calling the node in a JSON tree, use reference the "type" with the CapWords name of the node class, i.e.

The arguments passed into the node definition in the tree JSON should exactly match the names of the arguments defined in the python class __init__ function, for example if the class definition looks like this:

Your tree JSON should look like this:

Working with Parent Nodes in Tree JSON

The usage of parent nodes follows the same rules as the usage of the leaf nodes, however all parent nodes require their children to be defined in the tree JSON as well. The children are defined as a list of nodes within the "children" agument of the parent node. Here is an example parent node with two children:

defining_references.md

Due to the recursively defined nature of the behavior tree, the JSON definitions can get messy and unreadable for larger trees. The solution for splitting up different parts of your tree is using a reference to another JSON within your workspace instead of an entire node or tree definition.

Anywhere you could include a node or tree definition, you could instead reference another JSON using the "ref" keyword. The root directory of the tree parser is set to mr_bt/src/tree_jsons/, so your reference provided must be relative to that root directory.

For example, let's say that you are creating a new behavior tree in the folder mr_bt/src/tree_jsons/my_new_tree/ and your folder contains the following:

You want to include move.json and calculate_dist.json as children for a parent node in root.json. This is what that would look like

You can also make references to other behavior tree JSONs as long as they are in the directory mr_bt/src/tree_jsons by providing their path within that directory.

custom_nodes

You may find yourself wanting to extend the functionality provided by the default nodes in this package by adding your own parent, action, conditional, or update nodes.

Directory structure

In order to create your own custom nodes, the nodes can exist anywhere in the directory mr_bt/src/nodes/ as a .py file.

Naming

All behavior tree nodes are created as a python class in a python file. The name of your .py file should correspond with the name of your class within the file.

For example, if you want to create a node called MyNewNode, the file that it exists in should be called my_new_node.py and the class definition should be class MyNewNode(SomeNodeType):.

Required function

Each different type of node will have a required "tick" function, but the naming is different depending on the type of node you are creating. Regardless of what the "main" of function is called, it always returns one of three string type values: "success", "failure", or "running".

For further details on how to create custom nodes of each type, see the following sections.

custom_action.md

To create a custom action node, you must define your node class by inheriting from the superclass that defines a generic action node.

You also must include the execute function as the "tick" function that performs the actions of the node.

Here is an example of a custom action node:

This type of node will return one of the following string values: "success", "failure", or "running"

custom_conditional.md

To create a custom conditional node, you must define your node class by inheriting from the superclass that defines a generic conditional node.

You also must include the condition function as the "tick" function that returns a bool type depending on the state of the relavent blackboard

Here is an example of a custom conditional node:

This type of node will return a boolean value.

custom_update.md

To create a custom update node, you must define your node class by inheriting from the superclass that defines a generic update node.

You also must include the update_blackboard function as the "tick" function that updates the blackboard with relevant information.

Here is an example of a custom update node:

from ...nodes.update import Update

class MyUpdateNode(Update):
    def __init__(self):
        super().__init__()
    
    def update_blackboard(self, blackboard: dict) -> str:
        ...

This type of node will return one of the following string values: "success", "failure", or "running"

included_nodes

action_nodes.md

Basic Movement

LinearAngularStatic
LinearAngularDynamic
Stop

conditional_nodes.md

Basic Conditionals

BoolVar
BoolVarNot

Odometry Conditionals

ReachedPosition

LaserScan Conditionals

ClearAhead

included_nodes.md

##Documentation for included nodes

Action Nodes

Basic Movement

The 3 nodes classified as "basic movement" nodes are the fundamental building blocks needed in order to make a robotics behavior tree application.

Conditional Nodes

Basic Conditionals

Odometry Conditionals

Laserscan Conditionals

Update Nodes

Basic Updates

Movement Control Updates

Odometry Updates

Laserscan Updates

parent_nodes.md

update_nodes.md

nodes

leaf_nodes.md

Action Nodes
- Action nodes send ROS topic messages from the behavior tree to the robot.
- Often the type of message sent from an Action node is a cmd_vel message which encodes movement instructions for the robot.
Update Nodes
- Update nodes are designated for updating data in the blackboard.
- Often times the types of data updates performed by Update nodes include preprocessing or processing of message data from the robot.
Conditional Nodes
- Conditional nodes will return either "success" or "failure", corresponding to the boolean values "true" and "false" respectively
- Conditional nodes will access data in the blackboard and return one of the two values listed above based on if a particular condition is met within the data.

parent_nodes.md

Selector
- The Selector executes its children sequentially from left to right.
- If one of its children returns either "success" or "running", it will halt execution of its children and it will return the result of the child it stopped on.
- If all of its children return "failure", the Selector will also return "failure".
Sequencer
- The Sequencer executes its children sequentially from left to right.
- The Sequencer will not halt execution of its children unless one of them returns "failure" or "running", in which case it will also return "failure" or "running".
- If all children return "success" the Sequencer will return "success"
Multitasker
- The Multitasker runs all of its children concurrently, each in a separate thread.
- The Multitasker will return "success" only if all of it's children return "success".
- If any of its children return "running" but none return "failure", the Multitasker will return "running".
- If any of its children return "failure", the Multitasker will return "failure".