Working Decision Trees and ID3 algorithm!

YAY!! It works!!

I spent today working on getting the navigation of the tree working so that I can start putting it into my OGRE application and start the final stages of my project.

Luckily and to my gratitude, it worked nearly first time with no major errors or mistakes. So right now, the program reads in past examples, calculates the entropy of each of the attributes that make up the examples, and builds a tree based on this. This tree is then navigated until a leaf node is reached at which point the PerfromAction() method is called. This function will no doubt become a lot more complicated as more decision trees are added to the project, but right now, it prints out either “ATTACK!!” or “Don’t attack” based on the outcome of the tree.

This was a big step and because it happened so quickly I can make a start on the graphics app now. The application will be simple to start of with, but will ultimately provide the basis for the final demonstration. It is my aim for this first demonstration that I will have a number of characters in the scene, each representing different tribes, loyalties, and strengths. An intelligent agent will then be added to the scene and will perform an action in front of each of these characters depending on the results of the decision tree. While this is a simple demonstration, it is enough to put across the idea of the final project. This will then be expanded once complete.

Update – 25/03/2009

Ok, so so far this week progress has been pretty good. The combining of the two techniques took a little longer than I first thought so I’m a little bit behind again. Although that is changing fast.

I was experiencing a problem in splitting the list of examples up so that only relevant examples were passed down the tree, but this was solved and now works perfectly. This was the part that took the longest and now this is done I can make some proper headway.

With this problem now solved, it was only a short step into building the tree properly. This step was almost seamless. It took a little over an hour and worked first time, meaning I finally have a decision tree built on past examples using the ID3 algorithm!! YAY!! The most annoying part of this process so far has definitely been that the most time consuming parts to code as the “little” things. What I mean by this is that most of my time has been spent fighting with entropy and lists of examples, but actually building the damn tree took all of 5 seconds by comparison. Still I guess that’s programming though eh?

I’m hoping to have the function that navigates the tree finished tonight or early tomorrow afternoon. If this is the case and there are no complications then I’ll be able to crack on with putting these classes into my OGRE application to give life to the model that my artist (Fei Hoi) kindly put together for me. I’ll put up another post when I get the tree navigation stuff in, but until then….have a video of the animations I’ll be using in the main application.

Update – 19/03/2009

So I thought I’d post a quick update regarding my progress over the last week and what I plan on doing over the course of this week and what's left to do for the remainder of the project.

So this last week has been a busy week so the project took a little bit of a back seat. However that's not to say that nothing was done….just very little! The next step in the project is putting the decision tree code and the ID3 algorithm together to finish of the main crux of the project. This was a big step that needed to be coded carefully and efficiently so I spent most of my time this week planning out this process. Now that it is clear in my mind the coding should fall into place fairly easily with little or no hassle.

So this week it implementation time! I’m hoping to have this in place by the end of 21/03/2009 leaving the rest of the week to make a start on the graphical aspect of the project.

So after this is done, all that’s left to do is refine the project and build upon this foundation  to take into account the decision that will need to be made for the demo. A certain amount of optimization and cleaning up code will be required as well so as to assure that the code runs at the optimal speed, not wasting any processing power that could be used elsewhere.

Who knows? Maybe my next post will include a short video of a guy moving about making decision!!

Progress Report

Over the last few weeks I have been progressing steadily in an attempt to finish my honours project by the set deadline. I have progressed in both the practical side and the technical writing side of the project and this report will outline this.

The progress I have made in the practical side of things, whilst hindered by small errors, has been mostly steady. So far I have created the graphical framework that the AI will be based in. During this process, I was slowed down by having to revise how the engine works and dealing with other problems that cropped up along the way. It is still in the early stages, but by having this completed so early in the term, I am now safe in the knowledge that something will appear on screen by the end of the project.

I have also made good headway on the actual AI itself. I have created a small basic application that creates decision trees. This is the ground work on what will be the final application. At the moment it is hard coded and only can only be navigated by the user. By the end of the project the application will build these trees based on the past experiences of the AI agent dynamically, reaching the most appropriate decision, for that scenario.

To further this goal, most my recent work has been put into implementing the ID3 algorithm. This algorithm uses the concept of entropy and the “knowledge” of the intelligent agent to build tree decision tree. So far this has been the most challenging aspect of the project so far and as a result I am slightly behind as to where I should be based on the time line I set myself at the start of the year. Despite this set back it is a crucial part of the program and without it none of the rest of the project will matter. However after a few extra days on solving this problem I have managed to solve the issues and am now finished creating the algorithm that will eventually lead to a decision tree being created.

The writing is also starting to take shape. At the moment, I have separated the dissertation into the sections that I believe will be the most crucial. As I progress or an issue occurs, I write short notes under the appropriate section. As of right now, I have written a draft abstract, 700 words of the introduction and around 500 words of notes on the two mentioned techniques. It is hoped that these notes will be used and the gaps filled in at the end of the project and the dissertation finished with little or no trouble.

The next step that I plan to take in the project implementation is to combine the ID3 algorithm and the decision tree code so that an AI agent can actually make decisions. This should take no longer than one week to complete as I believe I may have to make slight changes to the structure of the code I have already written in order for the two to fit together. However once this is finished the main hurdle for the project has been overcome and the project needs only be refined.

As I have already said I am now slightly behind in the project, I hope to make up a lot of time over the coming weeks after the two techniques have been merged. I set myself probably more time that absolutely necessary to complete the graphical aspect of the project so I should be able to make up time at this stage provided all things go smoothly. Please see below for an updated Gannt Chart for further information as to the changes in the time line.

Progress and ID3

Made some progress this week, mainly focussed around implementing a version of the ID3 algorithm. So far the code reads in a text file of examples that will later be used to generate the decision tree. This presented a bit of a tricky situation. Obviously the code needs to be as flexible as possible so that different decision trees can be created simply by loading in a different example set. Basically I had to resort to writing a rudimentary tool to load in the file, parse it to make sure it makes sense and then convert the text into useful values for the code. There are still a few little bugs that need to be sorted out but in general I'm nearly there.

At this point I should probably go into a little more detail about the ID3 algorithm. The ID3 algorithm is a method of creating a decision tree based on past experience to introduce learning to an intelligent agent. For example, if a decision tree was to be created as to whether or not to attack an enemy, the algorithm would take into account the entities strength, health, weaponry and the enemies strength, health and weaponry and use past experience and previous outcomes to build and navigate the tree effectively and realistically. ID3 uses entropy to decide which attributes weighs more heavily on the on the decision and split the tree accordingly. Entropy is a measure of uncertainty that gives an accurate yet not perfect way of finding the most efficient way to build the tree.

The advantage to using this method is that a new tree can be generated quickly and easily when an agent learns something new about its environment and thus the agent can act accordingly.

Update - Better late than never!

OK, so its been a while but i figured it was about time I reported on my progress so far.

We've been back a few weeks now and so far the majority of the time has been taken up by the busy work of getting the framework up and running. It took longer than I expected to re familiarise myself with OGRE and as a result I'm a little bit behind in my plan.

The first problem encountered was getting the new version of OGRE working and creating a window, sounds simple? Of course it wasn't! The new version of OGRE required newer versions of other libraries, which I didn't have. However once this was discovered everything came together fairly quickly.

It is essential that some sort of GUI is Incorporated into the application so that the user can navigate and interact with the environment as they desire. For this reason CEGUI was Incorporated into the framework. This again proved to be far more troublesome that it should have been. While the GUI libraries have now been successfully included into the framework, they are still not functional within the program. It is hoped that this problem with reveal itself soon, but enough time has been spent focusing on this so it has been put onto the back burner for now. I also said that there would be a level of audio in the application so FMOD has been included and a sound manager added so that audio can be added when the time comes. This was comparatively easy (thank god) so didn't take up much time.

The rest of the time has been spent into further research and application of decision trees. I created a simple application where a decision tree is used to establish what someone should do with their spare time. Currently it is hard coded and not generated from a data set. It also requires user input and does not reach a decision by itself. Its a trivial example, but its a start and hopefully I'll be able to build upon this soon.

The next two weeks will be spent building upon the start I've made with the decision trees application. It is my aim to have the ID3 algorithm included by then.
This algorithm builds a decision tree based on a data set. It builds the tree in a way that aims to reach the final decision as quick as possible. It can do this via the use of probability or entropy. I'm not sure which way will work the best so I will attempt to implement both and see which one works better.

I also want to make some head way on the graphical side of things. I hope to have a basic version of the environment and camera included soon, so that I can get some intelligent agents in as soon as possible.

Worksheet 4

Introduction

With non player characters becoming more and more important to the next generation of games, it is an area of games that warrants further research to develop these characters to act within the realms of believability. Communities of characters that are able to act based on there own knowledge and environmental factors could possibly be the next step for artificial intelligence in games. The aim of this project will be to determine whether or not it is possible to incorporate cognitively modeled, self animating non player characters (NPC's) on a mass scale within a games environment. This will allow for communities of game characters that can think for themselves and act somewhat realistically and independently of player input. This could be used in many game applications where NPC’s are used heavily throughout such as role playing games (World of Warcraft, Fable 2) and real time strategy games (Command & Conquer, Dawn of War).

Issues

Games such as Assassins Creed and Fable 2 both use NPC’s heavily and both somewhat fail on the believability of these characters. When they are not walking aimlessly around there environment they quiet often partake in walking into walls, standing still and watching when the player assaults a stranger on the street and generally acting strangely. These are 2 example are next generation games and it seems that the AI for the NPC’s is lacking greatly for them both, and it is unacceptable in games of this caliber.
Issues will include avoiding bugs and other behavior related issues that other games have fallen into. While this is the ideal, I do not expect to create a perfect system or to out perform a professional games company, it is simply the aim to try and avoid some of the more basic and aesthetically annoying bugs within that occur regularly in games.
The two main issues that will have to be addressed are that of performance and believability of the actions the character takes. The application will have to incorporate a blend of both these as one is no more important than the other…if the game runs smooth and the character behaves irrationally then no improvement has been made, but if the characters act realistically and the games runs below an acceptable frame rate then the technique will have to be dropped. Finding the right mix will be the most difficult task and the final result may suffer from this decision if the wrong one is made.

Research question

"Is it possible to implement cognitively modeled, self animating non-player characters into a computer game on a mass scale and if so what is the best method for achieving this?"

Addressing the Question

I will need to create a basic 3D game engine as an environment for the NPC's. This will most likely be created using the OGRE graphics rendering engine to try and save time, as it would require minimum work to set up fully. For it to be a realistic interpretation of a game, collision detection, accurate lighting, multiple environmental models and audio will need to be included in this, again OGRE allows for all of these. Once this has been completed I will create the systems which will animate the NPC's. Based on current research it is the plan to try and implement at least 2 and possibly 3 techniques to do this. The first technique will be a fuzzy logic based system, and the second will be an implementation of a technique known as “Situation Calculus”. If time allows the third technique that will be implemented will be a decision tree system. These will be integrated into the game engine and NPC's will be added until the frame rate drops below an acceptable level. The number of NPC's the environment can hold will be the initial bases for my results (the more NPC's that can be contained in the environment, the better) and the secondary criteria of the accuracy of the NPC's actions will be tested after this.

Progress

So far progress has been limited to research into the techniques that will be used. Through this research it has been decided that a comparative study may not be the best course of action. The length of time to develop the application may not be enough to produce a study into the three techniques mentioned earlier. A better course of action may be to pick one method and develop that as far as possible to the same end. More research will be carried out to determine what technique will be the best for this and whether or not it is the best course of action to take. A period of three days has been set to decide once and for all what route to take.
After this period has been passed, I will start to create the environment that the characters will be placed into. The sooner that this is up and running the more work can be carried out on the AI side of things.