Behavior tree (2015 Archive)

This page provides a sketch of the behavior tree implementation that was created to drive the Hanson Robotics Eva robot, in late-2014 to early-2015 timeframe. It was a part of the 2015 embodiment system design. It was used directly for several years to drive the robot demos, and has since morphed to provide some of the lower-level infrastructure for ghost. Thus, some (much?) of what is sketched here remains technically valid; it just no longer provides the top-level control for the robot.

The development of the behavior tree was a major spur in clarifying and solidifying the core ideas behind Atomese. However, the actual implementation proved too difficult for any except the most senior programmers to understand. To add injury to insult, it turned out that the perception subsystem was far too primitive for the behavior scripts: the robot was very nearly blind, and more or less totally deaf, and so the behavior scripts were reacting to low-quality, low-bit-rate, almost-white-noise sensory data. In this situation, scripting proved to be not a very good approach. Despite this, the ghost scripting system was created, to bring scripting usability to a new level, and meet the operational demands of a celebrity robot. As of 2018, ghost continues to use the control and sequencing ideas presented here, at the lower levels of the system.

Motivation

• A good-quality behavior tree implementation could work to replace many of the troublesome spots in embodiment...

• A simple set of clearly defined primitives can be easily translated into equivalent combo nodes, and so learning algorithms, such as MOSES, can train and discover new, better behavior trees.

• A simple set of clearly defined primitives would also allow a planning module to express plans in terms of these primitives (i.e. outputting these primitives), which are then used to drive performances of the plan. One could loosely say that this is a high-level "motor control langauge".

• Many robot performances need to be scripted. The behavior tree provides a "scripting language" (now called "atomese") that can work consistently with other parts of OpenCog.

Overview

Background reading can be found here: Behavior trees - Wikipedia and Popular approaches to behavior tree design - AIGameDev.

Conceptually there are four basic link types needed to define a behavior tree: sequence, random-choice, and repeat-forever.

• The sequence link executes an ordered series of actions. Execution stops with the first action that returns false; else the sequence continues. Implemented with the SequentialAndLink.

• The fallback link executes an ordered series of actions. Execution stops with the first action that returns true. In terms of boolean logic, this is just (NotLink (SequentialAndLink (NotLink ...))) of the above; however, as a conceptual device, it is very convenient to handle this distinctly, rather than mentally juggling NotLinks in one's head. Implemented by SequentialOrLink.

• The RandomChoiceLink randomly selects one of the N possible cases, and runs it.

• The repeat-forever link repeats an action forever (halting only when that action returns 'false'). Currently, this is implemented using tail recursion; i.e. the sequence can call itself; a new link type is not needed for this.

Mapping these to OpenCog links is fairly 'obvious', except for misc implementation issues. So for example:

   BindLink
       VariableNode $X
       ImplicationLink
           SequentialAndLink
               EvaluationLink
                   GroundedPredicateNode "scm: find"
                   VariableNode $X
               EvaluationLink
                   GroundedPredicateNode "scm: shoot"
                   VariableNode $X
           EvaluationLink
               PredicateNode "did get shot"
               VariableNode $X

which runs a sequence of EvaluationLink's until one of them returns false, thus terminating the sequence. If all of them return true, then the pattern is considered to be matched, and the implication consequent is returned by the pattern matcher.

So for example, consider Elmer Fudd in Duck Season, Rabbit Season. The atomspace contains (ConceptNode "Elmer Fudd") (ConceptNode "Bugs Bunny") (ConceptNode "Daffy Duck"). The function find is defined as (define (find atom) (if (equal? atom (ConceptNode "Daffy Duck")) (stv 1 1) (stv 0 1))) That is, if 'atom' is Daffy Duck, then it returns TrueTV, else it returns FalseTV. When the pattern matcher runs, then, if $X get bound to (ConceptNode "Bugs Bunny"), then find returns FalseTV, and thus "shoot" never happens. But if $X gets bound to (ConceptNode "Daffy Duck"), then find returns TrueTV, causing the pattern matcher to proceed onward to the second clause, "shoot". If this evaluates to TrueTV as well, then the whole pattern is considered to be matched, and the consequent of the ImplicationLink is instantiated in the atomspace (automatically, by the pattern matcher).

The above works, today, in the pattern matcher. See, for example, the SequntialAnd unit test. A More complex example is here: GreaterThan unit test, which performs calculations of all sorts during the pattern match.

Performance scripting, parallel actions, sync points

Some tasks requires multiple actions to be carried out in parallel, and synced up at various points in time. For example, consider the act of "juggling": two hands and arms, one of which is holding an object that must be passed to the other arm. Both arms must be moving at once, and there is one critical time-window, the hand-off window, when the two movements must be precisely coordinated.

There are low-level atoms for creating and working with threads: ParallelLink, ThreadJoinLink and SleepLink.

For high-level synchronization, see Action orchestrator.

Mapping to combo

In order to allow MOSES to train up new behavior trees, these nodes need to be mapped to combo.

Currently combo implementes sequential_and, sequential_or, as well as sequential_exec (which executes no matter what).

Extensions, Generalizations

A fuller, more complete system might make more explicit reference to fluents, and thus might look more like a situation calculus or an event calculus.

Ben has ideas for a probabilistic version.

The proper implementation requires "real-world understanding", which can be based on creating models of the real world, and then analyzing what is happening in the real world by analyzing the internal model of it. A prototype of world-model system can be found here, in github. The architecture of the world-model system is described in this PDF.