Behavior tree

From OpenCog
Jump to: navigation, search

This page describes simple prototype sketch for implementing behavior trees (such as Owyl behavior trees) in OpenCog. This is needed for the New Embodiment Module, March 2015.

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, JoinLink 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 calulus or an event calculus.

Ben has ideas for a probilistic version.