Researching Different AI Techniques - Behaviour Trees (Part 2)
Autonomous agents need to be reactive to situations happening in the world around them, especially in the sense of a guard artificial intelligence (AI) which will need to react to the player's actions. Collendanchise and Ogren talk about the trade of between modularity and reactivity "in terms of the classical Goto statement that was used in early programming languages" (Collendanchise and Ogren, 2018) The Goto statement is as a one-way control transfer which caused the program to jump to another section of code and continue execution from there rather than the more common two-way control transfer where code jumps down to perform the execution, then returns to where it left off such as calling a function. Finite State Machines (FSMs) execute code similar to the one-way control transfer as each state needs a transition to and from the state, so "a new state or behavior[sic] to a character requires not only coding the new state itself but also adding the transitions between all related states." (Goebel, n.d) Behaviour Trees (BTs) are much more modular and act similar to the two-way control transfer as each behaviour can act on its own without depending on the rest of the tree.
The reason I have decided to use a BT for my guard AI is because they are able to switch "between a finite set of tasks in a modular fashion". (En.wikipedia.org, 2019). This will help me build simple reusable behaviours that the agents will be able to quickly switch between and while building the system as I add in more behaviours it should be easier to "plug" them in, rather than a FSM where I would have to spend time writing and checking transitions.
A BT is made up of several different types of nodes which commonly fall under Composite Nodes, Decorator Nodes, Leaf Nodes and a Root Node.
A composite node is a node that can have one or more children nodes. The common way these children nodes are processed are in a first to last order, however some composite nodes will execute their children in a random order.
The counterpart composite node to the sequence is the selector node, which while similar to the sequence only one child needs to succeed for the selector to succeed and only failing if all the children return a failure.
While sequence and selector nodes are enough to create a complex BT decorators are needed "to modify the result of another behavior or task. In other words, a decorator task "decorates" another task" (Goebel, n.d). There are many types of decorators able to adjust the flow of the BT such as an inverter node which as implied will return the reverse of the child's result turning a failure into a success and vice versa. As an example Simpson uses an "Until Fail repeater node which will continue to reprocess its child until its child returns a failure." (Simpson, 2014) which shows just how powerful and useful decorator nodes can be.
Leaf nodes cannot have any children nodes and are where the actions for the agents are defined. An example would be a node that would hold the logic and instruct an agent to open a door or walk to a location.
Reference List
[1] En.wikipedia.org. (2019). Behavior tree (artificial intelligence, robotics and control). [online] Available at: https://en.wikipedia.org/wiki/Behavior_tree_(artificial_intelligence,_robotics_and_control) [Accessed 2 November 2018].
[2] Goebel, P. (n.d.). Behavior Trees: Simple yet Powerful AI for your Robot. [online] Pirobot.org. Available at: https://www.pirobot.org/blog/0030/ [Accessed 5 November 2018].
[3] Wiki.c2.com. (2013). Goto Considered Harmful. [online] Available at: http://wiki.c2.com/?GotoConsideredHarmful [Accessed 5 Novemeber 2018].
[4] GeeksforGeeks. (n.d.). goto statement in C/C++ - GeeksforGeeks. [online] Available at: https://www.geeksforgeeks.org/goto-statement-in-c-cpp/ [Accessed 5 November 2018].
The reason I have decided to use a BT for my guard AI is because they are able to switch "between a finite set of tasks in a modular fashion". (En.wikipedia.org, 2019). This will help me build simple reusable behaviours that the agents will be able to quickly switch between and while building the system as I add in more behaviours it should be easier to "plug" them in, rather than a FSM where I would have to spend time writing and checking transitions.
A BT is made up of several different types of nodes which commonly fall under Composite Nodes, Decorator Nodes, Leaf Nodes and a Root Node.
A composite node is a node that can have one or more children nodes. The common way these children nodes are processed are in a first to last order, however some composite nodes will execute their children in a random order.
"The most commonly used composite node is the Sequence, which simply runs each child in sequence, returning failure at the point any of the children fail, and returning success if every child returned a successful status." (Simpson, 2014).
 |
| (Simpson, 2014). |
While sequence and selector nodes are enough to create a complex BT decorators are needed "to modify the result of another behavior or task. In other words, a decorator task "decorates" another task" (Goebel, n.d). There are many types of decorators able to adjust the flow of the BT such as an inverter node which as implied will return the reverse of the child's result turning a failure into a success and vice versa. As an example Simpson uses an "Until Fail repeater node which will continue to reprocess its child until its child returns a failure." (Simpson, 2014) which shows just how powerful and useful decorator nodes can be.
Leaf nodes cannot have any children nodes and are where the actions for the agents are defined. An example would be a node that would hold the logic and instruct an agent to open a door or walk to a location.
Reference List
[1] En.wikipedia.org. (2019). Behavior tree (artificial intelligence, robotics and control). [online] Available at: https://en.wikipedia.org/wiki/Behavior_tree_(artificial_intelligence,_robotics_and_control) [Accessed 2 November 2018].
[2] Goebel, P. (n.d.). Behavior Trees: Simple yet Powerful AI for your Robot. [online] Pirobot.org. Available at: https://www.pirobot.org/blog/0030/ [Accessed 5 November 2018].
[3] Wiki.c2.com. (2013). Goto Considered Harmful. [online] Available at: http://wiki.c2.com/?GotoConsideredHarmful [Accessed 5 Novemeber 2018].
[4] GeeksforGeeks. (n.d.). goto statement in C/C++ - GeeksforGeeks. [online] Available at: https://www.geeksforgeeks.org/goto-statement-in-c-cpp/ [Accessed 5 November 2018].
[5] M. Collendanchise and P. Ogren, (2018) "Behavior Trees in Robotics and AI,". Available: https://arxiv.org/abs/1709.00084 [Accessed 3 November 2018].
[6] Sekhavat, Y. (2016). Behavior Trees for Computer Games. International Journal on Artificial Intelligence Tools, 26(02), pp.1-27.
[6] Sekhavat, Y. (2016). Behavior Trees for Computer Games. International Journal on Artificial Intelligence Tools, 26(02), pp.1-27.
[7] Simpson, C. (2014). Behavior trees for AI: How they work. [online] Gamasutra.com. Available at: https://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php [Accessed 2 Novemeber 2018].
[8] Thompson, T. (n.d.). Outsmarting the Covenant. [online] AI and Games. Available at: https://aiandgames.com/outsmarting-the-covenant/ [Accessed 3 November 2018].