What are behavior trees and how are they used



    / photo Harry Li CC

    We at IT-GRAD are very interested in artificial intelligence. We 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 complex process. Input variables are often unknown, because the machine has to adapt to the environment on the fly. Standard robot control models were developed in the form of finite state machines [FSM - Finite-State Machine], however, this method is not suitable for creating complex algorithms, because as new elements of the model are added, its complexity begins to increase rapidly.

    To alleviate these shortcomings, an approach widely used by video game developers began to be used. It's about behavior trees. Unlike finite state machines, trees have a more formal structure, so using them is easier to program the behavior of the machine.

    The Behavior Tree [BT - Behavior Tree] is an oriented acyclic graph whose nodes are the possible behaviors of the robot. The "width" of the 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 state machines? As the number of states of a finite state machine increases, its complexity increases sharply. The number of transitions in FSM with the number of states N equals N * (N-1). If we take N = 4, then we get 12 possible transitions. If we add one more state, there will be 20 transitions, one more - 30.

    The so-called hierarchical problems partially solve this problem.FSM, however, with a large number of states, the structure is still too complex.



    Finite state machine architecture and behavior tree

    "Woody" architecture is free from this drawback. If the FSM for each state has its own decision-making logic, then in BT it is, as it were, taken out of their limits. This allows you to add and remove nodes even during the program: 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 further simplifies the "orientation on the ground" and the search for bugs.

    The principle of behavior trees




    How the Behavior Tree Works

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

    • "Success" if the task is completed successfully;
    • “Failure” if the condition is not fulfilled or the task, for some reason, is not feasible;
    • “In progress” if the task is launched and is awaiting completion
    • “Error” if an unknown error occurs in the program.

    The result of the operation of any node is always transmitted to the parent node located one level higher. The tree is viewed from the highest node - the root. From it, a depth search is performed starting 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: an action, an execution node of a sequence, a parallel node, a selector, a condition, an inverter.

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

    Parallel action nodes execute the behavior of child nodes until a specified number of them returns the status of Failure or Success.

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

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

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

    The tree is represented as libGDX code. 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 behavior tree diagram here . A slightly more complex version of the behavior tree is presented here : the dog walks through the garden until it is called by the owner. This model already uses subtree calls.

    The main advantage of behavior trees is formality. Using a set of tools, templates, and structures, very interesting and expressive behaviors can be realized, even related to each other. This is one of the reasons that it was BT that became the frequent choice for the implementation of artificial intelligence in computer games and the creation of small robots.

    For example, a group of scientists from the Delft University of Technology in the Netherlands developeda 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 a robot had to find an open window in a room and fly into it.



    Scientists decided to abandon artificial neural networks: in platforms for small robots, the possibilities for collecting data and computing are very limited, in addition, developed ANNs are difficult to analyze and difficult to configure manually. Instead, behavior trees were selected that have a simpler and more understandable structure, as well as evolutionary algorithms to optimize learning.

    As for the gaming theme, here is an example. 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-Behavior-Tree library . All code and flowcharts can be found here .

    Conclusion

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

    Modern AI requires technologies that can support complex systems with qualitatively complex and unique behavior. An AI is needed that can perform unpredictable actions and make decisions in situations not provided for by the developer.

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

    Such an approach will automatically solve another problem - it will make the electronic-mechanical assistants 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, Andrew Ng, a well-known robotics researcher, is engaged in 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é:


    Also popular now: