How should I share the states amongst all the executions of a Behaviour Tree triggered from all ticks?

Question

I'm still learning about Behaviour Tress and my understanding of the "blackboard" is essentially a state object. When passing the state object through the ticks to the function calls (which are nodes and leaves), how should I share the states amongst all the executions of the trees triggered from all previous ticks?

I initially thought the states should be immutable so that the functions can be "pure". However, if the states are immutable, that would mean that whatever consequences triggered from a previous tick will have to be performed in its entirety even if a later tick that came in the middle of the execution has a different state value.

For example, if the behaviour tree was something like this:

When Tick_1 first came in, the state was something like this:

{ 
  user: { cash: 10 }
}

So, at Tick_1, user has $10 and has enough cash to buy milk. The behaviour tree will go down the path of walking to the store and then buying milk.

However, the action of "Walking to Store" is asynchronous and takes some time before the "Buy Milk" action can take place. Now, when the "Walking to Store" action from Tick_1 is still taking place, another tick Tick_2 came in at this time with a state that the user now has $0 in his pocket:

{ 
  user: { cash: 0 }
}

Based on the latest state from Tick_2 the user has no more money probably due to something that happened during Tick_2. But because the previous execution of the tree from Tick_1 is still in progress and has no knowledge about the new state since its copy of the state is the old one and they don't shared a common mutable state, it will eventually go on and perform the "Buy Milk" action when it really shouldn't because by this time, the user has no more cash!

It seems to me that if the states passed to the ticks are immutable separate copy of states, the previous decision made has to be completed and we can't "cancel" the previous decision or execution.

If we use a shared state, however, this would mean the state is mutable and any of the functions or actions can change them through any side effects. It might turn out to be very messy and difficult to maintain with too many places changing a common state.

My question is:

• How should the blackboard or states of a behaviour tree be constructed? Should the states be mutable or immutable?
• Should every ticks share a common copy of states so that executions of the tree from the previous ticks are aware of the latest values in the states so that they either stop proceeding or react differently?
  • If so, how should this be done elegantly?

I'm using Typescript in my case but I'm assuming(?) the concept should be similar in any other context and languages.

PS: I guess I could swap the positions of the condition and "walk to store" to reduce the problem in my example but I'm trying to use this to illustrate the dilemma I'm having.

Answer 1

Blackboards need to be mutable and thread safe, if you support parallel nodes. You are correct that in your example, it could be a problem that one asynchronous node changes the value of cash while a second traversal believes it has enough cash to perform certain actions.

You could either pass a reference or pointer to the blackboard down to each node for each tick or during creation of the nodes, give them a reference/pointer to the blackboard. Either approach is valid, but regardless, nodes should not have copies of the blackboard or the values within them. This would be wasteful and trying to keep the copies of the blackboard coherent would add significant overhead.

There is also something else to consider. You mentioned

But because the previous execution of the tree from Tick_1 is still in progress ... it will eventually go on and perform the "Buy Milk" action when it really shouldn't because by this time, the user has no more cash!

That is not entirely correct. After Tick_1 ticks the asynchronous node, it will immediately return a "Running" state, which the sequence passes up the root. So Tick_1 is finished before Tick_2 comes along, however the "walking to the store" node is still active on some other thread.

In your example, I do not think that this would be an issue. The sequence will not continue to the "buy milk" node until all previous nodes are successful (ie. not failed and not running).

If you have a more complex tree where a node from an entirely different branch is running asynchronously and may also modify cash then the precondition must be checked atomically before the action node can be executed. i.e. the "buy milk" node is replaced with a subtree that tests if the agent has enough cash and then goes to buy milk.