Free JavaScript Editor Ajax Editor

↑

Main Page

## Fuzzy LogicFuzzy 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 TheoryA 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. ## Figure 12.35. Some simple 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:
NOTE Usually a slash ( 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 TheoryThe 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.
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 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 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 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 RulesAll 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. ## Figure 12.36. The fuzzy I/O system.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 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:
## Figure 12.37. A fuzzy manifold composed of range FLVs.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 ## Figure 12.38. Computing the degree of membership of a domain value in one or more FLVs.Each triangle in the fuzzy surface represents the area of influence of each fuzzy linguistic variable ( NOTE You've already seen a similar technique used to select states in a previous FSM example (in the section Patterns with Conditional Logic Processing, earlier in this chapter). The range to a target was checked, which forced the FSM to switch states, but in the example with FSMs you used crisp values without overlap or fuzzy computations. There was an exact range where the crisp FSM AI switched from 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 MembershipIt'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 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. ## Figure 12.39. Typical fuzzy linguistic variable 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 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 ## Figure 12.40. The details of computing DOM for an FLV.To compute the DOM of any given input x // 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 Assume that you have input ranges x ## Figure 12.41. Your range manifold with a number of inputs.In that case, the degrees of membership for each
Studying the values, there are a number of interesting properties. First, note that for any input value x Secondly, for some x For an example of creating a fuzzy manifold for some input and a number of FLVs, check out At this point you know how to create a fuzzy manifold for an input x 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. ## Figure 12.42. The fuzzy manifold for the power level.The fuzzy linguistic variables are as follows:
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 MatricesFuzzy 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. ## Figure 12.43. Using a fuzzy associative matrix.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: -
Select your inputs, define the FLVs, and build your manifolds. The inputs to your fuzzy system are going to be the range to the player and the power level of the AI-controlled bot. Input X Range to player. Input Y Power level of self. Refer again to Figures 12.37 and 12.42—these are the fuzzy manifolds that you're using. -
Create a rule base for the inputs that tie them to an output. The rule base is nothing more than a collection of logical propositions of the form "if X AND Y then Z" or "if X OR Y then z." This makes a difference when you're computing the `FAM`outputs. A logical`AND`means "minimum of the set," while a logical`OR`means "maximum of the set" when dealing with fuzzy set theory. For now, use all`AND`s, but I'll explain how to use`OR`s later.
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):
The fuzzy manifold for these FLVs is shown in Figure 12.44. ## Figure 12.44. The output fuzzy manifold for the thrust level.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.
Input 2: Power level of self.
Output: Internal navigational thrust level (speed).
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. ## Figure 12.45. The FAM, complete with all the rules.## Processing the FAM with the Fuzzified InputsTo 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:
For Input 1 = 275, the degree of membership of each FLV is as follows:
For Input 2 = 6.5, the degree of membership of each FLV is as follows:
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. ## Figure 12.47. The fuzzy associative matrix showing active cells and their values.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 if (0.16) AND (0.0) then on HALF This is computed using the (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 (0.11) _ (0.25) = (0.11) A-ha! The rule 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 ## Method 1: The MAX TechniqueIf you look at the FAM data, you have the following fuzzy outputs:
Note that the rule This is still fuzzy, but looking at the data, it looks like 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% ## Method 2: The Fuzzy CentroidTo find the fuzzy centroid, you take the fuzzy values for each FLV in the output:
Plug them into the y-axis of the FLV diagram and fill in the area for each. This is shown in Figure 12.48. ## Figure 12.48. Finding the area and the centroids of the fuzzy manifold graphically.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 You need a loop variable d ## Figure 12.49. Computing the final crisp output from the fuzzy centroid.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):
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
As you can see, using the As for computing a crisp value for the final output rather than a linear value, that's easy. Just use the ## Warm and FuzzyThat 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! |

↓

Ajax Editor JavaScript Editor