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