Fuzzy State Machines

A fuzzy state machine is an extension to standard finite-state machines. Instead of processing crisp symbols, both the inputs and outputs are fuzzy values. This has the advantage of smooth control and reasoning with degrees of truth, which often proves more humanlike.

Internally, each state is defined as fuzzy variables, too. Like other fuzzy systems, this leads to a combinatorial explosion of applicable rules determined by the number of states and input/output symbols.

Contrary to common beliefs, a fuzzy state machine is intrinsically deterministic—just like a fuzzy rule-based system. Common terminology among game developers associates fuzzy state machines as probabilistic ones. This is not only misleading, but also ambiguous and inconsistent, so we'll stick to the standard definition.

Definitions

As with their nonfuzzy counterparts, fuzzy automatons are used as acceptors, and fuzzy machines used as transducers.

Fuzzy Finite-State Automaton

A fuzzy finite-state automaton (FFSA) can be seen as an acceptor that outputs degree of membership. It is defined as a quadruple:

Here, S is an alphabet of fuzzy input values, Q is a collection of fuzzy variables representing the states, F Q is a subset of accepting states, and d is a fuzzy transition map that defines the next state R_t+1 of the fuzzy automaton in terms of the current state R_t. The state of the automaton corresponds to the set of all fuzzy values Q:

F(Q) is the set of all possible states of the fuzzy automaton, so d is defined as a mapping this set onto itself, given a fuzzy input symbol.

Fuzzy Finite-State Machine

Like its nonfuzzy counterpart, a fuzzy finite-state machine (FFSM) is a version of the fuzzy automaton that can output symbols as it consumes input symbols. The outputs, obviously fuzzy symbols too, can be defined in terms of the transitions or the states (corresponding to Mealy and Moore machines). It is defined as a quintuple:

Z is the output alphabet, namely a set of fuzzy symbols. l corresponds to the fuzzy output map, defined in terms of the inputs and current state.

In this case, the output isn't only one symbol, but a set of fuzzy symbols defined with a smooth membership function.

Representation

The graphical representation of a fuzzy state machine shown in Figure 40.1 is still graph based. The active state cannot be denoted as a unique bold node, because many states may have nonzero degrees of membership. To visualize this aspect of the finite-state machine, the size or shade of gray of each state can indicate the degree of membership. This is especially useful when debugging the machine or trying to explain the outcome of a situation.

The finite-state machine itself may be unfolded into a set of fuzzy rules defined over the states and the input/output alphabet. Because none of these rules can be discarded when simulating the state machine accurately, there is little hope for significant optimizations in the representation. In the end, the rulebase contains fuzzy rules with the following format:

IF <state1> AND <transition> THEN <state2>

If the FFSM is not unfolded into a set of rules, the transitions themselves must be stored differently compared to a finite-state machine's graph. Crisp finite-state machines associate the transitions with the active state, so the simulation can check each transition when it becomes active. With a fuzzy model, state activity is not passed forward as a crisp Boolean. Instead, each state inherits the combined activity of the predecessor states (weighted by the fuzzy transition symbol). This implies that it's easier to compute the fuzzy value of a state based on its predecessors, instead of trying to propagate activity to the successors. The implementation stores the predecessor states for each state, which allows the fuzzy rules to be applied to each state to determine their next value in one pass.

Look at the example behavior in Listing 40.1. A crisp finite-state machine would store transitions from the three states (wandering, attacking, and gathering) to the fleeing state. On the other hand, the fuzzy finite-state machine needs to store backward links from the fleeing state, so its fuzzy value can be computed in terms of the antecedents states (an OR relationship between the three rules).

Listing 40.1 A Small Subset of Rules That Represent Part of a Fuzzy Finite-State Machine Graph

IF <wandering> AND <attacked> THEN <fleeing>
IF <attacking> AND <near_death> THEN <fleeing>
IF <gathering> AND <surprised> THEN <fleeing>

Simulation

Because the representation can be converted to a set of fuzzy rules, the simulation too will be little different from a fuzzy rule-based system.

There are two aspects of the simulation: computing the next fuzzy state using d, and computing the output with w. Computing the next state is done as a set of IF-THEN implications. Let's take an example, defining a state's degree membership as a disjunction over the neighboring state/transition pairs:

The fuzzy OR is defined as the maximum of the two operands; the fuzzy AND is expressed as a minimum. Using MIN/MAX inference leaves us with the pseudo-code in Listing 40.2 to determine the degree of membership of a state.

Listing 40.2 Determining the Fuzzy Value of a State s, and the Degree of Membership of the Output

s = 0
for each predecessor state q and input i
     output = MIN( q, i )
     s = MAX( s, output )
end for

The output itself is defined as a rule mapping the input symbol s₄ and previous state q₁ onto the output z_1/0. This is the conjunction:

No operations on sets are needed to simulate the FFSM. However, these may be required if the output variables need to be defuzzified.

Discussion

Fuzzy state machines have the advantages of both fuzzy expert systems and finite-state machines. They are straightforward to create, especially using graphical tools. They operate with fuzzy terms and linguistic variables, which prove more intuitive for humans. FFSA can recognize partial degrees of membership in input strings, whereas FFSMs have the capability to generate smooth output—ideal for control.

The major problem with fuzzy state machines is the combinatorial explosion, which follows from fuzzy expert systems. It's difficult—if not impossible—to reduce this problem without simplifying the problem. The sparse nature of the state machine is a small advantage here, because the numbers of rules does not reach its upper bounds. FFSMs also have problems dealing with complexity, as the design process becomes tougher with large machines. Although given the use of fuzzy concepts, this proves generally simpler than with crisp states.