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.I think that viewpoint is wrong.
Orthogonality/Concurrency
The single most important reason that makes behavior trees 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 [12]–[14].”
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?
It is my firm belief that this will not work because it will not scale.
Improving the Parallel Execution of Behavior Trees (9-2018)
Analysis and Exploitation of Synchronized Parallel Executions in Behavior Trees (8-2019)
Recovery Modes/States
- 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 and 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 goblin NPC’s 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.
Where are the robots?
But let’s put theory aside. Where are the complex robotic systems using behavior trees? – I’m not saying that the don’t exist, but I’ve yet to find open source examples of BT implementations…
And the Nao walking around in the videos found in the link below is somewhat misleading in my opinion, because one might think that it qualifies as a complex robotic system, but in my opinion really doesn’t.
https://www.youtube.com/channel/UCw-9RbG53IMyMAf9Km4Y7CA/videos
Readability
I disagree, with the claim often made, that behavior trees are more readable. I actually think for many situations, if not most, behavior trees are less readable due to their condition based syntax.
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?
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?”
https://www.behaviortree.dev/bt_basics/ – Recommended by Mr. Davide Faconti, the esteemed Author of Behaviortree.cpp
Performance
And, I don’t think the condition based flow (polling) lends itself to high performance, vis a vis an event-based system. Particularly in asynchronous environments.
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.
Calling BS (I admit I should not have used this headline – B.A. 6/27/20)
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…