Using behaviour three notation for behaviour description in Capella in comparison with statechart notation

Hi all

I am interested in what you think about the possibility of using the Behaviour Tree (BT) method for behaviour description in Capella. Though in some industries BTs are used as a standard for behaviour description from example in the document below it’s not obvious for me that they outperformed statecharts. In any case I assume that BT can be used for behaviour description in Capella, adding some semantic information to composition functions.

I’ve formulated my thoughts on this subject with an example BT for ping pong behaviour in the document provided

BehaviourTreesInCapella - google docs link

Would like to discuss this subject in detail

Regards,
Dmitry Ryzhov

1 Like

Have updated document with new simple examples of behaviour trees

  • for simple decision tree with one condition
  • for more complex decision tree with several conditions

Bellow first example

Simple decision tree

Equivalent behaviour tree on the LFBD diagram

Behaviour tree in the model browser
image

Another example convertion for behaviour tree. In this case from BT to statechart

This behaviour tree contains an instruction how to learn behaviour tree notation

image

Translated to statemachine

image

This instruction from software library implementing BT notation for ROS2 navigation stack
This library was implemented by Intel.
It contains simple introduction to BTrees

More ppractical and theoretical information about behaviour trees is here (~ 200 pages)

Hello

I just discovered these Behaviour Trees, thanks for sharing about this formalism. If I understand properly, it is a way to define expected behaviour in terms of execution of actions.

If we consider that Functions are actions, then I guess the way to “mimic” BT in Capella would be using Sequence Links in Functional Chains:

I wouldn’t suggest to go with decomposition of function as this is about performing a functional analysis. Neither with modes diagrams representing modes as actions, because they are related to specific components of the system, which will make difficult the task of representing the expected behaviour when actions are executed by several components, and because the semantics are not that close (modes (or states) are not actions, but they can enable actions).

However, Functional Chains and Sequence Links won’t be enough, as semantics such as “find and execute the first child that has not yet succeeded” are not native in Arcadia and would require some extension or some free-text explanaition.

Hop this helps.

1 Like

Hello,

I think that Behaviour tree notation is not clear for you yet ))
It’s ok. It’s not very simple.

Functional chains can be used for DECISION Trees modeling but not Behaviour Trees.

The key of Behaviour Tree notation is it’s hierarchical nature and parent-child relations between elements. It gives this notation high modularity.

And I agree that functional chains should be used for decision trees but not statecharts.
Statecharts should be used for modeling of state based behaviours.
It would be great to add for Functional Chains function’s drag and drop from model. Now you need do add them by Diagram Tools. It’s very slow.

Regards,
Dmitry

Have updated my original document (link in my first message).

Added more exmaples that helps to understand the notation correctly.

  • BTree nodes execution in dynamics (step by step nodes execution)
  • different result of BT nodes executions (SUCEES, FAILED)
  • combined behaviour tree (to show good scaling of BTs)

By the way it’s quite simple to create a new Capella viepoint for behaviour tree notation.

Currently in my examples I use colors to denote semantics of composite functions.

Viewpoint can add properties to denote such functions.
Special visual notation can be added when showning on diagrams.

For creation of composition functions with neded semantics (Sequence, Select, …)
new Tools can be added to diagram panel.

A new diagram type for behaviour tree definition can be created wtih these tools. Or function breakdown diagram can be extened with new tools.

In the theoretical consideration of behaviour trees there is a theoretical justification that BTree generalises desision trees and hierarchical state machine.

Below is an example of behaviour tree for Ping Pong statemachine.

legend:

  • yellow : condition nodes
  • chyan: select\failover nodes
  • magenta: sequence nodes
  • green: action nodes

You can see that BTree easily model event handling in composition state. (see evStop event).

Functional chains can be used in conjunctions with BTrees for the standard purpose : to show different scenarios of execution of functions. In case of BTrees it can be used to show sequence of execution of leaf functions.

On the diagram

Function chanin for this example shows scenario of leaf function execution.

legend
magenta: nodes with success execution
chyan: nodes with faulure execution
green: not executed nodes

In the book I’ve provided before transitions in statecharts are compared to goto statements in programming languages.
BTree notation is compared to traditional call statements.

It’s very good known that code with goto statements much easy to write but much difficult to understand.

When goto is used what to do next is decided by the block that receives execution.
When function call is used called function does not decide what to do next. It returns some result and parent function decide what to do next.

In BTree when some node is executed with FAILED result execution returns to parent node and it decides what to do next. Several types of compositions functions can be defined. Parent node can break it’s execution and returns Failure to it’s parent. Or it can try to execute it’s child one more time.

Capella does not define any semantics for composition function. BTree adds execution semantics to composition functions. As this execution semantics is sequantial it also results in definition of more clear functional hierarchy.

It’s common in Capella to have some composition functions for a algorithm that contains a lot of leaf functions that are not grouped in any way. Behaviour of function usage is defined in statecharts or functional chains.

BTree results in grouping of leaf functions into coherent groups of functions of several levels.

Grouping algorithm’ function as in BTree simplifies documentation generation. Full algorithm behaviour in such documentation is visible from function hierarchy.

Hello

Arcadia does define semantics for functions decomposition:

The conventional top-down hierarchical approach such as promoted by structured
analysis and its derivatives, expresses the required functionality in the form
of a limited number of first-level functions and then determines necessary exchanges
between these functions. This high-level synthetic vision is then refined, on a function basis, through the definition of subfunctions (or child functinos) for each identified function

Leaf functions are always somehow related, as they are functional decompositions of their “parent” function. BT could serve to express the expected execution of these functions, if a BT is associated to a parent function. Or could express the expected execution of functions regardless their decomposition tree if the BT is associated to a Functional Chain or a Capability.

Hope this helps.

weill add some elaboration …

BT - is integral part of functional decomposition in which additional execution semantics is added to the non-leaf functions. It can’t be used outside functional hierarchy

Leaf functions are interconnected to each other using ports.
Leaf functions can exchange data with leaffunctions of the same BT and with leaf functions from different BT.

BT fully specify behaviour as statechart do.
BT or part of it can be assosiated with one or several capabilities.
Functional chains and scenarions can be used to show different scenarios “inside” full behaviour specified by BT.

I agree that BT trees can be used to specify behaviur “otside function hierarchy” like statecharts, functional chains in Cappella. Some additional model element can be defined and contains BT hierachy with leaf-elements calling leaf functions from functional decomposition three.

I think that this way of utilizing BT have lower scalability compared to the way of using BT as a part of functional decomposition.

The best way to create BTrees could be to have a textual DSL with possibility to create functional decomposition (with ports) and create visual repressentation from DSL.

Example DSL for bahaviour tree in the form of VSCode plugin
https://marketplace.visualstudio.com/items?itemName=jan-dolejsi.btree&ssr=false
It helps to create BTree with DSL and in parallel show visual representation of DSL.
It works the same way as Yakindu Statechart DSL works with statemachines

VSCode plugin helps to edit DSL, check syntax, create\update list of existing condition\actions, substitute existing condition\actions, visualize and analyze BTree in graphical form.

On the visual representation it’s possible to show\analyze execution history. It’s possible to set execution results (SUCCESS, FAILURE, RUNNING) for some nodes and see what node is currently executing.
Nodes with SUCCESS result marked with green. Call stack is shown in blue (nodes and edges).


In this case Action1 was already executed. Condition “Check == False” is True.
Action4 is executing.

image
In this case Action1 was executed with SUCCESS result. Condition “Check == True” is true. Action2 was executed with SUCCES. Currently Action3 is executed.

In game engines such as Unity or Unreal Engine both of these notations are used: behaviour tree and statemachines. There are a lot of discussions what notation to use and when.
I see general undestanding that results in the following rules:

  • use decision tree if behaviour is simple
  • use statemachines when behaviour is more complex but not very much
  • use decision three for complex behaviours

When statemachines and behaviour trees are used together statemachines is used to describe behaviours of leaf-functions of behaviour tree.

I also see that it’s common for many tools to have separate lists of actions and separate hierarchies for behaviour trees. Actions from the list (simple form of functional decomposition) can be reused in several behaviour trees. This principle is also valid for the VSCode plugin I’ve mentioned before.
Workspace can have several folders. In each folder a list of possible actions\conditions can be defined (using json file). And several BTrees can be defined inside the folder in separate files (*.tree).

The main question for me now: What is the right way of using BT: as part of functional decomposition or as an external hierarchy (as in state machines or functional chains).

I understand that from Capella methodology point of view the separate hierarchy would be the right choice. Let’s name it “Capella way”. This way @JNavas is suggested for me. Now I see is three ways of using BT inside Capella in “Capella way”. May be some other ways can be added.

The first way is to use BT as a separate hierarchy is to create new element type BehaviourTree for components. User will select notation that is suitable for concrete case. In this case strict new meta-model can be defined for BT notation and special kinds of visual diagrams or tables. Leaf-elements of this BT element will be reference leaf-functions from functional hierarchy. Drag and drop from model to diagram can be implemented for leaf-functions from functional hierarchy that will create actions in BT element. Behaviour trees can be added on different levels in component hierarchy. Behaviour tree of parent component can “tick” behaviour trees of child component or “enable” state machine execution of child components or “call” functions allocated to the component.

The second way of using a separate hierarchy for BT is to create special model element BT inside any functions. In the same way as functional chain elements are defined. This will add the possibility to define control flow for function using BT.

The third way is to create BT elements in capabilities to describe behaviours of several components using BTrees. It’s also the same way as functional chains are used for capabilities.

All this three ways to be used assume Capella customization. If these ways are selected it will result in no CURRENT way of using BT inside Capella. In fact it’s not very hard to make this customization of Capella but in any case some work is needed.

On the “Capella way” behaviour is specified for components (using state machines). So behavior is a “characteristics” of a component or a set of components.

On the “Capella way” there are no behaviour semantics for composite functions. Any composite function is a simple group of subfunctions.

That’s why only leaf functions are allocated to components. After allocation, leaf functions can be used in the definition of component’ behaviour. Functional decomposition should define a list of functions(grouped in some hierarchy that does not influence behavior).

If use BT as part of functional decomposition behaviour becomes to be “characteristics” of the composition functions. To make this composite function behaviour to become behaviour of some component composite function allocation is needed. And it’s not “the Capella way”. In Capella only leaf functions can be allocated to components.

In fact the same situation takes place with functional chains in which control flow is defined. There is no way to connect this behavior to components. It seems to me that on “Capella way” it’s not correct to use functional chains inside functional decomposition and use them to define control flow (that is outside of components).

On “Capella way” behaviours should be specified for components. Potentially it could be used decision trees, state machines or BT for behaviour specification. Currently Capella provides only state machines in components for the behaviour specification. As a consequence in many cases decision trees are also specified using state machines in many situations. There is a good reason to have a special “tool” for decision trees in components. As well for BTree.

I’ve decided to describe the main reason why I am trying to find a way to use BT inside functional decompositon. It seems to me more practical and more easy.
I will explain my thoughts on some use case.

Let’s start from functional decomposition that is standard and is a simple list of leaf-functions grouped in some hierarchy. Let’s look at some leaf-function. At some stage of modeling it can be atomic and does not have sub-functions. The function bahaviour can be defined usind textual description. This leaf functions is allocated to some components and involved into it’s behaviour, for example is called on some transition.

On the next stage Modeler can decide to use modeling to add details to it’s behaviour specification to make it more formal than simple textual description.

To achive this Modeler needs to add severla sub functions and define behaviour for original function in which new subfunctions are used. If BT are used inside functinal decomposition it’s very simple to do this step to the next level of function\behaviour decomposition and specification. Original function can be continue to be allocated to the same component. All you need for behaviour specification is to add new sub functions using BT notation.

It’s not simple to understand and use the right “Capella way” to do the same thing.

  1. Decompose original function into sub function
  2. Allocate new subfunctions into the same component as original function. Allocation for original function is not valid after it was decomposed.
  3. Change statchart for the existing component to add detailed behavior of original function.
  4. Or create new component, allocate new subfunctions to it, create new statechart and define original function behaviour.

It’s very simple common use case but very hard and not obvious solution using “Capella way”.

Please correct me if my understanding of “Capella way” in this scenario is not correct.

In my opinion it would be great to have a new way to define bahaviour inside functional decompositions adding behaviour semantics to composite functions. And after that allocate composite function with behaviour defined to components. It could be more scalable and simple approach.