Finite State Machines (FSM)
By ai-depot | July 8, 2002
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:
- states which define behavior and may produce actions
- state transitions which are movement from one state to another
- rules or conditions which must be met to allow a state transition
- input events which are either externally or internally generated, which may possibly trigger rules and lead to state transitions
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
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.
- State Transition Diagram: also called a bubble diagram, shows the relationships between states and inputs that cause state transitions [1]
- State-Action-Decision Diagram: simply a flow diagram with the addition of bubbles that show waiting for external inputs [1]
- Statechart Diagrams: a form of UML notation used to show behavior of an individual object as a number of states, and transitions between those states. [3]
- Hierarchical Task Analysis (HTA): though it does not look at states, HTA is a task decomposition technique that looks at the way a task can be split into subtasks, and the order in which they are performed [4]
Advantages of FSM
- Their simplicity make it easy for inexperienced developers to implement with little to no extra knowledge (low entry level)
- Predictability (in deterministic FSM), given a set of inputs and a known current state, the state transition can be predicted, allowing for easy testing
- Due to their simplicity, FSMs are quick to design, quick to implement and quick in execution
- FSM is an old knowledge representation and system modeling technique, and its been around for a long time, as such it is well proven even as an artificial intelligence technique, with lots of examples to learn from
- FSMs are relatively flexible. There are a number of ways to implement a FSM based system in terms of topology, and it is easy to incorporate many other techniques
- Easy to transfer from a meaningful abstract representation to a coded implementation
- Low processor overhead; well suited to domains where execution time is shared between modules or subsystems. Only the code for the current state need be executed, and perhaps a small amount of logic to determine the current state.
- Easy determination of reachability of a state, when represented in an abstract form, it is immediately obvious whether a state is achievable from another state, and what is required to achieve the state
Disadvantages of FSM
- The predictable nature of deterministic FSMs can be unwanted in some domains such as computer games (solution may be non-deterministic FSM).
- Larger systems implemented using a FSM can be difficult to manage and maintain without a well thought out design. The state transitions can cause a fair degree of “spaghetti- factor” when trying to follow the line of execution
- Not suited to all problem domains, should only be used when a systems behavior can be decomposed into separate states with well defined conditions for state transitions. This means that all states, transitions and conditions need to be known up front and be well defined
- The conditions for state transitions are ridged, meaning they are fixed (this can be over come by using a Fuzzy State Machine (FuSM))
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].
Tags: none
Category: tutorial |
