# An expressiveness hierarchy of Behavior Trees and related architectures

arXiv: https://arxiv.org/abs/2104.07919 · HTML: https://mlsanity.com/paper/2104.07919/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 27 references that are in the map.
- First posted on arXiv 16 Apr 2021.

## Builds on (most cited first, 5 of 5)

- [Behavior Trees in Robotics and AI: An Introduction](https://mlsanity.com/paper/1709.00084/) (2017)
- [A Survey of Behavior Trees in Robotics and AI](https://mlsanity.com/paper/2005.05842/) (2020)
- [On modularity in reactive control architectures, with an application to formal verification](https://mlsanity.com/paper/2008.12515/) (2020)
- [A principled analysis of Behavior Trees and their generalisations](https://mlsanity.com/paper/2008.11906/) (2020)
- [Hidden Markov Models derived from Behavior Trees](https://mlsanity.com/paper/1907.10029/) (2019)

## Built on by (most cited first, 6 of 6)

- [Behavior Trees in Robot Control Systems](https://mlsanity.com/paper/2203.13083/) (2022)
- [A Study on Training and Developing Large Language Models for Behavior Tree Generation](https://mlsanity.com/paper/2401.08089/) (2024)
- [Continuous-Time Behavior Trees as Discontinuous Dynamical Systems](https://mlsanity.com/paper/2109.01575/) (2021)
- [Multimodal Behavior Tree Generation: A Small Vision-Language Model for Robot Task Planning](https://mlsanity.com/paper/2603.06084/) (2026)
- [An Extended Convergence Result for Behaviour Tree Controllers](https://mlsanity.com/paper/2308.08994/) (2023)
- [Execution Semantics of Behavior Trees in Robotic Applications](https://mlsanity.com/paper/2408.00090/) (2024)

## Abstract (arXiv)

In this paper we provide a formal framework for comparing the expressive power of Behavior Trees (BTs) to other action selection architectures. Taking inspiration from the analogous comparisons of structural programming methodologies, we formalise the concept of `expressiveness'. This leads us to an expressiveness hierarchy of control architectures, which includes BTs, Decision Trees (DTs), Teleo-reactive Programs (TRs) and Finite State Machines (FSMs). By distinguishing between BTs with auxiliary variables and those without, we demonstrate the existence of a trade-off in BT design between readability and expressiveness. We discuss what this means for BTs in practice.