Behavior Trees with Automated Planning Capability | by Debby Nirwan | Dec, 2020
Now we can see that the Trees became more complex even for this rather simple system if we have multiple methods that we want to choose from to achieve our task.
Here are the full behavior trees:
If you replace each abstract action with the trees we designed above, you can see that they become quite complex. The trees would become enormously complex in the systems that have lots of behaviors and methods to choose from.
To simplify the trees — to only add nodes that will be used — which would help us greatly in analyzing and debugging the issues that we may encounter, we can incorporate automated planning into behavior trees — the topic that we have been discussing in all previous posts. We look at the details and implement them on Pacman in the sections below.
In a paper titled “Towards Blended Reactive Planning and Acting using Behavior Trees”, Michele, Diogo, and Petter show how a planning algorithm can be used to automatically create and update a Behavior Tree.
The planning is based on the idea of backward chaining, that is we work backward from the goal to create our plans. We set the goal as preconditions and iteratively run the behavior tree and expand the tree when preconditions of a branch return a failure status.
Expanding the tree means replacing the failed condition node with action node(s) and their condition node(s), as depicted in the illustration below.
Expanding Tree with Behavior Trees
In this article based on the idea published in the paper, we use a modified version of the algorithm, instead of following the pattern of adding fallback, effect condition, sequence, preconditions, and actions nodes, we make it more flexible by preparing a new behavior tree in any patterns and any sizes that we want as shown in the picture below.
Action Templates vs. Refinement Methods
Another difference that we make is that we use Refinement Methods instead of Action Templates to help our planning process.
Action Templates are used in classical planning approaches where the planner searches the state space to synthesize a plan — a sequence of actions.
Refinement Methods are commonly used in HTN (Hierarchical Task Networks) Planning where a Task — an abstract action, may have multiple methods that can be used to achieve it.
The primary advantage of using Refinement Methods is the speed of planning because by specifying which methods can be used to achieve a task, we basically limit the options in the search algorithm’s search space.
Now, let’s see the representation of our methods.
An example of a method is shown above, it is described as follows:
- The task name is for us to understand what the behavior tree is trying to achieve, in this case, “Eat Food”
- The preconditions are for us to check whether we can use this method in the current state of the world, and
- The effects are for us to check whether we can use this method to achieve the failing node in the existing behavior tree
We will look at the step-by-step example while implementing it on Pacman to see how it works in detail.
To illustrate how the algorithm works, we set a task for Pacman, which we call “Eat Food”. The goal for this task is “Food is not Available”, so we start with this node as our initial node.
To simplify the example, let’s assume that there is only one method available for the task “Eat food”. The method has one precondition, which is “Food is Available”. It has one effect, “Food is not Available”.
The associated tree is shown below:
When “FoodNotAvailable” is ticked it returns FAILURE status which will trigger the planning by searching through the collection of methods. Since we only have one applicable method, we’ll use it.
The initial tree which only contains a single node is expanded with the Behavior Tree for the Eat Food task.
Expanding the tree follows these steps:
- Create a Fallback Node — (i)
- Remove the failing node’s edge from its parent, if not a root node — (ii)
- Add the fallback node (i) as a child of the previous failing node’s parent — (iii)
- Add the failing node as (i)’s child
- Add the behavior tree as (i)’s child
Now after the first iteration of planning, we have our first version of the behavior tree.
When this behavior tree is ticked, it checks whether or not food is available, it then checks whether ghosts are far and execute the primitive actions sequentially, with memory:
- Find the closest food
- Plan a path there
- Execute planned path
This behavior tree is sufficient if there are no ghosts in Pacman’s world. Like in the Maze Problem below:
The Pacman execute primitive actions repeatedly until there are no more foods in its world.
As can be seen in the video, the simple behavior tree above is sufficient to solve this maze problem.
From the debugging console, we can see that the behavior tree is refined during runtime.
Expanding the Trees to Avoid Ghosts
This behavior tree won’t be sufficient if we added ghosts to the problem because when the ghosts are close, the GhostsAreFar condition node returns failure, which will trigger planning, again.
The following is the behavior tree for “Avoid Ghosts”:
The behavior tree is quite simple because the details are abstracted in the “Avoid Ghosts” primitive action.
The action will be executed only when there are active ghosts (not edible).
Combining this tree with the existing tree, we get:
With these combined behavior trees the Pacman can avoid ghosts to eat all foods in its world.
When it senses dangers, by detecting that ghosts are not far enough, it will check whether all of them are scared, if they are, Pacman won’t try to avoid them. If there are one or more active ghosts, Pacman tries to avoid them before trying to eat the remaining foods again.
This is the problem that we give to our agent, Pacman. It has to eat all four foods while avoiding ghosts. If on its way to eat food it eats a pill, it will ignore the ghosts as long as they are scared (they turn white when scared). We can see how the Pacman behaves in the video below.
We can see from the debugging console below how the Behavior Trees evolve during runtime.
There are two iterations before we get the final Behavior Trees that the Pacman can use in the video above.
To recap, we know that Behavior Tree is very powerful — hierarchical, modular, and reactive, which are the properties that we need for designing and implementing complex software systems.
In this post, we incorporate Automated Planning into Behavior Tree, to make it even more powerful for AI Agent’s Decision-making implementation.
As shown in Pacman’s Implementation, the Agent — Pacman is capable of building and updating Behavior Trees during run-time.
I hope this post gives some insights into what we can do with the Behavior Trees.
Read More …