The noncombatant character

Jan 25 2017. Written by brainific

The pilgrim walked down the hill to the entrance of the cave. A couple of bandits with steel shortswords guarded the entrance. One of them unsheathed its weapon after hearing the creaks made by the leather boots. The other followed after a brief moment.

“You vagrant! Get lost before we skewer you and roast you for dinner!”

The pilgrim shrugged and sighed.

“Sorry… I thought I could take a shortcut to the castle. The lady down the road doesn’t want to mingle with dusty pilgrims, either.”

“Lady down the road? What lady?”

“A lady with flashy clothes and shiny bracelets. She was travelling with a bard and a couple of maids.”

The eyes of the bandits opened, and one of them almost dropped his jaw.

“Come on, Krook! Let’s warn the boys and deal with this lady! But lock the cave door first. We don’t want the filthy pilgrim to take our fine jewels, do we?”

The pilgrim waited for some moments after the bandits had run away, and unlocked the door with a whispered spell. He sighed; it was seldom so easy. Lady Bertha and her goblin-summoning spells would prove a match for the rogues, and her tanks in magical disguise would keep her safe. But the band of heroes would be delayed long enough for him to take the spell tome from the bandits and claim the prize all for himself. He just hated the hassle of combat.

Current online games are all about combat, and a not so smart one after all. We have heard long discussions about the holy triad of tank, DPS and healer and how to handle aggro in mobs. It is a pity that role playing games need to restrict themselves so much that these meager concepts are all that is left from the wealth of fantasy and imagination poured on these games.
The paragraph above represents an example of a more interesting and combat-less scenario. The player contacts some bandits who hold a quest object coveted by two parties. In all online games we can think of, the only real choice would be how to execute the bandits. But here at Brainific we think that it should be possible for the players to take other routes, in a similar way as Deus Ex allows. The pilgrim tricks the bandits into choosing another prey, and takes advantage of this situation to take the quest object alone. All this without a single drop of blood (spilled by him, anyway) and a single Open Locks spell. But what wondrous piece of automated logic could possibly enable this scenario?

Natural Language Processing

The first piece in the puzzle is Natural Language Processing. NLP is a very broad area, covering many difficult and complex (as in EXPTIME complexity) problems. Not so recently, IBM’s Watson has cracked quite some nuts dealing with natural language in different areas. Regarding games, restricting the domain may be the answer. After all, we deal mainly with conflict in RPG games, so we can leave out entire language areas. In Brainific we are exploring the content of Morrowind with Stanford’s CoreNLP and NLTK packages to see what subsets are enough for fantasy RPGs.

Natural Language Generation is also a useful technique. Even if the content to deliver is the same in different situations, different phrases, structures and slang can be used to render them unique, akin to “color schemes” in stereotyped characters. This could also provide stereotypes to guide the human player’s actions, in an unfortunate reflection of the real world.

Unfortunately, to be able to say something interesting we need some kind of formal language to which our language can be translated. That is, the listener needs to build a model of what the speaker is saying. Richard Montague tried to tackle this problem using a higher order logic system with modalities and other mechanisms, called Montague semantics. This problem will lead us into the following technical area that we need to tackle.

Modal Logic

The term “modal logic” encompasses whole families of logics that use predicates relating other sets of predicates (at least, in one of its interpretations). Human thought is complex enough to incorporate at least several modalities:

  • Temporal: reasoning about the past, or what could happen in the future.
  • Dynamic: reasoning about what becomes true after performing an action.
  • Doxastic: reasoning about beliefs, that may or may not correspond to the real situation.
  • Multiagent: reasoning about what other people are thinking (yes, this includes what they think we think and what they… well, you sure get the point).
  • Public announcements: reasoning about how one’s knowledge changes after hearing statements from other agents.

These logics often use a “possible world” semantics, where a logic proposition evaluates to true or false if some or all of a number of related “worlds” (those reachable by the modalities’ accessibility relation) hold another proposition. For example, a temporal logic may have a LATER(P) operator that holds true if P is true in the future (which is definitely another “world”). The logic used in these worlds is usually propositional or first-order logic. However, current logic tools (which mainly amount to production systems) in games and other sectors can hardly manage first order logic, let alone modalities.

Agent Communication Languages

Although they were initially designed for machine-to-machine communications, and they are almost 15 years old, the FIPA ACL specifications contains a library of communicative acts that is fairly complete, and contains a semi-formal description of the expected changes in the listener’s mind when certain acts of speech are used. This description can be used to infer the changes in the listener’s minds. For example, we can find a definition for a communicative act of “agree” in <here>:

<i, agree (j, <i, act>, φ))> ≡
<i, inform (j, Ii Done (<i, act>, φ))>
FP: Bi α ∧ ¬Bi (Bifj α ∨ Uifj α)
RE: Bj α
Where:
α = Ii Done(<i, act>, φ)

where RE stands for “rational effect” (a sort of desired postconditions) and FP stands for “feasibility preconditions”. The whole definition means that “agent i agrees before j to execute act only if φ is true before”, and that translates into “agent i informs agent j that agent i INTENDS to do action φ

As we can see, the FIPA ACL primitives relate to Searle’s speech acts, and use the BDI logic framework that comprises modalities addressing beliefs and goals. In our opinion, the BDI logic used in the FIPA standards lacks a proper formalization and theoretical support. Also, temporal aspects or dynamic epistemic aspects are not properly modelled in the standard. Lastly, FIPA ACL is oriented at cooperating agents, and so does not cover such “relevant” interactions as threats or manipulation.

Planning Algorithms

In its broadest sense, an exchange of phrases can be thought as a turn game in which each player must maximize the return of their actions. In the described case above, the bandits realize that they gain nothing by staying there and punishing the pilgrim, and instead take the action of running to the travelling lady to relief her of her riches. As we have explained in our previous section, this action becomes “enabled”, or ready for selection, since a new object appears in the bandits’ minds to which the “rob” action can be applied. The use of planning algorithms that maximize a benefit from a certain initial state by selecting the appropriate actions are clearly useful techniques for an exciting and intriguing conversation in a fictional discussion. Some actions (sensing actions) even allow the user to probe its surroundings and further refine their plans. Academics like Thomas Bolander or Jan van Eijk apply modal logics as described above (mainly dynamic epistemic logic) to planning in the hope of devising more powerful planning algorithms.

Planning can also be useful for NLG. Even though many NLG systems use generative grammars, like Tracery, there have been some experiments applying proven planning algorithms to language generation. These algorithms, as opposed as purely generative systems, can keep a “goal” state to guide the language generation.

Fiction or live action?

As promising as the theories and technologies described here may sound, state of the art tools hardly implement any of them. Scripts, chatbots and simple planning are still used or considered top-notch in current games. Here in Brainific we hope to research existing tools and develop new ones to expand the limits of tomorrow’s narrative games. Stay tuned!

Filed under Uncategorized

Twisting your trees

Sep 8 2015. Written by brainific

In the previous post “Introducing the Action Framework”, we presented a separate architecture where behaviours act as reactors to the current state of the game. This allows active behaviours to run synchronously and quickly, moving the more “deliberate” processing to a separate thread or fiber. But how do we select our behaviours? FSMs, trees, planners, as discussed previously?

(UPDATE: the previous post not only owes to the CERA architecture, as we will see later, but also Carle Côté’s article on “Reactivity and Deliberation in Decision-Making Systems” in the Game AI Pro book. Browsing this title has also shown that the choice of title, as well as some inspiration, has been drawn from Bill Merrill’s article, “Building Utility Decisions into Your Existing Behavior Tree”.)

Trees for Funs

In the last nucl.ai, recent developments in behaviour trees arose a number of comments from the attendants about how nodes in a behaviour tree are becoming more similar to functions in a more traditional programming language, and why there was not more general programming support in behaviour trees. After some thinking, we believe that general programming languages are far too complex and varied to be useful as they are. Some sort of constrained, simpler execution model would be much more useful to AI programmers (that can build more powerful tools themselves if need be) and AI authors (that do not need to learn several programming languages to come up with sensible AI). But we also believe that a good model for behaviours need not mimic any of the existing constructs in programming languages. Why and how? Let’s take a look at the current approach.

From Trees to Sprouts

A behaviour tree in many current tools looks like this:

Original behaviour trees

You can see active nodes in green, and non-active nodes in red. This might seem enough at first. However, we have realized that separating the specification data from the runtime data provides much more flexibility at little cost. We can visualize this separation in the following drawing:

Separated behaviour trees

Effectively, we have a specification part, that tells us how new nodes are generated in the runtime part; and a runtime part, that looks suspiciously similar to a function stack (and it works as one, as well; but there are some differences). Note the word “generated”. New runtime nodes are instantiated from the parent node, which is in turn an instantiation of some kind of “prototype” node, or a lambda, or a factory. In our case, a sequence node inserts itself in the runtime tree, and spawns another node as a child.

The important point is that the structure does not need to have a one-to-one correspondence to the runtime node tree. It only generates this runtime tree using some rules. In the following examples we will use mainly Haskell to illustrate these rules and they way we can twist and enrich them, but many of these mechanisms can be implemented in other languages  (albeit much less succintly).

Before jumping to an example, let us be honest: this is not new at all. Whether consciously or by chance, we are replicating the mechanisms sketched by Mateas and Stern in their article “A Behavior Language: Joint Actions and Behavioral Idioms” about the tools used in their game, Façade. The authors even speak about generating appropriate behaviors according to preconditions, so basically they are unifying behavior trees and some kind of hierarchical, no backtracking, contingent planning. One of the differences is that we have separated the behaviour active part from its planning part. Once a behaviour becomes active, it reacts to everything coming from the game world, until the planning layer removes it from play. Even if this means skipping a couple of frames when thinking what to do next, behaviours become simpler to understand: if the state is like this, we do like that. When some conditions are met, then we think for a frame or two what is the next action, change the active behaviors after acting for the frame and off we go again.

But let us be even more honest. Not even the idea of separating a lower and an upper layer is really ours. It bears enough resemblance to Raúl Arrabales and Jorge Muñoz’ CERA-CRANIUM architecture for their award-winning UT bot “Conscious Robots”. We think that our only merit here is to streamline both ideas and use an appropriate tool (Haskell, in this case) to better provide these capabilities to a game programmer.

An Easy Patrol

We will illustrate this separation between specification and runtime parts in an example. Our first task will be to specify a patrol behaviour. With the current state of the art, one would draw a sequence tree, with some kind of “loop” modifier since we need the patrol to run forever. If the patrol fails (by, say, spotting an enemy), then an alternate tree will spawn that activates behaviours for chasing and shooting the target. It would look something like this:

Patrol tree - Mk1

Our first issue is that, after the chase, we want to start the patrol, but not starting in the first point in the specified patrol, but instead in the closest point to the patrol. Repeating the patrol from the farthest end would not look very intelligent, right? So we modify our tree to look something like this:

Patrol tree - Mk2

One issue with this approach is that the runtime view now differs from the specification view: whereas the specification view says “move to the closest point” (and needs to check the blackboard), the runtime view knows the point towards which we are heading, and it will not change. Current behaviour trees can cope with this situation with little changes.

But we want to make our game much more flexible. Take into account that, even if we move to the closest point in the patrol, we need to specify where in the patrol we start. Now our sequence node needs to have some additional list-specific code that modifies the sequence. The separation of specification and runtime views comes in handy at this point.

Instead of moving to a predefined set of points (first go to XaYa, then to XbYb…), we want to specify these points at runtime. As we said, the specification view will handle node spawns (or factories) whereas the runtime view will always handle proper nodes. The specification can say, “this node spawn will take a BlackBoard and issue a Sequence node holding the shortest prefix of the patrol list”. However complicated we want to make the specification, it will nonetheless will be a Sequence node spawning MoveBehaviour nodes at runtime. The specification and runtime views would look something like this.

Patrol tree - Mk3

We will make a function (or a factory, or whatnot) that returns a sequence node using a BlackBoard:

data SeqNode = SeqNode NodeId (forall n. (Node n) => [n])
type seqNodeSpawn = BlackBoard -> SeqNode
patrolPoints = [(0,0), (3,3), (8,8), (10,10)]
prePatrolNodeSpawn = runFromCloserSeqNode "prepatrol" patrolPoints
cycleMoveNodeSpawn = runSeqNode "patrol" $ moveSpawnList $ cycle patrolPoints
patrolNodeSpawn = runSeqNode "complete_patrol" [prePatrolNodeSpawn, cycleMoveNodeSpawn]

You can find all the source code in bitbucket; please take into account that this is WIP, and is appropriately dirty and badly structured for the moment.

(Haskellers out there: the definition of the SeqNode has some complexities that we decided to leave out. For the complete datatype specification, using a “generic node” that holds the specific type of the type class and that performs the polymorphic action, refer to the source code . A profane probably understands it better like this.)

The “runSeqNode” spawn creates a sequence node from a blackboard. It takes an ID and a node spawn list (note that each node spawn will create a node from the data in the blackboard and insert it in the runtime tree under the parent node). One interesting feature in Haskell is that we can easily use and handle infinite lists: the cycle function takes a finite list and repeats it to make it infinite. One drawback is that we can no longer write the list of children, but instead we need to make “event runs” or “event traces” an inspect the runtime trees they create. The auxiliary function “moveSpawnList” takes a list of positions and turns them into Move behaviours for those positions:

moveSpawnList posList = moveBehavioursList
where
moveId = (++) "move-" . show
moveBehavioursList = map (\x -> runBehNode (moveId x) (moveBehaviour x)) posList

The “runBehNode” spawn, as expected, creates a behaviour node with an ID and an associated low level behaviour (see our previous post and remember that behaviours are properly reactive, always-on actions that produce actions with each frame).

In our second approach, we needed to find the closest point in the patrol list. How would we do this in this “separated” framework? We need a move behaviour spawn that creates a runtime node depending on values of the BlackBoard:

runMoveToCloserNode id posList (mem, bb) | length posList > 0 = (runTree, behaviours)
where
BlackBoard _ _ _ curPos _ _ _ = bb
    runTree = Node (GenNode $ BehaviourNode id) []
    closeList = [(p, d p curPos) | p <- posList]
    d (x1,y1) (x2,y2) = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)
    (closest, _) = foldl1' (\tmin@(pmin,dmin) t@(p,d) -> if d<dmin then t else tmin) closeList
    behaviours = [moveBehaviour closest]

We fold the values of (un-square-rooted) distances to find out the closest point, and then issue a behaviour move with the right point. Finding out the prefix is somewhat more complex, but equally compact:

runFromCloserSeqNode id posList env@(mem, bb) | length posList > 0 = (runTree, behaviours)
where
BlackBoard _ _ _ curPos _ _ _ = bb
    d (x1,y1) (x2,y2) = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)
    pointSubListDistList = unfoldr (\x -> case x of [] -> Nothing; l@(p:xs) -> Just ((p,l,d p curPos),xs)) posList
    (closest, closestSubList, _) = foldl1' (\tmin@(pmin,smin,dmin) t@(p,s,d) -> if d<dmin then t else tmin) pointSubListDistList
    spawnList = moveSpawnList closestSubList
    firstSp = head spawnList
    restSp = tail spawnList
    runTree = Node (GenNode $ SeqNode id restSp) [nextTree]
    (nextTree, behaviours) = firstSp env

We create a list of patrol points, with their distance values and suffixes. We find out the closest point, and then generate a list of behaviours that the sequence node spawn will use. When spawned, this sequence node gets inserted in the runtime tree, running the first move spawn node and inserting it underneath it, and holds the rest of spawns. Note that, at each point where a node needs to handle an event (success or failure), the node accesses the blackboard and generates new runtime nodes with this information.

We now how to spawn new nodes in response to events, but the only event we have now is the “start” event. In a following post we will introduce event handling along the runtime tree, including some areas where the behaviour of the system is still undefined. We will also explain how the separation of specification and runtime trees allows us to handle FSMs more naturally using a common framework, and why the usual “function call” abstraction is not powerful enough to implement this framework. Stay tuned!!!!

Filed under Uncategorized

Introducing the Action Framework

Mar 1 2015. Written by brainific

After watching many behaviour tree implementations and GOAP prototypes, we decided that Brainific could build a tool that takes the best from both, and hopefully allows other interesting structures. As we explain in our previous post, there are some common aspects in them, mainly low level reactive behaviours, and some mechanism to find out when an action succeeds or fails and how to select the next action, that could make this approach feasible.

Layered tastes better

DISCLAIMER: As any work in progress, the architecture of the Action Framework is subject to changes. Please comment as much as you want so we can design the kind of engine you really need.

In the Action Framework, we intend to separate the “planning” aspects of the engine from the “reactive” aspects. Planning can be amortized over several frames and interrupted, even scheduled on a separate core; whereas reactive behaviours need to run very fast and synchronously. So we will fork the “sensory” input when it arrives: one copy will proceed synchronously to the reactive engine and another will be updated in the planning engine. Note that we will sometimes want to act asynchronously on the planning engine, for example to abort the execution of a planning stage that is not necessary anymore. Note also that this separation has been inspired by cognitive architectures.

ActionFW diagram

Apart from a reactive engine and a planning engine, we will add an internal memory that can be accessed by both. This internal memory can be used as a more flexible mechanism where one could use a state machine.

The reactive engine contains two types of reactors: perceptors and behaviours. Behaviours are your bread and butter: they take an input state and output an action, and contain conditions for success and failure. Perceptors, on the other hand, build an abstraction over the purely sensory data, potentially across frames. For example, one can build a “danger” perception that builds up across frames and maxes out when 10 frames pass with health below a 5% threshold. We favor “perceptors” over “sensors” to reflect the structure and high-level function of perception compared to sensation in cognitive psychology. Perceptors can act over internal memory, or send events asynchronously to the planning engine.

The planner engine acts whenever the reactive engine tells it to: either a perceptor detects some kind of “end of action” event (run to point A includes the running behaviour, but also the end condition of reaching point A) or someone adds a goal to be fulfilled (e.g. “remove that soldier”, that can translate into different plans like shooting at him or just distracting him to run somewhere else). The planner comes up with the “best thing to do next” and updates the reactive engine accordingly. A planner could be a utility behaviour selector, a behaviour tree execution, or a planner proper. Its only requirement is to take the external state, the internal memory, the reactive engine state and its own state to come up with a change in the active behaviours. The planner engine will usually work asynchronously, unless the whole current planning stage does not make sense any more. This usually happens when a fundamental behaviour has failed (e.g. when an agent cannot reach point A, the current plan beyond point A is now useless), or there is some more important goal at stake (e.g. throw away flanking plans to come up with a retreat plan when health is low).

Enter Haskell

To develop this architecture we need a language that lends itself naturally to the kind of AI mechanisms we want to use. We need both flexibility and as much speed as we can get. In the end the choice was Haskell.

Haskell is a pure, lazy, declarative functional language with a lot of mileage. The language structure itself is deceptively simple, providing a rich and complex type system (the Hindley-Milner type system, with several extensions available) that catches a lot of errors in compile time. Most constructs in Haskell are either type- or function-related. For the newcomers, this might seem a bit like an outdated Scala. The fact is that Scala borrows some of the features from Haskell, making some compromises with uneven results. Haskell also compiles to native code via LLVM, making it appropriate for some applications (e.g. videogames or embedded environments) where a virtual machine’s stats like memory usage may not be appropriate.

Haskell provides a lot of interesting features:

  • Easy concurrency on several mechanisms (our favourites are Channels and STM transactions) with user threads scheduled by the Haskell runtime
  • Performance on the order of x2 related to equivalent hand-tuned C++ for dummy nonsense applications (i.e. the computer language shootout)
  • Multithreaded execution scheduling decoupled user threads (à la Java Executor, but with preemptive user thread scheduling like in Erlang)
  • Monads that encapsulate side effects, making it easy to know which of your functions can execute in which contexts, e.g. inside a transaction, inside an imperative computation…
  • Advanced compilation and runtime system providing small CPU and memory footprint (priceless for computer games)
  • Backends for several architectures, including… OpenCL!
  • A powerful but relatively complex to use Foreign Function Interface (FFI) mechanism, usable in both Linux and Windows (with some small tweaks)

After passing the point of maximum slope, advancing in the language was fairly easy. The concurrency constructs are clear and easy to use, user threading works just fine, and the compiler gives mostly useful comments, mainly related to typing. But we need to tackle FFI if we want it to be used in production environments. In the next post we will detail exactly how the Action Framework can be used in a Windows C++ project.

Filed under Uncategorized

Behaviours in Games

Oct 22 2014. Written by brainific

Agents in a virtual world need a brain to provide fun to the players: the smarter the brain, the merrier. However, this smartness is bound by two limits: processing power and algorithms. As the game Republique has shown, processing power is not an issue, once the detail is kept under control. On the algorithmic side, there are several alternatives that are now successfully in use, each one with their pros and cons, of course. These are hierarchical state machines (HFSM), behaviour trees (BT), goal oriented planning (GOAP, a variant of the STRIPS planner) and hierarchical task networks (HTN). Our first intention was to provide a comparison of these approaches to highlight their similarities and differences. However, we found two excellent summaries in AI Game Dev and the Intrinsic Algorithm blog that already fill this gap. So, we would like to take a somewhat more academic approach to try and tackle the problem of a unified approach that could cover all these alternatives.

First, we would like to point to the Open Course Ware provided by Professor Daniel Borrajo’s Planning and Learning Group, at the Carlos III University in Madrid. They contain a comprehensive guide to automated planning and related areas that we will discuss in this post.

Behaviour trees and goal oriented planning are, actually, just two parts of a bigger animal: planning algorithms. GOAP is exactly a small example of such algorithms: if you provide them with a goal and a set of possible actions, then they will provide a plan, a sequence of actions that will finally reach the goal. This is commonly known as classical planning, the simplest form of planning. Each action has some preconditions (conditions to be met before the action can be performed) and some postconditions (conditions that will be true when the action is performed). The agent tries some sort of forward chaining (from current situation to goal) or backward chaining (from goal to the current situation) in its “head” to try and find a path of actions that will lead us to the goal. As we are exploring the implicit graph made of states and actions between states, this can take some time. A useful algorithm called A* is used in GOAP to accelerate this task. It is more commonly known as the main algorithm for navigation in a mesh, but it can be used in any kind of graph as long as we have a useful heuristic, an “optimistic” measurement of the distance between any state and the goal. This heuristic must always be less than or equal to the real distance between a state and a goal. In an environment with obstacles, for example, the straight distance between points can be used since any path avoiding obstacles. Finding a heuristic for an abstract graph of an “state space” with actions is somewhat trickier, but there are alternatives like relaxing intermediate steps. Planning can get much more complex in several dimensions (see slide 4 from this set from Stanford), like rich temporal models, durative and nondeterministic actions, or partial observability of the results of our actions.

Any FPS designer will immediately recognize a couple of limitations in this approach. What if we fail in an action? When do we consider an action as finished? Let us approach each of these aspects separately.

First of all, we have said that actions have a set of postconditions. This is not entirely true; they have a distinct set for each possible outcome of the action. Imagine the action of firing: we could hit the target, or we could miss. The outcome is different in each case, and depending on it we may need to take one action or another, and probabilistic in nature, so that the end state depends on the current state, the action and some random number (it is, formally, a Markov decision process). One possible approach is to find the best sequence of actions in average. Yet another approach is to provide contingent planning: instead of finding a sequence of actions, we compute, at least for some paths, corrective actions in case our actions fail. That leaves us with a tree of actions to execute when the main actions fail. That rings a bell, right?

Exactly, a behaviour tree can be considered exactly this: a plan with additional contingent plans on several levels. Of course, we are missing the whole pre- and postconditions parts that enable us to reason about plans. This prevents us from adapting our actions in the tree or discarding branches that we may know will fail. Maybe if we added pre- and post- to the actions and separated the tree declaration from its execution we could unify the approaches. But we will try that out in a later post.

And what about FSMs and HTNs? FSMs are a way of specifying traces of actions with mechanisms that are hard to build into behaviour trees, like recursion. Imagine switching from the alert to the relaxed state and viceversa in a behaviour tree. One of the states must be the parent of the other; adding a third state will further confuse things because we will need to work out an artificial hierarchy among them. We might use sequence and loop nodes to organize actions, but state switching as described here can be hard to express in a behaviour tree.

Regarding HTNs, they also come from the planning domain, as a sort of “hint” to alleviate the computational burden on the planner by specifying some conditions that need to be reached at some steps. Instead of leaving the planner explore all the state space, the designer will mark some spots that the agent has to reach: We do not fix actions in this way, but rather subgoals. If we want to buy meat, we first need to go to the butcher, and then get the meat. The agent can go to the butcher walking, taking a taxi or driving the car, and fulfill these subgoals with different actions (like building a car or hiring a driver to drive the taxi). The specific actions selected for the subgoal may depend on some metric, like probability of success or a utility measurement (e.g. being “green” instead of being fast). HTNs are probably a good middle ground among behaviour trees, GOAP and utility based actions.

In a future post we will try to find some middle ground among all these. Warning! It may include Haskell, graph algorithms and cognitive architectures…

Filed under Uncategorized

Evidence Based Medicine Made Dead Easy – Part II

Mar 2 2012. Written by brainific

The following post describes the specific architectural and software design issues in our EBM demo, framed in the scenario described previously in Evidence Based Medicine Made Dead Easy – Part I. We hope health IT people out there will enjoy this small demo.

Requirements and Architecture

The described system may sit alongside the EHR system. Of course, it will need some integration in the EHR interface so that the doctor does not need to start yet another application. It will further need to understand the data model used in the EHR, to be able to allow the health professional to select the patient info to include in the tests. Finally, it must also provide libraries for numerical analysis, also including parallel, concurrent and distributed capabilities to some extent. A preliminary architecture is shown below.

We have decided to use Python as the programming language in this demo as it is suitable both for prototyping and for deployment in a web server like Django, many connector modules for different databases are available, is relatively easy to use for newcomers, and also includes libraries for numerical calculus and distributed processing. Note that we have not addressed the messaging interface (the dotted box in the architecture).

Design

In the following sections, we will describe the components included in the architecture. We will not, however, address the integration with openEHR’s UI, as it is not the focus of these posts.

Data Retrieval

First of all, we need a way to obtain the patient data from the EHR. In our case, we chose PatientOS as explained in our previous post. In this aspect, the boon and curse of PatientOS is its flexibility. All forms, records and record items are not specified in code, but rather described in rows of different tables and the relations among them. So, we will have to find out which record item stores the information we want.

In our case, let’s assume we store the weight records as procedures in the patient’s medical history. The procedure we will use is 2001F “WEIGHT RECORDED” in CPT, with a freeform string value of “XX kg”, where XX is the weight in kilograms. It seemed a natural place to put this data; however, doctors might decide to use less structured data records to store the visit information. In this case we could think about using natural language processing techniques using e.g. NLTK.

After some research, we can obtain the query that gets the procedures we want for the user we want:

SELECT p.first_name, p.last_name, f.title, fr.value_string, t.term_name, t.description FROM refs, forms f, patients p, form_records fr, terms t WHERE p.last_name='Cave' AND fr.patient_id=p.patient_id AND fr.form_id=f.form_id AND refs.ref_id=fr.record_item_ref_id AND refs.ref_key='PROCEDUREDESCRIPTION' AND t.abbreviation='2001F WEIGHT RECORD' AND fr.term_id=t.term_id ORDER BY fr.record_dt;

We will run this query from Python using Psycopg2 to connect to the PostgreSQL DB used by PatientOS.:

import psycopg2
conn = psycopg2.connect("dbname='patientos_db' user='patientos_user' host='localhost' password='patientos_user'")
cur = conn.cursor()
cur.execute("""select p.first_name, p.last_name, f.title, fr.value_string, t.term_name, t.description from refs, forms f, patients p, form_records fr, terms t where
p.last_name='Cave' and fr.patient_id=p.patient_id and fr.form_id=f.form_id and refs.ref_id=fr.record_item_ref_id and refs.ref_key='PROCEDUREDESCRIPTION' and t.abbreviation='2001F WEIGHT RECORD' and fr.term_id=t.term_id order by fr.record_dt;""")
patients = cur.fetchall()
conn.commit
weights = []
for patient in patients:
    weight = int(patient[3].split()[0])
    weights.append(weight)
print "Weight: ",weight
print weights

Data Analysis

Once we have the data in place, we could use any statistical program to analyze them, such as SAS, SPSS, R, Matlab or, in our case, Scipy. Scipy is a Python package that includes many numerical methods. It even allows us to use optimized libraries like ATLAS, BLAS and LAPACK, or distribute our calculations with MPI (e.g. using mpi4Py).

Let’s suppose we have retrieved the weight of two groups of 30 patients at two points in time, before and after the prescription of a drug, which may alter the patient’s weight. One of the groups will be a control group that will not take it, but otherwise (and ideally) have all other independent variables controlled. We will simulate both groups using the following piece of code, which generates two populations with different means for the difference of pre-and post-drug conditions:

import numpy.random
 
randn = numpy.random.randn
floor = numpy.floor
ttest = scipy.stats.ttest_ind
 
group1_pre = floor(randn(30,1)*10 + 65)
group2_pre = floor(randn(30,1)*10 + 65)
 
print group1_pre.T
print group2_pre.T
 
group1_post = floor(randn(30,1)*3 + group1_pre)
group2_post = floor(randn(30,1)*3 + group2_pre*0.95)
 
print group1_post.T
print group2_post.T
 
group1_diff = group1_post - group1_pre
group2_diff = group2_post - group2_pre

Now we will just apply a Student t-test to both populations, and check whether both groups have a different distribution:

(t, p) = ttest(group1_diff, group2_diff)
# Remember we have aliased ttest before...
print (t, p)

As simple as this. Our obtained p is 0.00386893, so it passes a 1% test.

There are many more statistical tests we can use in Scipy: ANOVA, Kolmogorov-Smirnoff… But, furthermore, there are many Python packages that can provide other data mining methods, like Orange or SciKit-learn. Even if you want to write your own, as we may want our statistician to do, Python is as good a language as, say, Matlab, for a quick implementation (and able to run fast too if you use an optimized numerical library).

Filed under medical
Tags: ,

Evidence Based Medicine Made Dead Easy – Part I

Jan 16 2012. Written by brainific

Disclaimer

Okay, so it will not be dead easy. We’ll see later the full list of tricks and obstacles we find when trying to deploy an evidence based medicine system in an EHR system in a later post. But hopefully this one will help you realize that data analysis modules can and should be installed alongside an EHR to make clinical research much more agile.

What’s EBM anyway?

According to Wikipedia (and, in turn, to Timmermann and Mauck) evidence-based medicine is about “apply[ing] the best available evidence gained from the scientific method to clinical decision making”. We all thought this was already true, given the amount of clinical magazines out there. However, evidence is not so easy to gather, and leaving out the doctor’s instinct out of the diagnosis is rarely a good idea. Now that EHRs are widespread, we at Brainific think that it is easy and convenient to deploy analysis systems that provide the kind of evidence EBM needs, and present it in a way that doctors can readily work with.

We will use PatientOS as the starting EHR on which to build our decision support demo. PatientOS follows the OpenEHR standard, an open specification for a health information model. An information model specification is more generic and flexible than a data model specification and more concerned about semantics. For these reasons, an information model tends to be more difficult to implement. All the data we handle in PatientOS falls in some Entry category, as specified in the OpenEHR architecture overview. OpenEHR is flexible enough to allow different processes on data, but it does not dig into the issue of how these data can be handled automatically. In our case, we would take Observations and Actions as inputs, and produce Assessments that will be reviewed by health professionals.

This series of posts will explain the use case, architecture, design and conclusions for a simple prototype, showing how a few open source products will allow us to quickly obtain evidence from our own clinical data.

The Scenario

Suppose we have already deployed PatientOS in our health center. We would like to relieve the statistician of so many doctors asking about simple tests, and instead have him focused on researching more robust and avanced ones. So we want our application to automatically retrieve the data the doctors need, and perform some standard test on it that the statistician will have already coded.

One such test will be whether one drug affects the patient’s weight after its prescription. We will use a Student t-test, where we will compare the difference in weight before and after the prescription for prescribed patients against the same measurements in a control group. The null hypothesis says that both groups will have zero difference, that is, that the mean in weight will be the same before and after the prescription. Note that there are thousands datasets in a clinical environment to which the Student t-test can be applied.

The statistician already knows how to code such a test. The IT staff can help him out with the code needed to interface the clinical data. We may use any data that follow its rules, so the statistician only needs to code the test once, and then the IT staff will access the data the doctors need in each specific case. Once the statistician has made its code available, exactly the same process can be applied to any specific dataset.

In turn, apart from all the billing, prescription and data record solutions, doctors may use a small window to interface this application and create a Student t-test. There they can select the data for each patient they want to analyze, as long as it is suitable for the test. The data of any patient can then be included in this experiment as soon as they come to the doctor’s office with a couple of clicks, so a new analysis can be done on the fly after enough new evidence has arrived. It can also be automated so that it runs in the background every nth patient, or even perform tests on other variables the doctor has not thought of, just in case.

The following post will illustrate how such a data analysis server would interface with the EHR system to retrieve the data and perform our statistical tests. We will perform a small proof of concept on a toy PatientOS installation including data collection from PatientOS and statistical analysis.

Filed under Uncategorized

Applications of Artificial Intelligence in Interactive Content

Jul 13 2011. Written by brainific

Brainific aims to provide leading innovative artificial intelligence and machine learning solutions. We strongly think there are different fields that would obtain benefits from their applications. For example, we are aware that fields such as on-demand content, advertisement, streaming media and interactive software are not taking advantage of what artificial intelligence and machine learning can offer.

Due to this reason, here in Brainific we decided to write a position paper in order to create and lead a work group inside eNEM platform.
eNEM is the Spanish Technology Platform dedicated to Networked Electronic Media that takes the European NEM platform as a reference.

We have titled our paper “Aplicaciones de la inteligencia artificil en contenidos interactivos” (Applications of Artificial Intelligence in Interactive Content).
This paper has been accepted and published on the eNEM site for being studied by the eNEM members. We hope that this initiative will attract other eNEM members so a work group can be formed.

Note: the paper is unfortunately available only in Spanish; however it will be translated shortly.

Filed under Uncategorized
Tags: , , , , ,

How to install PatientOS on Ubuntu server

Jul 11 2011. Written by brainific

Here in Brainific we are interested in the applications of machine learning and artificial intelligence in very diverse fields. Our current goal is to find out how these techniques have evolved in e-health since Mycin, and what would be the needs addressed by them. For the sake of experimentation, we decided to test an open source Health Information System (HIS).

We chose PatientOS, developed and maintained by PatientOS, Inc. It is an open source HIS that appealed to us due to several features. First of all, PatientOS relies on well-known open source technologies like PostgreSQL, JBoss or Mirth. This means that both the code and, more important, the interfaces are open, subject to inspection and extenal connections. PatientOS it also seems to be actively pushed in different fora, and supported by a company with a strong background in EMR and HIS. Finally, it follows the openEHR information model, which we think will be important in the future of health IT systems.

As we had some problems to solve in order to install this software in our servers (using Ubuntu), we want to share the installation steps we finally followed. We hope you find it useful.

1. Download PatientOS software

wget http://sourceforge.net/projects/patientos/files/patientos/v1.20/patientos-12-setup.tar.gz

2. Install PostgreSQL

sudo apt-get install postgresql postgresql-8.4 php5-pgsql

change the password of system user created by PostgreSQL (“postgres”)

sudo passwd postgres

Connect to the database and change the password of the admin user, also called “postgres”

su postgres
psql

3. Create a postgre user to be used by PatientOS

It has to be a super user

createuser -P -h localhost -U postgres patientos_user

4. Create the PatientOS data base

createdb -E UTF8 -h localhost -U postgres patientos_db

5. Grant privileges

psql -h localhost -U postgres
postgres# GRANT ALL ON DATABASE patientos_db TO patientos_user;

On next posts we will describe how to configure the PatientOS client to access our server.

Filed under Uncategorized
Tags: , , , , ,

Mixing Machine Learning and Rule Systems

May 16 2010. Written by brainific

Rule systems are very powerful, flexible systems for describing an agent’s behaviour. However, it only usually learns facts; that is, the rules that govern their behaviour normally remain fixed. In this post we will try to couple rule systems with machine learning methods to augment an agent’s capabilities. This was basically the main goal of my master’s thesis, about 10 years ago. But we’ll see that the tools for this task have evolved enormously during this time.

Drools

Drools is JBoss’ suite for business logic. Drools includes Drools Expert, which is a nice rule engine usable in other areas, like of course AI for online games. Some other rule engines are CLIPS and Jess, but CLIPS is slightly more difficult to integrate with other packages since it’s a C package (please don’t yell too loud at the poor author) and Jess is not open source. It also seems that Drools is getting more and more momentum, implementing features like adding concurrency in the rule engine.

Weka

Weka is Pentaho’s (and originally University of Waikato’s) component for machine learning. Some will object that Java is not the best choice for statistical number crunching, but Java is perfect for system integration, and Weka includes a lot of different methods one can try out on a specific problem. Furthermore, JNI makes it possible to include your top-notch, processor-matched, fine-tuned ATLAS or LIBPACK libraries if it were necessary. The University of Waikato has also moved into adaptive, CEP-like methods with the Moa package, but that’s another story that will be told in another post.

Mixing it all

The starting point will be a very simple Drools rule file:

package com.brainific.learningDemo
 
import com.brainific.learningDemo.Opponent;
import com.brainific.learningDemo.ClassifierWrapper;
import com.brainific.learningDemo.Action;
 
rule "Decide what to do when you come across an opponent"
    when
        $opponent: Opponent(identifier:id)
        $classifier: ClassifierWrapper(id == "sample")
    then
        String cl = $classifier.classifyInstance($opponent);
        Action a = new Action();
        a.setOppId(identifier);
        a.setAction(cl);
        insert(a);
end
 
rule "Act!"
    when
        $action: Action()
    then
        System.out.println("Acting!!! " + $action);
end

Basically, this ruleset takes an opponent in the agent’s “cognitive focus” (aka fact base), classifies it using some Java function, and asserting some action to take. Asserting the action instead of sending it to some underlying engine allows us to further reason about the action. Note that this function could be anything; we’ll see how to derive it from learning examples.

I’ve seen that ogre before…

Our “sensory system” will provide us with the following information about the opponent:

  • Level: some overall measure of the opponent’s fighting capability
  • Armor: how well protected the opponent is
  • Weapon: what will the opponent use against us

We will in turn either “attack” the opponent or “flee” from it.
Our agent will have some time to experience different opponents, and whether attacking the opponent was a successful strategy. After a couple of combats, we can summarize the experience in the following ARFF file:

@relation 'opponents'
@attribute LEVEL integer
@attribute ARMOR integer
@attribute WEAPON {bow, sling, axe, sword, dagger}
@attribute class {attack, flee}
@data
1,3,sword,attack
2,3,axe,attack
9,0,bow,flee
8,1,sword,flee

This allows us to create a J48 classifier with this dataset. J48 is Weka’s own implementation of the well-known C4.5 decision tree extraction algorithm. This algorithm will take some classified examples and derive a decision tree that tries to account for as many classified examples as it can, while at the same time keeping the tree simple.

package com.brainific.learningDemo;
 
import java.io.File;
import java.io.IOException;
import java.util.Arrays;
 
import weka.classifiers.Classifier;
import weka.classifiers.trees.J48;
import weka.core.Attribute;
import weka.core.Instances;
import weka.core.converters.ArffLoader;
 
public class LearningSensor {
        //...some code omitted...
	public static Classifier loadClassifier(String file) throws Exception
	{
		ArffLoader myLoader = new ArffLoader();
		myLoader.setFile(new File(file));
		Instances opponents = myLoader.getDataSet();
		opponents.setClassIndex(3);
		J48 opponentTree = new J48();
		opponentTree.setUnpruned(true);
		opponentTree.setConfidenceFactor(0.1f);
		opponentTree.buildClassifier(opponents);
		return opponentTree;
	}
}

The LearningSensor class allows us to easily create a new Classifier (which will be wrapped in another class, ClassifierWrapper) from existing examples. So, we can see what happens when this classifier is added to the rule engine with the current example set:

package com.brainific.learningDemo;
// imports removed for clarity
 
public class RuleEngineAgent {
	public static void main(String[] argv) throws Exception
	{
        KnowledgeBuilder kbuilder = KnowledgeBuilderFactory.newKnowledgeBuilder();
        kbuilder.add(ResourceFactory.newInputStreamResource(new FileInputStream("opponents.drl")),ResourceType.DRL);
 
        if (kbuilder.hasErrors()) {
            System.out.println(kbuilder.getErrors());
            return;
        }
        Collection<knowledgePackage> kpkgs = kbuilder.getKnowledgePackages();
        KnowledgeBase kbase = KnowledgeBaseFactory.newKnowledgeBase();
        kbase.addKnowledgePackages( kpkgs );
 
        StatefulKnowledgeSession ksession = kbase.newStatefulKnowledgeSession();
        KnowledgeRuntimeLogger logger = KnowledgeRuntimeLoggerFactory.newConsoleLogger(ksession);
 
        Classifier c1 = LearningSensor.loadClassifier("opponents1.arff");
        ClassifierWrapper cw1 = new ClassifierWrapper();
        cw1.setId("sample");
        cw1.setClf(c1);
 
        Opponent opp = new Opponent();
        opp.setArmor(4);
        opp.setLevel(2);
        opp.setWeapon(Weapon.axe);
        opp.setId("ogre");
        ksession.insert(opp);
        ksession.insert(cw1);
        ksession.fireAllRules();
	}
}

The agent’s decision tree, as extracted from the examples, is:

J48 unpruned tree
------------------
 
LEVEL <= 2: attack (2.0)
LEVEL > 2: flee (2.0)

Quite simply, we will attack with a level less or equal than 2. When we come across the ogre described in the agent class, the agent thinks like this:

OBJECT ASSERTED value:com.brainific.learningDemo.Opponent@14275d4 factId: 1
ACTIVATION CREATED rule:Decide what to do when you come across an opponent activationId:Decide what to do when you come across an opponent [2, 1] declarations: $opponent=com.brainific.learningDemo.Opponent@14275d4(1); $classifier=com.brainific.learningDemo.ClassifierWrapper@2c17f7(2); identifier=ogre(1)
OBJECT ASSERTED value:com.brainific.learningDemo.ClassifierWrapper@2c17f7 factId: 2
BEFORE ACTIVATION FIRED rule:Decide what to do when you come across an opponent activationId:Decide what to do when you come across an opponent [2, 1] declarations: $opponent=com.brainific.learningDemo.Opponent@14275d4(1); $classifier=com.brainific.learningDemo.ClassifierWrapper@2c17f7(2); identifier=ogre(1)
ACTIVATION CREATED rule:Act! activationId:Act! [3] declarations: $action=<ogre - attack>(3)
OBJECT ASSERTED value:<ogre - attack> factId: 3
AFTER ACTIVATION FIRED rule:Decide what to do when you come across an opponent activationId:Decide what to do when you come across an opponent [2, 1] declarations: $opponent=com.brainific.learningDemo.Opponent@14275d4(1); $classifier=com.brainific.learningDemo.ClassifierWrapper@2c17f7(2); identifier=ogre(1)
BEFORE ACTIVATION FIRED rule:Act! activationId:Act! [3] declarations: $action=<ogre - attack>(3)
Acting!!! <ogre - attack>
AFTER ACTIVATION FIRED rule:Act! activationId:Act! [3] declarations: $action=<ogre - attack>(3)

Our brave agent grabs its weapon and dashes head on toward the approaching monster. Shazam!

Another one bites the dust

Unfortunately, our agent has not seen enough action yet. Our agent dwelves into the action… and fails miserably. After returning to the spawn point, it gathers some more information and updates its example list:

@relation 'opponents'
@attribute LEVEL integer
@attribute ARMOR integer
@attribute WEAPON {bow, sling, axe, sword, dagger}
@attribute class {attack, flee}
@data
1,0,bow,attack
3,1,bow,attack
1,3,sword,attack
2,0,dagger,attack
8,0,dagger,attack
2,1,sword,attack
7,2,dagger,attack
9,0,bow,flee
8,1,sling,flee
7,1,bow,flee
3,3,sword,flee
2,4,axe,flee
4,3,sword,flee
7,4,axe,flee

The agent then loads the classifier obtained from this second dataset, and it gets the following decision tree:

J48 unpruned tree
------------------
 
WEAPON = bow
|   LEVEL <= 4: attack (2.0)
|   LEVEL > 4: flee (2.0)
WEAPON = sling: flee (1.0)
WEAPON = axe: flee (2.0)
WEAPON = sword
|   LEVEL <= 2: attack (2.0)
|   LEVEL > 2: flee (2.0)
WEAPON = dagger: attack (3.0)

Suddenly the world seems a much more complicated place. Apparently, most of our prior judgments were biased towards swordsmen! Since most of the combats against axe-wielding opponents ended in failure, our learning phase has taught us that this time we should avoid the ogre in the example:

OBJECT ASSERTED value:com.brainific.learningDemo.Opponent@15b0333 factId: 1
ACTIVATION CREATED rule:Decide what to do when you come across an opponent activationId:Decide what to do when you come across an opponent [2, 1] declarations: $opponent=com.brainific.learningDemo.Opponent@15b0333(1); $classifier=com.brainific.learningDemo.ClassifierWrapper@13b9fae(2); identifier=ogre(1)
OBJECT ASSERTED value:com.brainific.learningDemo.ClassifierWrapper@13b9fae factId: 2
BEFORE ACTIVATION FIRED rule:Decide what to do when you come across an opponent activationId:Decide what to do when you come across an opponent [2, 1] declarations: $opponent=com.brainific.learningDemo.Opponent@15b0333(1); $classifier=com.brainific.learningDemo.ClassifierWrapper@13b9fae(2); identifier=ogre(1)
ACTIVATION CREATED rule:Act! activationId:Act! [3] declarations: $action=<ogre - flee>(3)
OBJECT ASSERTED value:<ogre - flee> factId: 3
AFTER ACTIVATION FIRED rule:Decide what to do when you come across an opponent activationId:Decide what to do when you come across an opponent [2, 1] declarations: $opponent=com.brainific.learningDemo.Opponent@15b0333(1); $classifier=com.brainific.learningDemo.ClassifierWrapper@13b9fae(2); identifier=ogre(1)
BEFORE ACTIVATION FIRED rule:Act! activationId:Act! [3] declarations: $action=<ogre - flee>(3)
Acting!!! <ogre - flee>
AFTER ACTIVATION FIRED rule:Act! activationId:Act! [3] declarations: $action=<ogre - flee>(3)

Our agent flees form the ogre… and lives to gather more information about the world.

Conclusion

In this example, we have seen that machine learning can be integrated in our high-level AI systems to make use of past experience and improve our agents’ actions. Many other methods, like COBWEB’s conceptual clustering or and SVM’s nonlinear classification capabilities, could be useful in other situations that will be hopefully explored in future posts.

Filed under Uncategorized

Behaviour Trees in Erlang flavour

May 9 2010. Written by brainific

Reading about current state of the art in AI games, I’ve found that behaviour trees seem to be the next best thing. There are many examples of behaviour trees around, like Behave for Unity from AngryAnt, or the AI Sandbox from the people at AIGameDev. So, I decided to build my own in Erlang.

Why Erlang? Well, I thought it might have some advantages for AI applications. First, it’s a functional language, with function pattern matching and function variables, and I hoped those features could be useful in AI algorithms. Second, the language provides message passing and lightweight processes as primitives, which should come in handy when designing large-scale AI simulations and organizing the different modules in an AI (perception, action, reasoning…). And third, I just love it :)

As a first approach, I decided that the tree would be contained in its own process, and that it would take a reference to the underlying “motor system”, containing the pathfinding or steering module and the locomotion (i.e. animation) system.

After reading a couple of very useful articles in AIGameDev, I got the idea that the action in a behaviour tree is selected running the root node and following the directions there, until we get to an “action node” that has an action that completes either successfully or unsuccessfully. The parent node for this action node can then take a choice on the next node to run. I decided to implement the following nodes:

  • Sequence: runs its nodes in sequence; if none fail, then it reports success, otherwise it reports fail.
  • Selector: runs nodes in sequence until one is successful (note that this may mean that it just runs the first node).
  • Loop: runs the child node N or inifite times, unless it fails. A loop is a special kind of decorator, a node that takes a single child node and executes it or not based on some condition.
  • Condition: another decorator. Runs its child behaviour if some condition about the world holds true, otherwise fails.
  • Action! This kind of node should send some message to the underlying “motor system” and wait for results.

Let’s take a look at each one in sequence.

Action Node

The action node is the simplest of them all. It just takes an action as a parameter and sends it to the motor system. It is as simple as this:

action(Engine, {Action, Params}) -&gt;
    Engine ! {action, Action, Params},
    receive
        {event,success} -&gt;
            {success};
        {event,fail,Reason} -&gt;
            {fail,Reason}
    end.

Note that one of the advantages of erlang is the simplicity of message passing. While the action is being performed, the lightweight process running the behaviour tree will be blocked – without blocking any OS thread. The engine can run on its own, performing the specific action, until it succeeds or fails. Thanks to several interface modules (jinterface, erlc, OTP.NET…), the engine can be written in other languages, like Java or C#, using different algorithms like graph-based pathfinding or steering.

Sequence Node

As we said before, this node runs its child actions one by one until either one fails, and so this action fails, or all succeed, meaning success.

seq_behaviours(_Engine, []) -&gt;
    {success};
seq_behaviours(Engine, [{FirstBeh, FirstParams}|RestBeh]) -&gt;
    case FirstBeh(Engine, FirstParams) of
        {success} -&gt;
            seq_behaviours(Engine,RestBeh);
        UnhandledEvent = {fail, _} -&gt;
            UnhandledEvent
    end.

Thanks to erlang’s pattern matching and list expressions, this node’s code is quite compact. Since this node does not deal with the underlying engine, it will not block.

Selector Node

Our implementation for a selector node will try a series of actions in turn until one succeeds. In a way, it is complementary to the sequence node.

alt_behaviours(_Engine, []) -&gt;
    {fail,no_more_actions};
alt_behaviours(Engine, [{FirstBeh, FirstParams}|RestBehs]) -&gt;
    case FirstBeh(Engine, FirstParams) of
        {success} -&gt;
            {success};
        {fail, _} -&gt;
            alt_behaviours(Engine, RestBehs)
    end.

Loop Node

The loop node takes a child node and runs its child behaviour N times, or always.

loop(Engine,{always,Behaviour={FirstBeh, FirstParams}}) -&gt;
    case FirstBeh(Engine, FirstParams) of
        {success} -&gt;
            loop(Engine,{always,Behaviour});
        UnhandledEvent = {fail, _} -&gt;
            UnhandledEvent
    end;
loop(_Engine,{0,_Behaviour}) -&gt;
    {success};
loop(Engine,{N,Behaviour={FirstBeh, FirstParams}}) -&gt;
    case FirstBeh(Engine, FirstParams) of
        {success} -&gt;
            loop(Engine,{N-1,Behaviour});
        UnhandledEvent = {fail, _} -&gt;
            UnhandledEvent
    end.

Condition Node

A Condition node succeed if the condition evaluates to true and the child node succeeds.

condition(Engine,{Condition, {Beh,Params}}) -&gt;
    if Condition -&gt;
           Beh(Engine, Params);
       true -&gt;
           {fail, condition_not_met}
    end.

Some Remarks

Using Erlang, a functional programming language, has some features that come quite handy:

  • A behaviour is composed of lists and tuples of the previously described behaviours. This means that a behaviour can be written in an XML format without much trouble, just by linking XML elements to Erlang functions (and you can easily parse XML in Erlang using the xmerl_scan:file/2 function).
  • A process executing a behaviour can become blocked until the engine sends some event back. This means that we don’t need to keep a explicit cursor telling us where we are in the behaviour tree; the execution stack for the behaviour process will do exactly that.

Testing Time!

To test this small module, we’ll write a small Engine process in erlang that provides a series of messages that will “tell a story” to be interpreted by the behaviour tree, and then see if the tree can follow the sequence. This mock engine could then be replaced by a real motor an sensor module that interacts with the game world and other players. But first we will describe the behaviour tree we will be using.

BehaviourTree =
             {fun beh_trees:loop/2,
                 {10,{fun beh_trees:alt_behaviours/2,[
                     {fun beh_trees:loop/2,
                         {always,{fun beh_trees:seq_behaviours/2,[
                             {fun beh_trees:action/2,{move_to,{xA,yA}}},
                             {fun beh_trees:action/2,{move_to,{xB,yB}}}
                         ]}}
                     },
                     {fun beh_trees:action/2,{pursue,{thief,10}}},
                     {fun beh_trees:alt_behaviours/2,[
                         {fun beh_trees:condition/2,{false,{fun beh_trees:action/2,{move_to,{xB,yB}}}}},
                         {fun beh_trees:condition/2,{true,{fun beh_trees:action/2,{move_to,{xA,yA}}}}}
                     ]}
                 ]} }
             }.

Our example tree will loop several times through the following routine:

  • First, the agent will go from A to B until this is no longer possible or acceptable (in our case, we consider that spotting a thief makes this behaviour fail). How we go from A to B is not important for the behaviour tree: a search algorithm such as A* or steering algorithms can provide the low level motor actions.
  • The agent will then pursue the “thief” (assuming the moving behaviour only stops due to spotting a thief), until this is no longer possible. Maybe the thief runs too much for some time, or the thief just disappears from sight.
  • Lastly, the agent will move to B if it is closer to B than to A (we will consider this condition to be false in our example) or to A otherwise. From there it will start again.

The Engine

To simulate an existing engine, we’ll use a simple list of “response events” which will be sent with no analysis of the action sent. Of course, this means that we know the behaviour beforehand, but, after all, this is just an example:

loop_responder(EventList) when length(EventList)&gt;0 -&gt;
    receive
        {init, Sender} -&gt;
            loop_responder(Sender, EventList, [])
    end.
loop_responder(Sender, [], EventList) -&gt;
    loop_responder(Sender, EventList, []);
loop_responder(Sender, [Event|Events], NextEvents) -&gt;
    io:format("Current: ~p - Next: ~p~n", [[Event|Events], NextEvents]),
    receive after 2000 -&gt; ok end,
    receive
        Action = {action, _ActionType, _ActionData} -&gt;
            io:format("Receive: ~p~n", [Action]),
            io:format("Send: ~p~n", [Event]),
            Sender ! Event
    end,
    loop_responder(Sender, Events, NextEvents ++ [Event]).

The event list that will be traversed by the loop engine will be defined as:

EventList2=[{event, success},
            {event, success},
            {event, success},
            {event, fail,seen_something},
            {event, fail,agent_escaped},
            {event, success}].

This auxiliary function will allow us to initialize the engine with the behaviour agent:

exec_beh_w_init(Engine,{FirstBeh, FirstParams}) -&gt;
    Engine ! {init, self()},
    FirstBeh(Engine, FirstParams).

Testing, Finally!!!

Let’s see how our agent will fare against the “world”:

(juggerlnaut1@azathoth)58&gt; Engine = spawn(beh_trees,loop_responder,[EventList2]).
&lt;0.122.0&gt;
(juggerlnaut1@azathoth)59&gt; Agent = spawn(beh_trees,exec_beh_w_init,[Engine, BehaviourTree]).
Current: [{event,success},
          {event,success},
          {event,success},
          {event,fail,seen_something},
          {event,fail,agent_escaped},
          {event,success}] - Next: []
&lt;0.124.0&gt;
(juggerlnaut1@azathoth)60&gt;
Receive: {action,move_to,{xA,yA}}
Send: {event,success}
 
Current: [{event,success},
          {event,success},
          {event,fail,seen_something},
          {event,fail,agent_escaped},
          {event,success}] - Next: [{event,success}]
Receive: {action,move_to,{xB,yB}}
Send: {event,success}
 
Current: [{event,success},
          {event,fail,seen_something},
          {event,fail,agent_escaped},
          {event,success}] - Next: [{event,success},{event,success}]
Receive: {action,move_to,{xA,yA}}
Send: {event,success}
 
Current: [{event,fail,seen_something},
          {event,fail,agent_escaped},
          {event,success}] - Next: [{event,success},
                                    {event,success},
                                    {event,success}]
Receive: {action,move_to,{xB,yB}}
Send: {event,fail,seen_something}
 
Current: [{event,fail,agent_escaped},{event,success}] - Next: [{event,success},
                                                               {event,success},
                                                               {event,success},
                                                               {event,fail,
                                                                seen_something}]
Receive: {action,pursue,{thief,10}}
Send: {event,fail,agent_escaped}
 
Current: [{event,success}] - Next: [{event,success},
                                    {event,success},
                                    {event,success},
                                    {event,fail,seen_something},
                                    {event,fail,agent_escaped}]
Receive: {action,move_to,{xA,yA}}
Send: {event,success}

We can see that our agent is capable of going from A to B (if the underlying engine provides the means to do so), of handling the unexpected event of seeing a thief, of pursuing the thief (again, using e.g. a steering algorithm), and of going back to its patrol waypoints when it loses sight of the thief. Not bad for a 2-hour agent!!!

Last Words

Of course, this is a very simplistic example. A much more detailed entity model would be necessary (e.g., a spotted agent is not necessarily a “thief”), and the low level motor and sensory components would still be missing. But this example shows how one can use Erlang to very easily write and test complex, high-level behaviour trees.

Filed under Uncategorized