What are Finite State Machines (FSMs)?

FSMs are used in various computing applications, from hardware design to AI algorithms, to manage and predict behavior in a controlled, structured manner.

What are the Types of FSMs

Finite State Machines (FSMs) are crucial in fields like electronics, robotics, networking, and everyday systems. Here’s a look at the main FSM types:

1. Deterministic Finite State Machine (DFSM): In a DFSM, each state transition is uniquely determined by the current state and input, with one defined outcome per condition.
   Example: In a vending machine, if in the “Idle” state, selecting an item triggers a transition to “Selection,” and confirming it moves to “Dispense.”
2. Non-deterministic Finite State Machine (NDFSM): Allows multiple possible transitions for the same input and current state, meaning the machine can move to several states simultaneously.
   Example: In an elevator system, pressing the third-floor button from “Ground” could result in multiple paths (e.g., via other floors) to reach the destination.
3. Mealy Machine: In this FSM, outputs are tied to both the current state and input, meaning each transition can produce a unique output.
   Example: A coin-operated turnstile unlocks (output) when a coin is inserted, allowing entry, but denies access if a coin isn’t present.
4. Moore Machine: Here, the output is based solely on the current state, independent of inputs. Transitions depend on inputs, but outputs are state-driven.
   Example: A doorbell system’s “Ring” state outputs sound until the button is released, after which it returns to “Idle.”

These FSM types serve as foundational models for designing systems with predictable, state-driven behaviors.

What are the Real Life Examples of Finite State Machines (FSMs)?

Here are some real-life examples of Finite State Machines (FSMs):

1. Traffic Light Control Systems: Traffic lights operate as FSMs, cycling through a set series of states (e.g., green, yellow, red) based on timing or sensor input. Each light state triggers the next, creating a predictable, controlled traffic flow.
2. Elevators: An elevator operates as an FSM by transitioning between states (floors) based on user button inputs and door conditions. It “decides” which state (floor) to move to next, depending on requests and safety protocols.
3. Vending Machines: Vending machines transition between states based on user inputs, such as coin insertion, selection, and product dispensing. Each input prompts a state change, allowing the machine to process orders step-by-step.
4. Video Game AI: NPCs (Non-Player Characters) in games often use FSMs to exhibit different behaviors, such as “patrolling,” “chasing,” or “attacking,” depending on the player’s actions. Each state defines specific behaviors, making NPCs responsive and predictable.

FSMs simplify control systems by clearly defining states and transitions, making them suitable for applications that require predictable and sequential operations.

How Do FSMs Work?

Here’s a simplified, step-by-step process for creating and implementing a Finite State Machine (FSM):

• Identify all possible states the system can occupy, each representing a unique mode or condition, like “Idle” or “Spin” in a washing machine.
• Specify transitions that move the system from one state to another based on specific inputs or events, such as a button press.
• Organize states, input events, and transitions in a state transition table or diagram to visually represent the FSM’s behavior.
• Initialize the FSM in an initial state, like “Idle,” to establish a starting point.
• Process incoming input events or stimuli, which trigger potential state transitions.
• Determine the current state and recent input event to identify the next action or transition.
• Use the state transition table or diagram to locate the correct transition based on the current state and input.
• Carry out actions tied to the transition, such as updating variables, changing outputs, or triggering events.
• Update the current state to the next state identified by the transition, preparing the FSM for the next input.
• Continue processing input events and following the steps until the system reaches a final state or completes its intended behavior.

How is a Finite State Machine Used in Artificial Intelligence?

A Finite State Machine (FSM) is widely used in artificial intelligence to handle different behaviors in a controlled, structured way.

Think of it as a set of predefined states where the AI can only be in one state at a time, like “attacking” or “defending,” and transitions between these states are based on specific conditions or inputs, like a player getting too close.

Finite State Machine is a Gamechanger for AI

People on Reddit often talk about FSM being a “game-changer” for AI, especially in gaming, because of its simplicity and predictability.

However, some feel it can make the AI seem a bit “scripted” or predictable, which is why many recommend pairing FSM with more flexible methods like utility-based AI for a smoother, more realistic experience.

Utility-based AI allows the AI to make decisions on a gradual scale rather than jumping between rigid states.

How do you use a Finite-State Machine to create Smart AI?

An FSM can be used to create AI routines like attack patterns in games. Here’s an example:

1. Define possible states using enums (e.g., Idle, Attack, Defend).
2. Implement a switch statement to transition between states based on certain conditions (e.g., distance from the player).
3. Visualize these states in an inspector using serialized variables.
4. Implement coroutines to simulate AI actions, such as attacking for a few seconds before returning to a walking state.

This system can be expanded for more complex AI behaviors.

Recap

Finite State Machines (FSM) offer a simple yet powerful way to manage behavior in both AI and other systems. Here is the recap of the main points:

• FSMs as Core Models: Finite State Machines (FSMs) create predictable, state-based systems by transitioning between states based on inputs, crucial for controlled behaviors.
• Types of FSMs: FSMs include Deterministic, Non-deterministic, Mealy, and Moore types, each adding unique input-output relationships and complexity.
• Real-World Uses: FSMs power systems like traffic lights, elevators, and NPC behaviors in gaming, which depend on predictable state changes.
• FSM in AI: FSMs manage AI behaviors, especially in gaming, where NPCs react based on player actions. Paired with utility-based AI, FSMs gain flexibility.
• Versatility: FSMs are reliable and simple, making them ideal for quick, structured responses in both hardware and software contexts.

For more such AI terminologies, visit the AI glossary at AllAboutAI.com.