A robot’s high-level behaviour is more than a single algorithm. It must follow a line until it reaches an intersection, then decide which branch to take, then navigate to a goal, but stop if an obstacle appears. Structuring this kind of conditional, sequential, reactive logic requires a principled architecture. This chapter covers two widely used approaches: Finite State Machines (FSMs) and Behaviour Trees (BTs).
An FSM consists of:
EXPLORE → (obstacle ahead) → AVOID
AVOID → (obstacle cleared) → EXPLORE
EXPLORE → (goal reached) → STOP
In Python:
from enum import Enum, auto
class State(Enum):
EXPLORE = auto()
AVOID = auto()
STOP = auto()
class RobotFSM:
def __init__(self):
self.state = State.EXPLORE
def tick(self, sensors):
if self.state == State.EXPLORE:
if sensors.obstacle_ahead:
self.state = State.AVOID
elif sensors.goal_reached:
self.state = State.STOP
else:
drive.move(0.25, 0.0)
elif self.state == State.AVOID:
cmd = potential_field_avoid(sensors)
drive.move(*cmd)
if not sensors.obstacle_ahead:
self.state = State.EXPLORE
elif self.state == State.STOP:
drive.stop()
FSMs scale poorly: adding a new condition may require adding transitions from every existing state. A 10-state robot FSM with 5 conditions can have up to 50 transitions to manage. Readability degrades rapidly. Hierarchical FSMs (sub-states within states) help, but the underlying problem remains.
A Behaviour Tree is a tree structure where:
Each node, when ticked, returns one of three statuses: SUCCESS, FAILURE, or RUNNING (if the action needs more time).
Sequence (→): ticks children left to right. Returns SUCCESS if all children succeed; returns FAILURE as soon as any child fails; returns RUNNING if the current child is running.
Fallback / Selector (?): ticks children left to right. Returns SUCCESS as soon as any child succeeds; returns FAILURE if all children fail; returns RUNNING if the current child is running.
Parallel: ticks all children simultaneously. Policy: succeed if $M$ of $N$ children succeed.
Fallback
├── Sequence (navigate safely)
│ ├── Condition: path_is_clear
│ └── Action: follow_path
└── Sequence (avoid obstacle)
├── Condition: obstacle_detected
└── Action: execute_avoidance
This tree first tries to follow the path (if it’s clear). If the path is not clear, it falls back to the avoidance sequence. The logic is easy to read and extend.
class NodeStatus(Enum):
SUCCESS = auto()
FAILURE = auto()
RUNNING = auto()
class Sequence:
def __init__(self, children):
self.children = children
self._idx = 0
def tick(self, blackboard):
while self._idx < len(self.children):
status = self.children[self._idx].tick(blackboard)
if status == NodeStatus.RUNNING:
return NodeStatus.RUNNING
if status == NodeStatus.FAILURE:
self._idx = 0
return NodeStatus.FAILURE
self._idx += 1
self._idx = 0
return NodeStatus.SUCCESS
The blackboard is a shared dictionary that nodes use to communicate (e.g., the current sensor readings, planned path, goal pose). It serves the same purpose as global variables but with explicit access control.
| Property | FSM | Behaviour Tree |
|---|---|---|
| Readability | Good for small FSMs | Scales well |
| Reactivity | Transition-based | Re-ticked every cycle |
| Modularity | Poor (entangled edges) | Excellent (subtrees) |
| Memory | Current state | Running node per path |
| Debugging | State log | Node status log |
For robots with more than 5–6 distinct behaviours, BTs are almost always the better choice. The py_trees library provides a production-quality BT framework for Python, including visualisation tools.
Decorators wrap a single child node and modify its behaviour:
The Timeout decorator is particularly useful for robotics: if the execute_avoidance action is still RUNNING after 10 seconds, something has gone wrong and the robot should try another approach.
A complete robot mission can be structured as a top-level BT with sub-trees for each phase:
Sequence (full mission)
├── Action: initialise_hardware
├── Action: build_initial_map
├── Fallback (navigate to goal)
│ ├── Sequence
│ │ ├── Condition: path_known
│ │ └── Action: execute_path
│ └── Action: explore_to_find_path
└── Action: report_mission_complete
The explore_to_find_path subtree internally uses the reactive navigation algorithms from Chapter 9 while building the map incrementally (Chapter 12). This nested use of behaviours is where BTs shine over FSMs.
Chapter 15 instantiates this architecture for the capstone navigation task.
Navigation: