Implementation of a parallel node

[slapers]

Hi,

I was wondering if with the current API it is possible to implement a parallel node.
I guess with a parallel you will end up with multiple active leaf nodes, end thus to signal fail/success the tree would need to accept some kind of identifier to mark the specific node that finished underneath the parallel.

  Node.parallel([:a, :b, :c])
  |> BehaviorTree.start()
  |> BehaviorTree.succeed(:b)

Currently the tree only accepts BehaviorTree.succeed/1 or BehaviorTree.fail/1.

Is there another way to achieve the parallel node with the current API ?

[jschomay]

Hi! Thank you for your interesting in this library. You are quite correct to wonder about parallel nodes. In fact, at ElixirConf I mentioned that parallel nodes (and priority selector nodes) were a trade-off in my design decision to base the implementation on a zipper tree.

The issue is that the behavior tree is a zipper tree, and zipper trees by definition only have one focus (or "active" node) at any given time. This excludes the possibility to have multiple active nodes as you mention above.

There are some possible approaches though, to get this kind of behavior. I haven't given it a lot of thought, but the basic idea is to rely on Elixir/Erlang's own concurrency constructs inside of a single leaf node.

For example, if you had Node.sequence([:do_first, {:parallel, [:a, :b, :c]}, :do_after_a_b_and_c]) (keep in mind that leaf nodes can be anything you want), then you could start the tree and get the active node and pattern match to "handle" it with a function that can run :a, :b, and :c in parallel (with Tasks for example). That same function would wait for the tasks to finish, and then fail or succeed the tree accordingly.

Does that make sense? Would that be a sufficient solution? The main issue is that since this is in a leaf node, you couldn't compose subtrees in parallel, however, you could probably wrap up the "handler" I just described into a new Node type (with Node.Protocol) to get that behavior "built in", and allow for parallel composed subtrees, though I'm not sure quite how that would look.

Let me know what you think of that solution. Also, I am curious what your use case is, and what you would expect a parallel node to do. I can imagine 3 types of useful parallel nodes: succeed_on_first_success, fail_on_first_failure, and succeed_if_all_succeed. The first 2 would involve race conditions that would have to be handled somehow, the last one could be achieved with a simple actions |> pmap run_action |> Enum.all(& &1 == :succeed).

If you come up with any other solutions, or experiment along the lines that I suggested, please keep me informed. I would be happy to merge a PR that could add a BehaviorTree.Nodes.Parallel module.

[slapers]

Hi,

Thanks for the quick and detailed response !

Really love the zipper tree :-) its such a neat way to traverse the tree.
I had been thinking indeed of modelling separate trees inside child processes, it seems like a natural thing in elixir. But i think for my purpose it would make things a bit more difficult.

I was actually interested in checking if it is possible to use behaviour trees to automate business processes. Unsure if it fits, but since people seem to sell bpm solutions using actor models and state machines (s-bpm), i think behaviour trees might actually work out fine... Im really impressed on their simplicity when visualised.

To be specific on the parallel node, i wanted to model 2 human tasks that need to be performed (filling in and submitting 2 independent forms). Each form that is submitted would succeed the respective node, and i would probably need a succeed_if_all_succeed policy in this specific case.

My dilemma is i'm not actually running parallel computations, but represent parallel or independent things for which the results will come in at some point in time. Having this in a process would be possible, but does not feel like the best solution for my use/test case :-)

I will probably experiment/think a bit, if i come up with something useful i will definitely send you an update ... Or if you have some insights on my use case i am definitely interested !

[jschomay]

Very interesting. I have actually spoken to one or two other people who want to use behavior trees for something very similar, so I think it can be a good fit.

I'm not sure what an elegant solution for your parallel issue would be, but I'm thinking that when the tree gets to a parallel task, you would just let the tree sit in memory, and start a new piece of state in an Agent, tracking each "form" that needs to be processed (I'm thinking of a map with the form names as keys and :open | :completed as the values). When forms get completed, something would trigger that part of your app to mark the given form as completed, and you do a check to see if all forms have been completed. If so, you succeed the behavior tree, and continue as normal.

Perhaps that can be built into a special parallel node, to avoid splintering the architecture, but I'm not sure what the api would look like, since the idea of "keying" the succeed call would only apply in a "parallel" state. Perhaps BT.value on a "parallel" node would return something like {:parallel, [:a, :b, :c], parallel_tracking_pid} and each time a form gets completed you call Node.parallel.task_finished(parallel_tracking_pid, :a) which returns a map of the keys/values described above, and you can decide in the calling code if you want to succeed or fail the tree at that time. Not sure if that would work well, I'm just trying to work out if any of it can be added to the library.

Also note that when you do get into a parallel state, you could start up new sub trees for each "form" if they required multiple steps, and then only consider a form "completed" when reaching the last step in the sub tree. I do wish it could be more integrated though.

Let me know how you get along with it, I'm sure this will be useful for others as well.