Understanding the Behaviour Tree

Prerequisites

This chapter has the aim to explain, how the Behavioiur Tree (BHT) in the Raindancer firmware works logicaly. It will not explain how to programm/change it.

To understand this chapter, you need to know the core principles of Behaviour Trees.

There are lot of sides in the internet. I suggest the following side to read:

http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

You can download the BHT from https://github.com/kwrtz/Raindancer/tree/master/Documentation File: RaindancerBHT.spl7

To view the files of the BHT the following free software can be used: https://www.electronic-software-shop.com/support/kostenlose-datei-viewer/?language=en

Which nodes are used in the BHT

Leaf: These are the lowest level node type, and are incapable of having any children.

In a leaf stands the code which do the action. For example: stop the motors, drive back 20cm, ...

Or it could be a condition, which checks something. For example: is perimeter outside, was a flag on the blackboard set, ...

A condition only checks something. It never ever do an action or sets a variable.

A node can return one ot three statuses:

 Success
 Failure
 Running

In the BHT you see on most leafs, what they return and under which conditions:

 running: rotating
 true: both coils inside
 false: na

Selector: Execute every child till one returns Success or Running. If none then it return Failure. In other words, it returns the value of the first child that complete his logic.

Sequence: Execute every child unless one of them return failure.

Memory Selector: Same as Selector, but if one child return Running then at the next run the BT will resume its execution on the node that returned Running.

Memory Sequence: Same logic as Memory Selector but applying the Sequence logic.

Parallel: executes the children parallel. Returns running if all children return running. If one child suceed or fail the entire operation suceeds or fails.

You can find the description in the first sheet: BHT Root in the file.

Blackboard

When a node is called, it gets as argument the Blackboard (BB). It has access to the variables on the Blackboard (BB) and can query the services through the BB.

The Blackboard (BB) is a class, where the leafs of the BHT stores their variables, which other nodes also useses. This means nodes communicate whith each other over variables on the BB. There is only one BB for the whole tree.

How a leaf will be presented in the documentation

In the picture below you see the presentation of a leaf. The pink arrows show from/to the variables which will read from the BB and which the node changes on the BB.

You see also the return values of the node. The node will return running while rotating and success (true) if both coils inside. Failure (false) is not used.

The text below the picture explains, what the aim of the node is.

TRotateBothCoilsInside is the name of the node class where this node is implemented. If you want to find the node in the code, you have to search for this class.

Furthermore, you see, that the node set an error, if it is running too long.

A leaf is non blocking

This means, that a leaf does not block the execution of the BHT (for example with delay). How does this work?

See the following abbrevaited code of TRotateBothCoilsInside:

class TRotateBothCoilsInside : public Node
{
public:
       virtual void onInitialize(Blackboard& bb) {
               bb.cruiseSpeed = bb.CRUISE_SPEED_OBSTACLE;
               if (bb.flagForceRotateDirection == FRD_CC) {
                       bb.motor.turnTo(-380, bb.cruiseSpeed);
               }
                else {
                       bb.motor.turnTo(380, bb.cruiseSpeed);
                 }
         }
      virtual NodeStatus onUpdate(Blackboard& bb) {
              if (bb.perimeterSensoren.isLeftInside() && bb.perimeterSensoren.isRightInside()) { // wenn beide coils innen dann weitermachen
                   return BH_SUCCESS;
               }
               return BH_RUNNING;
       }
       virtual void onTerminate(NodeStatus status, Blackboard& bb) {
              if(status != BH_ABORTED) {
              }
       }
}

If the node is called in the tree and is not in running state, the onInitialize will be called. The node sets the rotate direction depending on bb.flagForceRotateDirection and commands the motors to rotate the robot +/-380 degree. Then the onUpdate function is called. In this function will be checked if both coils are inside. If not, running will be returned. At the next run of the BHT onUpdate will be called without calling onInitialize. The function checks again if both coils inside. Remember, the mower is currently rotating because of the command bb.motor.turnTo(). When both coils are inside, success will be returned. Then onTerminate will be called and the node has done it's job.

So never use a code like:

while(! (bb.perimeterSensoren.isLeftInside() && bb.perimeterSensoren.isRightInside())){
 //do nothing
}
return BH_SUCCESS;

Behaviours of the BHT

The BHT represents different behaviours. In the picture below, you can see that six behaviours are currently defined.

In charging station
Goto area X
Perimeter tracking
Find perimeter
Mowing
Restore History

Only one of these behaviours can be activated at a time. A decorator node blocks the access to the behaviour, if the associated flag is not set. Vor example: If the flag flagEnableMowing is true, the decorator node executes the selector selMowing.

The BHT is alway executed (ticked). No node should ever block the BHT. The BHT will be executed counter clockwise. The top left node will be executed first, and then the nodes in CCW direction or from left to right.

Let see how this works to warm up: The selector selRoot is called to execute the BHT. It first executes TdnCharging. Because flagEnableCharging is false, the decorator node returns false and selRoot executes the next node selCheck2. This selector runs first TChec2PerSignal. This nodes checks if the perimeter signal is available. Lets say, it is not available, then TCheck2PerSignal stops the motors and returns running. selCheck2 gets the return value and because of running, he gives the control back to selRoot. Because selRoot gets the running as return value, the run of the tree is finished. Now the next run starts.

Again selRoot is called. Then TdnCharging. Then selCheck2. Then TChec2PerSignal. And because we have no perimeter signal, selCheck2 is called and then selRoot. After this all starts from the beginning until TCheck2PerSignal recognice the perimeter signal.

Ok lets say the signal was recognised, then TChec2PerSignal returns false. Then selCheck2 executes Tcheck2CoilSignalAreax which retrurns false. Than Tcheck2LefCoilSigal which returns false and then Tcheck2RightoilSigal which returns false also. Now selChek2 returns false to selRoot, which then executes TdnGotoAreaX. Because flagEnable GotoAreaX is false, TdnGotoAreaX returns false. Same with TdnPerimeterTracking and TdnFindperimeter. Now TdnMowing is called and because flagEnableMowing is true, the selector selMowing will be executed. What is behind this selector you see on the page BHT Mowing.

I hope you understand now the concept, that the BHT is never ever blocking. If it returns from a run (tick) it starts again form the beginning. Branches of the BHT can be activated through Decorator nodes or through conditions. That we will see in a next chapter.

If you can't read the text in the image, you can klick on it and then zoom it.