Functional Behaviour Tree

This Functional Behaviour Tree package contains a library of building block components for behaviour tree systems that lean toward a functional programming paradigm.

Behaviour trees, which are often associated with the field of AI (artificial intelligence) and used predominantly within the games industry, are a solution to systems that have complex logical infrastructures and follow a similar node based structure to neural networks, but control the data flow with discrete boolean responses, rather than probability (floats - fuzzy logic).

By following functional programming conventions there can be less programming side-effects to be had than if one were to follow an object-orientated approach. In this library each node is defined by a function and won't be store persistent variables in itself like a class can. This means that all required variables of the node should be passed in by the function's parameter rather than referencing variables outside the scope of the function.

Structure

The library's components:

  1. Node
  2. Decorator * Inverter

  3. Composite Selector Sequence

Components

Blackboard

Behaviour tree frameworks often define a 'Blackboard' object to act as the 'container' for (or to represent) the problem domain/s that the behaviour tree system is to address. The responsibility of the behaviour tree system is then to interact with and incur a state of change upon the problem domain, or blackboard, by passing the blackboard around its internal structure. Each node then accesses and changes the information within the blackboard, and/or controls the flow of what nodes it should transverse.

Node

The behaviour tree's internal structure comprises of nodes that are responsible for interacting with the blackboard individually, without any explicit dependency on adjacent nodes. It is up the the node to carry out some process on the blackboard object and return a Boolean (true or false) value pending the outcome of that process. One reason for using a behaviour tree is modularity, thus the absence of explicit dependency is important, but all nodes must be able to 'know' this blackboard object.

Each of the nodes will specialise in the performance of a particular task, which when in a particular sequence, help reach the overall solution. The response of these nodes feed back to a composite node (explained below) that determines the flow of the system, affecting what future nodes will be processed.

Since all components of the behaviour tree are nodes and nodes generally call other nodes, then one node must triggers all of the other nodes to begin. This is the root node of the tree. The root node is the one that needs to begin the processing of the tree and is the entry point for the blackboard object. Generally speaking, the root node is going to be a type of composite node (such as a sequence or selector) that can trigger off other contain nodes it's been given reference to. By calling this node and passing the blackboard object in, it trickles through all internal nodes, returning once the tree has finished the processing.

These nodes/components/modules of the tree (terms that can be used interchangeably in the context) are also known as the KSs (knowledge sources). The blackboard, or problem domain, is worked on collectively by each node the tree comprises of, to break down the problem into 'sub-problems' that are each resolved by specific nodes, which reach a solution for the overall system.

Action

Actions by the conventions of their name are the nodes that carry out change upon the problem domain. Actions will nearly always return true unless something prevented the action from taking place. Before an action is carried out however, the blackboard can be queried to determine if it has the correct conditions to incur that change. This is what conditions are used for.

In this framework actions are not defined as a type because it adds no definition advantage over the node type. Actions purely distinguish a node's purpose.

Condition

Conditions by convention of their name do not carry out any change on the problem domain. Conditions are nodes that query the problem domain to check if it meets certain criteria, returning true or false. These nodes help indirectly control the flow of the behaviour tree through their output when used in conjunction with composite nodes.

In this framework conditions are not defined as a type because it adds no definition advantage over the node type. Conditions purely distinguish a node's purpose.

Decorator

The decorator (or wrapper) contains or 'wraps' a node to extend the contained node's functionality without altering the node's internal implementation or defining a new node.

Inverter

The inverter decorator inverts the response given by a node contained within it, returning true if the contained node returned false, and vice versa. If conditions follow the 'is' true convention, i.e. all the conditions check if something 'is' working or a property 'is' present, rather than 'is not', then when-ever a condition needs to find out if something 'is not' true it can simply be wrapped in this inverter decorator rather than creating an additional node for the task.

Composite

Composite nodes (also know as the control flow nodes, or a branch) are nodes that contain an array of nodes within themselves, along with the logic behind how these encapsulated nodes should be executed. As such, these nodes are responsible for controlling the flow of execution of the encapsulated nodes within them through use of their own logic.

The two most common types of composite nodes are the Selector and Sequence nodes. Both of these are included in this framework.

Sequence

The sequence composite processes an array of nodes that it iterates through. Along the way, the sequence node will stop its iterating processing of internal nodes if any node returns false. If any node returns false, the sequence returns false. The sequence will return true if the processing of the internal array reaches the end without any of the nodes returning false; thus completing the sequence.

Selector

The selector composite processes an array of nodes that it iterates through. Along the way, the selector node will stop its iterating processing of internal nodes if any node returns true. If any node returns true, the selector returns true. The selector will return false if the processing of the internal array reaches the end without any of the nodes returning true; thus failing to make a selection.

Usage

Node

In this library each node is simply a function that meets a specific set of criteria, defined by the Node typedef. The Node type used simply to validate node functions that are defined as expressions or passed as parameters into other functions (like composites). Each node function must take Map as it's first and only parameter and return a Future\<bool\>.

The node can be defined by either a function declaration:


import 'package:functional_behaviour_tree/functional_behaviour_tree.dart';
import 'dart:async';

Future<bool> isHttpStatusCode404(Map blackboard) {
  if (blackboard['http_status_code'] == '404')
    return new Future(() => true);
    
  return new Future(() => false);
}
    

Or a function expression (declared as type Node):


import 'package:functional_behaviour_tree/functional_behaviour_tree.dart';
import 'dart:async';

Node isHttpStatusCode404 = (blackboard) {
 if (blackboard['http_status_code'] == '404')
   return new Future(() => true);
   
 return new Future(() => false);
};
    

Each node should be called by passing the Map (or blackboard) parameter:


isHttpStatusCode404({'http_status_code' : '404'});

Decorator

The decorator by itself is a typedef in the library and is used to validate a decorator function as an expression or a parameter. Decorator functions take the first parameter as a blackboard of type Map, then a node as type Node as the second, with the return of type Future\<bool\>.

A decorator can be defined as an expression as per the example below:


import 'package:functional_behaviour_tree/functional_behaviour_tree.dart';
import 'dart:async';

Decorator invert = (Map blackboard, Node node) async {
  return !await node(blackboard);
};

Invert

To use invert on a node it requires a blackboard as type Map in the first parameter and a node of type Node as the second, with the return type of Future\<bool\>.


import 'package:functional_behaviour_tree/functional_behaviour_tree.dart';
import 'dart:async';

invert({'http_status_code' : '404'}, isHttpStatusCode404)

As this function takes two parameters it cannot be passed as a Node type, instead this function must be wrapped in another function to pass as a node and be used as a tree branch:


import 'package:functional_behaviour_tree/functional_behaviour_tree.dart';
import 'dart:async';

Node notHttpStatusCode404 = (Map blackboard) => invert(blackboard, isHttpStatusCode404);

Composite

The composite by itself is a typedef in the library and is used to validate a composite function as an expression or a parameter. Composite functions take the first parameter as a blackboard of type Map and the second as nodes of type List\<Node\>, with the return of type Future\<bool\>.

A composite can be defined as an expression as per the example below:


import 'package:functional_behaviour_tree/functional_behaviour_tree.dart';
import 'dart:async';

Composite sequence = (Map blackboard, List<Node> nodes) async {
  for(Node node in nodes) {
    if (!await node(blackboard))
      return new Future(() => false);
  }
  return new Future(() => true);
};

Sequence

To use sequence on an array of nodes it requires a blackboard as type Map in the first parameter and the nodes of type List\<Node\> as the second, with the return type of Future\<bool\>.


sequence({
    'user_logged_in' : true,
    'user_id' : 2
}, [
    isUserLoggedIn,
    isUserIdSet,
    //...
]);
    

As this function takes two parameters it cannot be passed as a Node type, instead this function must be wrapped in another function to pass as a node and be used as a tree branch:


isUserPermitted(Map blackboard) => sequence(blackboard, [
    isUserLoggedIn,
    isUserIdSet,
    //...
]);

Select

To use select on an array of nodes it requires a blackboard as type Map in the first parameter and the nodes of type List\<Node\> as the second, with the return type of Future\<bool\>.


select({'http_status_code' : '402'}, [
    isHttpStatusCode400,
    isHttpStatusCode401,
    isHttpStatusCode402,
    isHttpStatusCode403,
    //...
]);
    

As this function takes two parameters it cannot be passed as a Node type, instead this function must be wrapped in another function to pass as a node and be used as a tree branch:


isHttpStatusCode(Map blackboard) => select(blackboard, [
    isHttpStatusCode400,
    isHttpStatusCode401,
    isHttpStatusCode402,
    isHttpStatusCode403,
    //...
]);

Features and bugs

For any feature requests, bugs or questions feel free to email or message me on twitter. All feedback is valued.

Libraries

behaviour_tree

The functional_behaviour_tree library.