Xbt

• Index

Contents

• Result Types
• State
• Evaluation and Compilation
• Node Types

Modules

• xbt.util
• xbt.path
• xbt.graph
• xbt

Module xbt

Extended Behavior Trees in Lua(JIT).

Info:

• Copyright: © 2015, Matthias Hölzl
• License: MIT, see the file LICENSE.md.
• Author: Matthias Hölzl

Result Types

inactive (reward)	Create an XBT result value for inactive nodes.
running (reward)	Create an XBT result value for running nodes.
succeeded (reward, continue)	Create an XBT result value for successful nodes.
failed (reward, reason)	Create an XBT result value for failed nodes.
is_result (value)	Check whether a value is a valid result.
is_inactive (result)	Check whether result has status "inactive".
is_running (result)	Check whether result has status "running".
is_succeeded (result)	Check whether result has status "succeeded".
is_failed (result)	Check whether result has status "failed".
is_done (result)	Check whether a node needs to be ticked again.
can_continue (result)	Check whether a node can be ticked again.

State

make_state (table)	Make a new state, or update a table to become a state.
set_local_data (node, path, state, data)	Store local data for a node instance.
local_data (node, path, state, default)	Retreive local data for a node instance.
set_result (node, path, state, result)	Set the evaluation result for a node.
result (node, path, state)	Get the previous evaluation result for a node.

Evaluation and Compilation

evaluators	Evaluators for ticking nodes.
compilers	Compilers for XBTs.
default_failure_reward	The default reward for failures.
tick (node, path, state)	Trigger evaluation of a node.
define_node_type (nt, arg_names, evaluator, compilers)	Define an evaluation function and a constructor for node type nt.
deactivate_descendants (node, path, state)	Set all descendants of a node to result status inactive.
deactivate_node (node, path, state, clear_data)	Deactivate a node.
reset_node (node, path, state, clear_data)	Reset a node to inactive status.
functions	A table mapping function names to functions.
define_function_name (name, fun)	Define a name for a function or action.
lookup_function (f)	Look up a function or action given its name.

Node Types

fun (fun, args)	Generate a function node.
action (fun, args)	Generate an action node.
bool (fun, args)	Generate a node that wraps a Boolean result.
seq (children)	Generate a sequence node.
all (children)	Generate an all-sequence node.
choice (children)	Generate a choice node.
xchoice (children)	Generate an external choice node.
epsilon_greedy_child_fun (node, path, state)	Epsilon-greedy child_fun for xchoice.

Result Types

A node can either be inactive, running, succeeded or failed. We define functions that return tables correspondig to these XBT result types. These tables share several attributes: The Boolean continue attribute indicates whether a process can continue. Inactive and running processes can always continue; failed processes never can. Succeeded processes may set this flag to true if, given more time, they can improve the value they have previously returned. Each XBT result carries a reward attribute that indicates the execution reward for the evaluation of the subtree that produces the result.

inactive (reward)

Create an XBT result value for inactive nodes.

Parameters:

• reward The reward for executing the node (including all descendants). Default is 0.

Returns:

An XBT result indicating that node is inactive.

running (reward)

Create an XBT result value for running nodes.

Parameters:

• reward The reward for executing the node (including all descendants). Default is 0.

Returns:

An XBT result indicating that the node is running.

succeeded (reward, continue)

Create an XBT result value for successful nodes.

Parameters:

• reward The reward for executing the node (including all descendants). Default is 0.
• continue Boolean indicating whether reward can be improved by further computation. Default is false.

Returns:

An XBT result indicating that the node has completed successfully

failed (reward, reason)

Create an XBT result value for failed nodes.

Parameters:

• reward The reward of executing the node (including all descendants). Default is 0.
• reason A string describing the reason why the computation failed. Default is nil.

Returns:

An XBT result indicating that the node has failed.

is_result (value)

Check whether a value is a valid result. XBT results values are tables with a status attribute containing one of the values "inactive", "running", "succeeded" or "failed", a numerical reward attribute and a continue attribute. If the result is inactive or running the continue attribute must be truthy, if the result is failed it must be falsy. If result has status "succeeded" the continue flag indicates whether the node can continue in order to try to improve its result.

Parameters:

• value The value to be checked.

Returns:

A Boolean indicating whether value is a valid result.

is_inactive (result)

Check whether result has status "inactive".

Parameters:

• result The result to be checked.

Returns:

A Boolean indicatus whether result is inactive.

is_running (result)

Check whether result has status "running".

Parameters:

• result The result to be checked.

Returns:

A Boolean indicatus whether result is running.

is_succeeded (result)

Check whether result has status "succeeded".

Parameters:

• result The result to be checked.

Returns:

A Boolean indicatus whether result is succeeded.

is_failed (result)

Check whether result has status "failed".

Parameters:

• result The result to be checked.

Returns:

A Boolean indicatus whether result is failed.

is_done (result)

Check whether a node needs to be ticked again. The function is_done returns true if result indicates that node has already reached a state that allows the computation to progress (even if the node could still be improved).

Parameters:

• result The result to be checked.

Returns:

true if the result's status is either succeeded or failed, false otherwise.

can_continue (result)

Check whether a node can be ticked again. In contrast to is_done this function returns true whenever the node can continue executing, either to finish an incomplete computation or to improve a previous result.

Parameters:

• result The result to be checked.

Returns:

A Boolean indicating whether ticking the node may result in a different result than the one previously obtained.

State

XBTs are passed a state object when they are evaluated.

make_state (table)

Make a new state, or update a table to become a state. Any table can be used as state (there is no need to have a particular metatable), but it has to contain certain attributes:

• a blackboard for use by the nodes

• node_results, a table mapping paths to the corresponding XBT results.

• local_data, a table for storing local data that nodes want to persist between ticks. This data is cleared when nodes are deactivated, so data that should persist between runs of the XBT should be stored in the blackboard.

• improve, a Boolean flag that indicates whether nodes that can improve their values should restart the computation or return their previous values.

make_state takes a table and adds these attributes if necessry. It can also be called without argument (or with a falsy value) to generate a new state.

Parameters:

• table Either falsy in which case a new state is created or a table, in which case the missing fields are added.

Returns:

A state.

set_local_data (node, path, state, data)

Store local data for a node instance. Save data in state so that it persists during ticks. It can be read with local_data and is deleted by deactivate_node.

Parameters:

• node The node for which we are storing data. Ignored by the body, so it can be nil if local data is stored before a node is available.
• path A path identifying the instance of the node.
• state The current state of the evaluation.
• data The data we want to persist. Any old data stored for this instance is overwritten.

local_data (node, path, state, default)

Retreive local data for a node instance. Retreive data that was previously stored using set_local_data or return the default value if no previously stored value is available.

Parameters:

• node The node for which we are retreiving data. Ignored by the body, so it can be nil if the node for path is not known.
• path A path identifying the instance of the node.
• state The current state of the evaluation.
• default The value returned if no data is available. Default is {}

Returns:

The previously stored data or default.

set_result (node, path, state, result)

Set the evaluation result for a node. This is mostly useful for the tick function and for evaluators that can improve their results.

Parameters:

• node The node that was evaluated.
• path A path identifying the instance of the node.
• state The current state of the evaluation.
• result The new evaluation result for node.

Returns:

The new evaluation result for node, i.e., result.

result (node, path, state)

Get the previous evaluation result for a node. This is mostly useful for the tick function and for evaluators that can improve previous results.

Parameters:

• node The node to evaluate.
• path A path identifying the instance of the node.
• state The current state of the evaluation.

Returns:

The result of the previous evaluation of node. If node was not previously evaluated, an inactive result is returned.

Evaluation and Compilation

The following functions are concerned with evaluating nodes or compiling XBTs into a for that can be integrated into other systems (currently no compilers are available).

evaluators

Evaluators for ticking nodes. Ticking is the fundamental operation that triggers evaluation of nodes. To make the node types extensible we look up the ticking function in the table evaluators using the xbt_node_type as key. Each ticking function receives three arguments: the node that is ticked, the path to the node from the root of the XBT to uniquely identify the node instance, and the state of the evaluation.

compilers

Compilers for XBTs. To achieve greater performance (or to integrate XBTs into existing systems) it may be necessary to compile the XBT into a representation that can be executed by the target system. This table maps each node type to a table that in turn maps backend names to a compiler for the given node type and backend.

default_failure_reward

The default reward for failures.

tick (node, path, state)

Trigger evaluation of a node. A tick triggers the evaluation of an XBT. Each leaf node should perform a small amount of computation when ticked and then return an XBT result to its parent. Long-running computations repeatedly return a running result until they either successfully complete with result succeeded or fail with failed.

In this implementation XBTs are not instanced, i.e., an XBT holds no information about its evaluation. Therefore each XBT may be reused multiple times during an evaluation (e.g., by call nodes or by structural sharing between nodes in the XBT so that the tree becomes a DAG).

The function tick manages the evaluation state of the XBT. Each node is uniquely identified by its path in the tree which is passed as second argument. The state passed as third argument contains the state of the XBTs evaluation and methods to perform all actions that leaf nodes may trigger in the environment.

Parameters:

• node The node to be ticked.
• path The path to node.
• state The current state of the XBT's evaluation.

Returns:

The result of the evaluation of the subtree below node.

define_node_type (nt, arg_names, evaluator, compilers)

Define an evaluation function and a constructor for node type nt.

Parameters:

• nt The node type that will be stored as xbt_node_type in all instances.
• arg_names The names under which the arguments to the constructor are stored in the resulting node. For example, if nt is "foo" and arg_names is {"bar", "baz"}, define_node_type will define a function foo that takes two arguments arg1 and arg2 and returns a table {xbt_node_type="foo", bar=arg1, baz=arg2, id=...}. Composite nodes must have an argument named children.
• evaluator An evaluator function for this node type. It is called with three arguments: a node, a path and a state. The state always contains blackboard, node_results and improve attributes.
• compilers If provided the argument is a table mapping backend names to functions that can compile the XBT for that type of backend. Default is {}.

deactivate_descendants (node, path, state)

Set all descendants of a node to result status inactive. The desendants of an inactive node all have to be inactive as well, so we don't recurse into inactive children. However, since planning or learning nodes might reorder their children dynamically we cannot be sure that the right siblings of an inactive child are also inactive; therefore we always process the complete list of children.

Parameters:

• node The node whose descendants we are deactivating.
• path The path to node in the XBT.
• state The state of the XBT's evaluation.

deactivate_node (node, path, state, clear_data)

Deactivate a node. Set all descendants of a node to status inactive and clear any data the node might have stored under its path, but keep the current result status of the node in state.

Parameters:

• node The node whose descendants we are deactivating.
• path The path to node in the XBT.
• state The state of the XBT's evaluation.
• clear_data If true, the local data for the path is deleted, otherwise it is kept

reset_node (node, path, state, clear_data)

Reset a node to inactive status. Set the node and all of its descendants to status inactive and clear any data the node might have stored under its path.

Parameters:

• node The node whose descendants we are deactivating.
• path The path to node in the XBT.
• state The state of the XBT's evaluation.
• clear_data If true, the local data for the path is deleted, otherwise it is kept

functions

A table mapping function names to functions. Function and action nodes use this table to look up their fun attributes.

define_function_name (name, fun)

Define a name for a function or action. We often want to serialize XBTs. To make this more convenient we allow functions appearing in leaf nodes to be specified as strings, in which case we look up the function value in xbt.functions.

Parameters:

• name The name with which the function can be accessed in fun nodes.
• fun The function.

lookup_function (f)

Look up a function or action given its name.

Parameters:

• f A function or the name of a function defined using define_function_name.

Returns:

If f is a string, use it as key in the xbt.functions table and return the value found. Throw an error if no definition for f exists. Otherwise just return f.

Node Types

An XBT node is represented by a table containing an xbt_node_type attribute. Nodes can either be composite (have child nodes) or atomic (encapsulate a function or coroutine). Each node has a unique ID.

fun (fun, args)

Generate a function node. Function ("fun") nodes encapsulate a function. The function is called with the node, the path and a state as arguments and has to return a valid XBT result. The node and path are mainly useful if the function has to store local information in the state. If the information is for all occurences of the function then node can be used as key; if it is just for this occurrence of the function then tostring(path) can be used. Note that path itself is not a useful key, since there is no guarantee that different invocations of the function at the same position will receive identical paths. The paths are guaranteed to be ==, however.

Parameters:

• fun A function invoked with node, path and state as arguments. It performs the work of this node.
• args The "arguments" for the fun parameter. They are stored as node.args so that they can be accessed by the fun parameter when it is executing. These arguments are the same for all invocations of the node, since they are stored in the node itself, not in the path.

Returns:

An function node. This node is serializable if the fun and args arguments are serializable. Typically this is the case if fun is a string that references a function defined with define_function_name.

action (fun, args)

Generate an action node. Action nodes are similar to functions, but they wrap the return value of the function into a XBT result that indicates that the function has succeeded and contains the return value of the function as reward.

Parameters:

• fun A function invoked with node, path and state as arguments. It performs the work of this node and returns a number that is returned as the result of the action.
• args The "arguments" for the fun parameter. They are stored as node.args so that they can be accessed by the fun parameter when it is executing. These arguments are the same for all invocations of the node, since they are stored in the node itself, not in the path.

Returns:

An action node. This node is serializable if the fun and args arguments are serializable. Typically this is the case if fun is a string that references a function defined with define_function_name.

bool (fun, args)

Generate a node that wraps a Boolean result. Boolean nodes are specialized function nodes that return either failed or succeeded, depending on whether the encapsulated function returns a truthy or falsy value. The reward of the call has to be provided as args.reward when the node is created; it is the same for all invocations of this node. The evaluated function should not modify the node.args.reward value to return different rewards; functions that need to return different rewards for different invocations should instead be defined as fun nodes.

Parameters:

• fun A function invoked with node, path and state as arguments. It performs the work of this node.
• args The "arguments" for the fun parameter. They are stored as node.args so that they can be accessed by the fun parameter when it is executing. These arguments are the same for all invocations of the node, since they are stored in the node itself, not in the path.

Returns:

A Boolean node. This node is serializable if the fun and args arguments are serializable. Typically this is the case if fun is a string that references a function defined with define_function_name.

seq (children)

Generate a sequence node. Sequence ("seq") nodes evaluate their children sequentially and fail as soon as one of their children fails.

Parameters:

• children The child nodes of the node.

Returns:

A sequence node. This node is serializable if its children are.

all (children)

Generate an all-sequence node. All-sequence ("all") nodes evaluate their children sequentially. They always evaluate all of their children and return success, no matter whether their children succeed or fail.

Parameters:

• children The child nodes of the node.

Returns:

An all-sequence node. This node is serializable if its children are.

choice (children)

Generate a choice node. Choice nodes evaluate their children sequentially and succeed as soon as one of their children succeeds.

Parameters:

• children The child nodes of the node.

Returns:

A choice node. This node is serializable if its children are.

xchoice (children)

Generate an external choice node. External choice nodes call a function to determine the evaluation order of their children and succeed as soon as one of their children succeeds. If this function removes nodes from the list of children it has to deactivate them to free any resources the children might retain. The update_fun is called just before deactivating the node when a successful or failed result has been reached. It receives the node, path and state as arguments, and either the result of the evaluation if child_fun returned at least one child, or nil otherwise.

Parameters:

• children The child nodes of the node.

Returns:

An external choice node. This node is serializable if its children are.

epsilon_greedy_child_fun (node, path, state)

Epsilon-greedy child_fun for xchoice. Sort the children of a node and with probability state.epsilon or node.args.epsilon swap the first element of the result with another one. The function to generate the sorted list of children is taken from node.args.sorted_children.

Parameters:

• node The xchoice node.
• path Path that identifies the instance of the node
• state The current state of the evaluation.

Returns:

An epsilon-greedy result list of children.