Finished

Handed in my project today. Just need to work on the poster for friday

Honours Project

I am now more or less finished. All the sections are in, some of them need a few changes but nothing major. I will have to go and format the entire document which hopefully shouldnt take too long. Ive had it proof read again, still have a few comments in it where i have missed things or need to explain them more. Also still have to go through it and number all the figures etc

progress

The results write up is now finished as is most of the conclusions and future work.. Had the presentations last week, seemed to go fine. The application is now finished, will try and improve the visuals if I have time.

Ive been going through alot of the dissertation and again rewriting large sections of it, mostly to try and reduce the work count a bit. Ive had a few people read it through, including my supervisor who all agree that it would be very hard to remove parts without leaving a hole in the report. Therefore, it is going to have to stay the size it is.

progess

All the testing is now done and ive started organising the results that were dumped to text files into an excel sheet to make charts etc.

Ive spotted a few that might have to be done again.

I've now started wrting up my results section. I have finished the methodology section completely and will go back to it at a later date.

I have also briefly planned out what will be in the conclusions/ future work sections

testing

I have now fixed the problem i was having previously. Testing is now able to continue. Again, still just reading over my dissertation while running the tests as it is taking up most of my time

Progress

Managed to get more test done, however, hit a problem with the fact that it was running in release instead of debug, which meant that for some reason, a few minor changes that were made didnt actually apply to the program. This lead to several tests having to be scrapped.

To solve this, I'm going to have to completely redo several tests just to make sure that the results are fine.

As for the dissertation, I have been proof readin what i already have and rewording several sections at a time to make them read better

Testing

I have now managed to get up to test 20 which has involved running the program almost 600 times! I aim to have all the testing finished by the end of this week so that I can go back to working on my dissertation.

Update

I've spent the last few days completly re-writting sections of my dissertation. The fuzzy logic section of the literature review, as well as the FIS and FuSM sections have been reworded. The FIS and FuSM methodology has also had some re-wording and extra information put into them. Made a start on the Environment section of the methodology but decided to leave it untill the project has finished as I'm planning to redo parts of the environment code if I get the chance.

I've started writing up the results plan. There is so much that can be tested with this project that I'm having to spend a good deal of time working out what I will include in the results section along with an explanation about what the result is telling me. I can see this taking a good few days, I will mostly likely have to schedule another meeting with my technical supervisor to go over it just before I finalise it and begin the testing.

I've also for the first time been able to run the application with everything in it and the manager running which has reveled to me several hidden bugs as well as things that I had simply forgotten about. I'm going through these and trying to fix them as they come up. However, with the manager running, the ecosystem does seem to maintain itself within a state of balance which is what I had been hopeing for.

Progress

I think that is now me officially finished implmenting the techniques into the application. The fuzzy inference system now feeds the final defuzzified value as input into the fuzzy state machine which then performs transitions based upon the input. 

All that really remains to be done with the techniques now is continue to tune them so that they work better together. Some of the techniques simply feed into empty functions, these will have to added to so that they now have an effect of the ecosystem. The fuzzy state machine at the moment does not actually do anything to the plant that it is monitoring, however this should not take long to adjust.

Continued to reword my FIS implentation section. I have one last thing to check on it before it is ready to be added into the first draft of my dissertation.

Progress Update

Earlier today I managed to get a defuzzification method working on the Fuzzy Inference System within the application and am now able to return a single crisp numerical value. This value will then be fed into the FuSM. This now means that all the techniques that were going to be implemented within the application have been created and added. Now that these techniques are in place I can focus on making them work together.

More work has continued on the creating of freely growing vegetation within the environment. While in theory the methodology in place for this should work fine, after about 40 new plants have been created the graphics side of the application locks up. The program itself does not die as the console window continues to print of data as the ecosystem ages. A cause and a solution to this problem have yet to be found.

Yesterday I completely re-done the  FIS methodology section as I found some much better research on it. I now have to go back and finish off the methodology for the FIS, writing about the Defuzzification method, and then further update the FuSM.

The implmentation of the environment itself also has to be written up.

more updates

While I wait to have another discussion about my FiS within the application, I moved on to "tune up" parts of the ecosystem itself. While doing so, an architecture problem was uncovered. This problem related to how much vegetation and water could be present within the ecosystem at any one time. While on its own it does not appear to be very problematic, however since it had been continually build ontop of and the fact that several other components of the ecosystem were dependant on this a solution had to be found. The solution I was looking for would allow a limitless number of plants and lakes to be formed, simply creating new instances of the respective classes on the fly as the program ran. Two attemps at solving this earlier on were through the use of the STL - namely lists and maps. Therefore much of the day has been spent tyring to implment these as solutions. However, in the end, a much more straight forward solution was devised.

If the plant life was allowed to become unlimited, then the ecosystem itself may become to overpopulated resulting in the death of everything. Therefore an array of 100 pointers to the vegetation class was created which would remain nulled untill a new plant appears. Since the herbivores will always be eating, there will never be the full 100 plants on screen which means when one dies off completely, it can be remade in a new location, giving the impression of freely growing vegetation.

Some basic tests have been carried out with this approach, a new tree has been grown at the end of each system day. This method itself seems to be working fine, however a slighty annoying bug has developed which results occasionally in 2 plants being created instead off one as well as the positions of the lakes changing when a new tree appears.

With the dissertation, the Methodology section is almost finished, all that needs to be added to it is the end of the FIS section. Once that is done, I will need to go back and include the FIS into the RQ aswell as the literature review section as these were written before the FIS was included into the project.

EDIT:

Fixed the problem of the lakes changing position aswell as the vegetation. As it turns out, one of the positional arrays was not large enough so for some reason the data was then moving into a different array altering the positions of the lakes

FiS update

Managed to implement a Fuzzy Inference System within the application. However it still needs a proper defuzzification method applied to it. At present, it simply takes the output state with the highest DOM and uses it.

The FiS does not run constantly, it simply takes in a snapshot of the current system at the end of each "day" and then calculates the state of a specific vegetation piece. It was mentioned previously that the FiS will take in three seperate input states, however, for simplicity and untill I can implement the Combs Method effectively the FiS will only deal with two input states. These states are based on how much water is left within the system, and how much the piece of vegetation in question has been eaten. The output states of the FiS are as follows:

High yield - vegetation produces alot more resource than normal

Normal Yield - vegetation produces the standard amount

Low Yield - vegetation produces around 1/4 of the standard yield

DeadYield - the vegetation does not grow back as often

This is currently only applied to a single vegetation piece. Once the defizzufication method is applied fully, it will then be implemented on the majority of the vegetation

Progress meeting

Had my second progress meeting where I explained why I have not achieved much the last week or so. However, now that the dare application and math test are out of the way, I am now able to focus more on the honours application.

Also had a meeting with Dr. King today. I have been looking into the Combs Method for the Fuzzy Inference System. The combs method cuts down the amount of rules required by a FIS to come to a result. While this result is not as accurate as the normal method, the CPU time saved is rather helpful. It saves resource use-age by reducing the amount of rules required from an exponential equation to a linear equation which would be very helpful as has been shown in the literature review section of the dissertation, ecosystems are increadibly complex and as such would require alot of rules.

The rest of tonight and tomorrow will have to be written off as I am attending the code works, jobs in digital fair which takes place in Newcastle tomorrow. 

However, since I now have a normal fuzzy inference system running correctly (still minus the defuzzification part) I have decieded just to go ahead and implement a normal FIS into the application and then change it later when I manage to successfully implement the combs method

Week Update

Not much progress has been made this week as alot of time has been spent on the dare application as the deadline is only a few days away now. Also on the horizon is the annual Game In Scotland event which is happening on Saturday, because of this alot of time has been spent (and will continue to be spent) on polishing up demos and the CV for the event.

I had another meeting with my technical supervisor, i discussed more of my ideas and thoughts about the FIS and explained that I have been working on the AI coursework so that I can then hopefully port it over to the demonstration application once it is ready. I have now almost completly finished the methodology section and I'm now just waiting on constructiong the FIS before writing about it in the Dissertation.

I have also contined to take some of the base results from the application which will be used later for the next section of the dissertation, the results section

Progress

The math exam is over which gives me alot more time to focus on the project. The methodology section of the dissertation is coming along very well and is now almost finished. I hope to have more done on it for my meeting with my supervisor later this week. 

Since I am planning on trying out a Fuzzy Inference System (FIS) within the application, I have decided to spend more time on my A.I. coursework for Dr. King as this also entails creating a FIS. I have been doing research on FIS's reading up on several academic and other papers which has helped boost my understanding of them. I have constructed the basic FIS class (minus a defuzzification method) and have been testing it out. While it seemed to work at first, it does not return sensible values for all of the inputs, therefore I will have to spend some more time trying to find out why. 

Had my first progress meeting today. I will post up my progress report later on today

Update for this week

Unfortunately not much progress has been made with the project as a whole this week. Maths revision has continued to take up the majority of my time. Some progress has bee made with the dissertation as I continue to work away at the methodology section. Some minor additions have been made to the application, such as printing out some of the ecosystem information onto the screen. Once the math exam is over and the dare application has been submitted i should hopefully be able to concentrate more on my project as a whole

News

I have been continuing with my dissertation and have managed to make a start on the methodology section, writing up my implentation of the A-Life algorithms used within the application.

Work on the demonstration project itself has been rather slow to non existant due to other university and outside deadlines. This will most likly continue for the rest of the week therefore I do not expect much progress to be made on the application itself. There is a math class test which counts for 10% of the mathematics module on the 9th of this month, therefore alot of my time will be focused on revising for this. The deadline for the Dare to be Digital application is also looming closer which has resulted in longer dare related meetings.

I have however continued to think about how I will implement the fuzzy state machine into the demonstration application. I will also be able to continue the write up of the methodology section

Update

Since I had finished the literature review section, I had pulled together all that I had done on the dissertation so far and loosely arranged it into how it will appear in the final document. I then emailed it to my technical supervisor so that he could take a read over it so that I could have some feedback on it. I was slightly worried about the size of my literature review as it is around 6500 words alone, when the introduction, RQ, and motivation sections were added in, it came out at around 8300.

The feedback I got from the meeting was actually rather good. As it turns out my supervisor had expected this the size of my dissertation to be rather large simply because I have alot to write about. The size is going to stay the same for the time being so that I can weigh it up against the rest of the dissertation (if it turns out it is huge compared to the rest of it, then it will be cut down). 

As it turns out there were very few problems with what I had written so far, most of the things that were suggested to me was simply to reword a few senteces and then find the diagrams for the literature review section.

As for the practical side, I had a talk with my supervisor about the best way to implement the Fuzzy State Machine for the vegetation. As it stands, the FuSM can only accept one crisp input. I had been trying to use the rate at which the vegetation was increasing/decreasing as this input but with little success. We both agreed that it would probably be better if i could somehow base this input on several factors. In the end we decieded that three factors should influence the input to the FuSM: these would be the rate at which it is being eaten, the remaining herbivore population and the remaining water levels.

In order to base the input off three seperate values, a Fuzzy Inference System will be used. This would allow be to take into consideration the three input values and return a single crisp value which could then be used as input for the FuSM.

One other thing that did come out of this meeting was that allow the FuSM seems like a good idea, it may be overkill. By overkill I mean, it may be trying to be too realistic with out actually making much of a difference as it may turn out that its implemtation does not actually have a visible effect on the system. Therefore, it was decieded that it will only be applied to a handfull of vegetation as a test, if it goes well and does indeed make a difference, then it will be applied to all the vegetation.

progress

I have managed to finish the literature review section now. It still needs to be read over as there are a few sections within it that I will need to revisit and reword. I also still have to scan in a few diagrams and tables to help illustrate some of the points that have been made within this section.

Not much progress has been made on the application, seem to have hit a bit of a motivational slump with it. Some minor tweaks have been made, some of the code has been clean up and commented. The next major task in the Honours project is to implement the fuzzy state machine for the vegetation. The Fuzzy State Machine had been created near the start of the term (as I had been working on one over the winter break) . However, a lot of though needs to go into how this will actually be implemented within the application as I do not believe it will be a simple task.

Practical work and Dissertation

Work on my dissertation has continued. The Literature review section is coming along very well and should hopefully be finished soon. I have written down some thoughts on how to go about writing the Methodology section of the dissertation aswell. 

The MADTFDA is almost fully in-place. Several of the functions can now influence the application and its inhabitants. As an example of this, the function that checks for low herbivore populations and high resource amounts is able to alter the herbivores perception range (among other things) to allow them to spot food more easily etc.

Dissertation and application

I've been continuing to work on the first draft of my dissertation. I've managed to get a very large chunk of the Literature review out of the way and have finished a new introduction which is a combination of the proposal introducting, plus more up to date and more relevant information.

Hopefully I will have the first draft of the introduction and literature review finished by a week tomorrow (which will be the 26th Feb)

AS for the application, I now have acceptable boundaries within the MADTFDA. I am able to check if the data fed into the graphs is under specific thresholds (such as high population but low resources or vice versa) and also to get the threshold with the highest priority returned.

Next on the list is to actually make the manager start to alter variables to help restore the system. To do this, the variables with the largest impact will have to be found. Once this has been set up for the herbivore population, it can then be applied to the carnivores and after that the omnivores.

Further enhancements to the flocking algorithm and environment code will also have to be made, such as over grazing on areas of vegetation causing it to take longer to grow back

Practical Work and Dissertation

Started writing up my dissertation. written about 1250 words of the literature review which just now covers background reading on A-Life, fuzzy logic and eco-systems. Made a start at the previous work part as well.

On the application side, getting close to finishing enough to have a very basic model up and running. The herbivores successfully flock around the environment, avoiding obstacles. WHen they are hungry, they move over to vegetation to eat. When the vegetation drops too low, the system manager starts to grow more. Need to add in water resources and allow the manager access to the herbivores need to breed, average life expectancy and hunger rate to help control the flow. 

Practical work

Been working on combining the basic flocking model with the MADTFDA and fusm. Found a few problems with the boid and flock class feeding wrong information into the MADTFDa classes, but I think I have fixed that problem now. Will continue to combine the techniques to create the first iteration of teh basic system

Practical Work

Stopped working on my basic flocking.

Started coding the Multi-Axial Dynamic Threshold Fuzzy Decision Algorithm.

Once a basic one of these is up and running, I will need to plan out some graphs

FuSM

A basic FuSM has now been created. The initial thoughts for the FuSM was that it would represent the overall state of the entire ecosystem, however that Idea had been scrapped as ecosystems are too complex to be represented in this manner. A new idea was to have the FuSM control the desires of the entities that would inhabit the system. This would then allow the entities or agents to switch between behaviours depending on their current state(s).

Another Idea is instead to have the FuSM control the resources within the system. This would allow for factors such as over grazing and soil errosion to have an effect on how much resource is within the system.

The FuSM at present takes in a single crisp input value which is used to trigger state changes.

EDIT:

The FuSM will now be used to control only the vegetation within the system. Instead of monitoring the vegetation as a whole, it will monitor individual "trees" or "plants" making all the vegetation within the system different. Some plants will produce more than others depending on their current state

Flocking

Flocking

Flocking (sometimes known as swarming or Herding) is a technique created by Craig Reynolds in his 1987 paper for SIGGRAPH called “Flocks, Herds and Schools: A Distributed Behavioural Model”.

Five Steering Behaviours

Separation -> Steer to avoid crowding local flock mates.

Alignment -> Steer toward average heading of local flock mates.

Cohesion -> Steer to move toward average position of local flock mates.

Avoidance -> Steer to avoid running into local obstacles or enemies.

Survival->Steer to eat as needed, or to avoid being eaten if a predator is seen.

What’s interesting about these five simple behavioural rules is how life like the resulting behaviour of the boids can be.

Separation

Gives an agent the ability to try to maintain a certain separation distance from other agents in the immediate vicinity. This prevents crowding together while ensuring a “natural-looking” closeness that emulates groups in the real world.

Alignment

Provides an agent that has the ability to align itself with other agents in its immediate vicinity, (i.e. Head in the same direction and/or speed as other agents). As with separation, this accounts for alignment through each member of a flock looking at nearby flock mates and then adjusting its heading and speed to match the average of the flock.

Cohesion

Gives an agent the ability to “group” with nearby agents, emulating similar behaviour seen in nature.

Avoidance

Provides an agent with the ability to steer away from obstacles and avoid collisions. This behaviour is accomplished by giving each agent the ability to “look forward” some distance and determine whether a collision with something is likely and adjust to avoid.

Every boid is a bit different

To make each boid a bit different we would have to individualise all the boids with various parameters – range of sight, maximum speed of flight etc. We would have to allow a randomised component apon boid creation. A newly created boid would now have some “personality” making each one a little different from its fellows – some wont see well, others will see very well, some want to maintain more distance from their fellows than the norm. Some will be hungrier than the others.

Why Do This?

A couple of reasons for doing this. Both of which add to the life like behaviour of the creatures in our little world.

First, providing each boid with slightly different capabilities is simply more realistic than an endless army of clones.

Secondly, the differences will combine to provide some forms of novel emergent behaviour as out boids interact, again providing what in the end is a more realistic representation of a group of creatures moving “en masse”. The tug and pull of tow boids in the same flock, one of which wants to maintain a cohesion much tighter than it’s fellow, will make for some interesting group dynamics, as will a boid that can see an oncoming predator just a bit farther than any of his flock mates.

All of this adds overhead, but not much though.

Feeding the Flock

If follows that if were going to have classes of boids that feed on one another, we will need something to control that hunger. To represent this, each class of boids that have the ability to eat will have a hunger rating that decrements a little each update cycle. When it reaches zero, our boid will become hungry and will actively seek out prey to satisfy that hunger. Each time a boid eats, a random test will determine if it is still hungry by comparing its current hunger rating to its starting hunger rating. E.g. if a boid starts with 10 hunger points and eats 4 of those points away, theres a 40% chance it will be satisfied and stop eating.

No Memory

Note that the steering behaviours say nothing about state information or about a given agent maintaining knowledge of the flock, it’s environment, it’s heading etc. Flocking is therefore a stateless algorithm in that no information is maintained between updates, each boid re-evaluates it’s environment every update. This reduces memory requirements which might otherwise be needed for similar behaviour using other approaches/ techniques, but also allows the flock to react in real time to changing environmental conditions. The result of this is that the flocks exhibit elements of emergent behaviour. No individual boid knows about where it is going, the flock moves as a single mass, avoiding obstacles and enemies and keeps pace with each flock mate in a fluid, dynamic fashion.

How This is Useful for Computer Games

Flocking provides a powerful tool for unit motion and making more realistic environments that the player can explore. It has been used with great success in a variety of commercial titles e.g. Unreal(Epic) and HalfLife(Sierra) use flocking for many of their monsters. Enemy Nations (Windward Studios) used modified flocking to control unit formations and movement across 3D environments. Groups of animals can wander terrain in real time strategy games or RPG’s more realistically than simple scripting. Groups of archers or swordsmen can be made to realistically move across bridges or around boulders or other obstacles. Monsters in an FPS can wander the dungeon halls in a more believable fashion, avoiding players where possible but perhaps launching an attack when the flock grows large enough.

The possibilities are practically endless.

Constraints

Several constraints on the boids restrict how they move and react. Possibly the most influential is the boids perception range, which restricts how far a flock mate can “look” about its environment to detect other flock mates, potential obstacles ro enemies. The larger this range, the more organised and coherent the flocks and the better they are at avoiding enemies and obstacles. Making it smaller results in more erratic flocks, groups of boids splitting off more often when confronted by onstacles or enemies and so on.

Another constraint on how the agents can move is their velocity and max velocity change. In the real world, animals in flocks are restricted in their ability to keep up with their flock mates by how fast they can move, how fast they can turn and the like. We can simplify this problem by ignoring acceleration and focus entirely on velocity. Changes in velocity can be restricted to some proportion of the overall maximum velocity – this would prevent ridiculous bursts of speed when boids try to catch up with each other. This also provides a governing restraint on how quickly they can slow down or alter course to avoid an obstacle.

More Fuzzy Logic and FuSMs Notes

Contrary to popular belief, FuSMs are not really fuzzy logic systems. Fuzzy logic is a process by which rules expressed in partial truths can be combined and inferred from to make actual decisions. It was created because many real-world problems couldn't always be expressed (with any degree of accuracy) as finite events, and real-world solutions couldn't always be expressed as finite actions. Fuzzy logic is merely an extension of regular logic that allows us to deal with these kinds of rule sets. The simplest form of actual fuzzy logic in games (which is very common), is straighforward if. . .else statements (or their equivalents, through a data table or some kind of combination matrix) that describes changes in behaviour. For example, the statement “if my health is low, and my enemy's health is high, I should run away” is a straightforward fuzzy rule. It compares wo perceptions (my health and my enemy's health) in a fuzzy manner (low versus high) and assigns it an action (run away). This statement has probably been written as an if statement for hundreds of games over the years. This represents the barest minimum of an actual fuzzy system. A real fuzzy logic system would comprise many general fuzzy guidelines for any given combination of my health, my enemy's health, and all the other variables of concern into matrices of rules that will give me a response action through algorithmic combination of my health, my enemy's health, and all the other variables of concern into matrices of rules that will give me a response action through algorithmic combination. This tens to be a powerful way of getting results from a fuzzy system, but suffers when there are many fuzzy variables (each of which may have numerous possible value states or ranges) by creating a quickly unmanageable necessary rule set size, a problem called combinatorial explosion. This can be worked around using a statistics technique called Comb's method, which can reduce the required rule set, but also reduces accuracy.

FuSMs are rapidly becoming common in game AI usage. The predictability of FSMs is becoming undesirable, and the overall content of many games is becoming rich enough to warrant the additional design and implementation complexity of FuSMs.

FuSM definitely require more forethought than their finite brothers do. The game problem must really be broken into the most independent elements that the problem allows. An FSM could be implemented within the confines of an FuSM system, by calculating the digital activation levels and designing the system so that there is no overlap in state execution. FuSMs are not suited to the general range of problems as FSMs are. FuSMs are a kind of FSM that simply allows for the activation of multiple states as the current state, as well as being able to have a level of activation of activation to the degree that the game situation merits each state.

In fact, many people will contend that FuSMs are not even really state machines at all (because the system isn't in a solitary state) but, rather, are more like fuzzy knowledge bases where multiple assertions can be partially true at the same time. But, by coding independent states to take advantage of these multiple assertions, we can use FuSMs to accomplish our AI goals that require this kind of mechanism.

From AI GAME ENGINE PROGRAMMING 1st ED

Some Notes on Weighted Sums

Extending Simple Weighted-Sum Systems

Decision making is one of the key functions of every AI engine. There are many decision-making strategies available, but a straightforward and powerful one is the weighted sum system, in which you simply weight the available options and select the one with the highest score. This is a very flexible technique that can be applied to situations that can't be easily modelled with more traditional approaches.

It is easy to write a naïve implementation of a weighted-sum system using only a direct combination of factors. Such an approach, however, is not easily adaptable to a number of situations that appear frequently during typical game development. The result is that much time is spent tweaking and tuning weights, often by trial and error, until the observed behaviour resembles the expected one.

Much research has been devoted to decision-making in the field of artificial intelligence. Utility theory is a formalization of the intuitive process of choosing the most desirable alternative when making a decision. Utility is a number used to measure desirability for all the possible outcomes of the decision. The rational choice then is to select the option with the highest utility.

Finding a value for the utility of a decision is highly subjective: different people might assign different values to the same situation. However, calculating an exact utility value is not possible in the presence of uncertainty, which is the norm in nearly every game. If you cant predict exactly what the result of a decision is going to be, you wont be able to evaluate how much you will like it. The traditional approach in this situation is to estimate the utility according to the probability of each possible outcome. This value is called expected utility.

Each situation demands a specific algorithm to calculate the expected utility of a decision. Typically, for games we have to resort to heuristics. A general method is to observe the factors that might affect the outcome, try to predict their influence on the result (whether positive or negative), and combine them using a mathematical formula. For instance, chess programs sometimes assign a payoff value to each piece. Each piece is a factor that helps calculate a value for the state of the board. By summing these payoff values, utility scores can be computed for every board configuration.

Unlike chess, most games have several different factors. Moreover, not all factors have the same influence in the outcome: some factors are more important than others are. A simple formula for combining factors that works fairly well is the weighted sum. Factors are multiplied by weights that represent their relative importance and then added together to calculate the expected utility:

EU(A) = (SUMOF) WiFi(A)

In practice, the exact factors that affect a decision depend heavily on the specific problem domain. A factor can be anything that can be measured in the game and has some kind of influence on the result of a decision. It is the programmer's responsibility to ensure the combination of factors represents an accurate measure of the desirability of making that decision.

One of the best features of this technique is that it is very robust in the face of emergent situations. Because the factors that define the game world are considered when making decisions, the AI will be coherent and act appropriately in nearly any circumstance. Contrast this with a heavily scripted AI, which has to explicitly take into account every single possible situation. The result is either incorrect behaviour when faced with an unexpected situation, or long and complex scripts, which take a lot of time to write and debug.

TO be finished

Notes on the Combs Method

The Combs Method.

The Combs method depends on a rather simple result stemming from classical logic. The rule

'a' AND 'b' ENTAILS c

can be re-written as

(a ENTAILS c) OR (b ENTAILS c)

where ENTAILS is a Boolean operator that has it's own truth table:

a	b	A ENTAILS b
TRUE	TRUE	TRUE
TRUE	FALSE	FALSE
FALSE	TRUE	TRUE
FALSE	FALSE	FALSE

The operator 'ENTAILS' can be expressed as “IF a THEN b”. A better explanation of this would be that if 'a' is true, then 'b' must also be true. If 'a' is false then it makes no difference if 'b' is true or false.

With this rule in mind, on first glance it would appear that the third rule from the table above is incorrect.

False ENTAILS true = true.

However, this rule is actually quite logical. To help clarify the logic behind this rule, consider the following example by (Millington, I. 2006).

IF I'm-in-the-bath THEN I'm-wet

so if were in the bath(which is not empty of water), then we will obviously be wet. However, the bath may not be the only reason for being wet: getting caught in heavy rain, being splashed by a hose and so on. Therefore the above rule can still be correct when I'm-wet is true and I'm-in-the-bath is false.

What the above equates to is that we can write:

IF a AND b THEN c

or

(IF a THEN c) or (IF b THEN c)

MAKE SURE I MENTION THAT THE CONCLUSIONS FROM RULES ARE OR_ED TOGETHER, this allows us to split this new method of formatting rules into two individual rules

IF a THEN c

IF b THEN c

For clarity, the above shall be referred to as the Combs format.

Larger rules can also be expressed in this formating:

IF a1 AND . . . AND a(n) THEN c

can be re-done as

IF a1 THEN c

:

IF a(n) THEN c

This has taken us from requiring rules in all the possible state combinations to a much simpler set of rules requiring only a single state in the IF and THEN clauses. This method removes the need for multiple combinations which in turn leaves us with the number of rules equalling the number of states. This cuts the growth of rules from exponential to linear. E.g. having 10 inputs each with 5 states would result in only 50 rules compared to the unmanageable 10million rules.

When using the Combs method, all the rules have to be built from scratch. It is not possible to change a general set of rules into Combs format as truth tables using Combs format rules cannot be created or represented. While their will be examples that can convert rather easily, these are nothing more than a convenient coincidence.

As an example of this, consider the following pair of rules:

IF corner-entry AND going-fast THEN brake

IF corner-exit AND going-fast THEN accelerate

These two rules would be broken down into the following four rules:

IF corner-entry THEN brake

IF going-fast THEN brake

IF corner-exit THEN accelerate

IF going-fast THEN accelerate

Decomposing the original two rules into Combs format results in an inconsistent rule set. Rule 2 and 4 from the decomposed set contradict each other, we cannot possibly accelerate and break at the same time. Therefore which rule do we follow? The answer to this question would depend on our location within the corner.

When limiting a fuzzy system to only using the Combs format, the systems overall sophistication will unavoidably restricted. However, the tractability of rule creation allows these rules to be altered more easily (Millington, I. 2006)

It is not practical to apply the Combs method to traditional logic, the result would be incredibly restrictive. But when used with FL, where multiple fuzzy states can be active at any one time, this means that the different states can interact with each other (meaning we can both accelerate and brake at the same time, but the overall change in speed would be determined by the DOM of each state). The Combs method produces rules that are still able to produce interaction effects between all the states, even although these interactions are not explicit within the rules.

FuSM - Practical Work

Work started on building a Fuzzy Finite State Machine(FuSM) on Friday the 16th January. A very basic FuSM is now up and running although a lot of work will have to be done to it to make it suitable. However, as the project is most likely going to go through several iterations, a basic FuSM will suffice for now.

At the moment, the FuSM in place monitors the total resources (plant life and water) within the system. The program takes in an integer (which at the moment is generated by srand()) as input. 

This input will later be set to the actual total amount of resources. The input is fuzzified and it's Degree of Membership(DOM) in the appropriate states is found. This degree is then de-fuzzified and at the moment, a simple text line is printed to the console, which will later be replaced by the appropriate action.

If the input falls into two states, the highest DOM is kept and the state that the DOM applies to is stored. When the action for this state is executed, it will do so in ratio to the DOM

Fuzzy Logic Notes

Fuzzy logic is a superset of conventional (boolen) logic that has been extended to handle the concept of partial truth – truth values between “completely true” and “completely false”. It was introduced by Dr. Lotfi in the 1960's as a means to model the uncertainty of natural language.

Zadeh says that rather than regarding fuzzy theory as a single theory, we should regard the process of “fuzzification” as a methodology to generalize any specific theory from a crisp (discrete) to a continuous (fuzzy) form.

Fuzzy Subsets

Just as there is a strong relationship between Boolean logic and the concept of a fuzzy subset, there is a similar strong relationship between fuzzy logic and fuzzy subset theory.

In classical set theory, a subset U of a set S can be defined as a mapping from the elements of S to the elements of the set {0,1},

U : S → {0,1]

This mapping may be represented as a set of ordered pairs, with exactly one ordered pair present for each element of S. The first element of the ordered pair is an element of the set S, and the second element is an element of the set {0,1}. The value zero is used to represent non-membership, and the value one is used to represent membership. The truth or falsity of the statement

x is in U

is determined by finding the ordered pair whose first element is x. The statement is true if the second element of the ordered pair is 1, and the statement is false if it is 0.

Similarly, a fuzzy subset F of a set S can be defined as a set of ordered pairs, each with the first element from S, and the second element from the interval [0,1], with exactly one ordered pair present for each element of S. This defines a mapping between elements of the set S and values in the interval [0,1]. The value zero is used to represent complete non-membership, the value one is used to represent intermediate degrees of membership. The set S is referred to as the universe of discourse for the fuzzy subset F. Frequently, the mapping is described as a function, the membership function of F. The degree to which the statement

x is in F

is true is determined by finding the ordered pair whose first element is x. The degree of truth of the statement is the second element of the ordered pair.

In practice, the terms “membership function” and fuzzy subset get used interchangebly.

An Example:

Let's talk about people and “tallness”. In this case the set S (the universe of discourse) is the set of people. Let's define a fuzzy subset TALL, which will answer the question “to what degree is person x tall?” Zadeh describes tall as a linguistic variable, which represents our cognitive category of “tallness”. To each person in the universe of discourse, we have to assign a degree of membership in the fuzzy subset TALL. The easiest was to do this is with a membership function based on the persons height.

    tall(x) = { 0,                                 if height(x) <>            (height(x)-5ft.)/2ft.,       if 5 ft. <= height (x) <= 7 ft.,            1,                                    if height(x) > 7 ft. }

A graph of this looks like:  1.0 +                   +-------------------     |                  /     |                 / 0.5 +                /     |               /     |              / 0.0 +-------------+-----+-------------------                   |     |                  5.0   7.0                  height, ft. -> Given this definition, here are some example values:  Person    Height    degree of tallness -------------------------------------- Billy     3' 2"     0.00 [I think] Yoke      5' 5"     0.21 Drew      5' 9"     0.38 Erik      5' 10"    0.42 Mark      6' 1"     0.54 Kareem    7' 2"     1.00 [depends on who you ask]  Expressions like "A is X" can be interpreted as degrees of truth, e.g., "Drew is TALL" = 0.38.

http://www.cs.cmu.edu/Groups/AI/html/faqs/ai/fuzzy/part1/faq-doc-2.html

Humans have the incredible ability to communicate skills simply and accurately by using vague linguistic rules. For example, medium thickness, small amount, very close. Conventional logic is inadequate for processing such rules.

When considering linguistic terms such as “far” and “close” or “gently” and “firmly”, a human being is able to place vague boundaries on those terms and allow a value to be associated with a term to a matter of degree.

Fuzzy Logic, invented by a man named Lotfi Zadeh in the mid-sixties, enables a computer to reason about linguistic terms and rules in a way similar to humans. Concepts like “far” or “slightly” are not represented by discrete intervals, but by fuzzy sets, enabling values to be assigned to sets to a matter of a degree – a process called fuzzification. Using fuzzified values computers are able to interpret linguistic rules and produce an output that may remain fuzzy or – more commonly, especially in video games – can be defuzzified to provide a crisp value. This is known as fuzzy rule based inference, and is one of the most popular uses of fuzzy logic. [See picture, pg 417 – programming game ai by example]

crisp sets

Crisp sets have clearly defined boundaries: An object (sometimes called an element) either completely belongs to a set or it doesnt. This is fine for many problems since many objects can be precisely classified. The domain of all elements a set belongs to is called the universe of discource. [see picture – p417]

Using mathematical notation these sets can be written as:

Odd = {1,3,5,7,9,11,13,15}
Even = {2,4,6,8,10,12,14}

As is evident, the degree of membership of a number to a crisp set is either true or false, 1 or 0. The number 5 is 100 percent odd and 0 percent even. In classical set theory all the integers are black and white in this way – they are members of one set to a degree of 1 and to the other to a degree of 0. It's also worth highlighting that an element can be contained in more than one crisp set. For example, the integer 3 is a member of the set of odd numbers, the set of prime numbers, and the set of all numbers less than 5. But in all these sets its degree of membership is 1.

Set Operators

There are a number of operations that can be performed on sets. The most common are union, intersection and complement.

The union of two sets is the set that contains all the elements from both sets. The union operator is usually written using the symbol [insert symbol]. Given the two sets A = {1,2,3,4} and B={3,5,7}, the union of A and B can be written as:

A[SYMBOL]B = {1,2,3,4,5,6,7}

The union of 2 sets is equivalent to ORing the the sets together – a given element is in one OR the other.

The intersection of two sets, written using the symbol [SYMBOL], is the set containing all the elements present in both sets. Using the sets A and B from above, their intersection is written as:

A[SYMBOL]B = {3}

The intersection of two sets is equivalent to ANDing the sets together. Using our two sets above there is only one element that is in set A AND in set B, making the intersection of sets A and B {3}.

The complement of a set is the set containing all the elements in the universe of discourse not present in the set. In other words, it is the inverse of the set. Lets say the universe of discourse of A and B is A[SYMBOL]B as given in equation(above) then A's complement is B, and B's complement is A. The complement operator is usually written using the ' symbol, although some times it is denoted by a bar across the top of the sets name.

Fuzzy Sets

Crisp sets are useful but problematic in many situations. For instance, lets examine the universe of discourse of all IQ's, and lets define sets for Dumb, Average and Clever like so:

Dumb = {70 . . .89}

Average = {90 . . .109}

Clever = {110. . . 129}

A graphical way of showing these crisp sets is shown below. Note how the degree of membership of an element in any of the sets can be either 1 or 0.

More still to come