An ever growing field of study in coding is the use of AI in a variety of settings. As this field evolves new techniques are discovered and used to design the desired behavior for AI agents in any given situation. While there are plenty of unique techniques, one of the more commonly known ones is the use of behavior trees to outline AI behavior. Behavior trees provide a relatively simple and versatile method for designing AI behavior that has a large flexibility in where and how it can be used. Despite some notable concerns with behavior trees, they are an extremely effective way for designing simple and complex AI behavior. When discussing behavior trees it is important to understand just what a behavior tree is. As described in AI for Games, behavior trees are, “A synthesis of a number of techniques that have been around in AI for a while: Hierarchical State Machines, Scheduling, Planning, and Action Executions.”(Millington, 2019). While not the most beneficial definition, this does describe the various aspects of a behavior tree fairly effectively. However, the major difference between using a hierarchical state machine versus a behavior tree provides the most beneficial aspect of defining behavior trees. This difference is in what the main building block for the structure is, tasks. A hierarchical state machine will use various states to define AI behavior, meanwhile, behavior trees use tasks in determining AI behavior. Tasks themselves can be a variety of things ranging from finding a variable’s value to executing an action such as shooting. Behavior trees themselves, are structured as directed rooted trees where nodes are either a control flow node or an execution node with individual tasks being represented as sub-trees designed to represent more complex actions. (Millington, 2019; Colledanchise et al., 2015). Despite the simple definition of what a task is there are numerous types of tasks that are used when building behavior trees. For simplicity sake, the four primary types used in the tech demo will be addressed: Conditions, Actions, Composites, and Decorators. Before moving on to define these terms one of the most essential aspects of behavior trees needs to be discussed, node statuses. When executing the various tasks in a behavior tree three different statuses are defined to help control the flow of a given tree: Running, Success, and Failure. The running status, as the name implies, returns to the parent node the status of running when the execution of the task has not finished. Similarly, success is returned when a task has achieved its goal and failure when the goal was not achieved.(Zhang et al., 2018). Each type of task uses either some or all of these statuses when defining what they are meant to achieve. With this understanding of statuses it is time to move on to defining the different types of tasks one might see when using behavior trees starting with Condition tasks. Condition tasks are fairly simple in their purpose in that they are meant to test a condition and whether or not it has been satisfied.(Zhang et al., 2018). These conditions being tested can be a variety of things including, but not limited to, testing proximity or the amount of health a character has. Each Condition being tested is meant to be a separate task within the tree and will only ever return success or failure statuses based on whether or not the given condition has been met. Following Condition tasks are Actions, which similarly have a variety of uses. Actions themselves are tasks that alter the state of the game or run a primitive behavior when not used in games. (Millington, 2019). Examples of Actions in games would include making AI take cover when being shot at, playing a bit of audio, or running a specific animation. Similar to Conditions, individual Actions are considered different tasks within a behavior tree. However, unlike Conditions, Actions are able to return success, failure, and running statuses. It is important to note that while Actions can return failure statuses this can be avoided by using a Condition before the Action to ensure it will run successfully when called. (Figure 1) Figure 1 provides an example of a basic behavior tree that uses two types of Composite tasks, a Selector and two Sequences that will be described later, and a mixture of Conditions and Actions. When represented in a behavior tree Conditions and Actions are the leaf nodes of the tree and in this specific case the Condition task checks to see if a door is open and if it is then the Action task is used where the character moves into the room. If the door is not open, the right side of the tree is used in which three Actions are used where the character will move to the door, plan an animation to open the door, and finally move into the room. Conditions and Actions have similar uses in other techniques such as state machines, however, they differ from their use in other techniques through the use of a single common interface for all tasks. Essentially, this means that the different Conditions and Actions can be combined without any of them needing to know what else is in the given behavior tree.(Millington, 2019). Moving on from Condition and Action tasks, Composite tasks generally represent the majority of the body of a behavior tree. There are numerous types of Composite tasks with two fo the more frequently used being Selectors and Sequences, but the general purpose of a Composite is to keep track of a collection of child tasks made up of Conditions, Actions, or other Composites with their behavior being based on the behavior of their children.(Millington, 2019). Typically, behavior trees will have a significantly smaller number of Composites compared to Conditions and Actions because the groupings under Composites can create complex behaviors. As mentioned earlier, two of the most common Composites are Selectors and Sequences. The purpose of a Selector is to determine the first set of successful Actions that can be achieved among its children. Selectors will cycle through their various children until a success or running statuses is returned by a child in which case the Selector will return the same status. If the Selector runs out of children to check before a success or running status is returned then the Selector will return a failure status. (Figure 2) Figure 2 provides a simple example of a Selector in action. The Selector itself is represented as a circle with a question mark in the middle although this representation can vary depending on the person and has also been shown as a box with a question mark. In this specific case, the Selector starts with trying to run an attack Action. If this Action fails then it will attempt to taunt or stare if the taunt also fails. The second type of Composite tasks are Sequences. Sequences consist of a series of children representing different tasks that need to be undertaken successfully for the Sequence itself to be successful. As long as the children of a Sequence succeed the Sequence will continue to run until either all the children have returned successful statuses or one of the children failed, which will cause the Sequence to also return a failure status and no longer check the remaining children if there are any. (Figure 3) Figure 3 shows a simple example of a Sequence task in action. In this case, the Sequence node is represented as a box with an arrow in it. The Sequence itself contains a Condition to see if there is a visible enemy that returns a success if there is. As long as this initial Condition is successful the following children will execute, which are Actions that will turn the character away followed by making the character run away from the enemy.(Millington, 2019). Looking back to figure 1, it is easier to understand the overall functionality of the behavior tree shown. A Selector is used to determine which of the Sequences should be used with the first Sequence checking a Condition to determine if the door is open followed by the Action of moving into the door. However, if the Condition fails the Sequence will return a failure to the Selector, which will move onto the next Sequence that runs a series of Actions to move to the door, run an animation to open the door, and ultimately move inside the door. The final type of task that is typically used in behavior trees is a Decorator. Decorators are similar to Composites in that they have children, however, unlike a Composite a Decorator will only have a single child. The Decorator itself can have a variety of functions, but it ultimately will modify the behavior of the child in some way.(Millington, 2019; 2014, July 18). There are numerous purposes for a Decorator in a behavior tree ranging from using them as filters to prevent a child behavior from being used repeatedly or cause it to be used repeatedly to using an Inverter to invert the result of the child. (Figure 4) Figure 4 represents a character’s behavior and how it will react to an enemy around it. The figure starts with a Selector that moves to a Sequence that determines if an enemy is visible. If the enemy is visible it will then move to the Decorator where until it fails the character will run a Sequence that runs the Condition to check if the enemy is conscious. While the enemy is conscious the character will hit the enemy, pause, then hit them again even if they have fallen conscious after the initial hit. Once the conscious Condition returns a failure the Decorator will end and the character will move to restrain finally sending a success status to the initial Selector. If the character had failed to spot an enemy at the start of the Sequence it would have returned a failure to the initial Selector before moving onto the next child which uses a Selector followed by a Sequence to determine if an enemy is in audible range causing the character to start creeping if it is. If the audible Condition fails then the Selector would move onto the move Action for the character(Millington, 2019). As the figure shows, Decorators can be used to create unique behaviors for a character that allow for a larger degree of creativity in how an AI will act at any given point. Hopefully it is clear now just how powerful behavior trees can be in creating unique AI with a variety of behaviors to enact at any given point in time. The large degree of flexibility these trees allow is extremely useful in a variety of settings and can be easily modified to perform any number of tasks using relatively minimal code. The variety of tasks described above and their subtypes allow for the relatively easy creation of AI elements to enhance any project. While behavior trees can’t or shouldn’t be used in all cases they do have a significant number of uses that make behavior trees a highly used technique for creating AI. Our demo uses a mixture of the aforementioned techniques to create a simple AI behavior for a shooter game. Our root/top node is a Selector that determines if the enemy should be in a shoot, chase, or run for cover Sequence. The shoot Sequence’s first node checks a Condition to see if the player is within firing range. If that returns a Success Status, then the enemy will perform the Shoot Action (which in this case is simply to turn green). The chase Sequence first checks a Condition to see if the player unit is within the chase range, and if it is it will perform the chase Action, which uses Unity’s navmesh functionality to path towards the player unit. The cover Sequence is the most complex part of our demo. The first node of the cover Sequence checks the health Condition and if the enemy’s health is less than a set amount, it will run the next node, which is the attempt to take cover Selector. This Selector will check the Condition if the enemy is currently behind cover, and if it is not then it will run the find cover Selector. The find cover Selector will either run the go to cover Sequence or the previously described chase Sequence, depending on the enemy’s health state. The go to cover Sequence will check if the cover is available Condition and then run the get to cover Action. The get to cover Action will path the enemies towards the “best” point behind one of our cover walls placed in the level. As previously mentioned, behavior trees have a great deal of versatility to them that allows for a large amount of area for application. For instance, in video games, Halo 2 was one of the first examples of a hugely successful AAA game that used behavior trees. Other examples in gaming include Bioshock, Spore, and many more. One of the benefits to using behavior trees is that they can be set up in such a way (oftentimes as visual coding) that designers or other team members could easily work on them for faster iteration. They have become so popular that widely used game engines such as Unreal have behavior tree systems built-in, and Unity has numerous user-made plugins that aid creation. Behavior trees are popular in video games but also used in other fields such as robotics as well. Behavior trees have a few limitations in the way tasks can be implemented (they don’t work well with “state-based behaviors”), but overall are very versatile, so they are used in many different genres of games. Behavior trees are highly adaptable allowing for use in nearly all platforms with exceptions only truly occurring with extremely complex trees. The performance of behavior trees is mostly limited by the tasks that it is performing, if all the tasks are O(1) then the tree will be O(n) in memory and O(logn) in speed, where n is the number of nodes in the tree (Millington, 2019). Nowadays behavior trees are beginning to fall out of favor and different techniques are being used. Newer games favor more complex AI with more lifelike and adaptable decision-making, and as such there are newer techniques, such as Utility AI, that more easily support the complex style of AI that is being implemented in newer and next-generation games (Rasmussen, 2016). A variety of references were used to create a better understanding of behavior trees and how they function in a variety of settings. Probably the most beneficial of these references was AI for Games Third Edition, by Ian Millington. Millington provides a basic description of what a behavior tree is as well as the numerous types of tasks that can be performed by a behavior tree such as Conditions, Actions, Composites, and Decorators. Each type of task consists of a fairly easy to understand description as well as numerous examples of how they would look in both pseudo code and figures to better illustrate their uses. In addition, Millington covers several different implementations of behavior trees that while not covered in this paper did provide for interesting reading material to help create a broader understanding of how behavior trees can be altered for a variety of uses. Another useful reference was the article Learning of Behavior Trees for Autonomous Agents, by Michele Colledanchise, Ramviyas Parasuraman, and Petter Ögren. This article focuses on the idea of using Genetic Programming to create optimal behavior trees that can play certain levels of Mario at various difficulties as an alternative to Finite State Machines. While behavior trees are not necessarily the primary focus of the article it does include a solid description of the basics of a behavior tree as well as different types of tasks that can be used in behavior trees such as Selectors, Sequences, Parallels, and Decorators. In addition, the article shows how behavior trees can be used to store knowledge gathered by learning algorithms to create the most optimized version of a behavior tree AI. A similar article to Colledanchise et al.’s referenced was Learning Behavior Trees for Autonomous Agents with Hybrid Constraints Evolution, by Qi Zhang, Jian Yao, Quanjun Yin, and Yabing Zha. This article proposes an alternative to using Genetic Programming with behavior trees to achieve more efficient learning and better solutions than Genetic Programming would allow. The suggested method is termed, evolving behavior trees with hybrid constraints. Overall, the article provides another good explanation of behavior trees as well as the various types of task nodes and how the different task nodes respond to the different types of statuses ie. Running, Failure, and Success. Instead of using Mario to test their generated behavior trees, they used Ms. Pac-Man to test the various behavior trees that were created through the learning algorithm they are suggesting. Ultimately, this article provides another unique purpose of behavior trees, how learning algorithms can be applied to optimize an AI’s behavior tree, while also providing a foundational knowledge of behavior trees and how the different types of tasks they use function. Another helpful article in creating a better understanding of various aspects of behavior trees was Behavior trees for AI: How they work, by Chris Simpson. This blog post discusses Simpson’s game Project Zomboid and how he used behavior trees to design the AI. The benefits from this blog post are similar to the other articles in that it provides a specific use example for behavior trees as well as general knowledge of various aspects of behavior trees. Additionally, this post provided examples of different types of Decorators and their purposes including Inverters, Succeeders, and Repeaters. Also included, were some mentions of possible negatives of using behavior trees such as traversal issues. While this post provided a decent amount of repeated information it was helpful for what new information it provided and the various figures that demonstrated the functionality of the behavior tree they used for their project. Jakob Rasmussen’s blog post, Are Behavior Trees a Thing of the Past?, provided a much-needed counterargument to using behavior trees. The post itself goes into a brief history of AI design and how it has evolved over the years discussing the use of Finite State Machines and behavior trees. Rasmussen discusses several benefits behavior trees have over Finite State Machines as well as some of the negatives such as the restrictions that occur when using very large behavior trees on memory and speed. He goes on to propose the use of Utility systems for AI design and discusses the various benefits and negatives this technique has compared to behavior trees. Overall, this was useful for providing more information on the negatives of behavior trees as well as showing how other approaches can be better depending on the circumstances. The last reference used was Introduction to BTs, by Davide Faconti. Compared to the other sources this one was probably the least useful overall. However, it does still have some benefits. Compared to the other sources the descriptions provided for the various aspects of behavior trees were fairly limited and only showed the bare minimum of understanding for the various aspects. What was useful about this source was the various diagrams. Each diagram showcased a specific aspect of behavior trees and how they can affect the resulting behavior of the AI. These diagrams provided a clear representation of how different types of tasks can be represented and their effects on a behavior tree. Outside of this use, the source really was not that helpful in comparison to the other references.
Demo Controls: WASD or Arrow Keys to move player unit Click on enemies to do damage Works Cited Colledanchise, M., Parasuraman, R., & Ogren, P. (2015, April 22). Learning of behavior trees for Autonomous Agents - arxiv.org. Retrieved December 14, 2021, from https://arxiv.org/pdf/1504.05811.pdf. Faconti, D. (2019). Introduction to BTS. Introduction to BT - BehaviorTree.CPP. Retrieved December 14, 2021, from https://www.behaviortree.dev/bt_basics/. Millington, I. (2019). Chapter 5.4 Behavior Trees. In Artificial Intelligence for Games (2nd ed.). CRC Press. Rasmussen, J. (2016, April 27). Are behavior trees a thing of the past? Game Developer. Retrieved December 14, 2021, from https://www.gamedeveloper.com/programming/are-behavior-trees-a-thing-of-the-past-. Simpson, C. (2014, July 18). Behavior trees for AI: How they work. Game Developer. Retrieved December 14, 2021, from https://www.gamedeveloper.com/programming/behavior-trees-for-ai-how-they-work. Zhang, Q., Yao, J., Yin, Q., & Zha, Y. (2018, July 3). Learning behavior trees for autonomous agents with hybrid constraints evolution. MDPI. Retrieved December 14, 2021, from https://www.mdpi.com/2076-3417/8/7/1077/htm.
0 Comments
|
AuthorWritten by Cormac MacKinnon and myself, Alexander Wood, as a portion of our Final Project for AI for Games in Fall 2021 |