[Dprglist] Subsumption expressed as a behavior tree

[Paul Bouchier]

David, Rud,

At Tuesday's RBNV you guys seemed to have agreed that the Subsumption
architecture was a special case of behavior trees. I wanted to understand
behavior trees, and to understand whether your assertion is correct. I
found a basic explanation of behavior trees here:
https://towardsdatascience.com/designing-ai-agents-behaviors-with-behavior-trees-b28aa1c3cf8a

It's a good overview, but is missing sufficient detail to design a
subsumption stack as a behavior tree. For example it's description of a
sequence node is "A node that returns success if all children return
SUCCESS" but it doesn't specify what happens if a child returns RUNNING -
does it retry all previous nodes next tick time? It only describes one kind
of decorator node (invert). It doesn't specify whether a Fallback node
re-ticks all nodes next tick-time if a child after the first returns
SUCCESS.

After some searching, I found this set of pages
https://www.behaviortree.dev/
They describe an implementation by David Faconte (of PlotJuggler fame) of a
behavior tree library that is general purpose, and doesn't depend on, but
works well with ROS. In the "Learn the basics" section they describe
variations on the sequence and fallback nodes which seem sufficient to
design a subsumption robot behavior. The attached image is that design. I'd
be interested in your thoughts on whether I'm on the right track here.

The following description of the design assumes the reader has read the
Sequence Nodes and Fallback Nodes and Decorators Nodes pages, and it offers
commentary on how the behavior tree implements the subsumption stack,
including non-ballistic behavior.

ReactiveFallback always ticks all nodes below it until it gets the first
SUCCESS. Thus, if Action ReverseTurn was running owing to a bumper press,
and then BatteryLow becomes active (SUCCESS), the ReactiveFallback node
calls HaltAllChildren() which propagates down the tree and halts (subsumes)
the ReverseTurn action. (This implementation produces an abort behavior,
but it's included to show that BumperPressed->ReverseTurn is subsumable,
not ballistic.)

The subsumption behavior arises from the way ReactiveFallback stops ticking
lower-priority (more rightward) nodes when any preceding nodes return
SUCCESS. If no bumper is pressed, no IR detection is made, and battery
isn't low, then the last action, "Drive toward goal" gets to run. But as
soon as bumper or IRDetection is true (SUCCESS), the corresponding behavior
is executed, and DriveTowardGoal is subsumed (doesn't run) until the
corresponding Sequence node is done and returns FAILURE

If IRDetection returns SUCCESS (IR sensor detects object), Action
"SteerAway" runs, and steers the robot away from the sensor with the
detection. Once the sensor clears, IRDetection condition returns FAILURE,
Action SteerAway doesn't run (is halted), and no longer subsumes
DriveTowardGoal, which can then start running again. This behavior relies
on ReactiveSequence ticking all nodes (starting at the beginning of its
list of children), so the sensor gets checked each tick.

By contrast, BumperPressed is called by a regular Sequence, which doesn't
tick all its children; if a child returns RUNNING (which will happen while
ReverseTurn action is active), it will only tick the running child. Thus
BumperPressed can become false as the robot backs away from the obstacle,
but it won't be ticked, so it won't affect the "ReverseTurn" action that
should run for some time after a bumper contact clears. The RepeatNode
decorator runs ReverseTurn up to 40 times (2 seconds at 20 Hz tick rate) as
long as ReverseTurn returns SUCCESS, then returns FAILURE (maybe - the
documentation isn't clear on this point - it might not work as described).
When it returns FAILURE the subsumption of lower priority actions ends.

The tree shown is a DriveToWaypoint behavior tree - it could be used as an
element in a higher-level sequence that did something else after achieving
the waypoint, like seek a cone.

This is of course all theoretical - may not work in practice - but it looks
to me as if your assertion that Subsumption can be represented as a
behavior tree is correct, and that a richer set of control-node behaviors
is beneficial. The Fallback node acts like David's arbiter, running the
highest priority behavior, as assessed by traversing the list of nodes and
not running any beyond the first to report SUCCESS. It relies on its
children to return FAILURE if they don't want to control the robot, so that
arbitration can pass on down the line.

A very nice aspect of this library is it works with GROOT which apparently
allows realtime and after-the-fact replay of state transitions (active
behaviors).

Thanks for an interesting exploration down an avenue I've wondered about. I
feel more knowledgeable now than I was.

Regards

Paul
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211104/37c9a0cd/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: SubsumptionAsBehaviorTree.drawio.png
Type: image/png
Size: 30082 bytes
Desc: not available
URL: <http://lists.dprg.org/pipermail/dprglist-dprg.org/attachments/20211104/37c9a0cd/attachment.png>