Home

Awesome

sts_bt_library

Overview

This module contains the behavior tree implementation for distributed robotic applications. It contains implementation for control flow of different action based command structures (behavior) and ros communication channels for a simple integration of user-nodes.

Publications, used work & special thanks

Installation

Installation from Packages

Dependencies

Building

To build from source, clone the latest version from this repository into your catkin workspace and compile the package using

cd catkin_ws/src
git clone git@gitlab_al.streetscooter.eu:al_SW_Team/sts_bt_library.git
cd ../
catkin build

Usage

You can see a running example in the sts_beavior_tree_testing package.

Bugs & Feature Requests

Please report bugs and request features using the Issue Tracker.

Documentation

General

This library provides the functionality to set up your own behavior tree logic by using the defined tree structures like Fallback, Sequence or Parallel Nodes. It provides an interface for some of these nodes, which allows the use of the basic ROS communication channels like subscriber, services and action clients.

Example image

Why a behavior tree

The main advantage of BTs compared to FSMs is their modularity, as can be seen by the following programming language analogy. In FSMs, the state transitions are encoded in the states themselves, and switching from one state to the other leaves no memory of where the transition was made from, a so-called one way control transfer. This is very general and flexible, but actually very similar to the now obsolete GOTO command, that was an important part of many early programming languages, e.g., BASIC. In BTs the equivalents of state transitions are governed by calls and return values being passed up and down the tree structure, i.e. two way control transfers. This is also flexible, but more similar to the use of function calls, that has replaced GOTO in almost all modern programming languages. Using function calls when programming made it much easier to modularize the code, which in turn improved readability and reusability. Thus, BTs exhibit many of the advantages in terms of modularity (including readability and reusability) that was gained when going from GOTO to function calls in the 1980s. Note however, that there are no claims that BTs are superior to FSMs from a purely theoretical standpoint. -- <cite>Michele Colledanchise - A Behavior Tree Library in C++ User Manual</cite>

How does it work

The behavior tree is a directed tree with nodes and edges using the usual definition of parents and children for neighboring nodes whereby the node without parents is called the root node, and nodes without children are called leaf nodes. These Nodes are separated into 2 categories, control nodes for flow control of the behavioral pattern and leaf nodes for executional patterns. Upon execution of the behavior tree, each time step of the control loop, the root node is ticked. This tick is then cascaded down the tree according to the types of each node. Once a tick reaches a leaf node (Action or Condition), the node does some computation, possibly affecting some continuous or discrete states/-variables of the behavior tree, and then returns either Success, Failure or Running. The return status is then progressed up the tree, back towards the root, according to the types of each node. If a running node does no longer receive a tick, it has to stop (preempted). The stopping of a preempted action is implemented in this library by the halt procedure.

Example image

Events

Multiple events are used to control the behavioral flow of a behavior tree. The most important, the "tick", resides inside the tick-engine as a clock signal for each and every existing node inside the given tree structure. Other signals are implemented (and can be further expanded upon) if new requirements have to be met regarding the relatively simple approach of the tree to make it more robust, more approachable or more complex.

Ticks

The tick engine itself consists of a clock and reset mechanism. It triggers 3 signals:

  1. PreTick Triggered from a parent before a child would be ticked
  2. Tick The actual Tick itself, used as a clock signal to execute and apply certain functionality
  3. PostTick Triggered from a parent after a child tick was executed and processed
Hooks

The hook engine is a node based execution event, which is not directly triggered by the behavior tree itself. Hooks are a simple way for nodes to communicate and relay information regarding their given task. From an outside perspective, these hooks would behave very much like a graphical programming language (for example: matlab/simulink). They are designed like special edges inside the tree, which are interpreted by their respective nodes (as they please) and can trigger multiple internal events. At the moment only a boolean value communication was chosen and implemented (to keep it simple, but any other data structure is possible):

As described later, hooks can either be called (hook source) or supplied (hook sink), which defines if the node applies (transmit) the hook event onto other nodes or if the node wants to get called with a specific hook event (receive).

Example image

Internal Structures

As described earlier there are multiple nodes, which can be used to implement your desired design. The different categories define whether or not the node has children (and therefore controls flow) or doesn't have children (and therefore controls execution). All the specific nodes are derived from their respective categories(control_node, leaf_node), which have a common base class (tree_node).

Base
Control Nodes

Example image

Example image

Example image

Example image

Example image

Example image

Leaf Nodes

There are two major types of leaf nodes:

  1. condition_node A Condition node determines if a condition C has been met. Conditions are technically a subset of the Actions, but are given a separate category and graphical symbol to improve readability and emphasize the fact, that they never return running and do not change any internal states/variables of the behavior tree.

    • sts_bt_if_topic This node behaves like a normal condition, but it will receive it's state from an external source/system via a ros topic. It uses 2 input buffers to secure synchronization of asynchronous data (distributed system) and a single enable latch to detach it's internal buffer from the behavior tree (block it's signal = disable)

      • Special Features: The name of this node is also the rostopic used This node can invert it's output when the first symbol of it's name is a '!'
      • Hook Source: Get: Fetches enable signals(bool) to identify whether or not the condition will return (Tick Event) it's newest internal state or return it's last stable (enabled) one

    • sts_bt_if_service This node behaves like a normal condition, but it will receive it's state from an external source/system via a ros service client. It works asynchronous by design and will therefore block the execution of the behavior tree (so be careful on the ros node side)

      • Special Features: The name of this node is also the rosservice used This node can invert it's output when the first symbol of it's name is a '!'

    • condition_node_hook This node behaves like a normal condition, but it will get it's value from a hooked partner via the hook GET event on Tick.

      • Special Features: This node can invert it's output when the first symbol of it's name is a '!'
      • Hook Source: Get: Fetches value(bool) to return success or failure.

Example image

Example image

  1. action_node An Action node performs an action, and returns Success if the action is completed, Failure if it can not be completed and Running if completion is under way.

    • sts_bt_if_action This node behaves like a normal action, but it will send parameters and receive it's state from an external source/system via a ros action client. If halted via the behavior tree, this action will return running state as long as the action of the communication partner has not acknowledged this abort (ros: cancelGoal) signal.

      • Special Features: The name of this node is also the ros action used

Example image

Support Nodes

Support nodes are not directly part of the tree. They exist as a data holders or single tick event triggers and are only ever reacting with other nodes when they are hooked properly.

Example image

Example image

Example image

How to use it

The behavior tree can be executed by creating a tree, either by parsing a .graphml or creating it yourself in code, and then executing that tree.

Building Trees

Parser / yEd .graphml

Building trees from scratch is lame, so we designed a .graphml parser which can be used to create a well documented graph and use it as a recipe for the behavior tree creation itself.

The package sts_bt_main and sts_behavior_tree_testing have an example tree in their configs which contain the necessary behavior tree building blocks in yEd.

How to set up yEd

yEd (v3.19.1.1) sadly cannot put data fields (which are used to identify and differentiate the nodes in the graph) in palettes because custom data fields are a file-specific attribute. Because of this, you have to import the palette and re-add custom data fields in your custom behavior_tree.graphml file. A List of data fields used for parsing the .graphml can be seen below.

Remember this when using .graphml

All the (above) described elements of the behavior tree should be inside the palette (.graphml). You should keep the following in mind when using yEd (.graphml) to design your behavior tree:

List of used data fields for .graphml for nodes:

List of used data fields for .graphml for edges:

Using the parser inside the code should be straightforward:

BT::TreeNode* rootPtr = sts_behavior_tree::BehaviorTree::Load(path, nh);
From Scratch (Code)
	//Build nodes here
	StsBtIfNodePtr action1 = sts_bt_if_factory::createNode("/sts_behavior_tree_testing_node/bt_action", 
		false, sts_bt_if_factory::ACTION, nodeHandle, false);
	StsBtIfNodePtr condition1 = sts_bt_if_factory::createNode("/sts_behavior_tree_testing_node/bt_topic", 
		true, sts_bt_if_factory::TOPIC, nodeHandle,false);
	StsBtIfNodePtr condition2 = sts_bt_if_factory::createNode("/sts_behavior_tree_testing_node/bt_service", 
		true, sts_bt_if_factory::SERVICE, nodeHandle, false);
	BT::SequenceNode* root = new BT::SequenceNode("root", true);
	BT::FallbackNode* condition_branch = new BT::FallbackNode("condition_branch", true);
	BT::SequenceNode* action_branch = new BT::SequenceNode("action_branch", true);
        //Build tree here
	root->AddChild(condition_branch);
	root->AddChild(action_branch);
	condition_branch->AddChild(condition1);
	condition_branch->AddChild(action1);
	action_branch->AddChild(condition2);

Normal nodes behave quite simple and don't need many arguments at creation:

The nodes interacting with ros are a little bit more complicated:

Starting Trees

The tree starts with the Execute() call and will run forwever. It takes a TreeNode* pointer to the root of your tree and executes from there.

try
{
	sts_behavior_tree::BehaviorTree::Execute(this->rootPtr, 
		this->treeTickPeriod_, id, this->nodeHandlePtr, this->nodename_,
		this->treeGenFeedback_, this->treeDebugDelay_);
}
catch (BT::BehaviorTreeException& Exception)
{
	this->PRINT_ERROR( Exception.what ( ));
}

How to interface it (Virtual Interfaces API)

Interfacing from user (node) perspective is done via the special interface for the behavior tree inside the sts_virtual_interfaces package. All you have to do is to declare the communication endpoints in your node and the interface will create and (mostly) maintain these interfaces for you.

Example image

Additional Information

A example of the possible ros communications and their messaging can be seen here:

ROS com channels