aido

Introduction

aido stands for "AI do" and is a behaviour tree library suitable for implementing AI behaviours into games or applications. It could be used to model the behaviour of a game character or for a chabot to control the different responses it might employ.

I won't introduce behaviour trees here (see Google) beyond the basics. A behaviour tree is a tree-like data structure that specifies conditions we are interested in, actions that might be taken in responsento a given set of conditions, and some control flow mechanisms hat govern how the tree "makes decisions".

The heart of the control flow are behaviours such as sequence and selector and the notion that any element of the behaviour tree either results in success or failure. In particular, a sequence considers each of its children until one of them fails while a selector selects among its children until one succeeds. From such a simple premise quite complex behaviours can emerge.

Changelog

• 15.07.20 - v0.4.0 - introduces the :choose-each node, implements 'node memory' for stateful node types, some expansion and tidying of documentation

Specifying a tree

aido behaviour trees are implemented as Clojure data structures much in the style of Hiccup markup. As such they can be implemented in EDN notation.

The structure of a behaviour is

[:ns/keyword {options}* children*]

The core aido behaviours do not have a namespace prefix. I recommend namespacing domain specific behaviours.

The author has developed a convention that behaviours that form conditions should have a ? suffix, e.g. :time/after? while behaviours that represent actions with side-effects should have a ! suffix, e.g. :beverage/drink!.

A behaviour can have zero or more child behaviours. For example the [:selector] and [:sequence] behaviour expect at least one child although, in practice, both only make sense with multiple children.

Example

[:selector
  [:sequence
    [:time/after? {:t :teatime}]
    [:beverage/drink! {:beverage :tea}]
  [:actor/say! {:message "Oh, how I wish it was time for tea!"}]

In this example the :selector runs and ticks its first child, the :sequence. The :sequence ticks each of its children in turn. If :time/after? fails then the :sequence fails and the :selector goes on to tick :actor/say!. On the other hand if it succeeds then the :beverage/drink! child is ticked and, we assume, succeeds leading to the :sequence succeeding and the :selector succeeding without ticking the :actor/say! child.

Options

In the example above we see that :time/after?, :beverage/drink!, and :actor/say! all specify a map of options. These are assumed to be understood by the implementation of the behaviour in question. The :selector and :sequence do not have options although some of the built-in behaviours, e.g. loop do. In the case of :loop it has a count option to specify how many times the loop should iterate.

Sometimes it is advantageous to be able to specify options that are dynamic. aido offers two approaches:

1. Specify a function value, the syntax for which is:

   [:aido/fn function-id arg1 ... argN]

   e.g.

   [:loop {:count [:aido/fn rand 5]} ...]

The function-id should correspond to a function registered with the compiler (see below).

These functions are stand-alone and executed each time the beheaviour is ticked with the return value of the function being passed into the options maps.

2. Specify a database key-path

   [:aido/db path1 ... pathN]

   e.g.

   [:loop {:count [:aido/db :settings :loop-count]]}]

When the behaviour is ticked the appropriate value in the database will be passed in instead, this example would be conceptually equivalent to:

  [:loop {:count (get-in db [:settings :loop-count])}]

Functions are specified by passing an optional map to compile for example to satisfy the trees above you might use:

(aido.compile/compile tree {:rand rand-int})

Return values and flow control

Any behaviour is expected to return one of four values:

SUCCESS
FAILURE
RUNNING
ERROR

Most commonly behaviours are going to return SUCCESS or FAILURE.

ERROR is intended to be a severe form of FAILURE indicating a problem processing the behaviour tree. In the current version of aido the two are interchangable and ERROR is essentially unused.

RUNNING is intended to be an alternative to SUCCESS that indicates that a behaviour has neither succeeded nor failed but is in-progress. The main difference between SUCCESS and RUNNING is that a sequence will terminate with the RUNNING status if any of its children returns RUNNING.

Flow control is primilarily implemented in terms of :selector and :sequence behaviours.

Usage

In basic usage you must compile a behaviour tree using aido.compile/compile and then to run it use the aido.core/run-tick function. It is not recommend to call the tick function directly.

(ns 'aido.example
  (:require
    [aido.core :as ai]
    [aido.compile :as ac]))

(let [tree-fns {:coin-toss #(< (rand) 0.5)}
      tree     (ac/compile [:selector
                            [:sequence
                             [:true? {:expr [:aido/fn coin-toss]}]
                             [:heads!]
                             [:tails!]]]
                           tree-fns)
      db       {:foo :bar}]
  (let [{:keys [db* status]} (ai/run-tick db tree)]
    (if (= ai/SUCCESS status)
      ; extract from or use db*
      ; otherwise...))

Memory

Some nodes use a working memory that is reset between invocations of run-tick. Some stateful nodes such as :choose-each use storage that is persisted in the database between invocations of run-tick using a namespaced key. It is important to preserve this key if the database is modified between invocations of run-tick.

Built-ins

:selector

The :selector node executes its children in turn until one of them succeeds at which point execution stops and the :selector succeeds. If none of the children suceeds the :selector fails.

:sequence

The :sequence node executes its children in turn. If a child fails execution stops and the :sequence fails. If all of the children succeed the :sequence succeeds.

:selector-p

The :selector-p node iterates over its children in turn. For each child it does a probability check which, if it passes, selects that child to be ticked. The :selector-p succeeds or fails based on whether the child succeeds or fails. If the probability test does not pass for any child :selector-p fails.

Parameters

:p - probability of ticking any child (0…1)

:loop

The :loop node executes a single child a specified number of times. It is successful if it completes the specified iterations. If the child fails then the :loop fails.

Parameters

:count - number of times the loop should execute

:loop-until-success

The :loop-until-success node executes a child up to a specified number of times. If the child succeeds then the :loop-until-success succeeds. Otherwise, after the specified number of iterations the :loop-until-success fails.

Parameters

:count - number of times the loop should execute

:parallel

The :parallel node executes all of its children.

Parameters

:mode - When :mode is :success the :how-many parameter refers to how many children must succeed. When :mode is :failure the parameter refers to how many children must fail. :how-many - Number of children that must succeed or fail for the node to return success or failure

:randomly

The :randomly node operates in one of two modes depending on whether it has one or two children.

With one child :randomly evaluates the child if the p test passes and succeeds or fails if the child succeeds or fails. If the p test fails :randomly fails.

With two children :randomly evaluates the first child if the p test passes or the second child if it fails. :randomly succeeds or fails based on the selected child succeeding or failing.

Parameters

:p - probability

:choose

The :choose node takes one or more children and, when evaluated, randomly selects one child and ticks it. :choose succeeds or fails if the child succeeds or fails.

:choose-each

The :choose-each node takes one or more children and, when evaluated, randomly selects one child, ticks, and then marks it. Once a node has been marked it will not be choosen again. :choose-each succeeeds or fails if the child succeeds or fails. Subsequent ticks will always select from unmarked children.

Parameters

:repeat - if repeat is true, after all children have been ticked the node "refills" its children. If repeat is false after all children have been ticked the node will thereafter fail.

:invert

The :invert node takes a single child. When :invert is ticked it ticks its child and inverts the success or failure of the child. So if the child returns failure, invert returns success and vice verca.

:always

The :always node expects one child that it ticks and then suceeds regardless of whether the child succeeds.

:never

The :never node expects one child that it ticks and then fails regardless of whether the child fails.

Not yet implemented

The following are extensions of the choice idea that provide for non-uniform behaviour. They are given as separate nodes but, in practice, could be implemented by extending the existing :choice node type with additional options.

:weighted-choice

The :weighted-choice node randomly selects a child to tick based on some weighting algorithm.

Extending AIDO

Behaviours in AIDO are defined by creating new tick node types. A node type is defined by implementing 3 multimethods: tick, options, and children. Implementing tick is required, options and children offer default behaviour ('no options' and 'no children' respectively).

Let's define a new node type that is a variation on a selector but has a probability check to determine whether to try and tick child nodes. If the probability check fails it moves on to the next child. It succeeds if a child succeeds, otherwise fails.

It would look something like:

[:selector-p {:p 0.15} [child1] [child2] [child3]]

Here is how the node type would be defined:

(defmethod options :selector-p [& _] [:p])

(defmethod children :selector-p [& _] :some)

(defmethod tick :selector-p [db [node-type {:keys [p]} & children]
  ...)

See aido.core source for definitions of the built in node-types.

Usage

(require '[aido.core :as aido]
          [aido.compile :as ac])

(let [tree (ac/compile ...)]
  (aido/run-tick {} tree))

License

Copyright 2017-2018 Matthew Mower self@mattmower.com