Geekly Articles each Day
📜 ⬆️ ⬇️

What are behavior trees and how are they used?



/ photo by Harry Li CC

We at IT-GRAD are very interested in questions of artificial intelligence. We have already touched on the topic of autopilot cars, and a week ago we published material in which we talked about new achievements of scientists and developers in the field of AI, as well as about the fears of skeptics.
')
Today we will again touch upon this issue and talk about what trees of behavior are, how they are used in robotics, and whether they have a future.

Programming a robot to perform certain actions is a complicated process. Input variables are often unknown, because the machine has to adapt to environmental conditions on the fly. Standard robot control models were developed as finite-state machines [FSM - Finite-State Machine], but this method is not well suited for creating complex algorithms, because as we add new model elements, its complexity begins to increase rapidly.

To smooth out these shortcomings, an approach widely used by video game developers has been used. It's about behavior trees. Unlike finite automata, trees have a more formal structure, so with their help it is easier to program the behavior of the machine.

The behavior tree [BT - Behavior Tree] is a directed acyclic graph whose nodes are the possible behaviors of the robot. The "width" of a tree indicates the number of available actions, and the "length" of its branches characterizes their complexity.



Four state machine

What is the advantage of behavior trees over finite automata? As the number of states of a finite automaton increases, its complexity increases dramatically. The number of transitions in FSM with the number of states N is N * (N-1). If we take N = 4, we get 12 possible transitions. If we add one more state, there will be 20 transitions, another one - 30.

Partially this problem is solved by the so-called hierarchical FSM, however, with a large number of states, the structure still turns out to be too complicated.



The state machine architecture and behavior tree

"Wood" architecture is devoid of this disadvantage. If the FSM for each state registers its own decision-making logic, then in BT it is, as it were, moved beyond their limits. This allows you to add and remove nodes even while the program is running: just write new code to call the node or delete the old one.

In addition, a tree with a large number of states can be divided into small subtrees - this additionally simplifies the "orientation on the ground" and the search for bugs.

Principle of behavior trees




Principle of behavior tree

BT nodes are called tasks or behaviors. Each task can have four states:


The result of the work of any node is always transmitted to the parent node located on the level above. The tree is viewed from the topmost node - the root. It is searched for depth from the left branch of the tree. If one node has several subtasks, they are executed from left to right.

Among the nodes, the following types are distinguished: action (action), sequence execution node (sequence), parallel node (parallel), selector (condition), inverter.

An action is a record of variables or some movement. Sequence nodes alternately execute the behavior of each child node until one of them produces the value “Failure”, “In operation”, or “Error”. If this does not happen, returns the value "Success."

Parallel action nodes execute the behavior of the child nodes until a specified number of them return the “Failure” or “Success” statuses.

Selectors alternately execute the behavior of each child node until one of them gives the value of “Success”, “In work” or “Error”. If this does not happen, returns the value "Failure".

Conditions contain the criterion by which the outcome is determined, and the variable. For example, the condition “Is there a person in this room?” Searches all the objects in the room and compares them with the variable “Person”. Inversion nodes perform the function of the NOT operator.

GitHub provides an example of a tree that simulates the behavior of a dog that can bark, walk, and do other dog chores.

The tree is represented as a code on libGDX. libGDX is a framework written in Java using C and C ++.

# # Dog tree # # Alias definitions import bark:"com.badlogic.gdx.ai.tests.btree.dog.BarkTask" import care:"com.badlogic.gdx.ai.tests.btree.dog.CareTask" import mark:"com.badlogic.gdx.ai.tests.btree.dog.MarkTask" import walk:"com.badlogic.gdx.ai.tests.btree.dog.WalkTask" # Tree definition (note that root is optional) root selector parallel care urgentProb:0.8 alwaysFail com.badlogic.gdx.ai.tests.btree.dog.RestTask # fully qualified task sequence bark times:"uniform,1,3" # the type of attribute times is a IntegerDistribution walk com.badlogic.gdx.ai.tests.btree.dog.BarkTask # fully qualified task mark


You can find the dog's behavior tree by the link . A slightly more complicated version of the behavior tree is presented here : the dog walks through the garden until the owner calls it. This model already uses calls to subtrees.

The main advantage of behavior trees is formality. With the help of a set of tools, templates and structures can be implemented very interesting and expressive behavior, even related to each other. This is one of the reasons why BT has become a frequent choice for implementing artificial intelligence in computer games and creating small robots.

For example, a group of scientists from the Delft Technical University in the Netherlands developed a robot based on the DelFly Explorer platform, which receives environmental data using two built-in cameras. In their article, they described an experiment during which the robot had to find an open window in the room and fly into it.



Scientists decided to abandon artificial neural networks: in platforms for small robots, the possibilities for data collection and computation are severely limited, besides, the developed INS are difficult to analyze and are difficult to adjust manually. Instead, behavior trees that have a simpler and more understandable structure, as well as evolutionary algorithms for optimizing learning, were chosen.

As for the game theme, here is an example. The behavior trees were used to create a car simulator for the University of Sunshine Coast. This simulator is now used for psychological testing of drivers.



The behavior tree of this project was built in the C # programming language using the Fluent-Behaviour-Tree library. All code and flowcharts can be found by reference .

Conclusion

In general, behavioral trees offer a comfortable and elegant organizational structure, but still do not have the potential to implement advanced decision making.

Modern AI requires technologies capable of supporting complex systems with qualitatively complex and peculiar behavior. An AI is required that can perform unpredictable actions and make decisions in situations not provided for by the developer.

For this, more powerful solutions and algorithms are used, the computing requirements of which the robot equipment often does not meet. However, there is a solution - cloud robotics. In this case, all the logic of the work is stored on a remote server, and the small robot receives only commands for action.

Such an approach will automatically solve another problem - it will allow electronic and mechanical assistants to become intelligent. Connecting to the cloud will provide the robot with all the necessary information about the world. Work in this direction is already underway, for example, the well-known robotics researcher Andrew Ng is working on these issues.

Perhaps in the near future, robots will begin to exchange data and code with each other over wireless networks.

PS Interesting materials from our blog on Habré:

Source: https://habr.com/ru/post/306214/

More articles:


All Articles