A Behavior Tree-inspired programming language for autonomous agents

Oliver Biggar, Iman Shames · 2024

Read A Behavior Tree-inspired programming language for autonomous agents by Oliver Biggar, Iman Shames (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-08654.txt.

Introduction

Oliver Biggar and Iman Shames proposed a programming language for autonomous agents in 2024. The design grows out of behavior trees, a popular way to plan robot and agent behavior. As trees get large, their simple model starts to limit what builders can express.

The authors list hard problems a fuller language must solve. It must react when choices change, watch safety conditions at all times, and pass data between actions. Small examples show that current tree methods handle these needs in ways that break modular design. They offer a small set of modular building blocks instead, give a full language spec, and build it in Haskell. A large tree is then rewritten as a short, clear program.

Catalog record

CREATOROliver Biggar, Iman Shames
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-08654

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Behavior Tree-inspired programming language for autonomous agents Oliver Biggar, Iman Shames Abstract We propose a design for a functional programming language for autonomous agents, built off the ideas and motivations of Behavior Trees (BTs). BTs are a popular model for designing agents behavior in robotics and AI. However, as their growth has increased dramatically, the simple model of BTs has come to be limiting. There is a growing push to increase the functionality of BTs, with the end goal of BTs evolving into a programming language in their own right, centred around the defining BT properties of modularity and reactiveness . In this paper, we examine how the BT model must be extended in order to grow into such a language. We identify some fundamental problems which must be solved: implementing ‘reactive’ selection, ’monitoring’ safety-critical conditions, and passing data between actions. We provide a variety of small examples which demonstrate that these problems are complex, and that current BT approaches do not handle them in a manner consistent with modularity. We instead provide a simple set of modular programming primitives for handling these use cases, and show how they can be combined to build complex programs. We present a full specification for our BT-inspired language, and give an implementation in the functional programming language Haskell. Finally, we demonstrate our language by translating a large and complex BT into a simple, unambiguous program. 1 Introduction How do we express agent behavior in a programming language? Understanding this question is key to designing reliable autonomy in robotics. Compared to traditional programming, autonomous systems present new challenges and requirements [ 19 ] , in particular an emphasis on real-time behavior , safety and transparency . We would like to be able to design our autonomy in a language which is centred on these fundamental principles. One model for behavioral programming is the Behavior Tree (BT) [ 10 ] . This tree-structured design originated in game AI, and has become significantly popular in both game AI and robotics [ 16 , 26 ] . Their popularity reflects their simple and effective design philosophy, which places the key principles of modularity and real-time reactiveness in a central role [ 9 , 5 ] . The building blocks of BTs (the leaves of the tree) are asynchronous actions, which can take time and succeed or fail. We build more complex behaviors from these actions through by composition, using a small number of ‘control flow nodes’. This gives the model a simple tree structure, and reasoning about behavior remains straightforward, even as the tree grows. Further, the two main control flow nodes, Sequence and Fallback, have built-in real-time reactiveness to unexpected events [ 26 ] , reflecting the importance of this kind of behavior in building autonomous systems. The importance of modularity and reactiveness is one of the main differences between BTs and the previously-dominant behavioral model, Finite State Machines (FSMs) [ 15 ] . FSMs are an expressive model with uses in many fields, but this flexibility can lead to abuse, and in practice FSMs can grow to great size and complexity as the modelled behavior grows [ 10 ] . The structure of FSMs is similar to early imperative languages which made extensive use of the goto statement [ 11 ] , resulting in unreadable ‘spaghetti code’ [ 10 ] . BTs, by contrast, have a structure which resembles a function call, and this programming analogy is a one of the original motivations for BTs [ 24 ] . This reflects a general programming principle learned in the structured programming revolution: a language should not only make good programming easy, it should make bad programming difficult. BTs isolated the strengths and weakness of FSMs, and built these into a new model which strictly enforced a modular design. More generally, and perhaps unsurprisingly, programming language design has been a significant source of inspiration for both BT concepts and philosophy [ 10 , 24 , 3 , 5 ] . A new ecosystem of tools has grown around the simple core model of BTs, augmenting them with constructs for handling data [ 29 , 27 ] , concurrency [ 7 ] , parallelism [ 6 ] , learning [ 30 , 18 ] , formal methods [ 2 , 28 ] , and much more [ 8 , 16 , 10 , 13 ] . Moreover, tools exist to automatically generate code from BTs, written in a visual editor or XML [ 12 ] . The result is that BTs are approaching a programming language in their own right, reflecting the value of the original reactiveness and modularity principles. The myriad of BT extensions are necessary precisely because BTs are a model and not a programming language. This means that their core semantics are comparatively underspecified. This makes sense—BTs are a tool for us to think in a modular way about behavior design, and this is what they achieve. The presence of these extensions, as we see it, is a call for more functionality from BTs, that is, for them to evolve into a fully-fledged programming language centred on the principles of behavioral programming. This evolution into a programming language is already taking place, in an ad hoc and piecemeal way [ 8 ] . However, there is a problem. The tree presentation of BTs, useful as a conceptual tool, presents a challenge for extensions. Importing additional functionality—including basic concepts from programming, like loops and variables—requires the overhead of building new control flow nodes. Accordingly, the simple BT model is being increasingly swamped by a proliferation of constructs borrowing different programming concepts and translating them into tree form [ 22 , 14 ] . By reinventing the wheel, BT extensions risk wasting half a century of insight from programming language design, leading to solutions which are not consistent with good programming practice [ 29 , 22 , 8 , 1 , 4 , 3 ] . Examples include [ 10 ] : Blackboards, the standard mechanism for introducing data to BTs, which is built on global variables (Section 4 ); using Success and Failure for both booleans and exceptions, leading to cases where we can’t distinguish between a failed behavior or a false value (Section 4.1 ); using Sequence and Fallback to implement branching in the absence of an if -statement; using auxiliary variables to implement stateful behavior (Section 3.2 ); and more. Similarly, the ‘tick’ mechanism used to create reactiveness can be misleading in concurrent implementations, leading to chattering or an inability to make progress (Section 3 ). This problems are in contrast with the programming analogies which motivated the original popularity of BTs. In our view, these problems arise from the original BT model having outgrown its roots. There is a natural solution, however. Just as BTs isolated the key strengths and weaknesses of FSMs and built them into a stricter framework for behavior modelling, we believe the time has come for a full programming language which is built on the key principles and use cases of BTs. That is, a language whose fundamental units are asynchronous actions, with a small set of built-in constructs to combine those units into larger units in a

Read the complete text