There has been much chatter recently in the robotics community with certain voices proclaiming the “death” of finite state machines and proposing that a new paradigm known as behavior trees is the path forward for robotics programming.
These voices, have lost their minds.
The single most important reason that makes behavior trees completely unsuitable for programming complex robotics, is that they do not support orthogonality.
In the book Behavior Trees for Robotics and AI, by Michael Colledanchise & Peter Eggerts, there is not one example that makes mention of an orthogonal, or a physical subsystem such as a robot base, infrared sensor, an imu, or a robotic arm.
In the 2019 paper, Analysis and Exploitation of Synchronized Parallel Executions in Behavior Trees the same authors propose acknowledge that behavior trees are faced with this limitation. From the opening paragraph…
“A very powerful composition is the parallel one, where the designer can easily encode the concurrent execution of several sub-behaviors. Unfortunately, the parallel composition is the least used composition due to its underlying concurrency problems –.”
Their solution, is to create separate processes, that each handle one orthogonal, in there case the robotic base, and a scanner. It should be obvious to all programmers that, this will not scale well.
What happens when you have 26 orthogonals, corresponding to 26 physical subsystems, say on a military uav. Are you going to run 26 processes and deal with all the interprocess communication? How would you debug such a system, and the inevitable race conditions that would almost certainly arise?
I repeat, this will not work, this will not scale, and whatever the benefits are of behavior trees, they will not find widespread use in the field of complex robotics.
- How do you handle recovery sequences?
- Do you put them in the beginning of the cycle, or the end?
- if it’s at the beginning, how is this going to be fast, since you loop through it every time?
- How do you handle orthogonals again? – see above
Behavior Trees are for Gaming
Behavior trees are how AI is done in the gaming world. The first, and most notable use of behavior trees was in the game Halo2 and it’s been built on from there.
But of course, little goblins running around on the screen, are not the same as complex robotic systems (see target robots). These items have fundamentally different costs, complexity and liability associated with them.
So, instead of figuring out what state we are in, let’s cycle through all the states, count on doing multiple checks that come back negative, and then use guard conditions to do something. – Should be real fast.
Where are the robots?
But let’s put theory aside. Where are the complex robotic systems using behavior trees? And the Nao walking around doesn’t count.
Try an experiment out for yourself. Find someone, who has never taken a computer science course in their life, and ask them a question like…
“How do you bake a cake?”
You’ll get an answer that, with very little massaging, gets turned into this..
Buy Ingredients —-> Place ingredients in the baking tin —-> Mix Ingredients —-> Place in oven for 30min at 350 degrees ——> Put on oven mitts ——> Remove pan from oven ———-> Wait for pan to cool —–> Eat.
And ouila, you’ve got your outline for a state machine.
Now expand the question, to other domain experts…
- How do you fly an airplane?
- How do you startup a computer?
- How do you
Never once, will you hear a human being outline the process by behaviors based on conditions (which is how BT’s are constructed).
“Do I have the ingredients? If yes, have I placed them in the baking tin? If yes, have I mixed them? If yes, Is the Oven 350 degrees? If yes, is the pan in the oven? If yes, has 30 min gone by?, If yes, have I put on my oven mitts? If yes, have I removed the pan from the oven? If yes, have I waited for the pan to cool?, If yes, have I eaten it?”
States really do exist
In the final analysis, it should be obvious that although they are a mental construct, states really do exist…
- In an airplane, you’re either in the air or on the ground
- A car is either moving, or its not
- A handgun is either loaded, or it’s not
- Your mother-in-law has either joined you for dinner, or she hasn’t
And you need to behave accordingly;)
The answer, is not to pretend that states don’t exist.
Which is what you do with behavior trees. You put everything in a while loop, and you do condition checks every time you cycle through the loop. Which does not scale.
If you ask some of the questions above to a proponent of behavior trees, and you hear the usual, “well, that’s an interesting area of research…” realize that it’s not. It’s a fundamentally flawed idea, and then come join the SMACC party…
Real-time, C++, Behavioral state machine with blazing speed and with the best Visual Programming tools today. We want you, we need you, lets change the world.