Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Should nodes loop internally or not? #71

Closed
maxpfingsthorn opened this issue Mar 12, 2019 · 13 comments
Closed

Should nodes loop internally or not? #71

maxpfingsthorn opened this issue Mar 12, 2019 · 13 comments
Labels
brainstorming Discussion about change of the library

Comments

@maxpfingsthorn
Copy link

I noticed that all nodes with multiple children (sequence, fallback, reactive*, retry, repeat, etc.) loop over children internally with while's and for's in their implementation of tick(). I wonder if this is a design decision, and if yes, why is this the case? Due to perceived efficiency?

I would argue that for each executeTick() on the root node, only one leaf should have their tick() method called. This would imply descending into the tree from the root every executeTick(), but I believe this cost would be negligible. However, tick()-ing only one leaf per executeTick() iteration would be more in line with the conceptual behavior tree model and it would help scheduling/preempting a lot.

What do you think?

@facontidavide
Copy link
Collaborator

facontidavide commented Mar 12, 2019

Hi @maxpfingsthorn

this is a very good question, and I am struggling to find the right answer myself, because all of of my users have a different opinion.

I agree with you that semantic correctness MUST be preferable over perceived efficiency; people usually believe that tree traversal is computationally expensive, even when it is not.

I agree with you the "internal loop" precludes the ability of a reactive tree to preempt a branch.

Unfortunately, this is a quite important change that might break someone else code in some subtle way...

Summarizing, I do see your point and I actually share it, but such a change needs a debate among users of these library; in such a debate, efficiency MUST not be considered, in my opinion, only correctness and predictability.

@maxpfingsthorn
Copy link
Author

Hi @facontidavide,

Ok, I see your point on this being a potentially breaking change. I would be happy to discuss.

What is a good forum to do this?

@facontidavide
Copy link
Collaborator

No forum, unfortunately.
Take a loop to this branch: https://github.com/BehaviorTree/BehaviorTree.CPP/tree/preemptable_loop

Is this what you had in mind?

I realized that the Reactive ControlNodes cannot be modified. Take a look at the commit for more details: 2dc84b1

@maxpfingsthorn
Copy link
Author

That looks very good to me! Thank you.

For the reactive controls: Why not? The implementation would be the same as for the ones with memory, but would reset the index on RUNNING as well. Or did I miss something?

@facontidavide
Copy link
Collaborator

@v-lopez @mjeronimo @miccol @Masadow @Thordreck

Would you like to join this discussion?

@miccol
Copy link
Member

miccol commented Mar 20, 2019

I am also still struggling to find the right answer.
I guess here we are talking about asynchronous action nodes. I think in some practical cases we need to have actions that loop internally (e.g. a navigation action what waits in a loop until the goal is reached).
The workaround was to check, at each loop, if the action is halted or not.

@facontidavide
Copy link
Collaborator

I guess here we are talking about asynchronous action nodes.

Quite the opposite, I am worry about synchronous nodes.

Consider for instance this tree

<ReactiveSequence>
    <CheckBattery>
    <Repeat num_cycles="10">
          <DoSomething>
    </Repeat>
</ReactiveSequence>

Let's suppose that DoSomething is synchronous and requires 1 second to be completed. The condition CheckBattery becomes false after 5 seconds.

The entire sequence will always take 10 seconds; this goes against the "Minimum WTF principle".
image

Unfortunately, since Repeat loops internally, CheckBatteryis invoked only once, not 10 times.

Allow me to use the word "atomic" as synonym of "synchronous" to make my point.

If Sequence, Fallback, Repeat or RetryUntilSuccesfull contains only atomic children, that ControlNode / DecoratorNode itself becomes atomic, i.e impossible to halt.

This is probably not what we want: in the previous example, a user would expect CheckBattery to be called many times.

The problem with the new semantic proposed by @maxpfingsthorn is that all those Conditions inside Reactive ControlNodes might be called MUCH more often, but this is the point of reactive trees, isn't it?

@v-lopez
Copy link
Contributor

v-lopez commented Mar 20, 2019

I agree that the example you provided should call check battery several times.

In my mind, the only "blocking" nodes should be the the sync action nodes. Any intermediate decorator that needs to loop should return RUNNING.

@hlzl
Copy link
Contributor

hlzl commented Mar 20, 2019

What confused me the most in the beginning was that we constantly call executeTick() from the root node when we use asynchronous nodes. I thought that because of these internal loops we could call executeTick() only once in the beginning and let it propagate through all nodes of the tree with Sequences ticking asynchronous children internally while they run.
As this is not the case, I would agree with @maxpfingsthorn and prefer to tick only one leaf per executeTick(). However, as @miccol said, this would require to make an exception for ReactiveSequences with asynchronous nodes.

Regarding your example, I don't see why you should use a ReactiveSequence if you're not using an asynchronous node. I would expect an implementation like this to achieve your desired behavior

<Repeat num_cycles="10">
    <Sequence>
        <CheckBattery>
        <DoSomething>
    </Sequence>
</Repeat>

One thing I think should also be mentioned here are the semantics of two asynchronous nodes inside a ReactiveSequence. This will currently result in an infinite loop. However, I think it would be an interesting tool to have, let's call it a ParallelAsynchronousNode, which allows to execute two or more ansynchronous nodes (only once) at the same time. However, I couldn't find any theory on this kind of behavior and its semantics would have to be discussed.

@facontidavide
Copy link
Collaborator

hi @hlzl , thanks for joining the discussion.

About the need to executeTick() repeatedly, that is "by design", otherwise a tree is not preemptable. But I need to make it less confusing in the documentation.

The alternative tree you suggested would work. what worries me is how intuitive a solution is compared to another for a newbie.

The problem with reactive nodes as you pointed out, is indeed that a ReactiveSequence or ReactiveFallback must not have more than an asynchronous child.
This is also a potential source of bugs for many people.

In the past, I used NodeStatus::IDLE to avoid ticking twice already ticked Actions, but @v-lopez complained about that too.

I am now thinking which is the least of two evils....

@mjeronimo
Copy link

As a relative newcomer to BehaviorTrees, the semantic difference between

<ReactiveSequence>
    <CheckBattery>
    <Repeat num_cycles="10">
          <DoSomething>
    </Repeat>
</ReactiveSequence>

and

<Repeat num_cycles="10">
    <Sequence>
        <CheckBattery>
        <DoSomething>
    </Sequence>
</Repeat>

is clear to me.

However, I find "ReactiveSequence or ReactiveFallback must not have more than one asynchronous child" confusing. I think of an action node simply returning its current state (RUNNING, etc.) and don't see why a parent node needs to know the internals details of an action node, such as whether it asynchronously communicating with another thread or process.

@miccol
Copy link
Member

miccol commented Mar 21, 2019

In my mind, the only "blocking" nodes should be the the sync action nodes. Any intermediate decorator that needs to loop should return RUNNING.

I agree.

The problem with reactive nodes as you pointed out, is indeed that a ReactiveSequence or ReactiveFallback must not have more than an asynchronous child.
This is also a potential source of bugs for many people

I have a solution to this in mind. I will discuss it in another thread.

In the past, I used NodeStatus::IDLE to avoid ticking twice already ticked Actions, but @v-lopez complained about that too.

Is the discussion about somewhere? I used to like the IDLE status

@facontidavide facontidavide added the brainstorming Discussion about change of the library label Jul 30, 2019
@facontidavide
Copy link
Collaborator

changed in version 4.
I decided to allow some Control/Decorators to return RUNNING between one child and the next

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
brainstorming Discussion about change of the library
Projects
None yet
Development

No branches or pull requests

6 participants