How to create Behavior Trees using Backward Chaining (BT intro part 2)

Backward chaining is a classical AI planning approach. It creates sequence of actions that leads to a given goal. In this video we show how a similar idea can be used to create Behavior Trees (BTs). The key difference compared to normal planning is that the BTs are reactive, and can handle unforeseen events requiring actions to be re-executed, or skipped, or replaced by alternative ways of achieving the same subgoals. The approach is illustrated with a fairly complex example.
Our book on BT is available for free here: arxiv.org/pdf/...

[@FlipYourLearning]

This series is promising, exactly what I was looking for as a beginner.

[@top1hit]

I love your high-quality and structured explanation

[@petterogren7535]

Thank you!

[@kawaiianthony8090]

Wanted to Behavior Trees to develop my game's AI, but my thought process is still stuck at using FSMs, this tutorial is very useful!

[@petterogren7535]

I'm happy to hear that!

[@Tymon0000]

Thank you for posting the series.

[@f0kes32]

Love this tutorial!

[@Telokis]

Thank you very much for those videos, they are very helpful!

[@basilbaby2069]

Thank you sir for the very well explained lecture

[@bommijn]

Very informative videos, Thank you!

[@ivailoburov1295]

Great tutorials, thank you.

[@TopShelfCookieJar]

Great explanation. Thank you!

[@1volkansezer]

Great video, thanks. But I have a confusion. In the last example (the burglar one), the solution to avoid the contradiction problem is adding a "Hide Camera" action to the right. But in this case, as long as the action of "turn light off" action is made, the rightmost "hide camera" action will still not be taken? Doesn't that mean the contradiction continues? Was the "Turn Light Off" action supposed to be deleted when adding "Hide camera"? Is there something I am missing?

[@petterogren7535]

Hi Volkan! Thanks for your question. Yes, I think a was a bit unclear around 18:28. As you note, for the fix to work you need to either disable or remove the "Turn light off", or add "Hide camera" to the left of "Turn light off". Thanks for pointing this out!

[@1volkansezer]

Hi Petter. Thank you for making a video series so clear and understandable that even a small mistake can be noticed :).

[@midimusicforever]

Good stuff!

[@kimochisaiko6442]

great material!!!!

[@petterogren7535]

Hi Kimochi, I'm glad you liked it!

[@nikodromikro]

you explain very well can you do tutorial on Utility AI as well?

[@pvmilk]

Thank you very much for a great lecture. I have a question regarding the tick and how the modern framework implemented this. Let's assume 1. the sequential programming language (1 process at a time, and no parallel process). 2. Tick is ticking every "t_tick" seconds. 3. Maximum time period to finish the whole sequence of the tree is "t_traverse" seconds. My question is, if t_traverse > t_tick, how can the agent complete the whole sequence, since the tick will always restarted and started to traverse from the left in order to check for the condition. In order words, for the one thread programming paradigm, how can you archive interruption while traversing the tree? (I would need a list to stored all the conditions and the action that failed previously and rerun them every ticks, but if re-running those failed action takes too much time, will the agent have a chance to restore their recent action in the previous tick?) You actually mentioned the exact same thing at 15:10, when "Person Nearby" return true while the Agent was "Searching" for the key.

[@pvmilk]

For those who is rush to ask like me, please check part 5 in the series below. It answered most of the question. kzbin.info/www/bejne/i3m4c4x8ltFjeq8 Again, great lectures. Thank you!

[@petterogren7535]

Thanks for your question. You are perfectly right, non-parallel implementations run into problems if t_traverse > t_tick. As you might have noticed, most BT designs, including theoretical guarantees of safety and convergence, assumes t_traverse to be "fast". Thus, if your BT includes conditions that take time to evaluate (such as sensor data computations involving point clouds) they should be running in parallel to the BT traversal. Some issues related to this was discussed in kzbin.info/www/bejne/i3m4c4x8ltFjeq8.

[@pvmilk]

@@petterogren7535 Thank you for your reply and the link. They answered the question perfectly.

[@player-eric]

The video mentioned, "If during that search a person came by a person nearby was suddenly returned success and the agent would stop searching and ask the person if the person could please open the door.". I'm not sure how this could be implemented using py_trees. I think this involves parallel processing, interruption. Could you please elaborate on this?

[@petterogren7535]

You need to have reactive versions (without memory) of both the Sequence and Fallback nodes. Unfortunately, some software has memory nodes as default. Sometimes this is a simple option, otherwise you have to use a workaround. In Panda BT you have to "reset" the BT every tick to remove the memory.

[@player-eric]

@@petterogren7535 Thank you for your reply. I am currently more familiar with Python, and I have hardly used Unity, so I has little knowledge about the usage of Panda BT. I am currently learning py_trees. What I actually wanted to say is that, for a single `tick()` of a BT, I feel that the traversal of the entire tree should be serial, maybe depth-first traversal. If so, then BT has already executed to "Has a key", then even if "a person came by" at this time, I feel that BT will not go back to "confirm that a person nearby was suddenly returned success", but will continue to "Search door mat / garden", unless there is a parallel mechanism that allows another subprocess to constantly detect whether "a person came by".

[@petterogren7535]

Yes, a single tick traverses as you describe, but the next tick starts from the root. So the next tick can respond to the presence of a person and act accordingly. @@player-eric

[@player-eric]

​@@petterogren7535 Thanks sincerely for your guidance.

[@AbhishekSharma-fp9db]

How would you model cleanup actions when a sub behaviour tree is interrupted midway? Ex: While opening a door with key was in progress, agent found a jacket. A safe cleanup of Open door BT requires agent to put the key back where it was found (or in pocket) and not leave it hanging in the keyhole.

[@petterogren7535]

Hi Abhishek This is a great question, thanks for asking it. I think the desired degree of cleanup depends on the circumstances. If you are out in the forrest and pick up a stone to use as a tool it is probably ok to just drop it when you are done. But, if you are in somebody’s kitchen and use a knife you might want to put it in the sink when you are done, or clean it and put it back in the drawer, or leave it on the table if you think you will be using it soon again. As you noted, the basic backward chained design is very result oriented and no cleanup is included out of the box (kind of like my teenage kids), so the proper degree of cleanup has to be added explicitly as a goal of its own when you want it. Either “the kitchen is spick and span”, if you want your agent to also clean up after other people, or “all items I’m not using are back where they belong” if you don’t care about the mess caused by others. In the example you mention with the key, it is probably good to have a goal such as “all my items are in their proper place when I’m not using them”. This would make the agent put the key back in the pocket after trying to open the lock.

[@AbhishekSharma-fp9db]

@@petterogren7535 Thanks for the quick response! Doesn't this break the modularity principal? Some other goal (BT) will have to worry about cleaning up some other BT mess? The clean up BT will have to make assumptions about the mess that could be caused by interrupted BT.

[@petterogren7535]

@@AbhishekSharma-fp9db I see what you mean, and one again, this question is important. I'd say that "cleaning up a mess" is a much more complex concept than one might first think. How should the agent know that in the forrest you are free to pick up a rock, and then drop it on the ground in a different place, while in a kitchen, putting a knife that you used on the floor is not ok. Any goal driven agent only cares about its goals. If preserving some kind of order in its environment is not a goal, it will not worry about it. So if we want order among items, we need to add it explicitly as a goal. As humans, we find it natural to instruct someone to "put the tools back when you used them", but what we really mean when we say that is that "it is important that all tools are in the drawers when you are not using them". So, I understand your point about decreasing modularity, but I believe that it makes sense to add as a goal. In this way you also get the benefit of an agent that cleans up not only after itself, but also after others, when needed.

[@balookli3374]

Thanks for these videos! I'm trying to build a behavior tree using the python package py_trees. There isn't a condition node in py_trees as the yellow circles used in the video here so I wonder if there's a combination of parallel composites and perhaps the blackboard (shared variable space between behaviors) that achieves the same thing..?

[@petterogren7535]

Thanks for the question. Technically a Condition is a special case of an Action. But I think drawing them differently improves readability. I believe that in py_trees the "Behaviours" are used as both actions and conditions. The website (py-trees.readthedocs.io/en/devel/behaviours.html) says "A Behaviour is the smallest element in a behaviour tree, i.e. it is the leaf. Behaviours are usually representative of either a check (am I hungry?), or an action (buy some chocolate cookies)." /Petter

[@andrewallbright]

I'm having trouble with this technique... (1) I'm confused if this is a behavior tree way of achieving what you can find in a goal oriented action planner (GOAP) or not. (2) What exactly is the "tree of this form" referring to? Is every fallback node whose left most node is a condition and whose subsequent child is a sequence with a left most condition "a tree of this form"?

[@petterogren7535]

Hi Andrew, thanks for your questions. (1)Short answer: yes. Longer answer: By using the backchaining idea (that is the core part of many planning algorithms) we get a BT that does what a planned solution would do. But this solution is also reactive. So if the any unexpected changes in the state occurs, the BT will execute the proper action. Either jumping back and re-executing some actions if needed, or jumping ahead and skipping some actions if the unexpected changes allows this. (2) "Tree of this form" refers to a BT of the following form: "Fallback(sub_goal_condition, Sequence(precondition, action_that_achieves_sub_goal), ...)", one example of this can be seen at 5:42, with "Fallback(door_open, Sequence(has_key, open_door_with_key), ...)". The backchaining BT design is then to start with a sequence of top level goal conditions, and then recursively replacing a condition with a BT "of this form" that first checks if the condition is already achieved, and if not takes action to achieve it, as illustrated at 8:48.

[@andrewallbright]

@@petterogren7535 I appreciate your response. I'll need to think on this more to get it, I think. Thanks so much for your content!

[@iNomanWaleed]

Hey Sir @Petter How to connect with you?

[@gmatheus10]

I like the material, but you speak too low