M7-T5 — Behavior Trees for Navigation

Learning objectives

After this lesson, you should be able to:

• Define tick, status (success, failure, running), sequence, fallback, condition, action and retry.
• Trace a tick through a small tree and write down the leaves that were visited.
• Build a tree that plans, drives, recovers in a sensible order and asks for help last.
• Compare a tree with a finite state machine and say how Nav2 uses trees to wrap planning and recovery.

The intuition

Think of a nurse’s checklist for delivering a sample. “Pick up the sample. Walk to the lab. Hand it over.” If any step fails, the checklist stops: that is a sequence. Now think of a rule for getting through a door: “push it; if that fails, pull it; if that fails, call security.” The first option that works ends the search: that is a fallback. Trees are made by nesting those two. “Deliver the sample, or else try the recovery routine, or else ask for help” puts sequences inside a fallback.

The key difference from a flowchart is that the whole tree is ticked over and over, usually ten times a second or more. Each tick starts at the root and decides again what to do. A node returns success, failure or running (“I am still working, call me again”). Because every tick re-checks the conditions at the top, a robot that is driving along a path notices that the path has just become blocked and reacts on the next tick, without any special transition.

That is also why trees scale. In a state machine every new behaviour needs transitions to and from the others. In a tree you insert a subtree where it belongs, and the rest keeps working.

The mathematics

Node types

The status running propagates upward: a sequence or a fallback whose current child is running is itself running, and the later children are not ticked. This is what stops a recovery from starting while the robot is still driving.

Reactive and memory nodes

A reactive sequence or fallback restarts from its first child on every tick, so a condition at the front is re-checked while a later action runs. A node with memory resumes at the child that was running. Reactive nodes keep the robot responsive; memory nodes avoid repeating finished work. Libraries offer both, and which one you meant is a common source of bugs.

Decorators and the blackboard

Decorators wrap one child and change when or how it runs: retry, timeout, rate limit, inverter. A blackboard is the shared key–value store through which nodes pass data (a goal, a path), kept outside the tree structure.

Trees and state machines

A worked example

Ticking the tree of the figure. The leaves return the following statuses over three ticks: the path becomes clear after the costmap is cleared, and follow_path runs for two ticks before it succeeds.

tick 1: path_clear = failure  → first sequence fails
        clear_costmap = success, follow_path = running
        → fallback returns running      visited [path_clear, clear_costmap, follow_path]
tick 2: path_clear = success, follow_path = running
        → fallback returns running      visited [path_clear, follow_path]
tick 3: path_clear = success, follow_path = success
        → fallback returns success      visited [path_clear, follow_path]

On tick 2 the reactive root starts from the first child again, finds the condition now true, and no longer needs the recovery branch. If follow_path had failed on tick 3, the first sequence would fail and the root would run the recovery branch again, then ask for help.

The order of recoveries. Scout has four recoveries with a time cost and a risk level (0 harmless, 1 moves blind, 2 turns in place). Score each as cost + 10 · risk: clear_costmap 1, wait 5, back_up 8 + 10 = 18, spin 12 + 20 = 32. Each recovery fixes one cause: ghost, person, wedged, dead-end pose. Run one after another and then retry the drive:

order                                  expected cost per fault
clear, wait, back_up, spin            (1 + 6 + 24 + 56) / 4 = 21.75
wait, clear, back_up, spin            22.75
spin, back_up, wait, clear            (56 + 55 + 50 + 32) / 4 = 48.25

Cheapest first costs less than half of the worst order on average, and, more importantly, avoids the risky spin until nothing safer worked (lab M7-L3, stage 2). A tree that puts all recoveries in one sequence runs all four every time: cost 56 for every fault.

Where Nav2 does this. Nav2’s navigator is a behaviour-tree executor. The default tree for navigating to a pose plans at a limited rate, follows the path, and wraps both in recovery nodes with a bounded number of retries; on repeated failure it runs a round-robin of recoveries such as clearing the costmaps, spinning, waiting and backing up. The exact tree is an XML file you can read and change, and its shape is the one used above.

Engineering implications and limitations

Keep leaves small and honest

An action should do one thing and report its status truthfully. “Follow path” returns running while it drives, success on arrival and failure when the controller gives up. An action that returns success to “keep the tree moving” hides the problem from every node above it.

Every retry has a budget

A tree without bounds on retries and recoveries can loop for ever. Give each recovery and each retry a limit, and end with a branch that tells a person (lab M7-L3, stage 3). The tree is the right place for these limits because they are policy, readable without compiling anything.

Recoveries need preconditions

Backing up needs free space behind; spinning needs clearance all round. Put these as conditions in front of the action, or the tree will cheerfully drive into a wall (lesson M7-T6).

Log the ticks

Record which leaves ran and their statuses. A tree is easy to read after the fact only if the log says which branch fired, and that is the first thing to look at in a failed run (lesson M1-T6).

A tree is policy, not safety

A behaviour tree orders actions; it does not guarantee that any of them is safe. The safety of a stop, a back-up or a spin comes from the layers below (lesson M7-T2) and from a safety case for the machine as a whole. This track does not replace that work.

Common misconceptions

Engineering takeaways

1. A tree is ticked repeatedly; each node returns success, failure or running.
2. A sequence stops at the first child that is not a success; a fallback stops at the first child that is not a failure.
3. Running passes upwards and prevents later children, such as recoveries, from starting.
4. Order recoveries by cost and risk, give them preconditions and budgets, and end with a request for help.
5. The tree orders actions; safety comes from the layers beneath it and from a proper safety case.

References and further reading

The behaviour-tree book is the standard primary reference; the Nav2 pages describe the trees used in practice.

• M. Colledanchise and P. Ögren, “Behavior Trees in Robotics and AI: An Introduction”, CRC Press, 2018.
• M. Colledanchise and P. Ögren, “How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture, and Decision Trees”, IEEE Transactions on Robotics, 33(2), 2017.
• S. Macenski, F. Martín, R. White and J. Ginés Clavero, “The Marathon 2: A Navigation System”, IEEE/RSJ IROS, 2020.
• Nav2 documentation, “Behavior Trees” and “Navigation Concepts”, docs.nav2.org; BehaviorTree.CPP documentation.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: how to tell that a robot is stuck, and how to choose and bound the recoveries.

Related content

Nothing below is required to finish this lesson.

• Before
  M7-T4: Perception Failures: Glass, Dust and Dropouts

  List the sensing failures that make costmaps lie, and the checks that expose them.

• Lab
  M7-L3: Build a Recovery Behavior Tree

  Scout gives up at the first obstacle: build a tree that retries, clears, backs up and then asks for help.