Forester. How to change the runtime tree on the fly. Part III. Trimming.

9 min readAug 10, 2023

Intro

Today, industrial robots can attack high-complex tasks in controlled environments, which can be nothing but inspiring.

But there is a small rub. Modern industrial applications in workspaces require robots to be able to act and orient in unpredictable surroundings as well.
One common way to deal with this is to control the robot with a reactive policy such as Behavior Trees (BTs).

Forester is an orchestration framework that operates above the behavior trees and enables to construction of the process of orchestration from scratch. It provides a clean and straightforward way to run the tasks that implement the conception of the behavior trees out of the box.

On the other hand, the framework is supposed to be a practical tool, that aids in integrating the new features in the whole field of BTs. This article describes a framework feature to change the runtime tree during execution.

Premises

First of all, the feature now is a low-level function that can be a foundation for further API. It can be used as is, but it is cumbersome.

The ability to change the runtime tree on the fly appears very promising from the different aspects:

Performance optimizations.

Analysing the trace of the execution of the current tree we can try to perform changes and see how the performance will change. In other words, this can be a ground for the just-in-time compilation methods.

Logical optimizations

The changes during execution, the flowing environment and so on can be a reason when we need to manually update the execution tree.

AI optimizations

Analyzing the tracing information, we can try to apply some methods of Machine Learning, for example, Reinforcement learning.

Experimenting variability

We can apply changes and then unapply them, rolling back to the previous state and measuring the different aspects of the execution. It can be useful, to find some meta patterns of the flow.

Preparing some changes in the environment between ticks.

It can be useful, to alter some data in Blackboard or perform some changes during the execution.

How it works.

A short introduction to Trimming (how it is defined in the framework) is given in the book.

The Forester provides a so-called Trimmer, which represents a queue of tasks. Between ticks, the engine extracts a task, validates it, and performs one of the possible actions:

Defers the task. When the task tries to affect the nodes that are still running or if the task itself decides to skip this tick. In that case, the task is placed at the end of the queue.
Rejects the task. If the task has some inconsistency with the current tree, or it tries to replace the root or it decides to get rejected.
Apply the task. If the validations are passed successfully, Forester replaces the subtree provided by the task.

The engine applies only one task at a time, between ticks. If there are two tasks in a line, the first will be applied in the current tick and the next one only in the next tick. If the task gets deferred or rejected, the next one will be pulled out from the line in the current tick.

The structure of TrimTask is the following

/// task to perform
pub enum TrimTask {
    // task that changes the runtime tree
    RtTree(Box<dyn RtTreeTrimTask>),
}

impl TrimTask {
    pub fn rt_tree<T>(task: T) -> Self
    where
        T: RtTreeTrimTask + 'static,
    {
        TrimTask::RtTree(Box::new(task))
    }

    pub fn process(&self, snapshot: TreeSnapshot<'_>) -> RtResult<TrimRequest> {
        match self {
            TrimTask::RtTree(t) => t.process(snapshot),
        }
    }
}

pub trait RtTreeTrimTask: Send {
    fn process(&self, snapshot: TreeSnapshot<'_>) -> RtResult<TrimRequest>;
}

/// represents a snapshot of the current runtime state
pub struct TreeSnapshot<'a> {
    // current tick
    pub tick: Timestamp,
    // Blackboard
    pub bb: Arc<Mutex<BlackBoard>>,
    // Tracer gives an ability to produce the custom events
    pub tracer: Arc<Mutex<Tracer>>,
    pub tree: &'a RuntimeTree,
    /// from the ctx, it gives a current state of every node in the tree.
    pub tree_state: &'a HashMap<RNodeId, RNodeState>,
    /// current actions. This field is important when we want to replace one action to another,
    /// that is not in the tree and thus we need to add it manually.
    ///This field helps us to check this out.
    pub actions: HashSet<&'a ActionName>,
}

/// The request to proceed or not.
/// There are three possible ways:
///  defer to the next tick, reject this task at all or try to proceed.
#[derive(Debug)]
pub enum TrimRequest {
    /// To reject current trim request.
    /// It can be useful when other request changed the needed data already.  
    Reject,

    /// The conditions are not suitable for the changes. Better to wait until it will be better.
    Skip,

    /// Tries to proceed.
    Attempt(RequestBody),
}


/// The information to change.
pub struct RequestBody {
    /// The subtree that needs to be replaced.
    /// Basically the major important change appears in the root node of the builder.
    /// The other nodes are just supporters.
    pub tree_b: RtTreeBuilder,

    /// If we deliver a new action or we change an implementation of the actions this field helps to handle it.
    /// Eventually all actions enlisted here will be delivered to the main tree.  
    pub actions: HashMap<ActionName, Action>,
}

and it can be delivered to the forester instance as follows:

fn add_task(forester: &mut Forester, task: TrimTask) {
    let r: JoinHandle<RtOk> = forester.add_trim_task(task);
}

Examples

The examples, given in the article carry a hypothetical trait and can appear very artificial, but the main incentive here is to reveal the main reasonings behind the given feature.

Breaking down a long operation

Let’s assume we have the following code

import "std::actions"

root main r_sequence {
    move()
    // just to have an infinite loop (reactive sequence helps here)
    running()
}

// move is a simple def that works in the following way
// try to pick(can get failed)
// check if the attempt is failed then recover
// check if the attempt is success then place it
r_sequence move() {
    // we can't predict the result of pick so we force 
    // it to be a success always
    force_success pick()
    recover()
    place()
}

r_fallback recover(){
     is_picked()
     recover_impl()
}
r_fallback place(){
     inverter is_picked()
     place_impl()
}

// checks if something is picked
impl is_picked();
// returns the robot to the pickablep osition
impl recover_impl();
// attempts to pick (initial implementation)
impl pick();
// attempt to place to some nearest available location
impl place_impl();

This is a visual representation of the tree

Here, the script describes a way to move the item. The steps are the following: try to pick the nearest item and if the item is being picked place it or otherwise recover to the initial position (allegedly).

Let’s imagine that during analyzing the runtime execution(tracing, and some meta information in the tree), we came to the conclusion that the pick operation is the most important here, and it spends the lion’s share of time and the result is still unpredictable(can fail at any time). So we need to break the current pick action into a subtree that initially, validates the possibility to pick an item(which can be done quickly) and then tries to pick it. It can increase the chances of success or reduce time in a failure scenario.

The implementation

The real implementation is left beyond the script and got replaced by stubs, to show the mechanism of the task.

struct Breaker;

impl RtTreeTrimTask for Breaker {
    fn process(&self, snapshot: TreeSnapshot<'_>) -> RtResult<TrimRequest> {
       // simulate the analysis time 
       if snapshot.tick < 5 {
            Ok(TrimRequest::Skip)
        } else {
            let tree = snapshot.tree;
            if let Some(pick_id) = tree.analyze().find_by(|n| n.is_name("pick")) {
                let mut rtb = RtTreeBuilder::new_from(tree.max_id());
                // manually, for now, create the subtree.
                let sub_tree = flow!(
                    r_sequence node_name!("complex_pick"), args!();
                        action!(node_name!("check_cond_pick")),
                        action!(node_name!("pick_impl"))
                );

                rtb.set_as_root(sub_tree, pick_id);
                
                // add the new actions
                let actions = HashMap::from_iter(vec![
                    (
                        "check_cond_pick".to_string(),
                        // we omit the possible real implementation here.
                        Action::sync(SimAction::Random(100)),
                    ),
                    (
                        "pick_impl".to_string(),
                        // we omit the possible real implementation here.
                        Action::sync(SimAction::Success(2000)),
                    ),
                ]);
                Ok(TrimRequest::attempt(RequestBody::new(rtb, actions)))
            } else {
                // if there is no node that we need we reject the task
                Ok(TrimRequest::Reject)
            }
        }
    }
}

This is a new visual representation of the runtime tree:

As you can see, node 8 has been replaced with the subtree, which is supposed to be more effective.

It is reflected in the trace log in the following way:

12:07:19.329 [1]  1 : Running(cursor=0,len=1)
12:07:19.330 [1]    2 : Running(cursor=0,len=2)
12:07:19.330 [1]      3 : Running(cursor=0,len=3)
...
12:07:28.747 [4]    2 : Running(cursor=1,len=2)
12:07:28.748 [4]  1 : Running(cursor=0,len=1)
12:07:28.748 [5]  next tick

12:07:28.749 [5]  trim 15 : None >>> Leaf(Name("pick_impl"), RtArgs([]))
12:07:28.749 [5]  trim 8 : Some(Leaf(Name("pick"), RtArgs([]))) >>> Flow(RSequence, Name("complex_pick"), RtArgs([]), [14, 15])
12:07:28.749 [5]  trim 14 : None >>> Leaf(Name("check_cond_pick"), RtArgs([]))

12:07:28.750 [5]    2 : Running(cursor=0,len=2)
12:07:28.750 [5]      3 : Running(cursor=0,len=3)
...
12:07:34.960 [9]    2 : Running(cursor=1,len=2)
12:07:34.961 [9]  1 : Running(cursor=0,len=1)
12:07:34.962 [10]  next tick

The trace shows the replacement of the node or the insertion of new nodes.

Here, we perform the change task in the middle (after the 5–th tick) of 10 ticks execution.

Reordering the children

Giving the following code:

// this is a simple representation of a queue of some tasks
// the index is a shift from head.
// The queue tries to execute the nearest task and if it fails goes to the next one etc
root queue
    repeat(10) r_fallback {
        task(env(1), exec())
        task(env(2), exec())
        task(env(3), exec())
        task(env(4), exec())
        task(env(5), exec())
    }
// a task consists of
// - a tree for prepare the envirounment, which can fail
// - a task itself, which can fail also
r_sequence task(prep:tree, action:tree){
    prep(..)
    action(..)
}
// just preparing some env, checking position, conditions etc
impl env(idx:num);
// executing some job
impl exec();

This is just a queue, that is supposed to execute given tasks, without a specific priority.

Below, is the visual representation of the tree

The queue tries to execute the tasks one by one until the first success. It goes forward with an increasing index, which represents a shift from the initial point. Every task consists of the preparation of the environment and trying to execute it. Let’s imagine (again), that during the analysis, we discovered that the execution is more or less stable in time and probability of success. As it comes to the other task, here we have a specific pattern, namely, that when the task then far from the original point then less preparation time we need. During the first part of the execution, we can measure the time of the different stories (if we are lucky) and make an assumption that the farthest tasks can be performed quickly.

And we decide to reorder the children of the fallback, starting from the farthest tasks. It is needed to highlight, that it can be wrong if we try to restart the tree with a new code. It would be subject to check as well.

Here is an implementation

struct Reorder;

impl RtTreeTrimTask for Reorder {
    fn process(&self, snapshot: TreeSnapshot<'_>) -> RtResult<TrimRequest> {
        // pretent to analaze the first part
        if snapshot.tick < 5 {
            Ok(TrimRequest::Skip)
        } else {
            let tree = snapshot.tree;

            let node = tree
                .analyze()
                .find_by(|node| node.is_flow(&FlowType::RFallback));

            if let Some(id) = node {
                let node = tree.node(&id).expect("the node should be there");
                let elems = match node {
                    RNode::Flow(_, _, _, children) => {
                        let mut children = children.clone();
                        children.reverse();
                        Ok(children)
                    }
                    _ => Err(RuntimeError::fail("recover from unexpected".to_string())),
                };
                let mut rtb = RtTreeBuilder::new();
                // here we loose the name and arguments, 
                // but it is not important since we know this is anonymous def
                rtb.set_as_root(flow!(r_fallback node_name!(), args!(), elems?), id);

                Ok(TrimRequest::attempt(RequestBody::new(
                    rtb,
                    Default::default(),
                )))
            } else {
                Ok(TrimRequest::Reject)
            }
        }
    }
}