TY - JOUR
T1 - An Expressiveness Hierarchy of Behavior Trees and Related Architectures
AU - Biggar, Oliver
AU - Zamani, Mohammad
AU - Shames, Iman
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2021/7
Y1 - 2021/7
N2 - In this letter, 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.
AB - In this letter, 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.
KW - Control architectures and programming
KW - methods and tools for robot system design
KW - software architecture for robotic and automation
UR - http://www.scopus.com/inward/record.url?scp=85104628603&partnerID=8YFLogxK
U2 - 10.1109/LRA.2021.3074337
DO - 10.1109/LRA.2021.3074337
M3 - Article
SN - 2377-3766
VL - 6
SP - 5397
EP - 5404
JO - IEEE Robotics and Automation Letters
JF - IEEE Robotics and Automation Letters
IS - 3
M1 - 9409618
ER -