lib-behavior-tree

Generic, thread-safe Behaviour Tree library for embedded C (C99). Supports bare-metal, FreeRTOS, and any POSIX-compatible RTOS.

---

Features

Feature	Detail
Language	Pure C99, no C++ required
Memory	Dynamic (configurable allocator — swap in pvPortMalloc / pool)
Thread safety	Per-tree recursive mutex; POSIX, FreeRTOS, or no-op (bare metal)
Node types	Action, Condition, Sequence, Selector, Parallel, Inverter, Repeater, Retry, ForceSuccess, ForceFailure
Composite policy	Sequence / Selector stateful/memory; Parallel fully reactive
Footprint	~2 KB flash; one bt_node_t ≈ 60–72 bytes

---

Architecture

Repository layout

lib-behavior-tree/
├── inc/
│   ├── conf_behaviour_tree.h   ← copy & edit for your project
│   ├── behavior_tree.h         ← only public header your app includes
│   ├── bt_port.h               ← platform mutex abstraction
│   └── bt_internal.h           ← cross-file internal declarations
├── src/
│   ├── behavior_tree.c         ← tree lifetime, node factories, tick/halt
│   ├── bt_composite.c          ← Sequence, Selector, Parallel
│   ├── bt_decorator.c          ← Inverter, Repeater, Retry, Force*
│   ├── bt_port_bare.c          ← bare-metal no-op port
│   ├── bt_port_posix.c         ← POSIX pthreads port
│   └── bt_port_freertos.c      ← FreeRTOS port
├── example/
│   └── freertos/
│       ├── freertos_sim.h      ← FreeRTOS simulation (POSIX pthreads)
│       ├── FreeRTOS.h / semphr.h  ← simulation stubs
│       ├── conf_behaviour_tree.h  ← FreeRTOS example config
│       └── bt_motor_controller.c  ← motor safety controller example
├── docs/                       ← generated by `doxygen Doxyfile`
├── Doxyfile
└── README.md

Node execution model

Every node follows a three-phase lifecycle managed by bt_node_tick and bt_node_halt:

                        bt_node_tick()
                              │
                    ┌─────────▼──────────┐
                    │ initialized = false?│
                    └─────────┬──────────┘
                              │ YES
                    ┌─────────▼──────────┐
                    │  call on_init_fn() │   ← once per execution cycle
                    └─────────┬──────────┘
                              │
                    ┌─────────▼──────────┐
                    │   call tick_fn()   │
                    └──┬──────┬──────┬───┘
                       │      │      │
                    RUNNING SUCCESS FAILURE
                       │      │      │
               initialized  initialized=false (resets for next cycle)
               stays true        │
                       │    parent composite decides
                       │    whether to continue
                bt_node_halt()
                       │
              ┌────────▼────────┐
              │ halt children   │  ← recursive, leaves first
              │ call on_halt_fn │
              │ initialized=false│
              └─────────────────┘

Composite node policies

Sequence (→) and Selector (?) — stateful/memory

Both store running_child, the index of the child that returned BT_RUNNING on the last tick. On the next tick, iteration resumes from that child, skipping earlier children that already completed.

Tick N:   [A:ok] [B:ok] [C:RUNNING] [D:...]
                          ↑ running_child = 2

Tick N+1: iteration starts here ──┘
          C is ticked again without re-executing A or B

This avoids restarting completed actions and is the correct behaviour for most embedded action pipelines (sensor calibration, motor ramp, comms handshake, …).

Parallel — fully reactive

Every child is ticked on every call. Children that previously returned SUCCESS or FAILURE have initialized = false, so bt_node_tick re-initialises them and calls their tick_fn again. This makes conditions re-evaluate on every tick.

The canonical safety-monitoring pattern:

Parallel [threshold = N]
├── Condition A   ← checked every tick (reactive guard)
├── Condition B   ← checked every tick (reactive guard)
└── Action C      ← continues its RUNNING state across ticks

If A or B fails → Parallel fails → Action C is halted immediately.

Thread safety model

bt_tree_create(..., thread_safe = true)
        │
        └── bt_port_mutex_create()   ← one recursive mutex per tree

bt_tree_tick(tree)
        │
        ├── bt_port_mutex_lock()
        │       └── bt_node_tick(root, ctx)   ← entire tick is protected
        └── bt_port_mutex_unlock()

• One recursive mutex per tree, held for the full duration of each tick.
• Recursive because callbacks may safely call other library utilities.
• Not protected: bt_node_add_child, factory functions — build the tree before sharing it with multiple tasks.
• bt_tree_destroy acquires then destroys the mutex.

Memory model

bt_tree_create()  → BT_MALLOC(sizeof bt_tree_t)
bt_*_create()     → BT_MALLOC(sizeof bt_node_t)
bt_node_add_child → BT_MALLOC(capacity × sizeof ptr)  [doubles on growth]
bt_tree_destroy() → BT_FREE (all nodes, children arrays, tree struct)

Override BT_MALLOC / BT_FREE in conf_behaviour_tree.h for RTOS heaps or pool allocators. Both macros must use the same underlying heap.

Port layer

bt_port.h
    │
    ├── defines BT_PLATFORM_BARE / POSIX / FREERTOS
    ├── includes <conf_behaviour_tree.h>  (angle-brackets: project version wins)
    └── selects bt_mutex_t typedef based on BT_PLATFORM

bt_port_bare.c     ← all four functions are no-ops
bt_port_posix.c    ← pthread_mutex_t with PTHREAD_MUTEX_RECURSIVE
bt_port_freertos.c ← xSemaphoreCreateRecursiveMutex

---

Integration

Step 1 — Copy the configuration file

cp lib-behavior-tree/inc/conf_behaviour_tree.h  <your-project>/include/

Edit the copy:

#define BT_PLATFORM    BT_PLATFORM_FREERTOS   /* or POSIX, or BARE */

/* Optional: use the RTOS heap */
#define BT_MALLOC    pvPortMalloc
#define BT_FREE      vPortFree

Step 2 — Add to your build

Compile four files — the three core sources plus exactly one port:

SRC += lib-behavior-tree/src/behavior_tree.c
SRC += lib-behavior-tree/src/bt_composite.c
SRC += lib-behavior-tree/src/bt_decorator.c
SRC += lib-behavior-tree/src/bt_port_freertos.c  # ← pick one

CFLAGS += -Ilib-behavior-tree/inc               # library includes LAST
CFLAGS += -I<your-project>/include              # project includes FIRST

Include path order matters: place your project's include directory before lib-behavior-tree/inc/ so that your conf_behaviour_tree.h is found before the library's template.

Step 3 — Include the public header

#include "behavior_tree.h"

---

Quick-start example (POSIX)

#include "behavior_tree.h"
#include <stdio.h>

typedef struct { int battery; bool arrived; } robot_ctx_t;

static bt_status_t cond_battery(bt_node_t *n, void *c) {
    (void)n; return ((robot_ctx_t *)c)->battery > 20 ? BT_SUCCESS : BT_FAILURE;
}
static bt_status_t action_navigate(bt_node_t *n, void *c) {
    (void)n; return ((robot_ctx_t *)c)->arrived ? BT_SUCCESS : BT_RUNNING;
}
static bt_status_t action_charge(bt_node_t *n, void *c) {
    (void)n; ((robot_ctx_t *)c)->battery = 100; return BT_SUCCESS;
}

int main(void) {
    robot_ctx_t ctx = { .battery = 80, .arrived = false };

    bt_node_t *cond = bt_condition_create("battery_ok", cond_battery, NULL);
    bt_node_t *nav  = bt_action_create("navigate", action_navigate, NULL, NULL, NULL);
    bt_node_t *chg  = bt_action_create("charge",   action_charge,   NULL, NULL, NULL);

    bt_node_t *seq = bt_sequence_create("nav_seq");
    bt_node_add_child(seq, cond);
    bt_node_add_child(seq, nav);

    bt_node_t *sel = bt_selector_create("root");
    bt_node_add_child(sel, seq);
    bt_node_add_child(sel, chg);

    bt_tree_t *tree = bt_tree_create(sel, &ctx, true);

    for (int i = 0; i < 4; i++) {
        bt_status_t s = bt_tree_tick(tree);
        printf("tick %d → %s\n", i, bt_status_str(s));
        if (i == 2) ctx.arrived = true;
    }

    bt_tree_destroy(tree);
    return 0;
}

Build (Linux/macOS):

gcc -std=c99 -D_POSIX_C_SOURCE=200809L -Iinc \
    src/behavior_tree.c src/bt_composite.c src/bt_decorator.c \
    src/bt_port_posix.c example.c -lpthread -o demo

---

FreeRTOS example — motor safety controller

example/freertos/bt_motor_controller.c demonstrates a 3-phase motor drive safety supervisor with two FreeRTOS tasks:

Selector [root]
├── Parallel [monitored_op, threshold=3]
│   ├── Condition : estop_clear          ← reactive: checked every tick
│   ├── Condition : temp_ok              ← reactive: checked every tick
│   └── Sequence  [run_motor]
│       ├── Action : enable_drive        ← one-shot (idempotent)
│       └── Action : ramp_speed          ← RUNNING while accelerating
└── Sequence [fault_response]
    ├── Action : disable_drive
    └── Action : set_fault_led

Build and run the simulation on Linux:

gcc -std=c99 -Wall -D_POSIX_C_SOURCE=200809L \
    -Iexample/freertos -Iinc \
    src/behavior_tree.c src/bt_composite.c src/bt_decorator.c \
    src/bt_port_freertos.c \
    example/freertos/bt_motor_controller.c \
    -lpthread -o motor_controller
./motor_controller

---

Node reference

Status values

Value	Meaning
BT_SUCCESS	Node completed successfully
BT_FAILURE	Node completed with failure
BT_RUNNING	Node is still executing
BT_INVALID	Node not yet ticked or was halted
BT_ERROR	Internal error (NULL pointer, alloc failure)

Composite nodes

Node	Symbol	Policy	Returns SUCCESS when	Returns FAILURE when
Sequence	→	Memory	All children succeed	First child fails
Selector	?	Memory	First child succeeds	All children fail
Parallel	⇉	Reactive	≥ threshold children succeed	Success impossible

Decorator nodes

Node	Behaviour
Inverter	SUCCESS ↔ FAILURE
Repeater	Loops N times (-1 = forever); FAILURE on child failure
Retry	Retries on FAILURE up to N times; SUCCESS on first success
ForceSuccess	Any terminal → SUCCESS
ForceFailure	Any terminal → FAILURE

---

Generate API documentation

doxygen Doxyfile
# Output: docs/index.html

---

Porting to a new RTOS

1. Add src/bt_port_myos.c implementing:

   bool bt_port_mutex_create (bt_mutex_t *mutex);
   void bt_port_mutex_destroy(bt_mutex_t *mutex);
   void bt_port_mutex_lock   (bt_mutex_t *mutex);
   void bt_port_mutex_unlock (bt_mutex_t *mutex);

2. In bt_port.h add #define BT_PLATFORM_MYOS 3 and the corresponding typedef for bt_mutex_t.
3. Set #define BT_PLATFORM BT_PLATFORM_MYOS in conf_behaviour_tree.h.

---

References

Topic	Resource
Behaviour Trees in AI	Colledanchise, M. & Ögren, P. (2018). Behaviour Trees in Robotics and AI. CRC Press. arXiv:1709.00084
Original BT paper	Isla, D. (2005). Handling Complexity in the Halo 2 AI. GDC 2005 Proceedings.
BT theory	Marzinotto, A. et al. (2014). Towards a Unified Behaviour Trees Framework. ICRA 2014. DOI
FreeRTOS	freertos.org — free, open-source RTOS for MCUs
POSIX threads	pubs.opengroup.org — pthread
BehaviorTree.CPP	behaviortree.dev — C++ reference implementation
BT visual editor	Groot2 — open-source BT editor

---

License

See LICENSE.