Enter the AI Article Writing Contest!', "Writing", "http://ai-depot.com/Contest" ); include('../Include/Header.php'); include('/usr/home/alexjc/public_www/Include/Utils.php'); Menu(); ?>

Background

Finite State Machines (FSM), also known as Finite State Automation (FSA), at their simplest, are models of the behaviors of a system or a complex object, with a limited number of defined conditions or modes, where mode transitions change with circumstance.

Finite state machines consist of 4 main elements:

A finite state machine must have an initial state which provides a starting point, and a current state which remembers the product of the last state transition. Received input events act as triggers, which cause an evaluation of some kind of the rules that govern the transitions from the current state to other states. The best way to visualize a FSM is to think of it as a flow chart or a directed graph of states, though as will be shown; there are more accurate abstract modeling techniques that can be used.

Figure 1.1: A possible finite state machine control system implementation

Finite State Machine

FSM is typically used as a type of control system where knowledge is represented in the states, and actions are constrained by rules.

"...One of the most fascinating things about FSMs is that the very same design techniques can be used for designing Visual Basic programs, logic circuits or firmware for a microcontroller. Many computers and microprocessor chips have, at their hearts, a FSM."[1]

Finite state machines are an adopted artificial intelligence technique which originated in the field of mathematics, initially used for language representation. It is closely related to other fundamental knowledge representation techniques which are worth mentioning, such as semantic networks [5] and an extension of semantic networks called state space [5].

Semantic networks were proposed to represent meaning and relationships of English words. A graph is constructed where nodes represent concepts and edges the relationships. State space is an extension on the idea of semantic networks, where a node denotes a valid state and the edges transitions between states. State space, unlike FSM, requires both an initial state and a goal state, and is typically used in problem solving domains where a sequence of actions is required for solving the overall problem (sequence from initial to goal states). Like FSM, state space has rules which constrain state transitions, and are triggered by input events.

Like any rule based systems, if all the antecedent(s) of a rule are true, then the rule is triggered. It is possible for multiple rules to be triggered, and in the area of reasoning systems, this is called a conflict set. There can only be one transition from the current state, so a consistent conflict resolution strategy is required to select only one of the triggered rules to fire and thus performing a state transition.

This brings us to two main types of FSM. The original simple FSM is whatís known as deterministic, meaning that given an input and the current state, the state transition can be predicted. An extension on the concept at the opposite end is a non-deterministic finite state machine. This is where given the current state; the state transition is not predictable. It may be the case that multiple inputs are received at various times, means the transition from the current state to another state cannot be known until the inputs are received (event driven).

An implementation of a deterministic finite state machine may see the firing of the first rule that is triggered. This may be ideal for many problem domains, but for computer games, easily predictable behavior is usually not a wanted feature as it tends to remove the "fun-factor" in the game.

"...a player feels like they are playing against a realistic simulation of intelligence, and not against a reproduction of a sequence of actions." [2]

The "sequence" which is one of the key benefits of FSM, should not be blindingly obvious in computer games. There are a number of extensions to FSM and workarounds for "mixing up" the sequence to make it harder to predict actions. One of these non-deterministic approaches involves the application of another proven artificial intelligence technique; Fuzzy Logic, called Fuzzy State Machines (FuSM).

Just like finite state machines there is a lot of flexibility when implementing a fuzzy state machine. A fuzzy value can be applied to various state transitions. When a conflict set is encountered the higher the fuzzy value for a transition, the higher the likelihood of the state transition. This allows the specification of a fuzzy priority to state transitions.

An implementation of FuSM may involve the assignment of fuzzy values to various inputs to represent the degree an input is defined. The fuzzy system would use these weighted input values in the evaluation of rules, triggering only state transitions whose assessed value is above a specified threshold.

Another approach for converting a deterministic FSM into a non-deterministic FSM would be to simply use a random number generator to select a triggered rule. It may not be necessary to implement a deterministic finite state machine to have a perceived level of unpredictability. This can be achieved by a system or object that has a large number of defined states and a complex mesh of transitions, giving the appearance of being unpredictable.

It is important to understand the difference between a state and an action. When designing a computer program, larger functionality are decomposed into a number of smaller actions or activities. This is done so that each can be defined in a function, making the overall solution modular, and easier to maintain. FSM is similar in that itís a decomposition of the behaviors of a system or object, and even a state can be decomposed into sub-states. The difference is a state may involve one or more actions.

Example 1: a moveUnit() action may be used by both the evadeEnemy state and the attackEnemy state.

Example 2: the evadeEnemy state may consist of many actions, some evaluations, some movement directives, and some actions which can change the entities own state. If the entity was cornered for example, there may be a state transition from evadeEnemy to attackEnemy, where the act of being cornered is the trigger.

The best way I like to think of the terms is an action is an activity that accomplishes something like an evaluation or a movement, and a state is a collection of actions that are used when in a particular mode. A state is the circumstance of a thing, its condition, and the actions are the attributes of that state. It provides the ability to limit the scope of actions or the amount of knowledge to only that required for the current state.

There are two main methods for handling where to generate the outputs for a finite state machine. They are called a Moore Machine and a Mearly Machine, named after their respective authors.

A Moore Machine is a type of finite state machine where the outputs are generate as products of the states. In the below example the states define what to do; such as apply power to the light globe.

Figure 1.2: A light system example of a Moore Machine

A Mearly Machine, unlike a Moore Machine is a type of finite state machine where the outputs are generated as products of the transition between states. In below example the light is affected by the process of changing states.

Figure 1.3: A light system example of a Mearly Machine

Finite state machines is not a new technique, it has been around for a long time. The concept of decomposition should be familiar to people with programming or design experience. There are a number of abstract modeling techniques that may help or spark understanding in the definition and design of a finite state machine, most come from the area of design or mathematics.

Advantages of FSM

Disadvantages of FSM

Like most techniques, heuristics for when and how to implement finite state machines are subjective and problem specific. It is clear that FSMs are well suited to problems domains that are easily expressed using a flow chart and possess a set of well defined states and rules to govern state transitions.

For a broader discussion of finite state machines I recommend you read; Finite State Machines - Making simple work of complex functions [1]

Remember you can visit the Message Store to discuss this tutorial. Comments are always welcome!. There are already replies in the thread, why not join in?