Behaviour trees explained

How games and robots organise behaviour in a tree: condition and action leaves, sequence and selector nodes, and what ticking from the top every loop buys you. Run a patrol-and-react tree and the same job as a state machine, side by side, and see why a tree scales better as behaviours pile up. Every demo runs in the browser.

Guidefree, runs in your browser

A behaviour tree is a way of writing what a robot or a game character should do next. The behaviours are kept in a tree, and the program walks the tree from the top many times a second, asking each part in turn: can you run? The first one that can, runs. Games have used them for enemy AI since the mid 2000s, with Halo 2 in 2004 usually given the credit for the idea catching on, and they are how ROS 2's navigation stack decides what a robot should do next. On this page a small robot patrols four corners of a mat and gets out of the way of whatever it meets, and each demo below is a real program you can change and run.

This page assumes you know what a finite state machine is. A behaviour tree does the same job. The difference is what you write down: a state machine is a list of transitions between states, and a tree is a list of behaviours in order of priority.

The idea in one loop

every tick:
    ask the top node to run
    each node answers one of three things:
        success  I am done
        failure  I cannot run, or I did not work
        running  I have started and I need more ticks

One pass down the tree is called a tick. The tree is ticked again from the top every time round the loop, ten times a second in the demos here.

There are four kinds of node on this page. Two of them are leaves, at the ends of the branches, and they are the only ones that touch the robot:

• a condition looks at a sensor or a variable and answers success or failure. It never moves the robot.
• an action drives the robot. It answers running while it is still working and success when it is done.

The other two are composites: nodes with children, which decide which child gets to run.

• a sequence runs its children in order and stops at the first one that does not say success. It is an AND: do this, then this, then this.
• a selector, also called a fallback, runs its children in order and stops at the first one that does not say failure. It is an OR: try this, and if you cannot, try this instead.

That is the whole language. A robot's priorities become a selector, with the most urgent behaviour first, and each behaviour becomes a sequence of "is this my moment?" followed by "then do it".

Ticking a tree in Python

The tree is a set of nested tuples, and one short function ticks it. A condition is a function that returns True or False. An action is a function that returns "running" or "success".

def tick(node):
    kind = node[0]
    if kind == "condition":
        return "success" if node[1]() else "failure"
    if kind == "action":
        return node[1]()
    if kind == "sequence":
        for child in node[1]:
            answer = tick(child)
            if answer != "success":
                return answer          # failure or running: stop here
        return "success"
    for child in node[1]:              # a selector
        answer = tick(child)
        if answer != "failure":
            return answer              # success or running: stop here
    return "failure"

Every demo below uses this same tick function, without a line changed. That is the point of the shape: the tree is data, and the program that walks it stays the same however many behaviours you add.

A tree with two branches

The smallest useful tree: drive on, unless something is close, in which case back away. The robot starts 81 cm from the wall.

from bugbot import *
connect()

# change these and press Run
TOO_CLOSE = 30      # cm: the way ahead is blocked
BACK_TO = 45        # cm: far enough to drive on again

running = "drive on"


def blocked():
    return distance() < TOO_CLOSE


def back_away():
    global running
    running = "back away"
    drive(-45, 0, 0)
    return "running" if distance() < BACK_TO else "success"


def drive_on():
    global running
    running = "drive on"
    drive(45, 0, 0)
    return "running"


TREE = ("selector", [
    ("sequence", [("condition", blocked), ("action", back_away)]),
    ("action", drive_on),
])


def tick(node):
    kind = node[0]
    if kind == "condition":
        return "success" if node[1]() else "failure"
    if kind == "action":
        return node[1]()
    if kind == "sequence":
        for child in node[1]:
            answer = tick(child)
            if answer != "success":
                return answer          # failure or running: stop here
        return "success"
    for child in node[1]:              # a selector
        answer = tick(child)
        if answer != "failure":
            return answer              # success or running: stop here
    return "failure"


was = ""
while clock() < 12:
    tick(TREE)
    if running != was:
        print(round(clock(), 1), running, "at", distance(), "cm")
        was = running
    plot("running", 1 if running == "back away" else 0)
    plot("distance", distance())
    wait(0.1)
stop()

On the chart, running is 0 while the drive-on branch has the robot and 1 while it is backing away. For the first 6.5 seconds the condition fails, so the sequence fails, so the selector falls through to drive_on. Nothing about "I am driving" is written down anywhere: the tree works it out again on every tick.

Then look at what happens after 6.5 s. The robot backs away to 30 cm, the condition distance() < 30 goes false, the sequence fails, and the selector drops the whole branch and drives on again, even though back_away had said "running". A tick starts from the top every time, so a branch is given up the moment its condition stops being true. That is what makes a tree react quickly, and it is also the first thing that catches people out.

The fix is the same one a state machine needs, and for the same reason: two thresholds instead of one. In the state machine guide that was called hysteresis. In a tree you get it by letting the running action hold its own condition true until it has finished.

Patrol and react

Now the real job. The robot patrols four corners of a mat with four boxes on it. Whenever the depth sensor sees something closer than 25 cm, it turns away until the way is clear and drives on past before going back to the patrol.

The tree has two branches, in order of priority:

dodge is an action that takes several seconds. It keeps its own two-part memory, phase, and it sets dodging so that the condition above it stays true while it works.

from bugbot import *
import math
connect()

# change these and press Run
ROUTE = [(75, 128), (128, 75), (75, 22), (22, 75)]   # the corners of the patrol
TOO_CLOSE = 25       # cm: something is in the way
CLEAR = 45           # cm: the way is open again
PAST = 2.5           # seconds of driving on after a dodge

START = (75.0, 75.0)
leg = 0
dodging = False
phase = "turn"
until = 0.0
running = "patrol"


def where():
    px, py = position()
    return START[0] + px, START[1] + py


def wrap(a):
    return (a + 180) % 360 - 180


# ---- the leaves of the tree -------------------------------------------------
def blocked():
    return dodging or distance() < TOO_CLOSE


def dodge():
    global running, dodging, phase, until
    running = "dodge"
    dodging = True
    if phase == "turn":
        drive(0, 0, 45)
        if distance() > CLEAR:
            phase, until = "past", clock() + PAST
        return "running"
    drive(55, 0, 0)
    if clock() < until:
        return "running"
    phase, dodging = "turn", False
    return "success"


def patrol():
    global running, leg
    running = "patrol"
    x, y = where()
    tx, ty = ROUTE[leg]
    if math.hypot(tx - x, ty - y) < 12:
        leg = (leg + 1) % len(ROUTE)
        print(round(clock(), 1), "corner reached, next is", ROUTE[leg])
        return "success"
    a = wrap(math.degrees(math.atan2(tx - x, ty - y)) - heading())
    drive(55 if abs(a) < 30 else 0, 0, 3 * a)
    return "running"


# ---- the tree ---------------------------------------------------------------
TREE = ("selector", [
    ("sequence", [("condition", blocked), ("action", dodge)]),
    ("action", patrol),
])


def tick(node):
    kind = node[0]
    if kind == "condition":
        return "success" if node[1]() else "failure"
    if kind == "action":
        return node[1]()
    if kind == "sequence":
        for child in node[1]:
            answer = tick(child)
            if answer != "success":
                return answer            # failure or running: stop here
        return "success"
    for child in node[1]:                # a selector
        answer = tick(child)
        if answer != "failure":
            return answer                # success or running: stop here
    return "failure"


NUMBER = {"patrol": 0, "dodge": 1}
COLOUR = {"patrol": "green", "dodge": "red"}
trail = {name: [] for name in NUMBER}
was = ""
changes = 0
step = 0
while clock() < 60:
    tick(TREE)
    if running != was:
        changes = changes + 1
        if running == "dodge":
            print(round(clock(), 1), "something at", distance(), "cm: dodging")
        was = running
    plot("running", NUMBER[running])
    plot("distance", distance())
    trail[running].append(where())
    step = step + 1
    if step % 10 == 0:
        for name in trail:
            draw(name, trail[name], COLOUR[name])
    wait(0.1)
stop()
print("changes of branch:", changes, " corners reached:", leg)

The trail on the mat is green where the patrol branch was driving and red where the dodge branch was. The chart's running line is 0 for patrol and 1 for dodge, and the distance line under it shows why each dodge started.

Two things are worth noticing in the program.

• Nothing says "go back to patrolling". The patrol branch is the last child of the selector, so it runs whenever no branch above it can. Putting a behaviour lower down the list is the whole of "this is less important".
• The patrol keeps its place by itself. leg is the patrol's own memory, not the tree's. When a dodge takes over for three seconds and then gives up, the patrol carries on from the corner it was heading for.

Try PAST = 0. The dodge stops the instant the way is clear, the patrol steers straight back at the box, and the robot dodges eleven times instead of five and clips the boxes as it goes. Try TOO_CLOSE = 12: it leaves the reaction so late that it dodges only twice and scrapes past. Try TOO_CLOSE = 40: no contact at all, but it is so careful that it dodges seven times and gets round only one corner in the minute.

The same job as a state machine

Here is the same behaviour written the other way. The three things the robot does become three states, and every change of behaviour becomes a transition written out by hand.

from bugbot import *
import math
connect()

# change these and press Run
ROUTE = [(75, 128), (128, 75), (75, 22), (22, 75)]
TOO_CLOSE = 25
CLEAR = 45
PAST = 2.5

START = (75.0, 75.0)
leg = 0
until = 0.0


def where():
    px, py = position()
    return START[0] + px, START[1] + py


def wrap(a):
    return (a + 180) % 360 - 180


def patrol_step():
    global leg
    x, y = where()
    tx, ty = ROUTE[leg]
    if math.hypot(tx - x, ty - y) < 12:
        leg = (leg + 1) % len(ROUTE)
        print(round(clock(), 1), "corner reached, next is", ROUTE[leg])
    a = wrap(math.degrees(math.atan2(tx - x, ty - y)) - heading())
    drive(55 if abs(a) < 30 else 0, 0, 3 * a)


COLOUR = {"PATROL": "green", "TURN": "red", "PAST": "yellow"}
trail = {name: [] for name in COLOUR}
state = "PATROL"
changes = 0
step = 0
while clock() < 60:
    was = state
    if state == "PATROL":
        if distance() < TOO_CLOSE:
            state = "TURN"
        else:
            patrol_step()
    elif state == "TURN":
        if distance() > CLEAR:
            state = "PAST"
            until = clock() + PAST
        else:
            drive(0, 0, 45)
    elif state == "PAST":
        if clock() >= until:
            state = "PATROL"
        else:
            drive(55, 0, 0)
    if state != was:
        changes = changes + 1
    plot("state", ["PATROL", "TURN", "PAST"].index(state))
    plot("distance", distance())
    trail[state].append(where())
    step = step + 1
    if step % 10 == 0:
        for name in trail:
            draw(name, trail[name], COLOUR[name])
    wait(0.1)
stop()
print("changes of state:", changes, " corners reached:", leg)

The two programs do the same job to within a fraction of a second, and at this size the state machine is the shorter of the two. Anyone who tells you a tree is always better is selling something. What the state machine has written down, though, is different: three states and three transitions, one of which, TURN to PAST, only exists because the dodge has two halves. The tree wrote down two behaviours in order of priority, and the two halves of the dodge stayed inside the dodge.

Notice also what the state machine still needs: leg and until are variables outside the state, because the current state cannot hold which corner the robot is going to. A behaviour with a parameter always needs memory of its own, whichever way you write it.

Adding one more behaviour

This is where the two ways part company. Give the robot a third job: every ten seconds it should stop and turn on the spot for a second and a half to look around.

In the tree it is one more branch, put at the top because it comes first, plus the two leaf functions it calls. Nothing else in the program changes.

from bugbot import *
import math
connect()

# change these and press Run
ROUTE = [(75, 128), (128, 75), (75, 22), (22, 75)]   # the corners of the patrol
TOO_CLOSE = 25       # cm: something is in the way
CLEAR = 45           # cm: the way is open again
PAST = 2.5           # seconds of driving on after a dodge
LOOK_EVERY = 10      # seconds between looks round
LOOK_FOR = 1.5       # seconds of turning on the spot

START = (75.0, 75.0)
leg = 0
dodging = False
phase = "turn"
until = 0.0
running = "patrol"


def where():
    px, py = position()
    return START[0] + px, START[1] + py


def wrap(a):
    return (a + 180) % 360 - 180


# ---- the leaves of the tree -------------------------------------------------
looking = False
last_look = 0.0
look_until = 0.0


def time_to_look():
    return looking or clock() - last_look > LOOK_EVERY


def look_around():
    global running, looking, last_look, look_until
    running = "look"
    if not looking:
        looking, look_until = True, clock() + LOOK_FOR
    drive(0, 0, 45)
    if clock() < look_until:
        return "running"
    looking, last_look = False, clock()
    return "success"


def blocked():
    return dodging or distance() < TOO_CLOSE


def dodge():
    global running, dodging, phase, until
    running = "dodge"
    dodging = True
    if phase == "turn":
        drive(0, 0, 45)
        if distance() > CLEAR:
            phase, until = "past", clock() + PAST
        return "running"
    drive(55, 0, 0)
    if clock() < until:
        return "running"
    phase, dodging = "turn", False
    return "success"


def patrol():
    global running, leg
    running = "patrol"
    x, y = where()
    tx, ty = ROUTE[leg]
    if math.hypot(tx - x, ty - y) < 12:
        leg = (leg + 1) % len(ROUTE)
        print(round(clock(), 1), "corner reached, next is", ROUTE[leg])
        return "success"
    a = wrap(math.degrees(math.atan2(tx - x, ty - y)) - heading())
    drive(55 if abs(a) < 30 else 0, 0, 3 * a)
    return "running"


# ---- the tree: one more branch, at the top ----------------------------------
TREE = ("selector", [
    ("sequence", [("condition", time_to_look), ("action", look_around)]),
    ("sequence", [("condition", blocked), ("action", dodge)]),
    ("action", patrol),
])


def tick(node):
    kind = node[0]
    if kind == "condition":
        return "success" if node[1]() else "failure"
    if kind == "action":
        return node[1]()
    if kind == "sequence":
        for child in node[1]:
            answer = tick(child)
            if answer != "success":
                return answer            # failure or running: stop here
        return "success"
    for child in node[1]:                # a selector
        answer = tick(child)
        if answer != "failure":
            return answer                # success or running: stop here
    return "failure"


NUMBER = {"patrol": 0, "dodge": 1, "look": 2}
COLOUR = {"patrol": "green", "dodge": "red", "look": "blue"}
trail = {name: [] for name in NUMBER}
was = ""
changes = 0
step = 0
while clock() < 60:
    tick(TREE)
    if running != was:
        changes = changes + 1
        print(round(clock(), 1), running)
        was = running
    plot("running", NUMBER[running])
    plot("distance", distance())
    trail[running].append(where())
    step = step + 1
    if step % 10 == 0:
        for name in trail:
            draw(name, trail[name], COLOUR[name])
    wait(0.1)
stop()
print("changes of branch:", changes, " corners reached:", leg)

Read the printed lines around 44 seconds. A dodge starts at 44.2 s, and at 44.8 s the look is due. The look branch is above the dodge branch, so on the next tick it wins, the robot turns on the spot for a second and a half, and at 46.4 s the dodge carries on from the phase it had reached. Nobody wrote a transition from TURN to LOOK, or a way back. The one thing the dodge does lose is its clock: until keeps counting while the look has the robot, so a dodge interrupted in its second half gets less driving on than it asked for. A behaviour that counts ticks instead of reading the clock does not have that problem.

To do the same to the state machine you would add a LOOK state, three transitions into it from PATROL, TURN and PAST, and a variable remembering which state to return to, because "go back to what you were doing" is not something a state machine can say. That is the scaling argument in one sentence: a new behaviour in a tree is one node in a list, and a new state in a machine is a new transition from every state that might be interrupted.

The counting is rough, because a real machine rarely needs every transition, but the shape of it is right. Behaviours that can interrupt each other grow as the square of their number in a state machine, and one at a time in a tree.

What a tree is bad at

• Order that matters. If the job really is one thing after another, a state machine or even a list of steps is clearer. A tree can do it with a sequence, but you are fighting the shape.
• Knowing why. In a state machine you can print the state and know exactly where you are. In a tree the answer is a path from the root, and by the next tick it may be a different path.
• Data between behaviours. Trees have no memory of their own. Every demo here needs globals (leg, phase, dodging), and real libraries give you a shared store, called a blackboard, for exactly that reason.
• The half-finished action. As the first demo shows, a branch is dropped as soon as a condition above it stops being true. Every serious tree ends up with some behaviours latched, as dodging is here.

Trees earn their place when behaviours pile up and priorities change: a game character with a dozen reactions, or a delivery robot that has to drop everything when a person steps in front of it. Under about four behaviours, write the state machine.

Where this is taught

• States and Priorities build the same idea of most urgent first, with the robot.
• Timers is where a behaviour that lasts a while comes from, which is what a running action is.
• Brains and Project: rescue put several behaviours together.
• Finite state machines and Mealy machines are the A level way of writing the same thing.
• Project: the behaviour controller writes behaviours as classes, which is how a tree library does it.
• The finite state machines guide covers states, transition tables and hysteresis in full.

Questions

What is a behaviour tree?

It is a tree of behaviours that a program walks from the top, many times a second. Each node answers success, failure or running. Composite nodes decide which child runs: a sequence stops at the first child that is not a success, and a selector stops at the first child that is not a failure. The leaves are conditions, which look at the world, and actions, which drive the robot.

What is the difference between a behaviour tree and a state machine?

A state machine writes down transitions: for each state, what takes it to which other state. A behaviour tree writes down behaviours in order of priority, and works out on every tick which one should be running. Adding a behaviour to a machine means adding transitions from every state it could interrupt. Adding one to a tree means adding one node. The machine is easier to follow when there are only a few states.

What are the node types in a behaviour tree?

Four to start with: condition and action, which are the leaves, and sequence and selector, which are the composites. Libraries add a few more: parallel, which ticks several children at once, and decorators, which change one child's answer, such as inverting it, repeating it, or only letting it run once a second.

What does running mean in a behaviour tree?

It means the node has started something that is not finished, so the tick should stop there and come back next time. It is what lets an action last several seconds without blocking the loop. A node that could only answer success or failure would have to finish inside one tick, and the robot could not react to anything while it did.

Why do games use behaviour trees?

Because a character's behaviour is a list of priorities that keeps growing during development, and a tree lets a designer add one without touching the others. Halo 2 is the game usually credited with making them standard, and most engines now ship with a tree editor.

Are behaviour trees used in real robots?

Yes. The common one is BehaviorTree.CPP, which is what ROS 2's navigation stack uses to decide what to do when a route is blocked or a goal is unreachable. The trees are written in XML and drawn in an editor called Groot, but the tick and the three answers are exactly what is on this page.

What is a blackboard in a behaviour tree?

A shared store that nodes read and write, because the tree itself holds no data. Where a node needs a number from another node, such as the corner the patrol is heading for, it goes on the blackboard. The demos here use ordinary Python globals for the same job.

How often should a behaviour tree be ticked?

Fast enough that the highest-priority condition is noticed in time. The demos tick ten times a second, so a reaction starts within 0.1 s. Ticking faster costs sensor reads and processing, and ticking slower means the robot is still doing the old thing when something urgent happens.

Learn it step by step

These lessons build the same ideas one at a time, each with tasks the simulator marks.

1. 5.1 The loop Behaviours, Robot club
2. 5.2 States Behaviours, Robot club
3. 5.3 Timers Behaviours, Robot club
4. 5.4 Priorities Behaviours, Robot club
5. 5.5 Brains Behaviours, Robot club
6. 5.6 Project: rescue Behaviours, Robot club
7. A6.1 Finite state machines Theory of computation, A level
8. A6.2 Mealy machines: FSMs with output Theory of computation, A level
9. A1.10 Project: the behaviour controller Programming techniques and object-oriented programming, A level