1. Introduction to behavior trees
BTs are a formalism for modeling the execution of procedures or tasks. The main design paradigm is a tree, where internal nodes are called control flow nodes and leaf nodes are denoted as execution nodes. When a BT starts, the root node emits periodic activation signals, called ticks, which are sent to the currently active child.
A node is only executed if, and only if, it receives a tick signal. Once a node is executed, it returns either Success (True), Failure (False) or Running (Waiting). In case a node is Running, it may propagate the tick to one of its children, based on its policy. The execution order of nodes inside the tree goes from top to down and left to right.
Control Flow Nodes determine in which order the child nodes are executed. The following three operators are available:
- Sequence node: Represented as an arrow [->], it executes its child nodes sequentially, until a node returns Failure.
- Fallback node: Marked as [?], it executes its child nodes sequentially, until a node returns Success.
- Decorator node: also known as conditional, it is a node that can have only a single child. It is up to the Decorator to decide if, when and how many times the child should be ticked. It is typically used for building loops, triggers or switches.
Sequence and fallback nodes both can have multiple child nodes.
Execution nodes represent the individual sub-tasks, often called primitive tasks, that the robot is able to execute. They are divided into:
- Actions: Nodes that can change the environment, for instance, move the robot from point A to B.
- Conditions Nodes that have access to the environment/robot state, but should not change it. For example, a condition might check if robot batteries are empty, or a specific sensor is ready to operate.
As illustrative example, a BT controlling the execution of tasks required for a robot to navigate to a goal is presented here:
In this example, A represents Actions, and C denotes Conditions.
Optimal software architectures usually offer the following characteristics:
- Modularity
- Reusability of components
- Composability
- Good separation of concerns
Ignoring these concepts, might result on modules/components that are highly coupled to a particular application, instead of being reusable. That is where the powerful modeling hierarchy of BT becomes important. It allows us to separate the expertise roles when designing complex applications.
Lets consider an example: A Computer Vision expert wants to install a camera on the robot arm, and then use it for a specific application. Ideally, the arm framework should be a [ready-to-use] [black-box] component, that he can import and use in his application.
Modelling the robot processes (such as Navigation or Arm motion) using BTs, allows us to [plug-and-play] existing components created by Navigation/Arm motion experts into new applications easily. It promotes reusability, modularity and reduces the application complexity.
-
A more detailed introduction to Behavior Trees is given on behaviortree.dev - Introduction to BTs
-
A nice paper about BTs and robotics: Behavior Trees in Robotics and AI: An Introduction
-
Some useful concepts are also given in Behavior trees in Wikipedia