Behavior Trees

xholonWorkbook.xml

<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Tue Oct 22 2019 13:52:04 GMT-0400 (Eastern Daylight Time)-->
<XholonWorkbook>

<Notes><![CDATA[
Xholon
------
Title: Behavior Trees
Description: 
Url: http://www.primordion.com/Xholon/gwt/
InternalName: 24fbc868269ea55b784fde196b209e18
Keywords: 

My Notes
--------
October 14, 2019
I have just discovered Behavior Trees.
They should fit very nicely into Xholon.
I will try 3 different implementations:
 1. using Xholon nodes and subtree nodes
    - with algorithms from ref 4 and ref 2, and maybe also from other references
    - it could be a Mechanism with multiple node types; similar to how I've implemented state machines and petri nets
 2. JavaScript library (ref 9)
 3. JavaScript library (ref 11)

To install, use, test behavior3js
---------------------------------
cd ~/nodespace
npm install behavior3js
 installs behavior3js to ~/nodespace/node_modules
sudo npm install --global gulp-cli
cd node_modules/behavior3js
npm install --save-dev gulp
gulp --version
  CLI version: 2.2.0
  Local version: 3.9.1
gulp build
- I cannot get it to work

To install and run
------------------
127.0.0.1:8888/Xholon.html?app=Behavior+Trees&src=lstr&gui=clsc&jslib=behaviortree-min

References
----------
(1) https://arxiv.org/pdf/1803.09099.pdf
    A Resourceful Reframing of Behavior Trees
    CHRIS MARTENS,North Carolina State University
    ERIC BUTLER,University of Washington
    JOSEPH C. OSBORN,University of California, Santa Cruz
    2016, 2018
    We present an alternative formulation of behavior trees through a language design perspective, giving a formal operational semantics, type system, and corresponding implementation.
    We express speci€cations for atomic behaviors as linear logic formulas describing how they transform the environment, and our typesystem uses linear sequent calculus to derive
    a compositional type assignment to behavior tree expressions.Œese types expose the conditions required for behaviors to succeed and allow abstraction over parameters tobehaviors,
    enabling the development of behavior “building blocks” amenable to compositional reasoning and reuse.

(2) http://www.csc.kth.se/~miccol/Michele_Colledanchise/Publications_files/2013_ICRA_mcko.pdf
    Towards  a  Unified  Behavior  Trees  Framework  for  Robot  Control
    Alejandro Marzinotto, Michele Colledanchise, Christian Smith, and Petter ̈Ogren

(3) https://en.wikipedia.org/wiki/Behavior_tree_(artificial_intelligence,_robotics_and_control)
    A Behavior Tree is a mathematical model of plan execution used in computer science, robotics, control systems and video games.
    They describe switchings between a finite set of tasks in a modular fashion.
    Their strength comes from their ability to create very complex tasks composed of simple tasks, without worrying how the simple tasks are implemented.
    Behavior trees present some similarities to hierarchical state machines with the key difference that the main building block of a behavior is a task rather than a state.
    Its ease of human understanding make behavior trees less error prone and very popular in the game developer community.
    Behavior trees have been shown to generalize several other control architectures.

(4) https://arxiv.org/pdf/1709.00084.pdf
    Michele Colledanchise and Petter ̈Ogren
    Behavior Trees in Robotics and AI - An Introduction
    2018
    this is a book, available from amazon as a hardcover

(5) https://www.pirobot.org/blog/0030/
    Behavior Trees: Simple yet Powerful AI for your Robot

(6) https://outforafight.wordpress.com/2014/07/15/behaviour-behavior-trees-for-ai-dudes-part-1/
    Behavior trees for AI: How they work
    Posted on July 15, 2014
    this is a good introduction

(7) https://github.com/gaia-ucm/jbt
    Java Behaviour Trees is a Java framework for easily building and running generic behaviour trees.
    Here, "behaviour tree" refers to the technique used to control the behaviour of characters in video games.
    latest update is 7 years ago

(8) github search: "behavior tree"


(9) https://github.com/behavior3/behavior3js
    Behavior3 client library for Javascript (Behavior Trees for Javascript)
    latest is 2 years ago
    Main features:
    * Based on the work of (Marzinotto et al., 2014), in which they propose a formal, consistent and general definition of Behavior Trees;
    * Optimized to control multiple agents: you can use a single behavior tree instance to handle hundreds of agents;
    * It was designed to load and save trees in a JSON format, in order to use, edit and test it in multiple environments, tools and languages;
    * A cool visual editor which you can access online;
    * Several composite, decorator and action nodes available within the library. You still can define your own nodes, including composites and decorators;
    * Completely free, the core module and the visual editor are all published under the MIT License, which means that you can use them for your open source and commercial projects;
    * Lightweight!

(10) https://github.com/behavior3/behavior3editor
    online visual editor for Behavior3 (Behavior Trees Visual Editor)

(11) https://github.com/Calamari/BehaviorTree.js
    An JavaScript implementation of Behavior Trees. 

]]></Notes> 

<_-.XholonClass>
  <PhysicalSystem/>
  <TestAgent/>
  
  <Building/>
  <Room/>
  <Door/>
  
</_-.XholonClass>

<xholonClassDetails>
  <Avatar><Color>indigo</Color></Avatar>
</xholonClassDetails>

<PhysicalSystem>
  
  <!-- initial test -->
  <TestAgent roleName="Mercury">
    <RootBT doact="false">
      <SequenceBT>
        <ActionBT roleName="One"><![CDATA[
const BT_STATUS_NOT_TICKED = "N";
const BT_STATUS_FAILURE = "F";
const BT_STATUS_SUCCESS = "S";
const BT_STATUS_RUNNING = "R";
const agentRoleNameArr = ["M", "Merc", "Ἑρμής", "Mercury"];

var me, arrix, beh = {
postConfigure: function() {
  me = this.cnode;
  arrix = 0;
},
act: function() {
  me.println(this.toString());
},
tick: function(obj) {
  //me.println("ticking3: " + obj);
  me.println(me.name() + " " + this["agent"].name() + " " + this["agent"].color());
  this["agent"].role(agentRoleNameArr[arrix]);
  arrix++;
  if (arrix == agentRoleNameArr.length) {arrix = 0;}
  return BT_STATUS_SUCCESS;
},
toString: function() {
  return "testing: 789";
}
}
//# sourceURL=ActionBt1.js
        ]]></ActionBT>
        <ActionBT roleName="Two"><![CDATA[
const BT_STATUS_NOT_TICKED = "N";
const BT_STATUS_FAILURE = "F";
const BT_STATUS_SUCCESS = "S";
const BT_STATUS_RUNNING = "R";
const agentColorArr = ["red", "green", "blue"];

var me, arrix, beh = {
postConfigure: function() {
  me = this.cnode;
  arrix = 0;
},
tick: function(obj) {
  //me.println("ticking4: " + obj);
  me.println(me.name());
  this["agent"].color(agentColorArr[arrix]);
  arrix++;
  if (arrix == agentColorArr.length) {arrix = 0;}
  return BT_STATUS_SUCCESS;
}
}
//# sourceURL=ActionBt2.js
        ]]></ActionBT>
        <ConditionBT roleName="Three"><![CDATA[
const BT_STATUS_NOT_TICKED = "N";
const BT_STATUS_FAILURE = "F";
const BT_STATUS_SUCCESS = "S";

var me, beh = {
postConfigure: function() {
  me = this.cnode;
},
tick: function(obj) {
  //me.println("ticking4: " + obj);
  me.println(me.name());
  return BT_STATUS_SUCCESS;
}
}
//# sourceURL=ConditionBT1.js
        ]]></ConditionBT>
      </SequenceBT>
    </RootBT>
  </TestAgent>
  
  <TestAgent roleName="Venus">
    <RootBT>
      <!-- test of RootBT with no child node  OK -->
    </RootBT>
  </TestAgent>
  
  <!-- test a sequence of empty nodes of all BT types -->
  <TestAgent roleName="Earth">
    <RootBT>
      <SequenceBT>
        <SequenceBT/>
        <SelectorBT/>
        <ParallelBT/>
        <InverterBT/>
        <ActionBT/> <!-- an Action without a beh will be automatically removed from the tree -->
        <ConditionBT/> <!-- a Condition without a beh will be automatically removed from the tree -->
        <ActionBT>this.println("This Action node has no beh, and will be automatically removed from the tree.");</ActionBT>
        <ConditionBT>this.println("This Condition node has no beh, and will be automatically removed from the tree.");</ConditionBT>
        <ActionBT>var beh = {}</ActionBT>
        <ConditionBT>var beh = {}</ConditionBT>
        <SuccessBT/>
        <FailureBT/>
        <RunningBT/>
      </SequenceBT>
    </RootBT>
  </TestAgent>
  
  <!-- test moving an Avatar using a BehaviorTree -->
  <Avatar roleName="Spaceship"><BehaviorsST>
    <RootBT>
      <SequenceBT>
        <ActionBT><![CDATA[
var currentTS, beh = {
postConfigure: function() {
  this["agent"].action("param subtrees true BehaviorsST;param loop true;who;where;");
  currentTS = $wnd.xh.param("TimeStep");
},
tick: function(obj) {
  if (this["agent"].parent().xhc().name() == "PhysicalSystem") {
    this["agent"].action("enter Venus;");
  }
  if (currentTS == $wnd.xh.param("TimeStep")) {
    // do nothing
    return "R";
  }
  else {
    this["agent"].action("go next;who;where;");
    currentTS = $wnd.xh.param("TimeStep");
    return "S";
  }
}
}
//# sourceURL=ActionBt101.js
        ]]></ActionBT>
      </SequenceBT>
    </RootBT>
  </BehaviorsST></Avatar>
  
  <TestAgent roleName="Mars"/>
  <TestAgent roleName="Jupiter"/>
  <TestAgent roleName="Saturn"/>
  <TestAgent roleName="Uranus"/>
  <TestAgent roleName="Neptune"/>
  <TestAgent roleName="Pluto"/>
  
  <!-- example from ref 6 -->
  <Building>
    <Room>
      <TestAgent roleName="Luna">
        <RootBT>
          <SequenceBT>
            <!-- the way I have implemented these 4 actions is quite tentative -->
            <ActionBT roleName="Walk to Door"><![CDATA[
const MAX_STEPS_TO_DOOR = 6;
var stepCounter, beh = {
postConfigure: function() {
  stepCounter = MAX_STEPS_TO_DOOR; // number of steps required to walk to door
},
tick: function(obj) {
  this.agent.println("walking to door ...");
  if (stepCounter <= 0) {
    return "S";
  }
  else {
    stepCounter--;
    return "R";
  }
}
}
//# sourceURL=WalktoDoor.js
            ]]></ActionBT>
            <ActionBT roleName="Open Door"><![CDATA[
var beh = {
postConfigure: function() {
},
tick: function(obj) {
  this.agent.println("opening door ...");
  var door = this.agent.xpath("../../Door");
  door.state = "open";
  return "S";
}
}
//# sourceURL=OpenDoor.js
            ]]></ActionBT>
            <ActionBT roleName="Walk through Door"><![CDATA[
var beh = {
postConfigure: function() {
},
tick: function(obj) {
  this.agent.println("walking through door ...");
  var door = this.agent.parent().next();
  if ((door != null) && (door.xhc().name() == "Door")) {
    this.agent.println("door: " + door);
    var nextRoom = door.next();
    this.agent.println("nextRoom: " + nextRoom);
    nextRoom.append(this.agent.remove());
  }
  return "S";
}
}
//# sourceURL=WalkthroughDoor.js
            ]]></ActionBT>
            <ActionBT roleName="Close Door"><![CDATA[
var beh = {
postConfigure: function() {
},
tick: function(obj) {
  this.agent.println("closing door ...");
  this.agent.println("agent is in " + this.agent.parent());
  var door = this.agent.xpath("../../Door");
  door.state = "closed";
  return "S";
}
}
//# sourceURL=CloseDoor.js
            ]]></ActionBT>
          </SequenceBT>
        </RootBT>
      </TestAgent>
    </Room>
    <Door state="closed"/>
    <Room/>
  </Building>
  
  <Animate
 selection="#xhgraph"
 xpathNOT="PhysicalSystem/TestAgent" xpath="PhysicalSystem"
 duration="2"
 cssStyle=".d3cpnode circle {stroke-width: 0.5px;} .d3cpleaf circle {stroke-width: 0px;}"
 efParams="{
 &quot;selection&quot;:&quot;#xhgraph&quot;,
 &quot;sort&quot;:&quot;disable&quot;,
 &quot;width&quot;:800,
 &quot;height&quot;:800,
 &quot;mode&quot;:&quot;tween&quot;,
 &quot;labelContainers&quot;:true,
 &quot;includeId&quot;:true,
 &quot;shape&quot;:&quot;circle&quot;,
 &quot;useSymbols&quot;:true,
 &quot;maxChars&quot;:1,
 &quot;togglePortColors&quot;:false,
 &quot;supportTouch&quot;:false,
 &quot;supportClick&quot;:false,
 &quot;supportContextmenu&quot;:false,
 &quot;supportDblclick&quot;:false,
 &quot;fontSizeMultiplier&quot;:1.75
 }"/>
  <script>
    // move the Animate node out of the way
    this.parent().parent().append(this.prev().remove());
  </script>
  
</PhysicalSystem>

<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<svg width="100" height="50" xmlns="http://www.w3.org/2000/svg">
  <g>
    <title>TestAgent</title>
    <rect id="PhysicalSystem/TestAgent" fill="#98FB98" height="50" width="50" x="25" y="0"/>
    <g>
      <title>RootBT</title>
      <rect id="PhysicalSystem/TestAgent/RootBT" fill="#6AB06A" height="50" width="10" x="80" y="0"/>
    </g>
  </g>
</svg>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>

</XholonWorkbook>