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 weightsData 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: EBM, open source
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
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: artificial intelligence, enem, interactive content, machine learning, nem, paper
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: EMR, Health Information System, healthcare, HIS, openEHR, PatientOS
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);
endBasically, 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,fleeThis 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,fleeThe 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
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}) ->
Engine ! {action, Action, Params},
receive
{event,success} ->
{success};
{event,fail,Reason} ->
{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, []) ->
{success};
seq_behaviours(Engine, [{FirstBeh, FirstParams}|RestBeh]) ->
case FirstBeh(Engine, FirstParams) of
{success} ->
seq_behaviours(Engine,RestBeh);
UnhandledEvent = {fail, _} ->
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, []) ->
{fail,no_more_actions};
alt_behaviours(Engine, [{FirstBeh, FirstParams}|RestBehs]) ->
case FirstBeh(Engine, FirstParams) of
{success} ->
{success};
{fail, _} ->
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}}) ->
case FirstBeh(Engine, FirstParams) of
{success} ->
loop(Engine,{always,Behaviour});
UnhandledEvent = {fail, _} ->
UnhandledEvent
end;
loop(_Engine,{0,_Behaviour}) ->
{success};
loop(Engine,{N,Behaviour={FirstBeh, FirstParams}}) ->
case FirstBeh(Engine, FirstParams) of
{success} ->
loop(Engine,{N-1,Behaviour});
UnhandledEvent = {fail, _} ->
UnhandledEvent
end.Condition Node
A Condition node succeed if the condition evaluates to true and the child node succeeds.
condition(Engine,{Condition, {Beh,Params}}) ->
if Condition ->
Beh(Engine, Params);
true ->
{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)>0 ->
receive
{init, Sender} ->
loop_responder(Sender, EventList, [])
end.
loop_responder(Sender, [], EventList) ->
loop_responder(Sender, EventList, []);
loop_responder(Sender, [Event|Events], NextEvents) ->
io:format("Current: ~p - Next: ~p~n", [[Event|Events], NextEvents]),
receive after 2000 -> ok end,
receive
Action = {action, _ActionType, _ActionData} ->
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}) ->
Engine ! {init, self()},
FirstBeh(Engine, FirstParams).Testing, Finally!!!
Let’s see how our agent will fare against the “world”:
(juggerlnaut1@azathoth)58> Engine = spawn(beh_trees,loop_responder,[EventList2]).
<0.122.0>
(juggerlnaut1@azathoth)59> 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: []
<0.124.0>
(juggerlnaut1@azathoth)60>
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
