FUZZY STATE MACHINES

– Huntington Technical Brief – Nov. 1990

A finite state machine (FSM) has traditionally been the most common structure for introducing sequential capability into a system. This Brief investigates extending a standard FSM structure to one allowing ftizzy states and events.

First, a little background. A state Is an indication of a unique position in which a system resides. A system moves from its current state to a next state via a transition. Transitions are triggered by events. which are typically (although not always) received asynchronously by the system as. inputs. Therefore, the next system state is a function of the current state and the triggering event. System outputs and actions can be functions of either the current state, or of the current transition.

The generalization from a tradltional state machine, to a fuzzy state machine is quite straightforward. A fuzzy state is a state with possible degrees of membership , as opposed to a (crisp) state with an implicit degree of membership of zero or one. That is, a fuzzy state machine allows the system to be partially In the current state.

To be able to assign a degree of membership , to a state, and because the next state is a function of both the current state and the triggering event, the system must also allow for fuzzy events. Given this, a first cut at the degree of membership in the next state, might be: where Is the degree of membership in the current state, Is the degree of membership of the event causing the transition, and AND is the fuzzy logic AND operation.

The major problem with this approach is that using the traditional fuzzy set operation deftnitions, with , a system eventually degrades, this because the degree of membership in subsequent states can never be greater than the degree of membership in the current state.

Similarly, there are times when, no matter how weak the membership Is in the current state or the, degree of membership of the triggering event, membership in the subsequent state is desired to be high, perhaps even one. Absolute adherence to the above convention disallows this.

Finally, there is no opportunity for weak membership in a given state to be strengthened by the occurrence of an event.

To overcome these shortcomings,we look at a generalized form of assigning the degree of membership in a next state. Given the two input parameters and , the degrees of membership in the current state and of the triggering event, respectively, in the next state can arbitrarilybe deftned to be one of the following:

- The degree of membership in the next state is dependent only on the degree of membership in the current state.

- The degree of membership -in the next state is dependent only on the degree of membership of the triggering event. Ibis option provides strengthening or weakening of the current state by an event.

- The degree of membership in the next state is dependent on the degree of membership in the current state ANDed with the degree of membership of the triggering event. This is the initial relationship suggested.

- The degree of membership in the next state is dependent on the degree of membership in the current state ORed with the degree of membership of the triggering event. This is the converse of the suggested relationship, and allows only strengthening (and not weakening) of the current state. 1hus while a system based exclusively on .will necessarily decay toward , a system based exclustvely on will "decay" to

- The degree of membership in the next state is always full.

Figure 1 - Diagrammatic representation of a fuzzy state machine. Crisp states (state_1 and state_3j),are unshaded, while fuzzy states(state_2 and static_4) are shaded, Transitions are triggered by, fuzzy events and the degree of membership of the next fuzzy state can depend on either that of the previous state ( designated [s]), that of the event (designated [e]), or both, (e.g., [s OR e]). where s is the degree of membership of the current state and e is the degree of, membership of the triggering event. State_2 is "strengthened" by event_c. The transition from state 3 is absolute (i.e., immediately - not triggered by an event). Degrees of membership into crisp states must necessarily be 1, and are therefore not specified.

Sate machines can be specified either verbally or diagrammatically. An example of the latter, incorporatIng an additional notation for fuzzy states (i.e., the shaded states), is shown in Figure 1.

One possible feature of a fuzzy state machine that warrants consideration is allowing membership by the system in more than one state at any given time. That is, if the system resides in one state with degree of membership  = 0.5, it seems logical that It rrdght also reside in other states, with the sum of the various states' degrees of membership totalling one.

In general, this is unwarranted. For one, it reduces the system to a multiple output concurrent system, thereby defeating the original goal of sequential capability. The strength of using a state structure is to know where the system is at any given time, and while the concept of partial membership in a given state appears

valuable, allowing partial membership in several states weakens the original purpose.

State machine / rule-base interaction - Interaction between the state machine and an underlying fuzy rule-base can be bi-directional. The more powerful interaction is the enabling and disabling of rules (or blocks of rules) depending on the state of the system.

In simple systems, the entire rule-base is searched at each system time interval. This is viable with smaller systems, but when system complexity and the corresponding number of rules grow, full rule-base searches become inefficient. A first step toward increased efficiency searches is the enabling and disabling of rules as a function of the current system state.

The second Interaction between state machine and rule-base is in the other direction, from the rule-base to the state machine. While it was previously indicated that the events that trigger state transitions most often occur as asynchronous, external events, this is not always the case. An action executed as a result of a rule firing may be the event that triggers state transition. This action may be as a result of purely internal conditions, or of a rule used to transform or combine external events into the desired event.

Conclusion - The addition of a fuzzy state machine to a fuzzy rulebased system is a consistent way to add sequential capability to the system. Allowing both states and events to be fuzzy extends the power of fuzzy logic beyond a standard fuzzy rulebased implementation.

David I. Brubaker, Ph.D. 19 November 1990