Artificial Intelligence

Fast links for other parts and tutorials:

If you’re looking for actual code to use, check it out:


In these days, I’ve being developing a Behavior Tree (BT) library in JavaScript, including the core structures of BTs, a visual editor and a visual debugger. In this post, the first part of two, I will explain my implementation choices of the core structure, which is almost finished in my library, and by the end of this series you will have an example code of fully functional behavior tree with some basic nodes.

*Notice that, you can translate the code here from JavaScript to any language.

Before any code, I’ve defined some objectives (the must-have) of the implementation:

  • Must be easy to connect the tree to a visual debugger (during the tick signal, the debug must know which node is executing);
  • The tree must know the open nodes from last tick (so it can close previous open nodes that weren’t called in the current tick);
  • Must be easy to load and save the tree in a JSON format (this is important because the visual editor will also save and load the tree as a JSON);
  • Nodes must have, at least, a function for events: open, tick, and close. The open function is only called before the tick function and only if the node is closed (if it returned RUNNING the last tick, the node is still open). In the tick function, a node will perform some computation. The close function will be called after the tick function and only if the node returned SUCCESS, FAILURE or ERROR (or if the tree force it);

After several implementations with different design choices, I came up with a fairly decent architecture for BTs, which can be seem in the figure below. This architecture will be explained in detail during this post, so don’t worry to understand it all right now.

bt_architecture

I’ve decided that, the tree and the nodes will not store a reference to a target object (e.g., an NPC instance or a monster instance) nor variables related to the execution of the tree or of the node (e.g., a list of opened nodes or the last child to return a RUNNING state), they will only store structural information (e.g, reference to the children) – Suppose you have 1000 NPCs in a game that share the same behaviors (e.g., villagers or pack of evil goblins), with this design choice, a single instance of the tree will control all the thousand agents.

Now, the execution information must be stored somewhere else. For this, we will create a Blackboard structure, which will serve to us as individual memory to our agents, thus, each one of the 1000 NPCs in the example above will have a different Blackboard instance.

In this architecture, I don’t see the needed to have multiparenting (explained here). The multiparenting implementation seems too complex and the outcome seems too low (not sure, but I think large trees will not consume that much memory with this architecture; later I will test if this is true and benchmark the multiparenting feature).

Constants and Helpers

Starting the code. First of all, we have to define some constants to represent the state values. I’m using the states SUCCESS, FAILURE, RUNNING, and ERROR, as described here.

// NODE STATES ================================================================
var SUCCESS   = 1;
var FAILURE   = 2;
var RUNNING   = 3;
var ERROR     = 4;

// GLOBAL & UTILITY FUNCTIONS =================================================
var createUUID = function() {
    var s = [];
    var hexDigits = "0123456789abcdef";
    for (var i = 0; i < 36; i++) {
        s[i] = hexDigits.substr(Math.floor(Math.random() * 0x10), 1);
    }
    // bits 12-15 of the time_hi_and_version field to 0010
    s[14] = "4";

    // bits 6-7 of the clock_seq_hi_and_reserved to 01
    s[19] = hexDigits.substr((s[19] & 0x3) | 0x8, 1);

    s[8] = s[13] = s[18] = s[23] = "-";

    var uuid = s.join("");
    return uuid;
}

Notice that I also included the function createUUID . This function will be used to create unique IDs for our objects (consult this if you want to know more about how UUID works).

Blackboard

So, the Blackboard will be the memory structure for our agents, which will be used by the tree to access the execution variables. The Blackboard must differentiate global information, accessed by any node in the tree, by the agent, or even other trees (yeah, with this implementation, you may use different trees to control the same agent using the same memory); per tree information, accessed only by the nodes in the same tree or the tree instance itself (e.g, a list of open nodes from last tick); and per node per tree information, accessed only by the node that wrote the information (e.g., a flag telling if the node is open or not).

var Blackboard = function() {
    this.initialize();
}
Blackboard.prototype.initialize = function() {
    this._baseMemory = {}; // used to store global information
    this._treeMemory = {}; // used to store tree and node information
}

Blackboard.prototype._getTreeMemory = function(treeScope) {
    if (!this._treeMemory[treeScope]) {
        this._treeMemory[treeScope] = {
            'nodeMemory'         : {},
            'openNodes'          : [],
        };
    }
    return this._treeMemory[treeScope];
};

Blackboard.prototype._getNodeMemory = function(treeMemory, nodeScope) {
    var memory = treeMemory['nodeMemory'];
    if (!memory[nodeScope]) {
        memory[nodeScope] = {};
    }

    return memory[nodeScope];
};

Blackboard.prototype._getMemory = function(treeScope, nodeScope) {
    var memory = this._baseMemory;

    if (treeScope) {
        memory = this._getTreeMemory(treeScope);

        if (nodeScope) {
            memory = this._getNodeMemory(memory, nodeScope);
        }
    }

    return memory;
};

Blackboard.prototype.set = function(key, value, treeScope, nodeScope) {
    var memory = this._getMemory(treeScope, nodeScope);
    memory[key] = value;
};

Blackboard.prototype.get = function(key, treeScope, nodeScope) {
    var memory = this._getMemory(treeScope, nodeScope);
    return memory[key];
};

The Blackboard class only defines two public methods: set  and get . Notice that, both receive the parameters treeScope and nodeScope, these parameters will be used to define the memory context (global if both aren’t provided, per tree if only treeScope is provided, or per node per tree is both are provided).

Both,  set  and get , are pretty simple, only get the contextual memory object and store/retrieve values to/from it. The _getMemory  will decide which memory will be used, depending on parameters.

Also notice that, the _getTreeMemory  and _getNodeMemory  methods will create a new object inside the tree memory if it doesn’t exist. The object used as memory is a common Object in JavaScript, but in other languages you can use dictionaries (also called hash tables or hash maps).

Tick

Nodes do not need to have a reference to their parents, only to their immediate children, in the same way, the tree will only know the root node. In order to tell nodes in which tree their are, and make references of the target and the blackboard visible to them, We will use a Tick object. This object will be created by the tree, will store the references, and will be propagated to the nodes during the tick.

var Tick = function() {
    this.initialize();
}

Tick.prototype.initialize = function() {
    this.tree       = null;
    this.openNodes  = [];
    this.nodeCount  = 0;
    this.debug      = null;
    this.target     = null;
    this.blackboard = null;
}

Tick.prototype.enterNode = function(node) {
    this.nodeCount++;
    this.openNodes.push(node);
    // call debug here
}

Tick.prototype.openNode = function(node) {
    // call debug here
}

Tick.prototype.tickNode = function(node) {
    // call debug here
}

Tick.prototype.closeNode = function(node) {
    // call debug here
    this.openNodes.pop();
}

Tick.prototype.exitNode = function(node) {
    // call debug here
}

The Tick is also used to:

  • Store the list of current open nodes and count the number of nodes ticked during the traversal;
  • Send the activation signals to debug (as commented in the code);

The tick have some methods that will be called by the node objects. See below the BaseNode  definition, to know more.

BehaviorTree

The tree must keep a list of open nodes of the last tick, in order to close them if another branch breaks the execution (e.g., when a priority branch returns RUNNING.). After each tick, the tree must close all open nodes that weren’t executed.

var BehaviorTree = function() {
    this.initialize();
}

BehaviorTree.prototype.initialize = function() {
    this.id          = createUUID();
    this.root        = null;
}

BehaviorTree.prototype.tick = function(target, blackboard) {
    /* CREATE A TICK OBJECT */
    var tick = new Tick();
    tick.target     = target;
    tick.blackboard = blackboard;
    tick.tree       = this;

    /* TICK NODE */
    this.root._execute(tick);

    /* CLOSE NODES FROM LAST TICK, IF NEEDED */
    var lastOpenNodes = blackboard.get('openNodes', this.id);
    var currOpenNodes = tick.openNodes.slice(0);

    // does not close if it is still open in this tick
    var start = 0;
    for (var i=0; i<Math.min(lastOpenNodes.length, currOpenNodes.length); i++) {
        start = i+1;
        if (lastOpenNodes[i] !== currOpenNodes[i]) {
            break;
        } 
    }

    // close the nodes
    for (var i=lastOpenNodes.length-1; i>=start; i--) {
        lastOpenNodes[i]._close(tick);
    }

    /* POPULATE BLACKBOARD */
    blackboard.set('openNodes', currOpenNodes, this.id);
    blackboard.set('nodeCount', tick.nodeCount, this.id);
};

The tree definition is also pretty simple, it only have one method, called tick. The tick method receives a reference to the target object and another to the target blackboard as parameter. With these references, it creates a Tick object and propagate it to the root node, and just waits for the root to return the status. After propagating the tick signal, the tree closes all open nodes from the last tick that weren’t called in the current one (the last open nodes list is stored in the blackboard while the current open node list is created by Tick during the propagation). Finally, the tree saves the list of open nodes in the blackboard.

BaseNode

All nodes will inherit from a BaseNode . This class will implement a execution method that will call all “interface” methods:

  • Enter: called every time a node is executed;
  • Open: called only when the node is opened (when a node returns RUNNING, it will keep opened until it returns other value or the tree forces the closing);
  • Tick: the real implementation of the node (e.g., the composite nodes will call their children in this method);
  • Close: called when a node return SUCCESS, FAILURE or ERROR, or when the tree forces the node to close;
  • Exit: called every time at the end of the node execution.

The user can create new nodes by inheriting the BaseNode and overriding the interface methods.

var BaseNode = function() {
    this.initialize();
}

BaseNode.prototype.initialize = function(children) {
    this.id          = createUUID();

    this.children = [];
    if (children) {
        for (var i=0; i<children.length; i++) {
            this.children.push(children[i]);
        }
    }
}

BaseNode.prototype._execute = function(tick) {
    /* ENTER */
    this._enter(tick);

    /* OPEN */
    if (!tick.blackboard.get('isOpen', tick.tree.id, this.id)) {
        this._open(tick);
    }

    /* TICK */
    var status = this._tick(tick);

    /* CLOSE */
    if (status !== RUNNING) {
        this._close(tick);
    }

    /* EXIT */
    this._exit(tick);

    return status;
}

// Wrapper functions
BaseNode.prototype._enter = function(tick) {
    tick.enterNode(this);
    this.enter(tick);
}
BaseNode.prototype._open  = function(tick) {
    tick.openNode(this);
    tick.blackboard.set('isOpen', true, tick.tree.id, this.id);
    this.open(tick);
}
BaseNode.prototype._tick  = function(tick) {
    tick.tickNode(this);
    return this.tick(tick);
}
BaseNode.prototype._close = function(tick) {
    tick.closeNode(this);
    tick.blackboard.set('isOpen', false, tick.tree.id, this.id);
    this.close(tick);
}
BaseNode.prototype._exit  = function(tick) {
    tick.exitNode(this);
    this.exit(tick);
}

// Override these to create nodes
BaseNode.prototype.enter = function(tick) {}
BaseNode.prototype.open  = function(tick) {}
BaseNode.prototype.tick  = function(tick) {}
BaseNode.prototype.close = function(tick) {}
BaseNode.prototype.exit  = function(tick) {}

Notice that, there is a wrapper method for all interface methods, they are used to update the isOpen  flag in the blackboard and call the Tick methods.

To be continued…

In the next post, I will show the implementation of some basic nodes and examples of use of this tree.

Read more

This post is the third and last part of the Introduction to Behavior Trees series. This part explains some implementation details of BTs.

Fast links for other parts and tutorials:

If you’re looking for actual code to use, check it out:


Decorator Examples

Inverter

Like the NOT operator, the inverter decorator negates the result of its child node, i.e., SUCCESS state becomes FAILURE, and FAILURE becomes SUCCESS. Notice that, inverter does not change RUNNING or ERROR states, as described in algorithm below.

state = Tick(child)

if state == SUCCESS:
    return FAILURE
else if state == FAILURE:
    return SUCCESS
else
    return state

 Succeeder

Succeeder is a decorator that returns SUCCESS always, no matter what its child returns. This is specially useful for debug and test purposes. The algorithm below shows the pseudo-code for this node.

state = Tick(child)

return SUCCESS

 Failer

Inverse of suceeder, this decorator return FAILURE for any child result, as shown below.

state = Tick(child)

return FAILURE

 Repeater

Repeater decorator sends the tick signal to its child every time that its child returns a SUCCESS or FAILURE value, or when this decorator receives the tick. Additionally, a maximum number of repetition can be provided.

while j < M:
   state = Tick(child)
   if state != SUCCESS and state != FAILURE:
       return state

   j++

return SUCCESS

 Repeat Until Fail

This decorator keeps calling its child until the child returns a FAILURE value. When this happen, the decorator return a SUCCESS state.

repeat
    state = Tick(child)
    if state != SUCCESS and state != FAILURE:
       return state

until state == FAILURE

return SUCCESS

Repeat Until Succeed

Similar to the previous one, this decorator calls the child until it returns a SUCCESS.

repeat
    state = Tick(child)
    if state != SUCCESS and state != FAILURE:
       return state

until state == SUCCESS

return SUCCESS

Limiter

This decorator imposes a maximum number of calls its child can have within the whole execution of the Behavior Tree, i.e., after a certain number of calls, its child will never be called again. The limiter pseudo-code is described in algorithm below.

if totalCalls < C_max:
   state = Tick(child)
   totalCalls++;

   return state

return FAILURE

Max Time

Max Time limits the maximum time its child can be running. If the child does not complete its execution before the maximum time, the child task is terminated and a failure is returned, as shown algorithm below.

if totalTime < T_max:
    state = Tick(child)
    return state
else:
    Stop(child)
    return FAILURE

Prioritizing Behaviors

Considering the composite nodes described in the previous post, the Behavior Tree traversal is performed with a dynamic depth-first algorithm (notice that, except by Parallel node, all composite nodes run a child at a time and run orderly from left to right). This procedure allows a definition of priority among behaviors in the tree: the left branch of the tree (starting from the root) contains the high-priority behaviors while the right branch contains the low-priority behaviors.

In order to exploit this, the designer must put important behaviors such as auto-preservation and collision avoidance at the left branches and low-priority behaviors such as idle or rest at the right branches. Notice that, depending on the agent, may be necessary to add an unconditional behavior as the lowest-priority in order to keep the tree executing at least this behavior.

Treating Running States

One common question when implementing a Behavior Tree is that: what to do in the next tick after a node returned a running state? There are two answer to it: starting the graph traversal from the running node or starting it over from the first node.

The major drawback of starting the tick at the node that returned the running state is that this node can take too much time running an action and, thus, avoiding the execution of most important behaviors. For instance, suppose a robot performing an action to follow a certain path; in the half way the robot finds a hole, but it cannot avoid it because the tree is running the action of path following.

Therefore, the best option is always start over the tree, and if a most-important behavior wants to run, the previous node stops.

Composite Node Extensions

Node*: Remembering Running Nodes

When we start the tree traversal at the root every tick, even after some node returned a running state, we can fall at the following situation. Suppose an agent performing a patrol behavior, which is illustrated by the figure below. Now suppose that the agent completed the first action (“go to point A”) at the tick 1 and then, the second action (“go to point B”) is started, returning a running state. At tick 2, the traversal starts from the top and reach the first action again, which will send the robot again to point A, thus, never completing the second action and never even calling the third one.

problem_running

The * extension over the Priority and Sequence nodes overcome this problem by recording the last child that returned RUNNING. The figure below shows the same example above but now using a sequence with * extension. After completed the first action (“go to point A”), the second action (“go to point B”) is executed and returned RUNNING state. In the next tick, the sequence node do not execute the first action, but jumps directly to the second one.

problem_running_2

This extension is only valid for the Sequence and Priority nodes. Parallel node does not suffer from the problem cited here, because it don’t execute its children sequentially but concurrently.

for i = lastRunning to N:
    state = Tick(child[i])

    if state != FAILURE:
        return state

return FAILURE
for i = lastRunning to N:
    state = Tick(child[i])

    if state != SUCCESS:
        return state

return SUCCESS

Node~: Probabilistic Choice

When an agent performs exactly the same sequence of actions given a particular situation, the agent may become predictable. The simplest way to avoid the predictability is to using random choices on some nodes. For example, an agent with a grasp behavior can randomly choose left or right hand to grasp some object.

The ~ extension allows Sequence and Priority nodes to randomly choose its children, instead of sequentially select them. The ~ nodes randomly choose one of its children to execute, then ignore the selected ones and choose other until all children were selected.

problem_random

A common use of this extension is to choose children with equiprobable distribution, but it can use other distributions by weighting the choices.

for i = 1 to N:
    selectedChild = RandomlyChoose(child)
    state = Tick(selectedChild)

    if state != FAILURE:
        return state

return FAILURE
for i = 1 to N:
    selectedChild = RandomlyChoose(child)
    state = Tick(selectedChild)

    if state != SUCCESS:
        return state

return SUCCESS

 Multi-Parenting

Behavior Trees provide the advantage of allowing reuse of conditions, actions or even subtrees. The reuse of subtrees can be done in two ways: creating a new instance of the branch or using the same branch but with multiple parents. Duplicating subtrees have a major drawback in the memory usage, because it consumes more memory than necessary to represent the same thing, specially when duplicating large subtrees. On the other hand, multiple parents save memory but prejudice the visualization of the tree, decreasing readability.

The solution to this problem is to use a hybrid approach: the duplication of the subtrees happens only in the level of control and visualization while multi-parenting is used in the level of implementation and execution. Notice that, the duplication of the subtrees is only virtual and does not apply to the real structure of the tree.

Handling Persistent Data

Autonomous intelligent agents, whether virtual or real, need an internal state to store its belief about the world. These beliefs may include information from its perception system (e.g., last known position of the enemy; last known position of the allies; etc.) and other computed information (e.g., world position).

Similarly, some actions in Behavior Tree may need to store information (e.g., total time running the child node; time since last action; total failures; etc.), but we do not want to add this inside the node because it would be attached to a specific agent, therefore, obligating the use of a different tree for all agents. Running a different tree for each agent is a waste of resources and may be impractical.

problem_memory

A common approach to fulfill the requirement for persistent data is using memory pools, which can be used to store information about the world and allow behaviors to read and write new information on it. Notice that, this memory pools are individually maintained for each agent, thus allowing to share a single Behavior Tree for hundreds of agents.

Read more

This is the second part of the tutorial on Behavior Trees for games and robotics.

Fast links for other parts and tutorials:

If you’re looking for actual code to use, check it out:


The Behavior Tree (BT) was born in the game industry and was quickly adopted and adapted by game developers around the world. However, the formalism required by the academy was developed later, mainly because its use in robotics. The lack of documentation and formalism, in conjunction with the fast adaptation of the BT, resulted in inconsistencies (of names, structure and definition) among papers and tutorials, for both robotics and games. We follow the definition of (Marzinotto, 2014)  and (Ogren, 2012) to describe how a Behavior Tree is structured and how it works.

As discussed in the previous post, Behavior Trees provide some improvements over the Finite State Machines, having some advantages such as:

  • maintainability: transitions in BT are defined by the structure, not by conditions inside the states. Because of this, nodes can be designed independent from each other, thus, when adding or removing new nodes (or even subtrees) in a small part of the tree, it is not necessary to change other parts of the model.
  • scalability: when a BT have many nodes, it can be decomposed into small subtrees saving the readability of the graphical model.
  • reusability: due to the independence of nodes in BT, the subtrees are also independent. This allows the reuse of nodes or subtrees among other trees or projects.
  • goal-oriented: although the nodes of BT are independent, they are still related due to the tree structure of the model. This allows the designer to build specific sub-trees for a given goal without losing  flexibility of the model.
  • parallelization: BT can specify parallel nodes which run all children at the same time without losing the control of the model execution. This is possible because the parallelization is locally contained to the parallel node.

Despite the name, the Behavior Tree is actually defined as a directed acyclic graph, because a node can have many parents. This structure may not be found in some papers but it have some advantages in the reusability and performance. The multi-parenting will be discussed in the part 3 of this post.

The model is composed of nodes and edges. For a pair of nodes connected by an edge, the outgoing node is called the parent and the incoming node is the child. There is no limit of how much children a node can have. The child-less nodes are called leaves while the parent-less node is called root; the nodes that stand between the root and the leaves can be of two types, composite or decorator nodes. Each subtree defines a different behavior, which can be simple ones (composed of few nodes) or complex behaviors (composed of a large number of modes).

The root of the BT generates a signal (called tick) periodically following a frequency f. The tick is propagated through the tree branches according to the algorithm defined by each node type. When the tick reaches a leaf, the node perform some computation and return a state value SUCCESS, FAILURE, RUNNING or ERROR). Then the returned value is propagated back through the tree according to each node type. The process is completed when a state value is returned to the root. Notice that, the tick frequency of the tree is independent of the control loop frequency of the
agent.

Node Types

The nodes types are divided into 3 categories: composite, decorator or leaf, which are described in detail below. In the nodes description, I present a graphicall example of how to use a node in a real situation and I also present their algorithms. The algorithms may use the Tick function in the statement Tick(child[i]), which triggers the algorithm corresponding to the i-th child node.

Leaf Nodes

The leaf nodes are the primitive building blocks of the behavior tree. These nodes do not have any child, thus, they do not propagate the tick signal, instead, they perform some computation and return a state value. There are two types of leaf nodes (conditions and actions) and are categorized by their responsibility.

Conditions

A condition node checks whether a certain condition has been met or not. In order to accomplish this, the node must have a target variable (e.g.: a perception information such as “obstacle distance'” or “other agent visibility”; or an internal variable such as “battery level” or “hungry level”; etc.) and a criteria to base the decision (e.g.: “obstacle distance > 100m?” or “battery power < 10%?”). These nodes return SUCCESS if the condition has been met and FAILURE otherwise. Notice that, conditions do not return RUNNING nor change values of system. Graphically, condition nodes are presented by gray ellipsis, as shown in the image below.

 node_condition

Actions

Action nodes perform computations to change the agent state. The actions implementation depends on the agent type, e.g., the actions of a robot may involve sending motor signals, sending sounds through speakers or turning on lights, while the actions of a NPC may involve executing animations, performing spacial transformations, playing a sound, etc.

Notice that action may not be only external (i.e, actions that changes the environment as result of changes on the agent), they can be internal too, e.g., registering logs, saving files, changing internal variables, etc.

An action returns SUCCESS if it could be completed; returns FAILURE if, for any reason, it could not be finished; or returns RUNNING while executing the action. The action node is represented as a gray box, as shown in the figure below, which presents 4 different example actions.

node_action

Composite Nodes

A composite node can have one or more children. The node is responsible to propagate the tick signal to its children, respecting some order. A composite node also must decide which and when to return the state values of its children, when the value is SUCCESS or FAILURE. Notice that, when a child returns RUNNING or ERROR, the composite node must return the state immediately. All composite nodes are represented graphically as a white box with a certain symbol inside.

Priority

The priority node (sometimes called selector) ticks its children sequentially until one of them returns SUCCESS, RUNNING or ERROR. If all children return the failure state, the priority also returns FAILURE.

For instance, suppose that a cleaning robot have a behavior to turn itself off, as shown in the figure below. When the robot try to turn itself off, the first action is performed and the robot try to get back to its charging dock and turn off all its systems, but if this action fail for some reason (e.g., it could not find the dock) an emergency shutdown will be performed.

node_selector

for i = 1 to N:
    state = Tick(child[i])

    if state != FAILURE:
        return state

return FAILURE

 Sequence

The sequence node ticks its children sequentially until one of them returns FAILURE, RUNNING or ERROR. If all children return the success state, the sequence also returns SUCCESS.

The figure below presents an example of the sequence node in a behavior that can be part of a real unmanned aerial vehicle (UAV) or a jet plane in a war game. In this behavior, the agent first verify if there is a missile following it, if it is true, the agent fires flares and then performs an evasive maneuver. Notice that, if there is no missile, there is not reason to fire flares nor to perform an evasive maneuver.

node_sequence

for i = 1 to N:
    state = Tick(child[i])

    if state != SUCCESS:
        return state

return SUCCESS

 Parallel

The parallel node ticks all children at the same time, allowing them to work in parallel. This node is a way to use concurrency in Behavior Trees. Notice that, using this node, the parallelization is contained locally, avoiding losing control of the execution flow as happens on the FSM.

Parallel nodes return SUCCESS if the number of succeeding children is larger than a local constant S (this constant may be different for each parallel node); return FAILURE if the number of failing children is larger than a local constant F; or return RUNNING otherwise.

As an example of use of a parallel node, consider an agent that is an intelligent house (real or virtual). The house have a behavior to turn the lights on and play music when it identifies that a human just entered the room.

node_parallel

for i = 1 to N:
    state_i = Tick(child[i])

if nSucc(state) >= S:
    return SUCCESS
else if nFail(state) >= F:
    return FAILURE
else
    return RUNNING

Decorator Nodes

Decorators are special nodes that can have only a single child. The goal of the decorator is to change the behavior of the child by manipulating the returning value or changing its ticking frequency. For example, a decorator may invert the result state of its child, similar to the NOT operator, or it can repeat the execution of the child for a predefined number of times. The figure below shows an example of the decorator “Repeat 3x”, which will execute the action “ring bell” three times before returning a state value.

node_decorator

There is no default algorithm for decorators, it depends on their purpose. Next post I will present some common decorators used in games.

State Values

Following the definition proposed in (Champanard, 2012), we consider four different values for the node states:

  • SUCCESS: returned when a criterion has been met by a condition node or an action node has been completed successfully;
  • FAILURE: returned when a criterion has not been met by a condition node or an action node could not finish its execution for any reason;
  • RUNNING: returned when an action node has been initialized but is still waiting the its resolution.
  • ERROR: returned when some unexpected error happened in the tree, probably by a programming error (trying to verify an undefined variable). Its use depends on the final implementation of the leaf nodes.

 

Read more

This post is actually part of the first draft of a report I’m doing for my PhD. My idea in PhD is to use Behavior Trees for both games and robotics, thus you will see some references and examples using robots here.

Fast links for other parts and tutorials:

If you’re looking for actual code to use, check it out:


 

The field of digital games and robotics have a common goal: to develop intelligent artificial agents to interact with the environment (whether real or virtual) and to interact with other agents (whether human or not).

In robotics, the robots are mechanical agents which act autonomously in real environments, such as houses, industries, farmlands or even in traffic. These agents have sensors and actuators to feel the entities of the environment and to interact with them. Robots can be used for different purposes, such as: to perform tasks dangerous for humans; to work in inaccessible places such as wreckage and pipes; to perform repetitive and mechanical tasks; to entertain people or to be used as a companion; among others. The actuators that the robot has and the actions it can perform depends on the environment and its goal. A robot that cleans the floor, for example, only need sensors to identify obstacles (such as walls, furniture, animals or people) and actuators to clean the floor (such as vacuum cleaners, brushes and cloths).

In games, an agent can be an object, a creature, a person, or even a system acting in the virtual world. Depending on the genre, mechanics and goal of the game, virtual agents may be desirable for several reasons, such as: to provide enemies and allies to the player and, thus, creating content to the game; to create intelligent entities that complement the virtual world, making the player experience more immersive; to create characters able to get the player’s empathy. In general, a virtual agent may interact with humans (as avatars in the game) or other artificial agents. Autonomous intelligent agents in games are called NPCs (non-playable characters) and, like robots, the sensors and action mechanisms of these agents varies accordingly to the environment and to its purpose. An NPC can, for example, be a potion seller human that simply stands in the city waiting for the player click on it or it can also be a companion cat that follows the player in every corner of the world and protects it when he or she is in danger.

Behaviors

To develop intelligent agents, it is necessary to build a vast repertoire of behaviors. Behavior involves controlling various actions over a period of time. For instance, imagine an action game where NPCs have a behavior of self-preservation. To perform this behavior, a NPC should check if it is in danger (e.g., below 10% of life), if true, the NPC performs actions to run away from the player. The number of behaviors that an agent can use indicate the number of different situations it can recognize and respond, such that an agent with few behaviors is more repeatable and predictable than an agent with many behaviors.

It is also important that the method used to control the agents also allows efficient coordination of behaviors, so that an agent can achieve its goal effectively, i.e., without performing random, unnecessary actions (a domestic robot with full battery does not need to change) or foolish actions (in battles a NPCs cannot stop to sell items).

Intelligent agents with large repertoires of effective behaviors make the experience in the interaction with humans more interesting, in both robotics and games. In addition, in games, these agents do not frustrate the player, allowing a greater immersion into the game. However, these results have a cost in the form of complexity, such as:

  • speed: many behaviors means high memory usage to keep them and high CPU usage to execute them. In robotics, the agents must respond quickly enough to not cause accidents or bother people (people do not want to wait too much only to robot understand a simple voice command) but they have major limitations of processing, memory and energy (depending on the type of the robot). In games, you may have plenty of these resources (depending on the device running the game), but they are divided among other modules of the game (in which the graphic rendering takes the most part of the resources).
  • transparency & reliability: developers must have total control over the agent actions. He or she must be able to debug and to know, in a relatively easy way, the internal state of the agent, being able to predict approximately its future actions. This requirement is particularly important for safety reasons. Losing control of what the agent does and when it should perform the behaviors can cause many problems. Robots can cause serious accidents (depending on the type and functions of the robot, it can even be a risk to the lives of human beings). Agents without control in games can ruin the player experience and impact on sales. Thus, the amount of behaviors can make the development harder and may result in an unreliable system.

Finite State Machines

Finite State Machine (FSM) is a widely used technique to implement and coordinate these behaviors. Each agent behavior is described in the model as a state and can be represented graphically as in the example below. Each state has transition conditions and the execution logic contained on it. Only one state can be running at at time and it is called the current state. A state only ceases to be the current one when it passes the execution to another state. The etransitions occurs only within the current state, i.e., the current state is who decides whether the transition will occur or not.

fsm_seal

FSM is a graphical model that allows an easy modeling of the agent behaviors and an easy understanding of the model. Furthermore, it is computationally efficient, since all changing conditions are inside the current state and no other state run simultaneously. However, FSM has big problems in real applications:

  • maintainability: when adding or removing a behavior, it is necessary to change the conditions of all other states that have transition to the new or old one. Big changes are more susceptible to errors that may pass unnoticed.
  • scalability: FSMs with many states lose the advantage of graphical readability, becoming a nightmare of boxes and arrows. Furthermore, higher the model, harder is to maintain it.
  • reusability: as the conditions are inside the states, the coupling between the states is strong, being practically impossible to use the same behavior in multiple projects.
  • goal-oriented: the FSM works as a Markovian process, i.e., knowing that a state is active, it is independent of the previous states. This causes a difficulty to coordinate states of the FSM to achieve different and variable goals.
  • parallelization: trying to run states in parallel on FSMs is a very big challenge, usually needing external modules to resolve conflicts and deadlocks.

Remarks

In 2005, the Behavior Tree (BT) was created to address the problem of control and decision making of NPCs in games, in a more efficient way compared to FSMs, and since then, BTs have been replacing FSMs in various segments, including robotics. In the next post, I will define what is exactly a Behavior Tree and explain what are its advantages and, step-by-step, how its works.

Read more