Before you go, check out these stories!

0
Hackernoon logoBehaviors Trees in AI: Why you Should Ditch Your Event Framework by@superstable

Behaviors Trees in AI: Why you Should Ditch Your Event Framework

Author profile picture

@superstableT de Souza

Developed Active Logic and Antistar: Rising; Intelligent control guy; narrative, immersive stuff

In this article, I look into some of the shortages of event-driven
programming and suggest behavior trees as an effective alternative,
suitable for back/front-end application development.

What is AI? (and what event frameworks have to do with it)

In 2020, for most people, AI is machine learning (ML). While ML is a revolution in its own right, it does not affect day to day application development.

Although Wikipedia roots artificial intelligence in classical philosophy, the cornerstone is formal reasoning - the idea that human thought can be mechanized.

TLDR: every computer program is AI, and the question becomes, what kind of AI does your program need? For most application developers handling events and interruptions is the norm, and the idea here is that a program receives a signal, such as a mouse button press, or an incoming request over the network, and (hopefully) there is enough context to process the request effectively.

So, is this a good thing? It has to be good, right? This is how we've been writing programs since the 1980s! Either that, or we are overlooking swathes of bugs?

Correctness vs Efficiency

Over on dev.to, I explained the difference between event handling and update loops from a management perspective: an event interrupts ongoing workflows. This only works when the problem at hand is very localized. Whereas running an update loop is like standup meetings. Concise, frequent standups are useful to keep team members synchronized.

The advantage of a "walk-in" policy is promoting a fast response. Event handling offers speed at the cost of accuracy, because we may be taking a decision without consulting the team.

Conversely, standups are often pretty bland as there isn't always something new or interesting happening. In fact, the takeaway from many stand up meetings is "keep at it". As such update loops promote correctness at the cost of efficiency.

In computer programming there is a rule about optimization: don't optimize.

Speed at the cost of accuracy is a raw deal.

The lesson here is: actively move away from event handling and get application development back in the (update) loop.

What is a Behavior Tree?

Behavior trees are a new (~2010) control paradigm based on tasks. A task can be succeeding, failing or running. Behavior trees are like decision trees (an intuitive concept, I hope) with the time dimension factored in.

Behavior trees were first introduced in games (Halo). They are making headway in robotics and the point of this article, essentially, is encouraging developers to consider their potential in developing interactive, time aware applications (front/back-end).

A behavior tree hooks a top-down decision process onto an update loop. The running state allows postponing decisions until an ongoing task has completed.

"Not done yet" is a specific flavor of uncertainty (see my paper on Arxiv).

As a case in point functional programming: (C/C++/Java/Python/Swift/[yourlang]) is already good at decision trees and this boils down to: if-elses understand decisions; bools understand decisions. So long as a yes/no answer can be provided.

What traditional control flow is not handling well is the "not done yet" factor involved in interaction - be it with users, other applications (local), or networked computers.

With BTs, the primary control flow structures are sequences and selectors:

  • A Sequence ( โˆ ) iterates a list of tasks, until the first failing (not succeeding or running) task is encountered.
  • A Selector ( โฐ ) iterates until the first succeeding task (and for this reason that is also known as a 'fallback node').

For clarity it is really important to understand that a sequence is not an action queue. If we have a sequence of tasks A, B, C we are going to run:

  1. A until it succeds.
  2. A and B until B succeeds (A is not really running at this stage; only acknowledging it is already succeeding).
  3. A and B and C until C is also succeeding.

Not coincidentally this execution model is stateless. Where no state is stored no state is out of date.

Similar to standup meetings (where we get information from everybody) stateless execution ensures correctness.

Behavior trees in code

"Behavior trees" - the wording has visual flair and it is also true that (in game development) BTs are perhaps most successful through visual tools.

Part of the problem (we are writing computer programs, not drawing arrows and boxes) was, as I already noted functional programming is good at decision trees, and control flow is designed to handle binary logic - not the three-valued logic implied by a 'running' state.

On the whole functional languages are not very well suited to intelligent control in the sense that, almost anything that goes beyond if-elses needs an explicit data/node structure.

Two years ago I redefined BT using binary operators and started working on a new behavior tree library; works especially well in C# (because they wanted to support three valued logic re: SQL), and to some extent still works (some memory/perf. overheads) in other languages.

This approach leads to concise control code; here is a small example showing how BT programs look using the Active Logic library:

// Sequence
status MySequence() 
=> TaskA() && TaskB() && TaskC();

// Selector
status MySelector()
=> A() || B() || ...;

A small gripe is, other than C#, no mainstream language does preserve the short-circuiting behavior of the (overloaded) conditional operators.

Still, behavior trees may be supported gracefully, effectively and efficiently in any of these languages, with the one feature needed filed under "oversight".

In the meantime C# is a better choice than you'd know. Via .NET Core it is cross platform and installs like a breeze (on Linux too).

The Active Logic library lives on Github (also, NuGet).

Disclosure: I am the author of the Active Logic Library; in the Unity Asset Store (and beyond AGPL) variants of this library may be sold; the A.L. calculus is MIT-Licensed.

Tags

Join Hacker Noon

Create your free account to unlock your custom reading experience.