Behavior trees in Haskell

Question

I've heard how there are strategies in Haskell for tree implementation, but I haven't found any information about a good behavior tree alternative.

My goal: Given a tuple representing a state, what's the best pattern for feeding that tuble to a tree of behavior nodes that each return busy/error/completed/running based on the tuple. The behavior may also change the tuple (causing a state change).

Nested nodes can be executed based on the strategy of their parent node. For example, if a child node returns 'error', no more child nodes will be evaluated. Another strategy is to execute all child nodes even if an error state is returned.

I hope this makes sense!

Answer 1

We're all a bit confused by your question, and I may not understand what you mean when you say "tuple", but shot in the dark:

I wrote a small library called simple-actors that is meant for Actor Model concurrency. If you can imagine what you need being accomplished by "actors" listening on concurrent "channels" and communicating to each other, then you might be interested in taking a look.

At the top of the docs here is an example of a sort of binary search tree of actors (your question brought that to mind, sorry if this is all off the mark).

Edit: I should mention I found the wikipedia page on Behavior Trees completely inscrutable; perhaps someone familiar with the enterprisey jargon can help.

Answer 2

Unfortunately you seem to be an expert in a niche that very few Haskell users know much about. All I know about these technologies is what I have overheard from non-technical people talking about different business rules engines, so I'm probably off-base but I think it's worth a shot since everyone else is stumped.

As far as forward-chaining reasoning systems and the Rete algorithm in particular, they're basically functional already. They iterate and add more knowledge to the database as they go until they run out of things to do. Provided you don't allow arbitrary effects, it would be a simple Control.Monad.State port; if you need arbitrary effects you can use a state monad transformer instead, and it's not something intermediate/advanced Haskellers would be all that intimidated by. You may find something you can use on the Haskell site but if you wind up doing this yourself the Monad Transformers chapter of Real World Haskell is indispensable.

I don't know anything about behavior trees, but at a glance on Wikipedia they look to me like the Rete algorithm plus concurrent processes in the background. If that's even close to correct, then you have to decide whether or not you need concurrency or parallelism. If you're content with pure values "magically" being computed faster (and, by extension, everything being written in Haskell) then you can get away with using the stuff in Control.Parallel for not much effort but you won't be able to (say) inquire which processes are running and which are not. If you genuinely need different observable behavior, then you'll need Control.Concurrent and it's less magical, so more book-keeping. Simon Marlow wrote a pretty nice tutorial about your options there. What you're describing sounds lower-level to me than most of the cool stuff Haskell can do for you; if you decide to accept a higher-level interface you may find it easier to implement. I'm far from an expert on this topic either.

Answer 3

Having found no BT implementations, I started some kind of implementation of BTs in Haskell myself, described here:

http://www.brainific.com/blog/2015/09/twisting-your-trees/

and stored here:

https://bitbucket.org/brainific/action-fw/src

With specific tests here:

https://bitbucket.org/brainific/action-fw/src/a6081b740dc4b8258f67f49df473458737fc4240/test/BehaviourTrees21Test.hs?at=master&fileviewer=file-view-default

Please note some different features from standard industry BTs:

• The trees are event driven, in a way that resembles more a tree of event handling processes than the more usual polled tree;
• Event types are generic: Success/Failure/Running states form just another event type, handled with transition functions, so you can actually mix and match BT nodes and FSM nodes with little fuss;
• Event nodes are not static, but rather generated from some Env data type at runtime (I haven't done deep performance checks, but hopefully the Haskell RTS should be helpful here);
• Nodes are specified through code so they can be a bit more exotic than usual (one of them can spawn a planning process and wait for a 'continuation' to be started, interrupting a default BT running while planning is being performed);
• No blackboard or inter-agent messages implemented yet (although maps and channels should be fairly straightforward to add).

Using Haskell has some issues (e.g., I still cannot bend the type system to express that a tree handling event type T1 can only contain subtrees that fire event type T1), but can provide some features with much expressive power (e.g. loops as infinite lazy lists).

Note that it is still fairly alpha or even pre-alpha! I am starting to integrate it with The Dark Mod (http://thedarkmod.com) where I hope to validate my assumptions. Feel free to send a mail if you end up interested.

Answer 4

I recently published smarties behavior tree library on hackage

https://hackage.haskell.org/package/smarties

I'm sure there other great ways for implementing BTs in haskell but I'm pretty happy with the design. Note smarties only supports 2 node states SUCCESS and FAIL.

In response to your questions:

what's the best pattern for feeding that tuple to a tree of behavior nodes that each return busy/error/completed/running based on the tuple. The behavior may also change the tuple (causing a state change).

smarties main type is a monad that represents a node sequence with an internal perception (state). In this sense it's pretty similar to the State monad. There are interfaces to enforce immutable perception as well.

Nested nodes can be executed based on the strategy of their parent node. For example, if a child node returns 'error', no more child nodes will be evaluated. Another strategy is to execute all child nodes even if an error state is returned.

It short circuits the status and final output anytime it hits a FAIL node. However, it still runs the remaining nodes to get its monadic return value which is super useful for composing logic in the BT.

Selectors (which represent branching logic) are thus implemented by passing in a list of node monads and taking the first one with SUCCESS state.

Monadic syntax turns out to be really powerful in behavior trees. You read state at some point in your tree and use its value much later on in the tree. This makes the nodes a lot easier to compose!