Breaking change to ReactiveSequence in minor version v3.8.6 prevents backchaining pattern

[asasine]

In 51f92c4, ReactiveSequence was updated with a new semantic around how it halts running children. Previously, it would halt all children after the current one. With this change, it now halts all children before the current. This change prevents a common design and implementation approach in BTs called backchaining. I think the change should be reconsidered and possibly reverted.

In this approach, synchronous condition nodes are replaced with (possibly asynchronous) subtrees of conditions and actions. The basic approach is to select a condition and refactoring it into the postcondition (the previous condition), an action to make this postcondition succeed, and preconditions to the action. Each of these conditions may be further backchained, continually evolving the reactivity of your behaviors. This pattern also combines with other design patterns such as implicit sequences, which create reactivity through an intuitive prioritization of postconditions (earlier children are prioritized over later children). More on this by Petter Ögren: How to create Behavior Trees using Backward Chaining. Also known as PPA for postcondition-precondition-action.

Since each additional action may be synchronous, when an earlier children's postcondition begins to fail, and its action begins to run, later children's actions should intuitively be preempted, as another action is running. As you've mentioned elsewhere, it only makes sense for one child to be running at a given time (unless you're using Parallel). Without propagating the halt to later children, it leaves them in an ambiguous state: not preempted, but also not running (not being ticked).

The trees created by this are naturally reactive and intuitive. An excerp from that video:

(yellow is condition, green is action, -> is reactive sequence, ? is reactive fallback)

---

Other issues have come across this issue, and it's exception thrown in v4.x, when attempting to backchain.

In #573, the OP has a postcondition for quality sensor measurements, with an action to restart the sensor, and a precondition that the action has been attempted 5 or less times. Following the postcondition (quality measurements), some action is performed.

In #83, miccol demonstrated several examples of backchained BTs that have a reactive sequence of multiple asynchronous children. If the battery is not ok (postcondition), goto charging station (action).

In #736, the OP explicitly mentions the principle of backchaining and shows a tree following this approach. Your recommended pattern moves uses a memory Sequence, which was not sufficient for OP. They also recommend the old behavior of preempting/halting all currently-running children.

I think what's missing in all of the responses is that these users are not attempting to run multiple nodes concurrently; the halting mechanism in BehaviorTree.CPP ensures this is the case. They are simply trying to construct reactive behaviors following established design patterns.

---

Parallel is not a viable alternative to ReactiveSequence for this pattern. Parallel ticks all children, ticking the next if one returns RUNNING. This would lead to multiple actions running concurrently, such as attempting to put a jacket on while searching the garden for a key and eating a banana.

[facontidavide]

I am planning to change this in 4.6

It would be great if you or anyone else help me defining a "backchain" unit test that has the behavior that people wants/expect.

Do we all agree, that NONE of the green boxes should run concurrently?

Also, the image is nice, but WHICH sequence here should be reactive and which ones shouldn't?
I think that this is the problem wit papers and publications that just cherry-pick examples but don't use this "in production": the lack of details

[facontidavide]

I believe that this code is correct, I just need to remove the exception.

https://github.com/BehaviorTree/BehaviorTree.CPP/blob/master/src/controls/reactive_sequence.cpp#L47-L53

I need to stop the following ones (if you "Wear jacket", you interrupt "eating the banana"), but also the one of the left, that should all be prevalently stopped already or be Conditions that need reset.

[asasine]

It would be great if you or anyone else help me defining a "backchain" unit test that has the behavior that people wants/expect.

I'll work one up next week and post it here/provide a PR.

Do we all agree, that NONE of the green boxes should run concurrently?

I do agree with this. IMO concurrency is something you opt into explicitly with the use of Parallel or other control nodes. With the backchaining model, only one leaf node is ever running at a time.

Also, the image is nice, but WHICH sequence here should be reactive and which ones shouldn't?
I think that this is the problem wit papers and publications that just cherry-pick examples but don't use this "in production": the lack of details

I tend to agree. I've found over time that paper/publications almost exclusively use reactive control nodes. Memory control nodes are only a thing that I come across regularly in BT software libraries. They're useful for certain side effects; we often use them for logging in our PPA actions to only log once per individual run of the action.

I believe that this code is correct, I just need to remove the exception.

https://github.com/BehaviorTree/BehaviorTree.CPP/blob/master/src/controls/reactive_sequence.cpp#L47-L53

I need to stop the following ones (if you "Wear jacket", you interrupt "eating the banana"), but also the one of the left, that should all be prevalently stopped already or be Conditions that need reset.

Agreed; the exception is problematic but the halting code looks good. You're spot on that the left nodes are probably already stopped. Despite calling halt on them, most/all wouldn't be reset (in BehaviorTree.CPP) because halts aren't propagated to nodes in a non-running state.

[asasine]

@facontidavide I believe this is a suitable example of a tree that starts simple and is backchained once to make a more complex and capable version. Included the test below and in this gist https://gist.github.com/asasine/bc20da23d1954d2f712f215bfacdc659

#include <gtest/gtest.h>
#include <gmock/gmock.h>
#include "behaviortree_cpp/leaf_node.h"
#include "behaviortree_cpp/bt_factory.h"

namespace BT::test
{
using ::testing::Assign;
using ::testing::DoAll;
using ::testing::Return;

/// @brief Mocked @c BT::LeafNode that allows callers to trivially customize behavior of @c tick() and @c halt().
/// @tparam NodeTypeT The type of leaf node this class is.
template <NodeType NodeTypeT>
class MockLeafNode : public LeafNode
{
public:
  MockLeafNode(const std::string& name)
    : LeafNode(name, {})
  {
  }

  // Made public for setting actions and expectations
  MOCK_METHOD(NodeStatus, tick, (), (override));
  MOCK_METHOD(void, halt, (), (override));

  NodeType type() const override
  {
      return NodeTypeT;
  }
};

TEST(PPA, EnsureWarm)
{
  // This test shows the basic structure of a PPA: a fallback of a postcondition and an action to make that
  //  postcondition true.
  /*
    <BehaviorTree ID="EnsureWarm">
      <ReactiveFallback>
        <IsWarm />
        <ReactiveSequence>
          <IsHoldingJacket />
          <WearJacket />
        </ReactiveSequence>
      </ReactiveFallback>
    </BehaviorTree>
  */

  // The final condition of the PPA; the thing that make_warm achieves. For this example, we're only warm after
  //  WearJacket returns success.
  MockLeafNode<NodeType::CONDITION> is_warm("IsWarm");
  NodeStatus is_warm_return = NodeStatus::FAILURE;
  EXPECT_CALL(is_warm, tick())
    .WillRepeatedly([&is_warm_return]() { return is_warm_return; });

  // For this example, we already have a jacket
  MockLeafNode<NodeType::CONDITION> is_holding_jacket("IsHoldingJacket");
  EXPECT_CALL(is_holding_jacket, tick())
    .Times(2)
    .WillRepeatedly(Return(NodeStatus::SUCCESS));

  // Putting the jacket on takes two ticks, and updates the return value of IsWarm
  MockLeafNode<NodeType::ACTION> wear_jacket("WearJacket");
  EXPECT_CALL(wear_jacket, tick())
    .WillOnce(Return(NodeStatus::RUNNING))
    .WillOnce(DoAll(Assign(&is_warm_return, NodeStatus::SUCCESS), Return(NodeStatus::SUCCESS)));

  ReactiveSequence make_warm("MakeWarm");
  make_warm.addChild(&is_holding_jacket);
  make_warm.addChild(&wear_jacket);

  ReactiveFallback ensure_warm("EnsureWarm");
  ensure_warm.addChild(&is_warm);
  ensure_warm.addChild(&make_warm);


  // first tick: not warm, have a jacket: start wearing it
  EXPECT_EQ(ensure_warm.executeTick(), NodeStatus::RUNNING);

  // second tick: warm (wearing succeeded)
  EXPECT_EQ(ensure_warm.executeTick(), NodeStatus::SUCCESS);

  // third tick: still warm (just the postcondition ticked)
  EXPECT_EQ(ensure_warm.executeTick(), NodeStatus::SUCCESS);
}

TEST(PPA, EnsureWarmWithEnsureHoldingHacket)
{
  // This test backchains on HoldingHacket => EnsureHoldingHacket to iteratively add reactivity and functionality to the tree.
  // The general structure of the PPA remains the same.
  /*
    <BehaviorTree ID="EnsureWarm">
      <ReactiveFallback>
        <IsWarm />
        <ReactiveSequence>
          <SubTree ID="EnsureHoldingJacket" />
          <WearJacket />
        </ReactiveSequence>
      </ReactiveFallback>
    </BehaviorTree>

    <BehaviorTree ID="EnsureHoldingJacket">
      <ReactiveFallback>
        <IsHoldingJacket />
        <ReactiveSequence>
          <IsNearCloset />
          <GrabJacket />
        </ReactiveSequence>
      </ReactiveFallback>
    </BehaviorTree>
  */

  // Same postcondition as first test.
  MockLeafNode<NodeType::CONDITION> is_warm("IsWarm");
  NodeStatus is_warm_return = NodeStatus::FAILURE;  // initially: not warm
  EXPECT_CALL(is_warm, tick())
    .WillRepeatedly([&is_warm_return]() { return is_warm_return; });
  
  // The new PPA's postcondition is the same condition that we're backchaining on.
  MockLeafNode<NodeType::CONDITION> is_holding_jacket("IsHoldingJacket");
  NodeStatus is_holding_jacket_return = NodeStatus::FAILURE;  // initially: not holding a jacket
  EXPECT_CALL(is_holding_jacket, tick())
    .WillRepeatedly([&is_holding_jacket_return]() { return is_holding_jacket_return; });

  // For this test, we're already near a closet. This condition could be backchained!
  MockLeafNode<NodeType::CONDITION> is_near_closet("IsNearCloset");
  EXPECT_CALL(is_near_closet, tick())
    .Times(2)
    .WillRepeatedly(Return(NodeStatus::SUCCESS));

  // Same as first test's action: running once, then success, updating this PPA's postcondition.
  MockLeafNode<NodeType::ACTION> grab_jacket("GrabJacket");
  EXPECT_CALL(grab_jacket, tick())
    .WillOnce(Return(NodeStatus::RUNNING))
    .WillRepeatedly(DoAll(Assign(&is_holding_jacket_return, NodeStatus::SUCCESS), Return(NodeStatus::SUCCESS)));

  // Same as first test.
  MockLeafNode<NodeType::ACTION> wear_jacket("WearJacket");
  EXPECT_CALL(wear_jacket, tick())
    .WillOnce(Return(NodeStatus::RUNNING))
    .WillOnce(DoAll(Assign(&is_warm_return, NodeStatus::SUCCESS), Return(NodeStatus::SUCCESS)));

  // The new PPA's precondition-action (PA) is the same form as the root PPA's PA. Similar to MakeWarm, this PA ticks
  //  running twice and updates the postcondition afterwards.
  ReactiveSequence grab_jacket_from_closet("GrabJacketFromCloset");
  grab_jacket_from_closet.addChild(&is_near_closet);
  grab_jacket_from_closet.addChild(&grab_jacket);

  // For this example, our precondition is another PPA: it short circuits if we already have a jacket, otherwise it
  //  fetches one asynchronously.
  ReactiveFallback ensure_holding_jacket("EnsureHoldingJacket");
  ensure_holding_jacket.addChild(&is_holding_jacket);
  ensure_holding_jacket.addChild(&grab_jacket_from_closet);

  ReactiveSequence make_warm("MakeWarm");
  make_warm.addChild(&ensure_holding_jacket);  // Use the new PPA within PA, not the original precondition.
  make_warm.addChild(&wear_jacket);

  ReactiveFallback ensure_warm("EnsureWarm");
  ensure_warm.addChild(&is_warm);
  ensure_warm.addChild(&make_warm);

  // BUG(755): need to disable exception throwing on reactive control nodes to support backchaining.
  ReactiveSequence::EnableException(false);
  ReactiveFallback::EnableException(false);

  // first tick: not warm, no jacket, near a closet: start grabbing a jacket
  EXPECT_EQ(ensure_warm.executeTick(), NodeStatus::RUNNING);

  // first tick: not warm, has a jacket (grabbing succeeded), not wearing: start wearing
  EXPECT_EQ(ensure_warm.executeTick(), NodeStatus::RUNNING);

  // third tick: warm (wearing succeeded)
  EXPECT_EQ(ensure_warm.executeTick(), NodeStatus::SUCCESS);

  // fourth tick: still warm (just the postcondition ticked)
  EXPECT_EQ(ensure_warm.executeTick(), NodeStatus::SUCCESS);
}
}

Any of the conditions in the tree could be further backchained. One more level could look like:

<BehaviorTree ID="EnsureWarm">
  <ReactiveFallback>
    <IsWarm />
    <ReactiveSequence>
      <SubTree ID="EnsureHoldingJacket" />
      <WearJacket />
    </ReactiveSequence>
  </ReactiveFallback>
</BehaviorTree>

<BehaviorTree ID="EnsureHoldingJacket">
  <ReactiveFallback>
    <IsHoldingJacket />
    <ReactiveSequence>
      <SubTree ID="EnsureNearCloset" />
      <GrabJacket />
    </ReactiveSequence>
  </ReactiveFallback>
</BehaviorTree>

<BehaviorTree ID="EnsureNearCloset">
  <ReactiveFallback>
    <IsNearCloset />
    <ReactiveSequence>
      <IsPathToClosetAvailable />
      <WalkToCloset />
    </ReactiveSequence>
  </ReactiveFallback>
</BehaviorTree>

Branching is trivially supportable if an action (or its precondition) fails. Additional explicit conditions are backchainable themselves with the same pattern. Each PPA can be tested in isolation by modifying the environment such that the preconditions hold, and then included in a larger tree with confidence that the PPA adds reactivity without unnecessary complexity: to the caller, it's all just EnsureWarm.

<BehaviorTree ID="EnsureWarm">
  <ReactiveFallback>
    <IsWarm />
    <ReactiveSequence>
      <SubTree ID="EnsureHoldingJacket" />
      <WearJacket />
    </ReactiveSequence>

    <ReactiveSequence>
      <!-- This could be backchained to give the agent the ability to find and use the thermostat. -->
      <IsInside />
      <AdjustThermostat />
    </ReactiveSequence>

    <ReactiveSequence>
      <!-- This could be backchained to give the agent the ability to acquire wood. -->
      <IsWoodNearby />
      <MakeFire />
    </ReactiveSequence>
  </ReactiveFallback>
</BehaviorTree>

<BehaviorTree ID="EnsureHoldingJacket">
  <!-- Trimming this example: we can't acquire a jacket for whatever reason. -->
  <AlwaysFailure />
</BehaviorTree>

[facontidavide]

I will finally have time to work on this the next week. Hopefully we get the changes merged by the end of the next week

[facontidavide]

I created the branch reactive_change_issue_755

I preferred to change the suggested code a little, but you saved me a lot of time. Please have a look

[asasine]

I don't see this branch in the main repo.

[facontidavide]

See open PR #770

[facontidavide]

I feel that I wil regret this...