arxiv.org/abs/1709.00084.Three statements open the deck, and the third is the ambitious one:
Chapter 6 gave two complaints about finite state automata: they are not easy to extend (the whole automaton must be redefined) and they are not modular. Behavior trees are the answer to both, while keeping the property that made FSAs attractive — a clean separation between the model you specify and the general code that executes it. And because BTs subsume the subsumption architecture too (section 5), a single formalism covers both of the arbitration mechanisms you have studied.
The introductory example in the slides is a high-level BT carrying out a task consisting of first finding, then picking and finally placing a ball — a sequence of three sub-tasks, which is exactly what the sequence control node expresses.
A BT is a tree structure that contains one root node, control nodes, and execution nodes (actions or conditions).
The structural rules:
Execution nodes are the leaves and come in two kinds — actions and conditions — whose semantics are given in section 3. The book that supports these slides (Colledanchise & Ögren, 2018) organises the control nodes into four categories — Sequence, Fallback, Parallel and Decorator — and the execution nodes into the two categories just named; the course slides, following Kuckling et al. (2018), present six different types of control nodes. The two you must be able to execute by hand, and the two the lectures develop, are the Fallback and the Sequence.
Execution is controlled by a tick generated by the root and propagated through the tree. When ticked by its parent, a node is activated. After execution, it returns one of three possible values:
success | failure | running| Node kind | Returns success | Returns failure | Returns running |
|---|---|---|---|
| Condition | if its condition is fulfilled | otherwise | — |
| Action | if its action is completed | if its action cannot be completed | if its action is still in progress |
| Control | distributes the tick to its children; its return value depends on those returned by the children | ||
Condition nodes that are ticked observe the world state. Note that they do not act: this is the formal separation between "checking" and "doing" that the FSA of Chapter 6 blurred into its transition table.
The slides spell out how a BT stays reactive: "In the basic implementation, the execution process traverses down from the root of the tree every single step, testing each node down the tree to see which is active, rechecking any nodes along the way, until it reaches the currently active node to tick it again."
Every tick re-evaluates all the conditions on the path. That is why a running pick ball action is abandoned the instant a higher-priority condition becomes true — no explicit interrupt, no transition to write. Compare the FSA, where you would have had to add an edge from every state to the emergency state by hand.
Selector node ≡ Fallback node. The slides state it twice, because the literature uses both names for the same thing. The course figures label it ?; the sequence node is labelled →.
Sequence → | Fallback / Selector ? | |
|---|---|---|
| Ticks children | left to right | left to right |
| Stops and returns failure | as soon as a child returns failure | only if all children return failure |
| Stops and returns success | only if all children return success | as soon as a child returns success |
| Returns running | if a child returns running | if a child returns running |
| Reads as | "do this and then this and then this" | "try this, or else this, or else this" |
| Encodes | a dependency between sub-tasks | a priority ordering between alternatives |
The "pick a ball" tree from the lectures. Set the world state, then tick. Watch the traversal start again from the root every single step and recheck the nodes along the way.
This is the section that makes good on the claim "BTs subsume the subsumption architecture". The recipe, verbatim:
Given a subsumption architecture, we can create an equivalent BT by arranging the controllers as actions under a Fallback composition, from highest to lowest priority, from left to right.
Furthermore, we let the return status of the actions be Failure if they do not need to execute, and Running if they do. They never return Success.
Each behavior contains both its activation conditions and the execution code.
Take a moment on the middle clause, because it is the clever part. A fallback ticks its children left to right and stops at the first one that does not fail. If a behaviour returns failure exactly when it has nothing to say, then the fallback automatically slides down the priority list until it finds a behaviour that wants to act — and that behaviour returns running, which stops the traversal and gives it the actuators. "Never return success" guarantees the tree never terminates: a robot controller is not a task that completes.
The worked example maps the three-level stack of Chapter 6 onto three children:
| Subsumption level | Position under the fallback |
|---|---|
| Level 2 — Obstacle avoidance | leftmost (highest priority) |
| Level 1 — Phototaxis | middle |
| Level 0 — Random walk | rightmost (lowest priority) |
Set the world and compare which behaviour takes control in the subsumption stack and in the equivalent BT. They agree, always — that is what "subsumes" means.
The deck then presents a variant of the same design:
Structurally, each behaviour becomes a sequence of (condition, behaviour), and those sequences become the children of the fallback:
| Pros | Cons |
|---|---|
| Favours modularity and reuse | Code might be redundant, and care must be taken about coherence between condition and behaviour |
The coherence problem is real and subtle. If the obstacle-avoidance condition triggers at 20 cm but the obstacle-avoidance behaviour was written assuming it is invoked at 10 cm, the tree is perfectly well formed and the robot misbehaves. In the section 5 design this could not happen, because the behaviour owned its own activation condition. Modularity has a price, and the exam likes you to be able to name it.
Choose which design you are reasoning about, then read what changes when you want to reuse phototaxis in a second robot with different sensors.
The deck points to a practical implementation: "A nice implementation of BTs in Lua (suitable to be used with ARGoS) is provided by Michael Allwright" — github.com/allsey87/luabt.
-- the subsumption-equivalent tree of section 5, as a BT specification
-- FAILURE = "I do not need to execute"; RUNNING = "I am taking control"
local tree = {
type = "fallback", -- the "?" node: try each child in priority order
children = {
{ type = "action", fn = obstacle_avoidance }, -- highest priority, leftmost
{ type = "action", fn = phototaxis },
{ type = "action", fn = random_walk } -- lowest priority, rightmost
}
}
function obstacle_avoidance()
local d = nearest_obstacle()
if d > THRESHOLD then return "failure" end -- nothing to do: let the next child try
drive_away_from(d)
return "running" -- taking control; never returns success
endBehavior trees reappear twice more in the course, and it is worth flagging both now:
A very likely question is: compare FSMs, the subsumption architecture and behavior trees as coordination mechanisms. The skeleton of a good answer: all three are arbitration (competitive) mechanisms. FSMs allow formal analysis and separate model from execution, but are not modular and not easy to extend. The subsumption architecture gives incremental design and graceful degradation, but its priority hierarchy is fixed and expressed in wiring. BTs are modular and reactive, they re-evaluate conditions at every tick, and they subsume both of the previous models — a fallback with children ordered by priority reproduces subsumption exactly, given the failure/running convention.
A BT is a way to structure the switching between different tasks. BTs are a very efficient way of creating control software for a robot that is modular and reactive, and they subsume several previous models, such as FSMs and the subsumption architecture.
A tree structure containing one root node, control nodes, and execution nodes (actions or conditions). The root is the node without parents; all other nodes have exactly one parent; control nodes have at least one child. Standard parent/child terminology is used for connected nodes.
Success, failure, running. A condition node observes the world state and returns success if its condition is fulfilled, failure otherwise. An action node returns success if its action is completed, failure if it cannot be completed, and running if it is still in progress. A control node distributes the tick to its children and its return value depends on those returned by the children.
The tick is generated by the root and propagated through the tree; a node ticked by its parent is activated. In the basic implementation, the execution process traverses down from the root every single step, testing each node to see which is active and rechecking any nodes along the way, until it reaches the currently active node and ticks it again. Because every condition on the path is re-evaluated at every tick, a running action is abandoned as soon as a higher-priority condition becomes true — no explicit interrupt is needed.
Both tick their children left to right. A sequence (→) returns failure as soon as a child fails and success only if all children succeed — it encodes a dependency: "do A and then B and then C". A fallback (?), also called a selector, returns success as soon as a child succeeds and failure only if all children fail — it encodes a priority ordering: "try A, or else B, or else C". Both return running if a child returns running.
Arrange the controllers as actions under a Fallback composition, from highest to lowest priority, from left to right. Let the return status of the actions be Failure if they do not need to execute and Running if they do; they never return Success. Each behavior contains both its activation conditions and the execution code.
Because a fallback returns success as soon as one child succeeds, which would terminate the composition. A robot controller is not a task that completes: it must keep running. Returning only failure ("I have nothing to do, try the next child") or running ("I am taking control") makes the fallback slide down the priority list every tick and stop at the highest-priority behaviour that wants to act.
A single fallback node with three action children, left to right: Obstacle avoidance (level 2, highest priority), Phototaxis (level 1), Random walk (level 0, lowest priority).
Behavior nodes are run only if the condition is satisfied: each behaviour becomes a sequence of (condition, behaviour), and these sequences are the children of the fallback. This lets us compose previously coded behaviors by adding suitable execution conditions. Pros: favours modularity and reuse. Cons: code might be redundant, and care must be taken about coherence between condition and behaviour.
All three are competitive (arbitration) schemes. FSMs: powerful for composing simple behaviours, allow formal analysis, and separate model from execution — but are not modular and not easy to extend, since the whole automaton must be redefined. Subsumption: incremental design, graceful degradation (partition at any level and the layers below still work), at most one level drives the actuators — but the priority hierarchy is fixed and encoded in suppression/inhibition wiring. BTs: modular and reactive, conditions rechecked at every tick, and they subsume both of the other models.
In automatic design (Chapter 11): the Kuckling, Ligot, Bozhinoski and Birattari paper cited in this deck is about behavior trees as a control architecture in the automatic modular design of robot swarms, where the tree is produced by an optimisation algorithm. And in experimental evaluation (Chapter 15), where two of the compared controllers are the same subsumption controller implemented with two different BTs, and the Wilcoxon test returns p = 0.661 — no evidence that they differ.