An expressiveness hierarchy of Behavior Trees and related architectures
This work addresses a foundational issue for researchers and practitioners in robotics and AI by providing a formal comparison of control architectures, though it is incremental as it builds on existing structural programming methodologies.
The paper tackles the problem of comparing the expressive power of Behavior Trees (BTs) to other action selection architectures by formalizing expressiveness, resulting in an expressiveness hierarchy that includes BTs, Decision Trees, Teleo-reactive Programs, and Finite State Machines, and demonstrating a trade-off between readability and expressiveness in BT design.
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.