Semantics of sequence without memory are wrong

[siteks]

In 2.1.5 it's good to see sequence without memory, but the semantics seem to be wrong. From [1], I would expect the tree:

root = py_trees.composites.Sequence(memory=False)
root.add_child(py_trees.behaviours.TickCounter(1))
root.add_child(py_trees.behaviours.Success('Reached second child'))

to return RUNNING on the first tick, then SUCCESS on the second. But what actually happens is that the running leaf node is invalidated on the second tick and so always returns RUNNING. It seems to me it should behave analogously to selector without memory, in that a previously RUNNING child node should not be invalidated unless the sel/seq receives no tick.

Or, sequence and selector should be semantically identical if you flip SUCCESS and FAILURE:

inv(sel(inv(c1), inv(c2)) = seq(c1, c2)

The code below illustrates this, with the inverted selector without memory returning SUCCESS on the second tick:

import py_trees

py_trees.logging.level = py_trees.logging.level.DEBUG

root = py_trees.composites.Sequence(memory=False)
root.add_child(py_trees.behaviours.TickCounter(1))
root.add_child(py_trees.behaviours.Success('Reached second child'))

print('### Built in sequence without memory')
for i in range(2):
    root.tick_once()
    print(root.status)

class FakeSequence(py_trees.decorators.Inverter):
    def __init__(self, **kwargs):
        super(FakeSequence, self).__init__(child=py_trees.composites.Selector(**kwargs))
    def add_child(self, child):
        self.decorated.add_child(py_trees.decorators.Inverter(child))

root = FakeSequence(memory=False)
root.add_child(py_trees.behaviours.TickCounter(1))
root.add_child(py_trees.behaviours.Success('Reached second child'))

print('### Inverted selector without memory')
for i in range(2):
    root.tick_once()
    print(root.status)

Giving the result

### Built in sequence without memory
[DEBUG] Sequence             : Sequence.tick()
[DEBUG] TickCounter          : TickCounter.tick()
Status.RUNNING
[DEBUG] Sequence             : Sequence.tick()
[DEBUG] TickCounter          : TickCounter.stop(Status.RUNNING->Status.INVALID)
[DEBUG] TickCounter          : TickCounter.tick()
Status.RUNNING
### Inverted selector without memory
[DEBUG] FakeSequence         : FakeSequence.tick()
[DEBUG] Selector             : Selector.tick()
[DEBUG] Selector             : Selector.tick() [!RUNNING->reset current_child]
[DEBUG] Inverter             : Inverter.tick()
[DEBUG] TickCounter          : TickCounter.tick()
Status.RUNNING
[DEBUG] FakeSequence         : FakeSequence.tick()
[DEBUG] Selector             : Selector.tick()
[DEBUG] Inverter             : Inverter.tick()
[DEBUG] TickCounter          : TickCounter.tick()
[DEBUG] TickCounter          : TickCounter.stop(Status.RUNNING->Status.SUCCESS)
[DEBUG] Inverter             : Inverter.stop(Status.FAILURE)
[DEBUG] Inverter             : Inverter.tick()
[DEBUG] Reached second child : Success.tick()
[DEBUG] Reached second child : Success.update()
[DEBUG] Reached second child : Success.stop(Status.INVALID->Status.SUCCESS)
[DEBUG] Inverter             : Inverter.stop(Status.FAILURE)
[DEBUG] FakeSequence         : FakeSequence.stop(Status.SUCCESS)
Status.SUCCESS

[1] Alejandro Marzinotto, Michele Colledanchise, Colin Smith, and Petter Ogren. Towards a unified behavior trees framework for robot control. In Robotics and Automation (ICRA), 2014

[stonier]

Certainly looks like an inconsistency here, I'll delve into it when I've a little more time (soon).

Resources:

• Definitions - Unified BT Framework, Wikipedia
• BehaviorTree.CPP - ReactiveSequence, Fallback
• ... <other BT implementations>

And some initial thoughts:

• Definitions Those in the paper and wikipedia fall short on how to handle running children when initialisation and termination of resources handled by behaviours is an integral part of the framework. For instance, if the sequence pseudo-code was implemented exactly as stated, it has the potential for leaving dangling runners.
• Surprise - some people might find it equally surprising if the sequence doesn't reset everything as well
• Semantic observation - is it truly w/o memory if the running child remembers it's state?
• Pytrees - Selectors and Sequences without memory do indeed follow different rules (partial reset vs full reset)
• BehaviourTree.CPP - FallbackNode and ReactiveSequence seem to follow different rules as well (need to check)
• Ternary Policy - Maybe there is in actual fact three different policies that could apply (as opposed to two). Is three necessary and useful though?

[siteks]

I agree that the literature is incomplete in specifying the handling the semantics of executing a complete tree i.e the handling of orphaned running nodes. I look at this in my thesis Sections 3.1.4-3.1.5. In general, a running node (indeed, complete subtree) should be reset if if does not receive a tick in a given cycle.

Least surprise is a great principle - but a common idiom in robotics is a guarded memoryless sequence, where a condition is always checked before continuing a long running task. If the condition is true, the long-running task can continue (and is not reset). Only if the guard fails, and thus the long-running task does not receive a tick that cycle, would we regard that task as being terminated. I was surprised by the non-orthogonality with sel without memory! Actually, the eternal_guard looks superficially like memoryless seq, but I haven't looked at how it handles RUNNING so I'm not clear on the differences..

I would argue that a sequence without memory node does not imply that its children have no memory, just that it always starts with ticking its leftmost child and does not remember and start from a previous running child. The memory only lasts as long as it continues to receive ticks - like all nodes, if it receives no ticks in a cycle, the state (in this case the child index) is reset.

Re. behaviortree.cpp - both reactive_sequence and reactive_fallback ensure that when ticks do not reach children, those to the right of SUCCESS/RUNNING for sel, FAILURE/RUNNING for seq, those children are halted. The code for the two nodes is completely orthogonal.

I generally agree with your philosophy of minimising the number of primitives - e.g. I'm not sure if I agree with behaviourtree.cpp third variant of sequence (but not sel/fallback), SequenceStar, where failure is treated like running. I think it is perhaps nicer to have a py-trees style decorator FailureIsRunning on the child of a normal memory sequence.

[stonier]

I look at this in my thesis Sections 3.1.4-3.1.5

That's a great writeup on tree algorithms. Been too busy just making things work rather than analysing, so love this. Especially These are not difficult questions to answer, but the answers imply certain things.. Resonates with many of the choices here and discussions we've had with folks.

I've added a link to it in my docs (if you don't mind), #332, as I think they're a great and easy read. If you do for any reason, let me know and I'll revert it.

Actually, the eternal_guard looks superficially like memoryless seq

Yeah, almost, but not quite. It's continuous guarding of a sequence with memory. More like

[-] Sequence w/o Memory]
  --> Guard
  [-] Sequence w/ Memory
     --> Task 1
     --> Task 2

Interestingly enough, if I switch the sequence w/o memory to tentatively remember the running state, then I can deprecate that idiom. It's simple enough to create as listed above. #333.

Re. behaviortree.cpp - both reactive_sequence and reactive_fallback ... The code for the two nodes is completely orthogonal.

Aha, totally missed reactive_fallback.cpp there. Like I mentioned, did a fly-by and needed to delve further. Thanks for pointing that out :)

I think it is perhaps nicer to have a py-trees style decorator FailureIsRunning on the child of a normal memory sequence.

I've recently started favouring implementing blocking (can return R) and non-blocking (returns only F or S) variants of behaviours in behaviour libraries. Fairly easy to implement in a way that the code is re-used nicely, but most importantly, so much easier to read from a tree.

---

Anyway, +1 for a seq w/o memory behaviour that tentatively remembers a running child's state.

Rationale:

• Consistency with the Selector behaviour. Inconsistency leads to surprise and a loss of faith in the universe as a whole.
• I'm agnostic on whether a full reset style is needed (I don't have a use case). If someone does, I'll consider then whether introducing a third variation on these two composites is desired.

Thanks for the discussion @siteks!

[jbcpollak]

I just want to add a reference to the way Blueshell handles this as well:

• Sequence (no memory) ** Sends an event to each child until one of the returns FAILURE, or RUNNING, then returns that value. ** If all children return SUCCESS, return SUCCESS.

• LatchedSequence (memory) ** Sends an event to each child until one of the returns FAILURE, or RUNNING, then returns that value. ** If all children return SUCCESS, return SUCCESS. ** If a child returns RUNNING, subsequent events start at that child.

[jstyrud]

Another +1 for siteks suggestion.

I found this to be problematic when trying to put a memory node under a sequence w/o memory since the memory is cleared every tick for the node with memory. Doing the whole eternal guard subtree seems a lot more complicated.

[stonier]

Apologies, this was a long time in coming.

Thanks for all the feedback everyone.