Skip to content

Should nodes loop internally or not? #71

Closed

Description

@maxpfingsthorn

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?

Activity

  1. facontidavide commented on Mar 12, 2019

    @facontidavide
    Collaborator

    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.

  2. maxpfingsthorn commented on Mar 12, 2019

    @maxpfingsthorn
    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?

  3. facontidavide commented on Mar 13, 2019

    @facontidavide
    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

  4. maxpfingsthorn commented on Mar 14, 2019

    @maxpfingsthorn
    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?

  5. facontidavide commented on Mar 20, 2019

    @facontidavide
    Collaborator

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

    Would you like to join this discussion?

  6. miccol commented on Mar 20, 2019

    @miccol
    Contributor

    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.

  7. facontidavide commented on Mar 20, 2019

    @facontidavide
    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?

  8. v-lopez commented on Mar 20, 2019

    @v-lopez

    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.

  9. hlzl commented on Mar 20, 2019

    @hlzl
    Contributor

    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.

  10. facontidavide commented on Mar 20, 2019

    @facontidavide
    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....

  11. mjeronimo commented on Mar 20, 2019

    @mjeronimo

    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.

  12. miccol commented on Mar 21, 2019

    @miccol
    Contributor

    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

  13. facontidavide commented on Nov 22, 2022

    @facontidavide
    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

Metadata

Metadata

Assignees

No one assigned

    Labels

    brainstormingDiscussion about change of the library

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions