A principled analysis of Behavior Trees and their generalisations

Abstract

As complex autonomous robotic systems become more widespread, the need for transparent and reusable Artificial Intelligence (AI) designs becomes more apparent. In this paper we analyse how the principles behind Behavior Trees (BTs), an increasingly popular tree-structured control architecture, are applicable to these goals. Using structured programming as a guide, we analyse the BT principles of reactiveness and modularity in a formal framework of action selection. Proceeding from these principles, we review a number of challenging use cases of BTs in the literature, and show that reasoning via these principles leads to compatible solutions. Extending these arguments, we introduce a new class of control architectures we call generalised BTs or $k$-BTs and show how they can extend the applicability of BTs to some of the aforementioned challenging BT use cases while preserving the BT principles.