Hi Steven, and everyone else…
Look, I’m keeping it positive. The only reason this conversation has gotten off to a bit of a rough start is that the thread was, in my opinion, rudely hijacked by Mr. Gramb, who took it upon himself to quickly answer the first question asked in this announcement, which was clearly addressed to me. He then took quotations out of context from things I had written some time ago on a web page where I was collecting my thoughts (but was public so I should have edited better) regarding behavior trees in general and not specifically Mr. Faconti’s implementation of a BT library in BehaviorTrees.cpp, but I digress…
And with all due respect, I think that the advantages and disadvantages of state machines (and SMACC specifically) vs. behavior trees is an important topic for serious developers to discuss.
Further, we now have Mr. Faconti, the author of BehaviorTrees.cpp, and Mr. Stonier, who I’ve recently discovered is the author of py_trees, presumably a python based behavior tree library, and myself, all on one post together. This is a rare and important opportunity to engage in discourse.
One thing that I think would be helpful to advance this discussion, is for all those joining the discussion and particularly those commenting about BT’s is to actually post links where we can see working examples of BT code in action, as opposed to tutorials, or hearsay examples.
Then we would be able to compare code side by side.
Example state machines for the SMACC library can be found here. And an instructional video on how to get these state machines running on your system can be found here.
I would like to thank Mr. Davide Faconti for joining the thread. I very much admire Mr. Faconti's work and character. This is a man that seeks the truth.
From Mr. Faconti’s post, I think he and I can agree on the following…
Polling vs. Event-Based
BT's rely on a polling pattern, whereas SMACC (and SM's in general) use an event-based approach. And I think he and I both agree that an event-based approach is generally better, particularly in an asynchronous environment.
That States really do exist
We agree on this as well and that this is an advantage for state machines in general.
And it seems that there are (at least;) two areas that we disagree on…
For this one, there is obviously a fair amount of subjectivity at play, but for the uninformed, one major difference between the way SM's and BT's are structured is rooted in the fact that SM's use states whereas BT's use conditions.
Mr. Faconti feels that the “bake a cake” example I had/have on the smacc.ninja page is unfair. So I would like to ask Mr. Faconti (and will do so offline) if he could provide us with a link to a sample he feels is a fair comparison. I would love to see it for my own understanding and I’ll incorporate it onto the smacc.ninja site as well.
Orthogonality (…and the real-timeness, scalability and modularity associated with it)
For this topic, I think being able to look at specific implementations of BT code would be particularly helpful. I think this is due to the fact that we are simultaneously discussing both runtime architecture (threads, nodes, etc.) and code modularity.
For myself, it’s hard for me to see how BT’s in general and this includes BehaviorTrees.cpp, would be able to handle robots that comprise many orthogonals, particularly when the sub-systems in those orthogonals are themselves complex (for instance, ROS Navigation, MoveIt! or a perception client vs. a low battery sensor or a thermostat), and maintain the code for each orthogonal/subsystem in different translation/compilation units to preserve modularity (so that you could later add another robot arm, 4 more sensors, or a pan-tilt unit, etc.), without resorting to spawning threads (or nodes) in one form or another…
I also think the fact that it’s a polling environment (vs. event-based) might also complicate this issue, but I admit that this is conjecture on my part.
But, I am not an expert in that library, or other BT libraries quite frankly. So perhaps it can be done…
Mr. Macenski's comments bring up another feature that we haven't discussed yet....
There are two features of SMACC and other “statechart” based state machines that I also think are relevant to this discussion.
The first is that every SMACC state contains a transition table where you can either explicitly (the most usual way) or programmatically, define your transitions.
I think, and would love to hear Mr. Faconti’s opinion on this, that SM’s generally have the advantage of providing more precise control over transitions, (because in state x, which may be a corner case, you transition to state y on event z, whereas in state q you can… etc.), with the inherent disadvantage that, as a programmer you might screw that up, thus making BT’s somewhat more robust to developer error.
This danger is greatly mitigated with SMACC, specifically because it uses template metaprogramming to check all your transitions for correctness at compile time. And I think that this is one of the main advantages SMACC has over non-template based state machine libraries written in C++.
And the second, that is also unique to “statechart” based machines, is that SMACC offers programmatic control of transitions. Programmatic transitions (which Harel referred to as broadcast-communication) is one of the three main additions to FSMs David Harel brought to state machines in his famous 1987 paper.
With it you can do things like this…
Say we have a hierarchal state machine with two modes, “Run” and “Recovery”. In those two mode states, say we have 10 states in Run, and a 4 state recovery sequence in Recovery. We start operation in Run/State1 and for all states in Run, in the case of a error X, we want to transition to our recovery mode.
So we start operation in Run/State1, progress to Run/State3, throw error X and transition to Recovery/State1, we progress through the recovery sequence to Recovery/State4, succeed and…
Uh oh… Where do we transition to? How do we program that we want to go back to the state we originally left from (in this case Run/State3) in an explicit way?
Clearly this creates a problem and programmatic transitions solve this. Here is an example of our code that demonstrates this in action and shows the syntax of these transitions…
We currently inherit this functionality from Boost Statechart. Boost Statechart uses this in it’s use of state machine history, which is why it is usually used for advanced error recovery situations.
I think that this feature may have relevance to the example briefly mentioned by Mr. Macenski involving “navigation systems orchestrating between N different planner and controller algorithms for specialized situations” that supposedly made an FSM infeasible due to the number of transitions.
It’s hard to say given the limited information provided regarding that example, but I wonder if the programmatic transitions and compiler validation features present in SMACC may have made that problem quite tractable.
Another reason I question that statement, is that we already have two example state machines (here and here, along with videos here and here) that use navigation and load N different planners and have multiple controller algorithms. So again it’s hard to tell given what little I know about that example but I think this highlights that SMACC isn’t technically an FSM, in that it inherits from D. Harel’s statecharts, and that I question whether Mr. Macenski’s comments regarding the infeasibility of SM’s for that application are correct.
And to those just joining the thread, I would again like to specify that my comments assume that we are talking about robots that generally look like this…
P.S. Mr. Macenski, If you have any links or other evidence substantiating your comments on industry practices regarding behavior trees in the world of pick/place complex manipulation, I’d love to see it.