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.
- 15.07.20 - v0.4.0 - introduces the
:choose-eachnode, implements 'node memory' for stateful node types, some expansion and tidying of documentation
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.
[: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.
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:
-
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.
-
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})
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.
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...))
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.
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.
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.
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.
:p - probability of ticking any child (0…1)
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.
:count - number of times the loop should execute
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.
:count - number of times the loop should execute
The :parallel node executes all of its children.
: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
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.
:p - probability
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.
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.
: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.
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.
The :always node expects one child that it ticks and then suceeds regardless of
whether the child succeeds.
The :never node expects one child that it ticks and then fails regardless of
whether the child fails.
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.
The :weighted-choice node randomly selects a child to tick based on some weighting algorithm.
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.
(require '[aido.core :as aido]
[aido.compile :as ac])
(let [tree (ac/compile ...)]
(aido/run-tick {} tree))
Copyright 2017-2018 Matthew Mower self@mattmower.com