﻿ Game Development

Free JavaScript Editor     Ajax Editor ﻿

Main Page

### Fuzzy Control and Decision Making

This section discusses how fuzzy logic can be applied to control systems or decision-making architectures. It's simple to understand why the applications are so successful when the technique is so close to rule-based systems (the single most successful AI technique, as discussed in Chapter 11, "Rule-Based Systems").

Isn't fuzzy control an oxymoron? Can it work at all? Of course. Humans do not require precise numerical information, yet they are capable of highly adaptive control. It seems obvious to try to program controllers to accept imprecise and noisy input. Then, the system may be able to deal with complex situations in a smarter fashion, and may be easier to implement. Decision making benefits from the same advantage: human-like reasoning on concepts with degrees of truth.

#### Working Memory

In fuzzy systems, there is also a working memory. Naturally, the symbols are not crisp values but fuzzy ones. Apart from the obvious fuzziness, there is little distinction between a working memory in a fuzzy system and a standard rule-base system. In fact, in most implementations, the same generic container could be used to store the fuzzy variables.

#### Knowledge Base

Just like rule-based systems, fuzzy systems rely on a knowledge base, containing a set of rules. Instead of being defined in terms of crisp symbols, fuzzy variables are used instead (see Table 30.5). Unconfident, vulnerable, attack, and retreat are fuzzy variables. Enemy and accuracy are linguistic variables, with healthy/damaged/dying and high/medium/low as fuzzy terms.

##### Table 30.5. Fuzzy Rules Defined Within the Knowledge Base

Index

Rule

1

IF NOT unconfident THEN attack.

2

IF very unconfident OR somewhat vulnerable THEN retreat.

3

IF ammo IS low AND extremely damaged THEN more or less unconfident.

4

IF enemy IS healthy THEN NOT unconfident.

5

IF enemy IS dying and accuracy IS very high THEN attack.

As in rule-based systems, the rules are composed of an antecedent clause (IF), and the consequent clause (THEN). However, there are two major extensions to rules in a fuzzy system:

• Linguistic variables can be used as elements in the rules. If allegiance is a linguistic variable, the rules could refer to a particular fuzzy term. This is done by using the keyword IS: IF allegiance IS friendly THEN happy. The construct (M is X) simplifies to a single fuzzy variable; it can be seen as an accessor to the X variable in M.

• Fuzzy modifiers can be applied to each of the variables to add nuance to their meaning. Modifiers are generally applied to the antecedent clause, but in some cases can be used on the consequent clause.

Despite these additions, the acquisition of knowledge is slightly simpler with fuzzy systems. Indeed, fuzzy rules are much closer to human knowledge, which can reduce the number of total rules required. The linguistic expressions and modifiers are also very intuitive to work with, so almost anyone can add rules to the system.

The major problem is creating the membership functions for each of the fuzzy variables. The membership functions have a tremendous effect on the output of the system, so it's important to get it right. Different approaches can be used to create membership functions:

• The knowledge engineer can consult with the experts in the usual way and extract enough information to understand the nature of the membership function.

• A survey can also be set up. Different people can be questioned about their understanding of different concepts, and statistics can be used to create a membership function that reflects the average opinion.

• In both cases, it's often necessary to perform incremental tuning. If the results are not as expected, the developer can attempt to trace the reasoning and correct the faulty membership functions.

After the knowledge base has been created, and all the rules and membership functions have been crafted, they can be manipulated by the interpreter.

#### Fuzzy Interpreter

The interpreter is responsible for manipulating the variables in the working memory using the rules. There are two key differences compared with crisp rule-based systems: the matching and the evaluation of rules. So almost everything changes!

##### Matching

In crisp systems, it's obvious which rules match the current working memory. All symbols are either true or false, so it's easy to identify the antecedent clauses that are applicable.

In fuzzy logic, true and false are just special cases. Most of the time, fuzzy values will have partial membership to sets. This is not a problem in itself; the fuzzy rules are meant to have fuzzy inputs.

The problem is that we cannot discard most of the rules. Even fuzzy values with small degrees of truth will need to be plugged into the relevant rules. In practice, most fuzzy values become nonzero after a short amount of execution. So almost every rule has to be checked!

The best way to deal with this is prevention. We can make sure there aren't that many rules in the system! There have been some suggestions to deal with the combinatorial explosion of rules by reorganizing the rules, but these have turned out mathematically inaccurate and only applicable in a few cases.

So it seems the only way to deal with many fuzzy rules is to approximate the computation, to discard rules as in crisp rule-based systems. To do this, the interpreter can just ignore fuzzy values below a certain threshold (considering them false). For example, all the fuzzy values below 0.5 can be ignored, and values above 0.5 can be rescaled to fit the [0,1] range. This can be seen as trimming all the membership functions, but dealing with this in the interpreter instead will be more flexible and no slower. The higher the threshold, the closer the system is to a crisp rule-based system.

This seems a good way to trade off precision with speed. Sadly, the results will not be the same at different thresholds, so precautions need to be taken when developing the system.

##### Inference

Inference is a process applied to each rule. Essentially, the purpose is to determine the degree of truth of the THEN part of the rule, based on the IF part. This can be achieved using fuzzy logic; the appropriate fuzzy operators can be used to reduce any linguistic expression into a single fuzzy value.

The resulting fuzzy value can be considered as the output of this rule. However, the output is also associated with a fuzzy set—as all other fuzzy variables. This set will only be used for defuzzification. There are two different ways to compute the fuzzy output set (see Figure 30.7):

##### Figure 30.7. Example of fuzzy inference using the product method to scale the output set. The actual fuzzy values are denoted underneath the membership functions.

• MIN inferencing essentially trims the top off the output membership function to produce the output set.

• PRODUCT inferencing instead scales the membership function by the output value.

In the implementation, there's usually no need to manipulate any fuzzy sets. The two different operations—MIN and PRODUCT—can be understood as an interpretation the output value and set. As such, we can take this interpretation into account during the defuzzification; this is lazy evaluation.

##### Composition

Many rules may have the same fuzzy variable in the body of the rule. The composition stage must take into account each consequent clause that affects a single variable, and combine them together (see Figure 30.8). Again, there are two common ways to do this:

##### Figure 30.8. Example of fuzzy composition over two sets using summation.

• MAX composition uses the maximum value of each of the rule outputs. Therefore, the final fuzzy value can be considered as a conjunction (AND) over each of the results for the inference stage.

• SUM composition takes the total of all the membership values. This can be a problem because the final fuzzy value may be greater than one. As such, summation is often followed by a defuzzification that can handle this problem. The alternative is to average the membership values.

Again, the composition can be interpreted as having two outputs: the actual fuzzy value, and a corresponding fuzzy set. The set itself is only used when defuzzifying, but the fuzzy value is reinserted into the working memory.

#### Algorithm

The simulation of the fuzzy system requires two copies of the working memory to be consistent. One stores the current results, and the other remembers the previous state (until the update is finished). This is necessary because updating the same working memory leads to somewhat unpredictable results, which depend on the order of processing.

All the rules are processed as shown in Listing 30.1. The system could discard some rules where the antecedent clause is exactly 0. Doing this efficiently requires a treelike structure, as discussed for the rule-based systems. For fuzzy systems, this trick will not pay off because the values are rarely 0.

##### Listing 30.1 Main Simulation Loop of the Fuzzy System
```current is the working memory with the latest fuzzy variables
previous is the last state of the working memory

for each value in the working memory
previous[value] = current[value]
current[value] = 0
end for
for each rule
result = evaluate( rule.expression, previous )
current[rule.body] = MAX( current[rule.body], result )
end for
```
﻿

Ajax Editor     JavaScript Editor