Fuzzy Logic

Fuzzy logic is the last technology I'm going to cover and perhaps one of the most interesting. It has to do with making deductions about the fuzzy set theory. In other words, fuzzy logic is a method of analyzing sets of data such that the elements of the sets can have partial inclusion. Most people are used to crisp logic, where something is either included or not. For example, if I created the sets child and adult, I would fall into the adult category and my three-year-old nephew would be part of the child category. That's crisp logic.

Fuzzy logic, on the other hand, allows objects to be contained within a set even if they aren't totally in the set. For example, I might say that I'm 10% part of the child set and 100% part of the adult set. Similarly, my nephew might be 2% part of the adult set and 100% part of the child set. These are fuzzy values. Also, you'll notice that they don't have to add up to 100%—they can be more or less—because they don't represent probabilities, but rather inclusion in different classes. However, the probabilities of an event or state in different classes still must add up to 1.0.

The cool thing about fuzzy logic is that it enables you to make decisions based on fuzzy or error-ridden data that are usually correct. You can't do this with a crisp logic system: If you're missing a variable or input, it won't work. But a fuzzy logic system can still function well with missing variables, just like a human brain. I mean, how many decisions do you make each day that feel fuzzy to you? You don't have all the facts, but you're still fairly confident about the decisions.

That's the two-cent tour of fuzzy logic. Its applications to AI in the areas of decision making, behavioral selections, and input/output filtering should be obvious. With that in mind, let's take a look at the various ways fuzzy logic is implemented and used.

Normal Set Theory

A normal set is simply a collection of objects. To write a set, use a capital letter to represent it and then place the elements contained in it between braces, separated by commas. Sets can consist of anything: names, numbers, colors, whatever. Figure 12.35 illustrates a number of normal sets.

For example, set A = {3,4,5,20} and set B = {1,3,9}. There are many operations that you can perform on these sets:

Element of (e)— When talking about a set, you might want to know if an object is contained within the set. This is called set inclusion. Hence, if you wrote "is 3 e A," or "is 3 an element of A," that would be true. But "2 e B" is not.

Union ()— This operator takes all the objects that exist in both sets and adds them into a new set. If an object appears in both sets initially, it is only added to the new set once. As a result, A B = 1,3,4,5,9,20}.

Intersection ()— This operator takes only the objects that the two sets have in common. Therefore, A B = {3}.

Subset of ()— Sometimes you want to know if one set is wholly contained in another. This is called set inclusion or subset of. Therefore, {1,3} B, which reads "the set {1,3}is a subset of B." However, A B, which reads "A is not a subset of B."

Okay, that's a little set theory for you. Nothing complicated, just some terminology and symbols. Everyone works with set theory every day; they just don't know it. The one thing I want you to get from this section is that normal sets are exact. It's either a fruit or it's not. Either 5 is in the set or it's not. This is not the case with fuzzy set theory.

Fuzzy Set Theory

The problem with computers is that they're exact machines, yet we continually use them to solve inexact or fuzzy problems—or at least we try to. In the '70s, computer scientists started applying a technique of mathematics called fuzzy logic, or uncertainty logic, to software programming and problem solving. The fuzzy logic that we're talking about here is really the application of fuzzy set theory and its properties. Let's take a look at the fuzzy set theory version of everything you just learned about with normal set theory.

With fuzzy set theory, you don't focus so much on the objects in the set anymore; the objects are in the set, but you focus on the degree of membership a particular object has within a certain class. For example, let's create a fuzzy class or category called Computer Special FX. Then take a few of your favorite movies (mine, at least) and estimate how much each of them fits in this fuzzy class. See Table 12.4.

Table 12.4. Degree of Membership for Computer Special FX class

Movie	Degree of Membership in Class
Antz	100%
Forrest Gump	20%
The Terminator	75%
Aliens	50%
The Matrix	90%

Do you see how fuzzy all this is? Although The Matrix had some really killer computer-generated effects, the entire movie Antz was computer-generated, so I have to be fair. However, do you agree with all these percentages? Antz is totally computer-generated and is an hour and 20 minutes, and Forrest Gump has only five minutes total of computer-enhanced imagery. Is it fair to rate Gump at 20 percent? I don't know. That's why we're using fuzzy logic.

Anyway, you write each fuzzy degree of membership as an ordered pair of the form "{candidate for inclusion, degree of membership}". Therefore, for the movie example you would write "{ANTZ, 1.00}, {Forrest Gump, 0.20}, {Terminator, 0.75}, {Aliens, 0.50}, {The Matrix, 0.9}". Finally, if you had the fuzzy class Rainy, what would you include today as? Where I live, for example, it's "{today, 1.00}"!

Now you can add a little more abstraction and create a full fuzzy set. In most cases, this is an ordered collection of the degrees of membership (DOM) of a set of objects in a specific class. For example, in the class Computer Special FX, you have the set composed of the degrees of membership: A = {1.0, 0.20, 0.75, 0.50, 0.90}. There's one entry for each movie—each variable represents the DOM of each movie as listed in Table 12.4, so the order counts!

Now, suppose that you have another set of movies that all have their own degrees of membership: B = {0.2, 0.45, 0.5, 0.9, 0.15}. Let's apply some of the set operations you've learned about and see the results. Before you do, there's one caveat: Because we're talking about fuzzy sets that represent degrees of membership, or fitness vectors of a set of objects, many set operations must have the same number of objects in each set. This will become more apparent when you see what the fuzzy set operators do below.

Fuzzy union ()— The union of two fuzzy sets is the MAX of each element from the two sets. For example, with fuzzy sets:

A={1.0, 0.20, 0.75, 0.50, 0.90}
B={0.2, 0.45, 0.5, 0.9, 0.15}

The resulting fuzzy set would be the MAX of each pair:

A  B  = {MAX(1.0,0.2), MAX(0.20,0.45),
          MAX(0.75,0.5), MAX(0.90,0.15)} = {1.0,0.45,0.75, 0.90}

Fuzzy intersection ()— The intersection of two fuzzy sets is just the MIN of each element from the two sets. For example, with fuzzy sets:

A={1.0, 0.20, 0.75, 0.50, 0.90}
B={0.2, 0.45, 0.5, 0.9, 0.15}
A  B  = {MIN(1.0,0.2), MIN(0.20,0.45),
          MIN(0.75,0.5), MIN(0.90,0.15)} = {0.2,0.20,0.5, 0.15}

Subsets and elements have less meaning with fuzzy sets than with standard sets, so I'm skipping them. However, the complement of a fuzzy value or set is of interest. The complement of a fuzzy variable with degree of membership x is (1-x), so the complement of A, written A', is computed as

A = {1.0, 0.20, 0.75, 0.50, 0.90}

Therefore:

A' = {1.0 - 1.0, 1.0 - 0.20, 1.0 - 0.75, 1.0 - 0.50, 1.0 - 0.90}
      = {0.0, 0.8, 0.25, 0.5, 0.1}

I know this is killing you, but bear with me.

Fuzzy Linguistic Variables and Rules

All righty, then! Now that you have an idea about how to refer to fuzzy variables and sets, let's take a look at how you're going to use them in game AI. You're going to create an AI engine that uses fuzzy rules, applies fuzzy logic to inputs, and outputs fuzzy or crisp outputs to the game object being controlled. Take a look at Figure 12.36 to see this graphically.

When you put together normal conditional logic, you create a number of statements, or a tree with propositions of the form

if X AND Y then Z

or

if X OR Y then Z

The X and Y variables are called the antecedents, and Z is called the consequence. However, with fuzzy logic, X and Y are fuzzy linguistic variables, or FLVs. Furthermore, Z can also be an FLV or a crisp value. The key to all this fuzzy stuff is that X and Y represent fuzzy variables, so they're not crisp. Fuzzy propositions of this form are called rules, and ultimately they're evaluated in a number of steps. You don't evaluate them like this:

if EXPLOSION AND DAMAGE then RUN

and execute the RUN consequence if EXPLOSION is TRUE and DAMAGE is TRUE. With fuzzy logic, the rules are only part of the final solution. The fuzzification and defuzzifaction are what produce the final result.

FLVs represent fuzzy concepts that have to do with a range. For example, let's say that you want to classify the distance between the player and the AI object with three different fuzzy linguistic variables (names, basically). Take a look at Figure 12.37. It shows a fuzzy manifold or surface, which is composed of three different triangular regions that I have labeled as follows:

NEAR	Domain range (0 to 300)
CLOSE	Domain range (250 to 700)
FAR	Domain range (500 to 1000)

The input variable is shown on the x-axis and can range from 0 to 1000. This is called the domain. The output of the fuzzy manifold is the y-axis and ranges from 0.0 to 1.0. For any input value x_i (which represents range to player in this example), you compute the degree of membership (DOM) by striking a line vertically, as shown in Figure 12.38, and computing the Y value(s) at the intersection(s) with each fuzzy linguistic variable's triangular area.

Each triangle in the fuzzy surface represents the area of influence of each fuzzy linguistic variable (NEAR, CLOSE, FAR). In addition, the regions overlap a little—usually 10-50 percent. This is because when NEAR becomes CLOSE and CLOSE becomes FAR, you don't want the value to instantly switch. There should be a little overlap to model the fuzziness of the situation. This is the idea of fuzzy logic.

Let's recap for a moment. We have rules that are based on fuzzy inputs from the game engine, environment, and so on. These rules may look like normal conditional logic statements, but they must be computed using fuzzy logic because they're really FLVs that classify the input(s) with various degrees of membership.

Furthermore, the final results of the fuzzy logic process may be converted into discrete crisp values, such as "fire phasers," "run," or "stand still," or converted into a continuous value such as a power level from 0–100. Or you might leave it fuzzy for another stage of fuzzy processing.

Fuzzy Manifolds and Membership

It's all coming together, so just hang in there. Now you know that you're going to have a number of inputs in your fuzzy logic AI system. These inputs are going to be classified into one or more (usually more) fuzzy linguistic variable FLVs (which represent some fuzzy range), and then you're going to compute the degree of membership for each input in each of the FLV's ranges. In general, at range input x_i, what is the degree of membership in each fuzzy linguistic variable NEAR, CLOSE, and FAR?

Thus far, the fuzzy linguistic variables are areas defined by symmetrical triangles. However, you can use asymmetrical triangles, trapezoids, sigmoid functions, or whatever. Take a look at Figure 12.39 to see other possible FLV geometries.

In most cases, symmetrical triangles (symmetrical about the x-axis) work fine. You might want to use trapezoids, though, if you need a range in the FLV that is always 1.0. In any case, to compute the degree of membership (DOM) for any input x_i in a particular FLV, you take the input value x_i and then project a line vertically and see where it intersects the triangle representing the FLV on the y-axis. This is the DOM.

Computing this value in software is easy. Let's assume that you're using a triangular geometry for each FLV, with the left and right starting points defining the triangle labeled min_range, max_range, as shown in Figure 12.40.

To compute the DOM of any given input x_i, the following algorithm can be used:

// first test if the input is in range
if (xi >= min_range && xi <= max_range)
   {
   // compute intersection with left edge or right
   // always assume height of triangle is 1.0

   float center_point = (max_range + min_range)/2;

   // compare xi to center
   if (xi <= center_point)
      {
      // compute intersection on left edge
      // dy/dx = 1.0/(center – left)
      slope = 1.0/(center_point – min_range);

      degree_of_membership = (xi – min_range) * slope;
      } // end if
   else
      {
      // compute intersection on right edge
      // dy/dx = 1.0/(center – right)
      slope = 1.0/(center_point – max_range);

      degree_of_membership = (xi – max_range) * slope;

      }// end else

   }// end if
else // not in range
   degree_of_membership = 0.0;

Of course, the function can be totally optimized, but I wanted you to see what was going on. If you had used a trapezoid instead, there would be three possible intersection regions to compute: the left edge, the plateau, and the right edge.

In most cases, you should have at least three fuzzy linguistic variables. If you have more than three, try to keep the number odd so there's always one variable that is centered. Otherwise you might have a trough or hole in the center of the fuzzy space.

In any case, let's take a look at some examples of computing the degree of membership of your previous fuzzy manifold, shown in Figure 12.37. Basically, for any input x_i, you project a line vertically and determine where it intersects each of the FLVs in the fuzzy manifold. The line might intersect more than one FLV, and this needs to be resolved. But first, let's get some DOMs.

Assume that you have input ranges x_i = { 50,75,250,450, 550,800}, as shown in Figure 12.41.

In that case, the degrees of membership for each FLV—NEAR, CLOSE, FAR—can be computed with the algorithm or read off graphically. They're listed in Table 12.5.

Table 12.5. Computations of Degree of Membership for Range Manifold

Degree of Membership Input "Range to target" xi	NEAR	CLOSE	FAR
50	0.33	0.0	0.0
75	0.5	0.0	0.0
250	0.33	0.0	0.0
450	0.0	0.88	0.0
550	0.0	0.66	0.20
800	0.0	0.0	0.80

Studying the values, there are a number of interesting properties. First, note that for any input value x_i, the results of membership don't add up to 1.0. Remember, these are degrees of membership, not probabilities, so this is okay.

Secondly, for some x_i's the DOM falls within one or two different fuzzy variables. There could have easily been cases where an input fell into all three regions (if I made the triangles big enough). The process of selecting the size (range) of each triangle is called tuning, and sometimes you may have to do this repeatedly to get the results you want. I tried to pick ranges that worked out nicely for examples, but in real life you may need more than three FLVs. And they may not have nice endpoints that are all multiples of 50!

For an example of creating a fuzzy manifold for some input and a number of FLVs, check out DEMO12_9.CPP|EXE on the CD. It enables you to create a number of fuzzy linguistic variables—that is, categories for some input domain. Then you can input numbers and it gives you the degree of membership for each input. It's a console application, so compile appropriately. The data printed for membership is also normalized to 1.0 each time. This is accomplished by taking each DOM and dividing by the sum of DOMs for each category.

At this point you know how to create a fuzzy manifold for an input x_i that is composed of a number of ranges, each of which is represented by a fuzzy linguistic variable. Then you select an input in the range, compute the degree of membership for each FLV in the manifold, and come up with a set of numbers for that particular input. This is called fuzzifaction.

The real power of fuzzy logic comes into play when you fuzzify two or more variables, connect them with if rules, and see the output. To accomplish this step, first you have to come up with another input to fuzzify—let's call it the power level of the AI bot that you're moving around. Figure 12.42 shows the fuzzy manifold for the power level input.

The fuzzy linguistic variables are as follows:

WEAK	Domain range (0.0 to 3.0)
NORMAL	Domain range (2.0 to 8.0)
ENERGIZED	Domain range (6.0 to 10.0)

Notice that this fuzzy variable domain is from 0 to 10.0, rather than 0 to 1000 as is the range to player variable. This is totally acceptable. You could have added more than three FLVs, but three makes the problem symmetrical. To process both fuzzy variables, you need to construct a rule base and then create a fuzzy associative matrix, so let's talk about that next.

Fuzzy Associative Matrices

Fuzzy associative matrices, or FAMs, are used to infer a result from two or more fuzzy inputs and a given rule base and output a fuzzy or crisp value. Figure 12.43 shows this graphically.

In most cases, FAMs deal with only two fuzzy variables because this can be laid out in a 2D matrix; one variable represents each axis. Each entry in the matrix is the logical proposition "if Xi AND Yi then Zi," where Xi is the fuzzy linguistic variable on the x-axis, Yi is the fuzzy linguistic variable on the y-axis, and Zi is the outcome—which may be a fuzzy variable or crisp value.

To build the FAM, you need to know the rules and the outputs to put in each of the matrix entries. In other words, you need to make a rule base and decide on an output variable that is either crisp or linear. A crisp output would be {"ATTACK", "WANDER", "SEARCH"}, while a linear output might be a thrust level from (0 to 10). Obtaining either one is relatively the same; in both cases, you have to defuzzify the output of the FAM and find the output.

You're going to see examples of both a crisp singular output that selects a class and one that simply outputs a value in a range. Much of the setup is the same. First, let's see the example that computes a range as the final output:

In general, if you have two fuzzy inputs and each input has m FLVs, the fuzzy associative matrix will have dimension mxm. And since each element represents a logical proposition, this means you need nine rules (3x3 = 9) that define all possible logical combinations and the output for each.

However, this is not necessary. If you only have four rules, the other outputs are just set to 0.0 in the FAM. Nevertheless, I will use up all nine slots in our example to make it more robust. For an output, I'm going to use the fuzzy output thrust level, which I'm going to make a fuzzy variable that is made up of the following fuzzy categories (FLVs):

OFF	Domain range (0 to 2)
ON HALF	Domain range (1 to 8)
ON FULL	Domain range (6 to 10)

The fuzzy manifold for these FLVs is shown in Figure 12.44.

Note that the output could have more categories, but I decided to pick three. Here are my somewhat arbitrary rules:

Input 1: Distance to player.

NEAR

CLOSE

FAR

Input 2: Power level of self.

WEAK

NORMAL

ENERGIZED

Output: Internal navigational thrust level (speed).

OFF

ON HALF

ON FULL

Rules: Somewhat made up (I'm a doctor, not a magician).

if NEAR AND WEAK then ON HALF
if NEAR AND NORMAL then ON HALF
if NEAR AND ENERGIZED then ON FULL

if CLOSE AND WEAK then OFF
if CLOSE AND NORMAL then ON HALF
if CLOSE AND ENERGIZED then ON HALF

if FAR AND WEAK then OFF
if FAR AND NORMAL then ON FULL
if FAR AND ENERGIZED then ON FULL

These rules are heuristic in nature, imparting knowledge from an "expert" about what the AI should do in these conditions. Although the rules may seem somewhat contradictory, I did think about them for about two minutes! Seriously, now that you have the rules, you can finally fill in the fuzzy associative matrix completely, as shown in Figure 12.45.

Processing the FAM with the Fuzzified Inputs

To use the FAM, do the following:

Get the crisp inputs for each fuzzy variable and fuzzify them by computing their DOM for each FLV. For example, let's say that you have the following inputs:

Input 1 Distance to player = 275

Input 2 Power level = 6.5

To fuzzify these, input them into the two fuzzy manifolds and compute the degree of membership for each fuzzy variable for each input. Refer to Figure 12.46.

Figure 12.46. Some inputs plugged into the fuzzy variables.

For Input 1 = 275, the degree of membership of each FLV is as follows:

NEAR	0.16
CLOSE	0.11
FAR	0.0

For Input 2 = 6.5, the degree of membership of each FLV is as follows:

WEAK	0.0
NORMAL	0.5
ENERGIZED	0.25

At this point, refer to the fuzzy associative matrix and test the rule in each cell to see what its output value is based on in the preceding fuzzy values. Of course, many of the FAM's cells will be 0.0 because two of the FLVs (one from each input) are 0.0. Anyway, take a look at Figure 12.47, which depicts your FAM along with all the cells that have non-zero outputs shaded in.

Now here comes the tricky part… Each one of those cells in the FAM represents a rule. For example, the upper-left cell represents

if NEAR AND WEAK then ON HALF

To evaluate this rule, take the antecedents and test them using a MIN() rule for the logical AND. In this case, you have that NEAR = 0.16 and WEAK = 0.0, hence:

if (0.16) AND (0.0) then on HALF

This is computed using the MIN() function as

(0.16) _ (0.0) = (0.0)

Thus, the rule doesn't fire at all. On the other hand, let's take a look at the rule

if CLOSE AND ENERGIZED then ON HALF

This means

if (0.11) AND (0.25) then ON HALF

which, computed using the MIN() function, is

(0.11) _ (0.25) = (0.11)

A-ha! The rule ON HALF fires at a level of 0.11, so you place that value in the FAM associated with the rule ON HALF at the intersection of CLOSE and ENERGIZED. Continue this process for the whole matrix until you've found all nine entries. This is shown in Figure 12.47.

At this point, you're finally ready to defuzzify the FAM. This can be accomplished in a number of ways. Basically, you need a final crisp value that represents the thrust level from (0.0 to 10.0). There are two main ways to compute this: You can use the disjunction or MAX() method to find the value, or you can use an averaging technique based on the fuzzy centroid. Let's take a look at the MAX() method first.

Method 1: The MAX Technique

If you look at the FAM data, you have the following fuzzy outputs:

OFF	(0.0)
ON HALF	{0.16, 0.11, 0.16}, use sum which is 0.43
ON FULL	(0.16)

Note that the rule ON HALF has fired within three different outputs, so you have to decide what you want to do with the results. Should you add them, average them, or max them? It's really up to you. For this example, choose sum: 0.16+0.11+0.16 = .43.

This is still fuzzy, but looking at the data, it looks like ON HALF has the strongest membership. So it makes sense to just go with that:

output = MAX(OFF, ON HALF, ON FULL)
       = MAX(0.0, 0.43, 0.16) = 0.43

Using the disjunction operator v:

And that's it. Simply multiply (0.43) times the scale of the output, and that's the answer:

(0.43) * (10) = (4.3)
Set the thrust to (4.3).

The only problem with this method is that even though you're taking the variable that has the highest membership, its total area of influence in the fuzzy space may be very small. For example, a 40% NORMAL is definitely stronger than a 50% WEAK. See my point? It might be better to plug some of the values into the output fuzzy manifold for (OFF, ON HALF, ON FULL), compute the area of influence, and then compute the centroid of the whole thing and use that as the final output.

Method 2: The Fuzzy Centroid

To find the fuzzy centroid, you take the fuzzy values for each FLV in the output:

OFF	(0.0)
ON HALF	(0.14) {average}
ON FULL	(0.16)

Plug them into the y-axis of the FLV diagram and fill in the area for each. This is shown in Figure 12.48.

Add the areas up and find the centroid of the resulting geometric shape. As you can see, there are two ways to add the areas up: overlap and additive. Overlapping loses a bit of information, but it's easier sometimes. The additive technique is more accurate.

The centroids of each method have been computed and are shown in Figure 12.48. That's great, but the computer isn't a piece of graph paper. How do you compute the centroid?

To compute a centroid, perform a numerical integration (that's a calculus term). All this means is that to find the center of area of this fuzzy area object you need to sum up each piece of the object and its contribution to the total and then divide by the total area:

d_i is the input value for the domain, and dom_i is the degree of membership of that value. This is much easier to explain with real examples. In this example, the output domain is from 0.0 to 10.0. This represents the thrust level.

You need a loop variable d_i that loops from 0 to 10. At each interval of the loop, you're going to compute the degree of membership that this particular d_i is in the merged geometry shown in Figure 12.49.

Because each triangle has a certain height now that was cut off by the original values, you have to compute the degree of membership with a trapezoid rather than a triangle (but that's not too bad):

OFF	(0.0)
ON HALF	(0.14)
ON FULL	(0.16)

Here's the pseudo-code:

sum        = 0.0;
total_area = 0.0;

for (int di = 0; di<=10; di++)
    {
    // compute next degree of membership and add to
    // total area
    total_area = total_area + degree_of_membersip(di);

    // add next contribution of the shape at position di
    sum = sum + di * degree_of_membersip(di);

    } // end for

// finally compute centroid
centroid = sum/total_area;

The thing to remember is that the function degree_of_membership() is taking the generic values (0..10) and plugging them into the merged output fuzzy manifold, which results from plugging the following fuzzy values into the output variable and finding the area of influence of each one:

OFF	(0.0)
ON HALF	(0.14)
ON FULL	(0.16)

As you can see, using the MAX() method sure is a lot easier, and most of the time it works just as well as the centroid.

As for computing a crisp value for the final output rather than a linear value, that's easy. Just use the MAX() method and pigeonhole the output. Or you could select the output domain to be 0,1,2,3,4 and have exactly five crisp output commands. It's all about scale.

Warm and Fuzzy

That about wraps up the topic of fuzzy logic. The idea of fuzzy logic is simple; it's the actual implementation that's detailed. There's no demo this time, but look on the Internet. There are lots of commercial fuzzy logic experimentation programs. They're a lot better than anything I can write in 20 minutes, which is all the time I have left to write this chapter!