An Introduction to Behavior Trees – Part 1

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.

One Comment, RSS

  1. […] are Behavior Trees? An Introduction to Behavior Trees Implementing a Behavior Tree Behavior Trees for AI – How They Work Second Generation Behavior […]

Your email address will not be published. Required fields are marked *

*