What is a Behavior Tree and How do they work? (BT intro part 1)
HTML-код
- Опубликовано: 19 июн 2024
- In this video lecture we explain what a Behavior Tree is, how it works and its advantages in terms of modularity, hierarchical structure, graphical representation and explicit handling of fallbacks, sequences and interruptions.
Our book on BT can be found on ArXiv as well as Amazon, but ArXiv is cheaper: arxiv.org/pdf/1709.00084.pdf
Clearly explained BT like a teacher. Thanks a lot :)
Thank you. I needed this kind of explanation.
Thanks for your teaching. It is really clear and helpful for me.
Great explanation, I'm new to the topic so It took me a bit to realize that the fallback nodes were represented with a question mark and the sequence nodes with an arrow, but the examples and visualization of the ticks were clear and helpful. Thanks.
Thank you so much for the very clear explanation
Thank you Petter, it was very insightful
I started watching your video without realizing you were the actual author of the book. Thanks for putting your time into this. It might be a bit much to ask for but I would highly appreciate an explanation of the section in your book on stochastic behavior trees. I have studied stochastic processes in the past, but it's still a bit dense for me. Thanks for the video.
Amazing explanation. Thanks!
Very pedagogical explanation!
Helpful video, thank you!
Very good video, thanks
This is the goto introductory video I share with people interested Behavior Trees. It explains the fundamentals and is not focused on gaming. Opened my eyes for using Behavior Trees in system engineering. Having a Behavior Tree manage the transitions in a Finite State Machine, I think is a very interesting concept.
This is the best intro to behavior trees that I've seen. Very easy to follow! I love that you use graphics a lot here.
I'm happy to hear this!
Very informative video 👍
Thank you.
Thank you! this lecture was very clear and informative!
nice!
Thank you very much for the series of videos, it is extremely helpful!
However, I noticed that only the first part has subtitles, the other videos do not have subtitles, is it convenient for you to add this? thanks again!.😀
Very informative introduction to the subject.
I'm glad you liked it!
BT reminds of me of scheduling inter-related tasks on a multi-tier project.
Amazing video, gives great intuition. I've watched a few other ai videos but they were a bit to fast and hand wavy and high level.
I'm glad you liked it.
Thank you very much for the series of videos, it is extremely helpful!
I have a remark, though: I do not really understand the concept of "RUNNING" actions.
If the ticking is synchronous, the action won't return anything before it's finished, right? At that point it will know whether the action succeeded or failed.
And if the action is asynchronous and return RUNNING because it's basically doing work in another thread, that means we can't as easily rely on the tree for interruptions because we need to stop the thread or at least alert it.
To take the examples from the video: if I'm eating the banana and the alarm suddenly rings, I won't instantly drop the banana and start leaving the building. I'll have some kind of "stop" effect that will let me cancel/pause the "Eat banana" action. Doesn't this basically bloats the complexity immensely in real-life behavior trees? I feel like I really am missing something, there.
Does the tree need to "remember" what task is currently running so it can tick it again next time? That would prevent interruptions from working at all but it really feels like interruptions are not as straightforward as what the video says when we try to think about the practice.
Hi Telokis. Thanks for your questions.
If you want to know more about real applications you might want to check out the PlanSys2 video here: ruclips.net/video/D7HkH6SvqjY/видео.html
As you might have noticed, there is one "version" of BTs that does not include the "Running", where basically all actions are allowed to terminate (returning Success or Failure) before another action starts. However, as you note, this makes reactivity impossible, so I think this version is crap.
In principle, I would say that if there is reason to believe that my life is in danger, I would indeed just drop the banana and start leaving the building. A banana on the floor might look a bit messy, but it is not that bad compared to dying in the fire. Another example where there is a bigger need for "gracefully terminating an action" is if you are driving a car when alarm goes off (imagine someone told you there is a bomb in the car). Just getting out of the car at full speed would probably kill you. Here I would say that the responsibility for stopping the car should be with the "get out of car" action. "get out of car" should have a precondition of "very low speed" and if that is not satisfied it would first slam the brakes, and then get out. (Check the video on Backchaining to see how preconditions and postconditions can be used to build the BT).
One drawback of this "goal directed" approach is that you would only execute actions needed to reach your next goals, and not tidy up after you. When you are done eating, you just leave the table, not putting dishes back in the sink. This can be addressed by explicitly adding the goal of "having a tidy home" to the BT (again using backchaining).
In some sense it comes down to your implementation. You might have a robot system where an action executes motor commands in a really high frequency control loop in a separate process, and if you stop sending new motor commands, the hardware might just stick to the last given command indefinitely, causing something to brake.
In such cases, if you implementation really requires that an action is "stopped" before another one is "started", you might just add a middle layer to your design keeping track of "current" and "next" action. The BT then keeps sending this layer an instruction of what should be done next. In the example the new command is "leave building", then the layer knows that it is currently executing "eat banana" and thus sends a "stop" message to "eat banana", waits for confirmation of a proper stop and then sends a "start" message to "leave building" and updates its notion of "current" to be "leave building" and "next" to be "(empty)". As long as "next" is empty, the current one is allowed to run. With this design, if stopping an action takes a long time, it might be that "next" is replaced by something else by the BT before "current" can confirmed its stop. Such a layer would not be overly complex.
I have one question regarding the interior nodes. Can there be more than 1 instance of "Open Banana" for example per Sequence node? Say I'd implement a BT to run a business case like an order-management. And how will the sequence node keep track of all the "Open Banana" nodes? Or do I need to spawn a complete BT for every incoming order-event in the sense that each BT can operate self contained? That would be a bit reminiscent of the Actor paradigm (I think) . Would love to hear any thoughts on this.
Hi TJ. There can certainly be several instances of the same action in a BT. For example, a navigation action "Goto (X)", that makes a robot go to position X, is natural as a part of many different subtrees, often with different values on the parameter X. A sequence node has a list of all its children. To have a high degree of modularity, we want every subtree to be able to operate self contained (but sometimes objectives are coupled, as can be seen in the video on Control Barrier Functions and BTs). I am unfortunately not familiar with the actor paradigm, so I do not know if my answers above are helpful or not.
@@petterogren7535 awesome thank you I think I get it. yes let's replace orders with robots :) I need to control an entire armada of robots. So I was wondering whether a single god-like BT is supposed to control every single robot out there or if it is easier to spawn a new BT instance per robot. So in any case, robots need to communicate (exchange messages) with other robots, for example to detect fellow robots in their vicinity. A god-like BT would take up the entire responsibility to control robots and handle inter-robot communication. For this, we need some form of book keeping or shared world view (where is everyone) on the god-BT itself. It also means that (during runtime) there can be multiple "Eat Banana" actions being executed at the _same_ sub-tree level (one action per robot who happens to eat a banana). But I thinkit can be difficult for god-like BTs to keep track of every robots action progress (like is it still eating banana?) because there can be millions of them. And in the other case if BTs are autonomous, independent and deployed as 1 BT per robot they will be much easier to debug, control and understand. Also communication is done through autonomous nodes and not through a shared worldview, it doesn't require the BT to know everything (no shared state). And in that sense BTnodes can be viewed as the actors in an Actor model. The actor model was made popular be Ericsson in their Erlang functional language which solves problems of shared state in highly concurrent environments ( think of a massive mobile network that requires 100% uptime and which nodes run on hardware with 25% failure rate.).
Erlang: ruclips.net/video/XVRGCIbbdUs/видео.html
Akka/Actor: ruclips.net/video/ELwEdb_pD0k/видео.html
@@TJ-hs1qm I believe your question is a classic one. Should the multi-agent system be controlled by one central AI, or in a decentralized fashion, where each agent has its own AI. The potential benefits of a central AI is that with all knowledge in one place, better coordination can be achieved enabling higher performance (for instance solving a multi-TSP to find near optimal routes for all agents). The corresponding drawbacks would be increased complexity, and a single point of failure, if the central AI stops, everything stops. The potential benefits of a decentralized approach are robustness and scalability. Agents can be added or removed at any time, and if one agent brakes down, the others keep doing their work.
When it comes to your situation I would try to estimate the consequences of each option, in terms of performance (worst case as well as best case), complexity, robustness to errors, need of adding removing agents etc, and then make a choice.
@@petterogren7535 haha I forgot to thank you... done :D
Great Video, makes me want to read your book! Can you please put a link in the description.
Thanks for the video! 🌸
I'm glad you liked it!
The book is available for free here: arxiv.org/pdf/1709.00084
and not for free here: www.amazon.se/Behavior-Trees-Robotics-AI-Introduction/dp/0367571331/ref=sr_1_5?crid=QX4AIKDLIXZK&keywords=behavior+trees+in+robotics+and+air&qid=1655799597&sprefix=behavior+trees+in+robotics+and+ai%2Caps%2C98&sr=8-5
@Petter Ögren Wow, that's really generous! Thank you!
Btw why do you give your hardwork for free? Writing a book takes a lot of effort.
@@AkashKumar-gu7jc You are welcome!
But there is some self interest involved as well. In science, the hard currency is Citations, not Dollars. With open access, more people can read, and hopefully cite the work we do.
@@petterogren7535 oh, now I get it...
I guess I learned something more than just Behavior Trees today. Hope you get good amount of citations on your work!
I'm planning to read it soon, I just downloaded and checked out the contents, there's a lot of interesting subject in there.
Hope it turns out as lucid as your videos!
How would I implement random behavior, or should behavior not be random? Based on the explained method, if a fallback-sort-of node (I will call random-selector) selects a random option to choose from (for example: I don't want the AI to always prefer to eat a sandwich), every tick it would choose a different option.
Maybe I could use the "running" return chain to remember where it was in a random selector, provided the previous tick returned a running command? Does that seem like a good idea? I guess if the tick hits the random-selector node, the node will check if the last return was a running status and continue from that selection.
If anyone has any other suggestions, I would like to hear them.
This is a very good question, thanks for asking it. You also make two key observations, first it is sometimes nice to have agents act a bit randomly, second, you do not want that randomness to happen with every tick, resulting in total indecisiveness.
Your solution with a "memory random node" sounds good. Remembering the choice as long as running is returned, and making a new random choice once success or failure is returned. This functionality can either be created as you suggest with a memory random node, or using some decorator solution.
In general I think memory nodes makes behavior less transparent and harder to predict, but in this instance (when non-predictability is the goal) is seems like a good option.
In some cases the perceived randomnes of an agent is due to a lack of information. Maybe the agent preferred an apple since it is tired of sandwiches after eating them 5 days straight. In those cases a more elaborate solution with utility fallback nodes (picking the options with highest utility) can be used, combined with a way of estimating that utility that leads to the desired outcome.
@@petterogren7535 that's true. I had briefly considered that simply making the tree more detailed with more conditions (for example to pick which food to eat) would make the system look more random simply because the situation is different. I think that would be a better, more realistic idea, but a memory random would be a faster implementation, since less thought would be needed for building the tree.
Thank you for your fast, detailed response!
@@mantisgaming another solution using his example hear with the different food types is you can simply make a random selector node. So rather than always going left to right it picks a random child to run, if that fails it picks another random child to run until all children have been checked. This way you get controlled but semi random decisions each time thats easy to debug. So when he eats hes not going to first eat a banana, then try an apple, then try a sandwich. hes instead going to maybe start with the apple, then the banana then the sandwich, another time he may go sandwich, apple, banana.
Should interruptions work even when eating is in Running state?
Yes. It is very important that all conditions are checked continuously. So just because one action returns running the BT should not wait for that action to return either success or failure, but constantly tick from the root. See some related topics in this video ruclips.net/video/UHUBYFal0DM/видео.html
Otherwise there would be no reactivity, no responses to fire alarms, and no safety guarantees (see ruclips.net/video/sgEBj6vNQVU/видео.html)
@@petterogren7535 Thanks! Ticking the whole BT sounds expensive when the tree is large (or even infinite if it is generated dynamically). What kind of workaround would you suggest for checking just the interruptions instead of ticking through the whole tree?
EDIT: I now opened the link and the title seems like it is going to answer my questions. :)
@@Haapavuo you can do event based ones, or tick it slower or even make smaller trees. you could also if you wanted force it not to fall back instantly on certain nodes. maybe it doesnt make sense to stop something imediately when a fire breaks out, may the guy needs to finish some task before he runs to it. You can make it what you want to be it doesnt have to fit with the mold of what they are taught as doing.
@@petterogren7535 In the model presented, when you get to the Run Away action, if it returns success doesn't the sequence (root) keep going and tick the Eat branch?
@@roadkill9173 Yes it will. Either Run Away returns success, or the agents runs far enough so that the alarm can no longer be heard (in which case the danger is probably not a problem anymore). In both cases the left-most subtree returns success and the agent will start eating (in one way or the other). The example might be a bit corny, but the assumption is that eating is a good thing to do, as long as there is no need to run away from danger.
İs This Unreal Engine Behavior Tree?
Hi Kaan. The video describes the general concept of Behavior Trees. There are many implementations: some tailored for Unreal Engine, some for Unity3D, some general implementations for Python, some for C++ and so on. There are some differences between different implementations: Sometimes the Fallback node is called a "Selector", sometimes nodes have memory (I think this is a bad idea as it reduces reactivity, as explained here: ruclips.net/video/W7p34qhBux8/видео.html).
It seems that the creators of the Unreal BT have described some of the ways their implementation differs from the "standard" under the heading "Differences in Unreal Engine Behavior Trees" found here: docs.unrealengine.com/5.1/en-US/behavior-tree-in-unreal-engine---overview/