Discussing Behavior Trees

[davebaol]

I've opened this to discuss behavior trees API enhancements.

@implicit-invocation Resuming discussion https://github.com/libgdx/gdx-ai/pull/4#issuecomment-56509640 ... Not sure why you don't like the XML format, but I think that it has some advantages:

• comments are supported which can be really useful
• it's more powerful than json or any inline tab-based format.
• being it a standard format, external tools like editors (written in any language) can easily read/write a behavior tree.

So I'm playing with the XML format just to see what can be done. Currently I can successfully load a behavior tree from this file:

<BehaviorTree>
  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.BarkTask" as="Bark"/>
  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.CareTask" as="Care"/>
  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.MarkTask" as="Mark"/>
  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.RestTask" as="Rest"/>
  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.WalkTask" as="Walk"/>
  <Root>
    <Selector>
      <Parallel>
        <com.badlogic.gdx.ai.tests.btree.dogtasks.CareTask urgentProb="0.8"/>
        <AlwaysFail>
          <com.badlogic.gdx.ai.tests.btree.dogtasks.RestTask/>
        </AlwaysFail>
      </Parallel>
      <Sequence>
        <Bark times="3"/>
        <Walk/>
        <Bark/> <!-- times defaults to 1, see BarkTask source code -->
        <com.badlogic.gdx.ai.tests.btree.dogtasks.MarkTask/>
      </Sequence>
    </Selector>
  </Root>
</BehaviorTree>

I added the "Import" tag to improve readability. It allows you to use the given alias in place of the fully qualified class name of the task. Actually Selector, Parallel, etc.. are predefined imports. Also, the "as" attribute is optional, meaning that the simple class name is used as the alias, i.e.

  <Import task="com.badlogic.gdx.ai.tests.btree.dogtasks.BarkTask"/>

creates the task alias "BarkTask". Also, I added task parameters, see urgentProb in CareTask and times in BarkTask. The attribute value is parsed according to the type of the corresponding field of the task class. For example, urgentProb is a float and times is an int. Supported types are: int, Integer, float, Float, boolean, Boolean, long, Long, double, Double, short, Short, char, Character, byte, Byte, and String.

Of course, we can maintain both formalisms as long as they have the same structural features. I mean, unlike task parameters, imports are just a syntactic sugar so they are not mandatory for the inline tab-based formalism.

I think we can use a "btree" branch in order to experiment with BT improvements while keeping the master branch clean.

[davebaol]

Ok pushed the btree branch.

I'm not fully convinced by the METADATA static field, but it's what I've come up with so far. METADATA contains task information for loaders and editors such as the minimum/maximum number of children and the set of attributes. When writing a new task the developer must declare a METADATA field only if the min/max number of children or the attributes change with respect to the task superclass. Having to add/remove attributes manually in METADATA may look annoying but gives you total control, preventing the user (the one that is creating the tree) from changing task fields that should not even be accessed.

[davebaol]

Now all branch nodes have an optional attribute "deterministic" which defaults to true. I'm not sure it makes sense for Parallel. Should we remove it from Parallel METADATA? We can do it like that:

// Copy BranchNode.METADATA, add no attribute and remove deterministic attribute
public static final Metadata METADATA = new Metadata(BranchNode.METADATA, new String[]{}, "deterministic");

or like that:

// Create a new METADATA with no limit on the number of children and with no attributes
public static final Metadata METADATA = new Metadata(-1);

[implicit-invocation]

If we are thinking about making an editor, XML will be fine with me. I just don't want anyone to write XML by hand :smile: If XML is generated by tools and we just have to edit some numbers or move some lines manually, I think everyone will be happy.

If we are using an XML syntax here, I don't think we should do

<com.badlogic.gdx.ai.tests.btree.dogtasks.RestTask />

or even

<bark />

How can we validate our XML then? It should be

<task name="bark" />
<task class="com.badlogic.gdx.ai.tests.btree.dogtasks.RestTask" />

for attribute

<repeat>
  <param name="time" value="3" />
  <tasks>
      <task name="bark" />
  </tasks>
</repeat>

With XML, everything is string, so how we can tell it's a "3" string and not a number with value of 3. Writing something like

<param name="title" value="3" type="string" />

is ugly :smile: We can do it more easily with JSON or our own format because not every value must be in quotes. And if not for formalization and validation, I don't think XML is the best choice here.

About METADATA, I'm not sure what you are using it for here and why it is static. If we need some configurations for all the sequence or parallel nodes, we can put it in the tree instance or in your BehaviorTreeLibrary static members. The configurations can be loaded from a file by methods. If we need parameters for 1 node, a map is enough For example, we have

<param name="time" value="3" type="int" />

The node will have a parameter map and set get method

private Map<String, Object> paramters;
public <E> void set(String name, E value, Class<E> type);
public <E> E get(String name, Class<E> type);
// some shortcut methods
public void setInt(String name, int value);
public int getInt(String name);
...

Parser will call setInt("time", 3) after create the node. The node will refer to the parameter getInt("time")

The time this node will be repeated is init param but the time the node did run is state. I think state can be stored in a map like that too, a different map, called data maybe. The get, set for parameters will be called setParam and getParam then. And the get, set for data will be call setData and getData. It will make the code harder to read but will make the serialization easier (I want lag compensation on a network use case too).

When we clone the tree, we clone only the params, not the data. When we store the tree state (to rewind in lag compensation use case) we store both params and data.

[davebaol]

@implicit-invocation

How can we validate our XML then?

Yes, we miss XML validation (which is always optional, anyways) but we can still verify if the document is well-formed. Despite being less formal, using class name or alias as a tag and parameters as attributes is less verbose and more readable. Even Ant uses the same technique.

With XML, everything is string, so how we can tell it's a "3" string and not a number with value of 3. Writing something like <param name="title" value="3" type="string" /> is ugly :smile:

Yep, it's really terrible :) Anyways, in "3" quotes are part of the XML syntax, so it's just 3. The actual type can be inferred from the class or the primitive type of the corresponding field/setter, just like it happens with JSON.

We can do it more easily with JSON or our own format because not every value must be in quotes. And if not for formalization and validation, I don't think XML is the best choice here.

I think that the problem with JSON, is that you have to give everything a name and you're forced to use arrays. For example in

{task:selector, deterministic:false, children: [
  {task:com.badlogic.gdx.ai.tests.btree.dogtasks.BarkTask},
  {task:com.badlogic.gdx.ai.tests.btree.dogtasks.CareTask}
]}

you must create an array named children and all those [{...}, ..., {..}] are more error prone and less readable IMO. With XML, children are simply nested tags, which looks to me like a more natural representation for a tree structure.

"Unfortunately" I have a meeting now. I'm going to reply the other stuff later.

Anyways, at the moment my major intent is to find the best compromise among simplicity, usability and performance for such a transitory where users have to write trees by hand since no editor is (yet) available.

And thanks for your valuable considerations, really. :) Later

[implicit-invocation]

The actual type can be inferred from the class or the primitive type of the corresponding field/setter, just like it happens with JSON.

With JSON, {"key": "value"} means string, {"key": true} means boolean and {"key": 3} means number. To do it with XML, it will become <sequence title="\"some random title\""> and even uglier.

I agree with you about the array notation being error prone and less readable. But it isn't true that you have to give everything a name

{
  "import": {
    "bark": "com.badlogic.gdx.ai.tests.btree.dogtasks.BarkTask",
    "care": "com.badlogic.gdx.ai.tests.btree.dogtasks.CareTask"
  },
  "root": {
    "sequence": {
      "title": "test",
      "children": [
        "bark",
        "com.badlogic.gdx.ai.tests.btree.dogtasks.WalkTask",
        {
          "repeat": {
            "time": 3,
            "children": [
              "bark"
            ]
          }
        }
      ]
    }
  }
}

I still prefer something we can write by hands

import
  some_registered_task:"packageName.className"
root
  type:sequence
    task:fromClass className:"packageName.className"
    task:fromScript scriptFile:"script_file_path"
    type:limit count:3
      type:some_registered_task
    type:include file:"path_to_file" lazy:true

I think it is easy enough to read, to write a parser or even to export from tools.

[davebaol]

Well, yes I meant that with JSON you're forced to use an array when the order is relevant since properties are unordered. Also, I was assuming that the XML tree is backed up by the Java classes of the nodes at runtime, so we can use reflection to infer the actual type of the attributes. This is always true when you run the tree form inside your Java application, but you're right, it's no longer true for external tools that parse the XML without having node classes in the classpath or if they are written with any other non Java language. Good point! :+1:

Back to the inline format then! Maybe we might make it a bit simpler and less verbose. I mean, what's the point of all those "type:" and "task:" ? Couldn't it just be something as simple as

import
  care:"packageName.CareTask"
root
  sequence
    care urgentProb:0.8
    script file:"script_file_path"
    limit count:3
      packageName.BarkTask
    include file:"path_to_file" lazy:true

By the way, the "times" attribute in BarkTask was just an example. I know it's recommended to use a limit decorator for things like that. :)

[implicit-invocation]

I'm not sure about the "deterministic" attribute you use for the branch nodes. Sequences and selectors will always pick the next child to run until one child fail or succeed. So if the node list is ordered, they will always be deterministic. Are you talking about a RandomSelector? If it is a random selector, it will be non-deterministic by default, unless we choose a deterministic random algorithm.

[davebaol]

@implicit-invocation Did you look into the implementation? https://github.com/libgdx/gdx-ai/blob/btree/gdx-ai/src/com/badlogic/gdx/ai/btree/BranchNode.java#L56

If the branch is non-deterministic the actualTask is chosen randomly among the next children.

EDIT: Note that children are swapped.

[implicit-invocation]

I did look at the implementation. But I think it would be better if we make a RandomSelector and not make everything have a random behavior like that. A sequence that is not sequential is semantically wrong.

[davebaol]

Hmmm.... why? Suppose you want to burn something.

sequence deterministic:false
  task:GetMatches
  task:GetGasoline

The order you get matches and gasoline is irrelevant but you need both. Am I missing something?

[implicit-invocation]

Oh, I missed that case. But I'm more familiar with the concept provided by aigamedev.com where

a sequence respects its order, it implicitly expresses dependencies between its child behaviors.

I usually use sequence in cases that the entity checks for a condition before executing an action. (I use task for condition)

And in your case where the order is less relevant, I'm thinking of a Probability selector

Probability selectors pick one of their child nodes randomly based on the weights provided by the designer.

We can even rank the node for a soft order, GetMatches and GetGasoline will have a same weight then.

[davebaol]

Yeah the use of a deterministic sequence whose first child is a condition task in the most common case. However when the order is irrelevant and the children have equal probability a non deterministic sequence might come in handy. Also, the overhead for deterministic branches is just an "if" per child.

Anyways, in order to make the file format easier for both the parser and the user I'm thinking of something like that:

import care:"packageName.CareTask"
import bark:"packageName.BarkTask"
root
  sequence
    care urgentProb:0.8
    script file:"script_file_path"
    limit count:3
      bark
    include file:"path_to_file" lazy:true

This way all the lines of the file have the same format:

indent name attr1:val1 attr2:val2 ...

Currently I'm rewriting the parser with Ragel which is a bit hard to learn when you're new to it, but it's really cool because is very fast and most importantly is cross-platform, meaning that external non Java tools can easily use similar code to load behavior trees as long as Ragel supports that particular programming language.

[davebaol]

@implicit-invocation Ok just pushed the new parser written with Ragel. Lines in the file have the following syntax:

[[indent] [name [attr:value ...]] [comment]]

where:

• name is in the form of a Java fully qualified class name
• attr is in the form of Java identifier
• value must be a boolean, a number or a quoted string accepting JSON-like escape sequences
• comment starts with a # and extends up to the newline

Sample tree: https://github.com/libgdx/gdx-ai/blob/btree/tests/data/dog.tree

Currently METADATA is still used, but I'm open to use a different approach. :)

[implicit-invocation]

Wow, you are fast. I am also experimenting with something I have in mind (mostly stuffs related to the traversal). Will discuss with you about them soon.

[davebaol]

Eh I had just to learn how to use Ragel and add JSON-like values, the rest is a mix of your old parser and my xml parser. Looking forward to discussing your new stuff :)

[davebaol]

Added clone capability.

[davebaol]

Added behavior tree library, subtree reference nodes and tests.

@implicit-invocation I created two distinct reference nodes instead of one with a lazy parameter, because they extend different classes: Task for the eager reference and Decorator for the lazy reference. Of course they can be merged in one class with the lazy parameter by extending Node. I'm not sure it's worth though.

[JesseTG]

Ooh, Ragel looks fun to use. I should keep it in my back pocket.

[implicit-invocation]

@davebaol So you choose the name "Reference" instead of "Include", the java class name is not that important but I still think "include" or "import" should look more natural in the tree definition file. And why extending Task for eager reference? Decorator is fine for both eager and lazy reference to extend. You don't run the reference anyway. And code-wise there is almost no difference between a Task and a Node. And I still don't get why Metadata is static. You don't want every sequence to act the same way, do you?

[davebaol]

@implicit-invocation ok, it makes sense. Lazy and eager subtree inclusion is now implemented as a single decorator.

And I still don't get why Metadata is static. You don't want every sequence to act the same way, do you?

Yes, METADATA is static because contains no runtime information. Actually, it is only used by the parser to emit errors in case an attribute doesn't exist or the number of children in a node is wrong. For instance, most decorators must have exactly one child. However Include is an anomalous decorator because must have no children at all when you define the tree. If it's lazy it will have 1 child at runtime though. If it's eager will never run. So include's METADATA is new Metadata("subtree", "lazy") which says no children and two attributes.

[implicit-invocation]

Oh, I misunderstood it. So there will be no logic concerning the METADATA. METADATA is just... METADATA after all

[davebaol]

Yeah, METADATA contains the name of the attributes, not their value. So it's static final and conceptually immutable too (no setters, and its fields are package private). Unfortunately it can not be accessed by external tools, unless they are written in Java and have nodes in the classpath. Maybe we can export such information somehow for external tools, or use a completely different technique.

[davebaol]

@implicit-invocation Just pushed some javadoc, code clean up, and minor fixes. I'd like to release gdx-ai 1.4.0 on sunday (old releases were part of the libgdx project, so we have to start with 1.4.0 due to maven artifacts). I'm going to merge the btree branch before releasing. Please let me know if you want to add or change something before we release. :)

[Tom-Ski]

Last release for gdx-ai was 1.3.1, so you'd only need to go to 1.3.2.

[davebaol]

Yeah @Tom-Ski, but a lot of stuff has been added since 1.3.1, namely Steering Behaviors and Behavior Trees. So it will be 1.4.0 :)

[implicit-invocation]

@davebaol please go ahead, I don't have anything to add yet.

[davebaol]

@implicit-invocation Ok thanks, no hurry.

BTW, I'm thinking of renaming Node to Task which is the typical superclass name in all the API I've seen in the past. It makes sense because everything is a task in a behavior tree. Actually, the entire behavior tree can be seen as a task made of subtask. So I'm going to make the following renaming:

• Task -> LeafTask
• BranchNode -> BranchTask
• Node -> Task

Hope you don't mind :)

[implicit-invocation]

Well, I think renaming Node to Task is not a good idea. People who want to create their trees will only use Sequence, Parallel, Include... and extend Task, they will never touch Node or BrachNode. Our documentations can tell them: "extend Task, not Node and do not add child to Task, they are leaves". There is no point making people call something LeafTask when they never see BranchTask or any other kind of Task. And Node and Task will create the boundary between our internal implementation and the API.

[davebaol]

TBH I don't see the problem. Usually the one who creates a tree (not necessarily the developer) is used to think in term of actions and conditions which are the leaf tasks. The same is true for the developer. Task and LeafTask seem to me more natural names and most of the behavior tree literature calls them like that. Why should our API use a different terminology? It might be confusing for the user.

[davebaol]

Also, I want to to add '?' as a legal char for attribute names (see the 1st import below) and task aliases. This gives the user the opportunity to improve readability by making explicit when a leaf task is a condition or an action.

import doorLocked?:"packageName.DoorLockedCondition"
import openDoor:"packageName.OpenDoorAction"
import enterRoom:"packageName.EnterRoomAction"

root
  selector
    sequence
      doorLocked?
      openDoor
      enterRoom
    enterRoom