A lightweight library of Behavior Trees Library in C++.

Overview

A lightweight behavior tree library in C++.

NEWS!

💥 Thanks to Davide Faconti there is now a more sophisticated version of the library. The new version of this library is available here. There is also GUI available here.

Our book Behavior Trees in Robotics and AI, published by CRC Press Taylor & Francis, is available for purchase (ebook and hardcover) on the CRC Press Store or Amazon. The Preprint version (free) is available here: https://arxiv.org/abs/1709.00084

Tutorials available at https://btirai.github.io/












portfolio_view BT++

License MIT Version

REFERENCE

Please refer to the following paper when using the library:

How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees. Michele Colledanchise and Petter Ogren. IEEE Transaction on Robotics 2017.

bibtex entry:

@ARTICLE{TRO17Colledanchise,
author={M. Colledanchise and P. Ögren},
journal={IEEE Transactions on Robotics},
title={{How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees}},
year={2017},
volume={33},
number={2},
pages={372-389},
keywords={Computer architecture;Decision trees;High definition video;Robot control;Switches;Behavior trees (BTs);decision trees;finite state machines (FSMs);hybrid dynamical systems (HDSs);modularity;sequential behavior compositions;subsumption architecture},
doi={10.1109/TRO.2016.2633567},
ISSN={1552-3098},
month={April},}

DEPENDENCIES

Regarding visualization purposes:

Regarding tests:

BT NODES SUPPORT

Fallback: Fallback nodes are used to find and execute the first child that does not fail. A Selector node will return immediately with a status code of success or running when one of its children returns success or running. The children are ticked in order of importance, from left to right.

Sequence: Sequence nodes are used to find and execute the first child that has not yet succeeded. A sequence node will return immediately with a status code of failure or running when one of its children returns failure or running. The children are ticked in order, from left to right.

Parallel: The parallel node ticks its children in parallel and returns success if M ≤ N children return success, it returns failure if N − M + 1 children return failure, and it returns running otherwise.

Decorator: The decorator node manipulates the return status of its child according to the policy defined by the user (e.g. it inverts the success/failure status of the child). In this library the decorators implemented are the two common ones: Decorator Retry which retries the execution of a node if this fails; and Decorator Negation That inverts the Success/Failure outcome.

Action: An Action node performs an action, and returns Success if the action is completed, Failure if it can not be completed and Running if completion is under way.

Condition: A Condition node determines if a desired condition c has been met. Conditions are technically a subset of the Actions, but are given a separate category and graphical symbol to improve readability of the BT and emphasize the fact that they never return running and do not change any internal states/variables of the BT.

A user manual is available in the project folder (BTppUserManual.pdf).

SETUP

The first step to use BT++ is to retrieve its source code. You can either download it here (https://github.com/miccol/Behavior-Tree) or clone the repository:

$ cd /path/to/folder
$ git clone https://github.com/miccol/Behavior−Tree.git

Once you have the repository, compile the library:

$ cd /path/to/folder/
$ mkdir ./build
$ cd build
$ cmake ..
$ make

NOTE In case you get the following error:

CMake Error: The following variables are used in this project, but they are set to NOTFOUND. Please set them or make sure they are set and tested correctly in the CMake files: GLUT_Xmu_LIBRARY (ADVANCED)

please see solution here. Thanks miquelramirez for this.

Check the installation by running a sample example.

$ cd /path/to/folder/
$ cd build/sample
$ ./btpp_example

INSTALL THE LIBRARY SYSTEM-WIDE (tested on Ubuntu 14.04 and 16.04)

If you would like to install the library system-wide, then run:

$ cd /path/to/folder/
$ cd build
$ sudo make install

On Ubuntu, this will install the library (libbtpp.so) in /usr/local/lib.
In an external project, just call in your CMakeLists 'find_package(BTpp)' to find the library.
The include directory is defined as BTpp_INCLUDE_DIRS and the libraries to link as BTpp_LIBRARIES.
The repository my-behavior-tree-project shows an example on how to use the library once system-wide installed.

CREATE YOUR OWN ACTION NODE

  1. Implement your action node class extending the abstract class BT::ActionNode.
  2. Implement the method BT::ReturnStatus Tick() with the code you want to execute while the action is running. Use the method is_halted() to check if the action has been prempted. When the execution of your action finished, return BT::SUCCESS or BT::FAILURE accordingly.
  3. Implement the method void Halt() with the code you want to execute when the action gets preempted (halted). See the file src/example.cpp for an example.

CREATE YOUR OWN CONDITION NODE

  1. Implement your condition node class extending the abstract class BT::ConditionNode.
  2. Implement the method BT::ReturnStatus Tick() with the code you want to execute to check the condition. Return BT::SUCCESS or BT::FAILURE accordingly.
    See the file src/example.cpp for an example.

NOTES

In case you are puzzled about why a sequence (or fallback) node with 2 or more actions as children never get past the first action, see this discussion.

LICENSE

The MIT License (MIT)

Copyright (c) 2014-2018 Michele Colledanchise

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Comments
  • First batch of changes

    First batch of changes

    Travis-CI and Catkin

    I updated the CMakeLists.txt file to detect the presence of catkin and, only in that case, to create a ROS package. This means that ROS is NOT a dependency, but releasing a behavior_tree_core package will be straightforward. This can be seen in the Travis built. Three compilation are tested:

    • Without ROS.
    • ROS Indigo
    • ROS Kinetic

    https://travis-ci.org/facontidavide/Behavior-Tree

    Include directory

    To avoid problems with include files, I moved all the .h files in include/behavior_tree. You might have noticed that this is common in ROS.

    Removed any reference to Draw and OpenGL.

    Even if the OpenGL lookee useful for people who do not want to install Qt, it must NOT be a requirement of the core library and its API.

    Naming consistency

    Few methods have been renamed to follow the UpperCase convention (there was no reason to use camel_case too).

    I don't really love it, though. I prefer Classes and functions to be UpperCase and methods to have the first letter a lower case (Google Style).

    Additionally, to be consistent with other API, I removed the prefix "Get" in the getters that is redundant.

    Removed TreeNode::type_

    the fact that type_ was a variable, allowed the user to change it (non-sense of course). It is more correct to create a pure virtual function like:

       virtual NodeType Type() const
    

    Additionally

    • Moved std::thread thread_ from TreeNode to ActionNode
    • Using the keywords virtual and override where appropriate.
    • Using const methods whenever is possible.
    • Using const references in the API to avoid copies.
    opened by facontidavide 11
  • Question: is a thread per node really necessary?

    Question: is a thread per node really necessary?

    Hi,

    I noticed that a single thread is created for each node. This seems like a waste of resources in large systems with potentially dozens of nodes.

    I guess that either a custom (simple) scheduler or a coroutine library might be able to do the job. Considering the overhead of the context switching, I have the feeling that even traversing the entire tree might be faster.

    Is there any reason I am not aware of to use a separate thread per node?

    Cheers

    Davide

    opened by facontidavide 11
  • Run-time factory

    Run-time factory

    Hi,

    this pretty large PR introduce the ability (optional) to create a Tree at run-time loading it from an XML.

    For simplicity, I included in the 3rdparty directory a popular library to parse XMLs.

    You can see an example of XML here.

    Hopefully the code in the unit test is self explaining ;)

    1. User must register actions into the class BehaviorTreeFactory as shown here and here.

    2. After that, an instance of a node can be created using the method instantiateTreeNode.

    3. The XML parser use the factory to create the entire Tree. Ignore the part related to BehaviorTreeMetaModel for the time being...

    4. As discussed, Actions and Decorators can have parameters. Since this parameters for the time being are read from XML, they are a pair of [attribute/value], both strings. We call them NodeParameters.

    5. Since the core library can not know all the possible ways in which a parameter can be parsed, it just assumes that it is up to the user's code to parse the string. You can see an example in DecoratorRetryNode.

    .... I just realized I didn't included in the unit test how to use these NodeParameters, whooops....

    If you have any suggestion, doubt, request, let me know.

    opened by facontidavide 10
  • Asynch Actions refactoring!

    Asynch Actions refactoring!

    Hi

    this PR contains 3 commits. I suggest to review them one by one

    Remove copy and paste related to ActionNode 6e31f5d69a84e8c55334fc9e1bb7d2b49bac87fa

    This commit looks intimidating but it is pretty simple and it does NOT change the behavior of the library.

    In all your ControlNodes there was some special code related to children of type ActionNode. The idea is: if you need to execute some special code when you tick() a Node, just displace that code inside the tick() itself !!!

    As a consequence, the resulting code is more readable and shorter.

    I insist: the logic AND the run-time behavior is completely unchanged!!!

    Remove memory leaks ba982f70cf7a1ae802b674c1276b848df000c3ed

    The fact that the unit test was ridden with memory leaks made difficult to find real problems. Fixed.

    Actions Zoo cca04249993e054d845f50083fcbe768ab498c93

    You gave for granted that action requires their own thread. This might be true or not. I added the Nodes of type

    • AsyncActionNode: the same you implemented, with it's own thread and the TickEngine.
    • SimpleActionNode: a very easy to build ActionNode that requires only a function pointer that is executed when tick() is invoked. It served me well in the past

    Cheers

    opened by facontidavide 10
  • Changes batch 2

    Changes batch 2

    Decorators

    Decorators have a different meta-model when compared with Control nodes, since they allow only a single node. Therefore I introduced the class DecoratorNode.

    Clang format

    Pure magic...

    Condition variables to wake up control nodes.

    I removed the sleep in a loop and used condition_variable instead, where notify_all is triggered by SetStatus.

    Cleanups

    It is always recommended to reduce as much as possible the scope of variables.

    As agreed I renamed ReturnStatus to NodeSttatus to keep it shorter and More consistent with other enum names.

    opened by facontidavide 10
  • Ewerlopes dev

    Ewerlopes dev

    Hi again.

    So, after looking the code a bit more I have made some changes. Specially, I created a folder for holding together the example. Using the word "Template" as a way of demonstrating the code usage don't sound a good idea. So, it is on a new folder now. I adjust the CMakeList for outputting the sample code in a named folder. Also, the compilation process now generates the shared lib (folder /lib) under success.

    I also took the liberty for creating a README. =)

    Regards.

    opened by ewerlopes 9
  • Enabled an action node's worker thread to break upon destruction of t…

    Enabled an action node's worker thread to break upon destruction of t…

    …he node.

    I'm working on an app that does dynamic creation of behavior trees to execute tasks and then destroys the behavior tree. As the action_node is currently implemented, there is no way to break out of the node's thread.

    opened by mjeronimo 8
  • Preliminary changes to add tracing/logging

    Preliminary changes to add tracing/logging

    Hi,

    this first PR create the initial infrastructure to create a sophisticated tracing/logging/publishing mechanism to observe or save state transitions.

    The important things to consider are:

    1. UID added to TreeNode, to make easier the tracking of state changes using less memory on file. Not used yet.

    2. I created an initial version of a Flatbuffers definition file. Don't spend too much time reviewing it, it may change once I get to that part. if you are not familiar, with it, Flatbuffers is a serialization library much faster that Protobuffers, Boot::serialize and, of course, ROS serialization ;)

    3. Loggers will inherit from the abstract class StatusChangeLogger. Right now the most trivial logger (which print to std:.cout) is implemented. You can see it in action with the added example crossdoor_example.cpp.

    4. I realized that the Decorators didn't set the child to IDLE as they should: 4a51d3b956fad58d7f6b7042ec49388e4e76bd46 .

    5. Check also the commit 6666f6dbea2b5764fc9a5866570ab5c5655df6f5 and tell me if you agree with the logic.

    6. Removed DEBUG_STDOUT. I know this might be controversial ;) but I think the new Logging infrastructure is sufficiently verbose, when the option showsTransitionToIdle() is turned on.

    Cheers

    Davide

    opened by facontidavide 8
  • Pre-release of 2.0

    Pre-release of 2.0

    Hi,

    this Pull Request contains some changes, being the most significant the change in behavior discussed here: https://discourse.robmosys.eu/t/semantic-of-sequence-vs-sequencestar/136/12?u=facontidavide

    You can see the important changes here: https://github.com/Eurecat/BehaviorTree.CPP/blob/devel/src/action_node.cpp#L27

    and the motivating unit test here: https://github.com/Eurecat/BehaviorTree.CPP/blob/devel/gtest/gtest_sequence.cpp#L245

    This new addition to the semantic of Fallback and Sequence (without memory) means that ONLY ConditionNodes are re-ticked, but ActionNodes are not.

    This was true already for ActionNode but not for ActionNodeBase.

    Hopefully this is the last breaking change before version 2.0.

    I am planning to add only unit tests, code comments, tutorials and documentation.

    Wit this PR, I personally consider the library feature-complete

    opened by facontidavide 6
  • Hiccup building the library on Ubuntu 16.04

    Hiccup building the library on Ubuntu 16.04

    Hello there,

    the build instructions given on Readme.md fail on Unbuntu 16.04 after installing the listed dependencies (GL, GLUT and googletest). CMake aborts with the following output:

    -- The C compiler identification is GNU 5.4.0
    -- The CXX compiler identification is GNU 5.4.0
    -- Check for working C compiler: /usr/bin/cc
    -- Check for working C compiler: /usr/bin/cc -- works
    -- Detecting C compiler ABI info
    -- Detecting C compiler ABI info - done
    -- Detecting C compile features
    -- Detecting C compile features - done
    -- Check for working CXX compiler: /usr/bin/c++
    -- Check for working CXX compiler: /usr/bin/c++ -- works
    -- Detecting CXX compiler ABI info
    -- Detecting CXX compiler ABI info - done
    -- Detecting CXX compile features
    -- Detecting CXX compile features - done
    -- Looking for XOpenDisplay in /usr/lib/x86_64-linux-gnu/libX11.so;/usr/lib/x86_64-linux-gnu/libXext.so
    -- Looking for XOpenDisplay in /usr/lib/x86_64-linux-gnu/libX11.so;/usr/lib/x86_64-linux-gnu/libXext.so - found
    -- Looking for gethostbyname
    -- Looking for gethostbyname - found
    -- Looking for connect
    -- Looking for connect - found
    -- Looking for remove
    -- Looking for remove - found
    -- Looking for shmat
    -- Looking for shmat - found
    -- Looking for IceConnectionNumber in ICE
    -- Looking for IceConnectionNumber in ICE - found
    -- Found X11: /usr/lib/x86_64-linux-gnu/libX11.so
    -- Found GTest: /usr/local/lib/libgtest.a  
    -- Looking for pthread.h
    -- Looking for pthread.h - found
    -- Looking for pthread_create
    -- Looking for pthread_create - not found
    -- Looking for pthread_create in pthreads
    -- Looking for pthread_create in pthreads - not found
    -- Looking for pthread_create in pthread
    -- Looking for pthread_create in pthread - found
    -- Found Threads: TRUE  
    -- Found GLUT: /usr/lib/x86_64-linux-gnu/libglut.so  
    -- Found OpenGL: /usr/lib/x86_64-linux-gnu/libGL.so  
    CMake Error: The following variables are used in this project, but they are set to NOTFOUND.
    Please set them or make sure they are set and tested correctly in the CMake files:
    GLUT_Xmu_LIBRARY (ADVANCED)
        linked by target "btpp_gtest" in directory /home/bowman/Sandboxes/libbtpp
        linked by target "btpp_example" in directory /home/bowman/Sandboxes/libbtpp
        linked by target "BTpp" in directory /home/bowman/Sandboxes/libbtpp
    

    The error is obscure, but fortunately well documented. Following the advice given in the link, namely to install the packages libxmu-dev and libxi-dev allows CMake to succeed.

    I'd advise to add a note on this to the README.md file, for future reference.

    Thanks a lot for making the library available @miccol!

    opened by miquelramirez 6
  • Plugins

    Plugins

    Hi,

    with commit d0e83dea3027e219e623c4d0b9036ec2224dc5cb it is now possible to deploy one or more tree nodes as a plugin (dynamically loaded shared library).

    Examples have been updated accordingly. See https://github.com/Eurecat/BehaviorTree.CPP/blob/devel/examples/t02_factory_tree.cpp#L64

    The plugin approach is optional and the old method (static linking) is still valid.

    opened by facontidavide 5
Owner
Michele Colledanchise
I am a postdoctoral researcher at IIT. My principal interests lie in Behavior Trees, Artificial Intelligence, and Automated Planning.
Michele Colledanchise
x64dbg plugin for simple spoofing of CPUID instruction behavior

CPUID Spoofer CpuidSpoofer is a x64dbg plugin which helps you to modify the behaviour of the CPUID instruction. For example, you can easily change the

null 54 Sep 28, 2022
A simple C library for working with KD-Trees

kdtree Overview kdtree is a simple, easy to use C library for working with kd-trees. Kd-trees are an extension of binary search trees to k-dimensional

John Tsiombikas 346 Nov 19, 2022
Several translations of segment trees for CMU's 15-451 (Algorithms).

segtrees Several translations of segment trees for CMU's 15-451 (Algorithms). Feel free to contact me at [email protected] for questions/comment

Abigale Kim 20 Jun 17, 2022
Complete introduction to size balanced trees (O(1) amortized complexity)

Size Balanced Tree A size balanced tree (SBT) is a self-balancing binary search tree (SBBST) rebalanced by examining the sizes of each node's subtrees

Jishan Shaikh 18 Jun 2, 2022
heuristically and dynamically sample (more) uniformly from large decision trees of unknown shape

PROBLEM STATEMENT When writing a randomized generator for some file format in a general-purpose programming language, we can view the resulting progra

John Regehr 4 Feb 15, 2022
Provides very lightweight outcome and result (non-Boost edition)

master branch develop branch CTest dashboard: https://my.cdash.org/index.php?project=Boost.Outcome All tests passing source tarballs: https://github.c

Niall Douglas 576 Nov 22, 2022
lightweight, compile-time and rust-like wrapper around the primitive numerical c++ data types

prim_wrapper header-only, fast, compile-time, rust-like wrapper around the primitive numerical c++ data types dependencies gcem - provides math functi

null 1 Oct 22, 2021
A library of generic data structures.

Collections-C A library of generic data structures including a list, array, hashtable, deque etc.. Examples Building and Installing Using the library

Srđan Panić 2.5k Nov 16, 2022
Library of generic and type safe containers in pure C language (C99 or C11) for a wide collection of container (comparable to the C++ STL).

M*LIB: Generic type-safe Container Library for C language Overview M*LIB (M star lib) is a C library enabling to use generic and type safe container i

PpHd 553 Nov 21, 2022
Linear Linked List Library

list.h Implementations for singly-linked and doubly-linked list functions. Basic Working Example #include <stdio.h> #include <stdlib.h> #include "list

Nick Bulischeck 45 Nov 17, 2022
C header library for typed lists (using macros and "template" C).

vector.h C header library for typed lists (using macros and "template" C). Essentially, this is a resizable array of elements of your choosing that is

Christopher Swenson 30 Oct 31, 2022
Directed Acyclic Graph Execution Engine (DAGEE) is a C++ library that enables programmers to express computation and data movement, as task graphs that are scheduled concurrently and asynchronously on both CPUs and GPUs.

Directed Acyclic Graph Execution Engine (DAGEE) is a C++ library that enables programmers to express computation and data movement, as tasks in a graph structure, where edges represent task dependencies

null 27 Nov 14, 2022
nanoplan is a header-only C++11 library for search-based robot planning.

nanoplan is a header-only C++11 library for search-based robot planning. The primary design goals are correctness, ease-of-use, and efficiency (in tha

Jordan Ford 14 May 17, 2022
libsais is a library for linear time suffix array and burrows wheeler transform construction based on induced sorting algorithm.

libsais libsais is a library for fast (see Benchmarks below) linear time suffix array and Burrows-Wheeler transform construction based on induced sort

Ilya Grebnov 111 Nov 12, 2022
An open source library for C

Eric O Meehan C Library Introduction Eric O Meehan's C Library is an open source collection of tools for the C programming language. The project is in

Eric O Meehan 112 Nov 14, 2022
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

Lib9wada Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada Usage Compile the library with mak

Lprogrammers Lm9awdine 52 Sep 23, 2022
Experimental managed C-strings library

Stricks Managed C strings library. ?? API Why ? Because handling C strings is tedious and error-prone. Appending while keeping track of length, null-t

Francois Alcover 88 Oct 10, 2022
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

LibC+ Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -lC+ Better than C, not as much as c++ Usage

BnademOverflow 53 Nov 21, 2022
Simple C++ Genetic Algorithm library

crsGA: Simple C++ Genetic Algorithm library crsGA is a simple C++ template library for developing genetic algorithms, plus some other utilities (Logge

Rafael Gaitán 6 Apr 24, 2022