Finite State Machines

in steemstem •  7 years ago 


Computer Science is a vast subject and the technology it offers is advancing rapidly, benefiting us in numerous ways. While Quantum Computers is a very hot topic, but what I'm going to discuss today is something old and basic.

As you know Artificial Intelligence is very common nowadays. Electronic gadgets, applications, games and what not is based on it. These applications exhibit intelligence, like a human brain works, if given different scenarios.

Have you ever wondered how does these apps work? For instance, if you talk about games, there are plenty of scenarios, a user could get into. Now, if you are a programmer, if-else statements must have come into your mind. 

if(Mario hits a brick and coins pop)
{Add Coins}
else if (Mario hits a brick and flower pops)
{Grow Mario}
else if (Mario falls or hits a bug)
{GAME OVER}


I have just typed three possibilities, whereas there could be plenty. Imagine writing hundreds of if-else or switch statements.

Here comes Finite State Machine into the picture which is hypothetical, of course. But it helps in writing the code and also minimize the spaghetti code. It is widely used by game developers.


Image Source

It's very informal FSM (Finite State Machine). I just want to give you a picture of where are we going.

In early 20th century, hypothetical models of neural networks and states were designed. This study formed the basis of Automata Theory. Automata is plural, Singular is Automaton which means self-acting.

Now if you google Automata Theory, you will find out that it's been classified into layers.

  1. Finite State Machine
  2. Push Down Automaton
  3. Turing Machine


So the basic concept that I want to discuss is Finite State Machine.

What is a Finite State Machine?

It’s an abstract machine which has finite states at any given time. According to the input received, states change. There is an initial state and final state and the states in between as required. Any current state has no information of the previous state thus it has no memory.

There are many practical examples of FSM like elevators, vending machines, combination locks, traffic lights, games. I will explain to you with the help of state diagrams for your better understanding.

Image Source

Above is some game where you have to go to Start state and just move along according to the arrows.

_______________________



Image source

In this diagram there are three possible states of a LED switch i.e., IDLE, ON, OFF.

At first, machine is in IDLE state. It receives an input 1, then it makes transition to ON state. 

Now at ON state, machine receives an input 0, it makes transition to OFF.

Here is a little transition table I have made. This kind of notation comes handy while programming.

Current State Input Next State
Idle Start/1 On
On Toggle/0 Off
Off Toggle/1 On

_________________________

Image Source

Now in this image you can see we are trying to detect sequence 1011. I have drawn a transition table for this state diagram as well.

Current State Input Next State
S0 0-1 S0-S1
S1 0-1 S2-S1
S2 0-1 S0-S3
S3 0-1 S2-S1

___________________________


There are several types of Finite State Machines:

  1. Acceptors
  2. Transducers
  3. Classifiers
  4. Sequence Detectors

Acceptors produce binary output i,e accepted or rejected. Here is an example.

Here I tried to pattern-match of the string STEEMIT.

_______________________

Sequence Detector or Recognizers are also basically type of Acceptors.

Transducers

These are not like FSM. While FSM can do pattern-matching, it can parse the string. It's widely used in Natural Langugae Processing. 

It has two tapes, can read from one tape and write to another tape. So basically it has memory.

Classifiers

These are like Acceptors but have single ouput and two termintation states.

Deterministic and Non-Deterministic FSA

Deterministic have no or single transition from every state. While non-deterministic can have multiple.


Those of you who are thinking that I'm making a useless fuss and making flow charts, must know that:

Finite State Machines are not Flow Charts.

I will tell you the difference. First, there are no states in flow charts. Those are Stages. And those stages don't require a certain input to move onto next stage. They move automatically on completion.

I have explained the basics of FSM, there is more to it. As you can see I haven't explained some types in detail. I have left that on purpose. We will discuss it in later posts.

I ask you a question:

Personal Computers are FSM or TM (Turing Machine) based?

I haven't discussed Turing Machine yet. It's an infinite tape and has memory, in short.

I read somewhere, Modeling Infinity is not the same as Obtaining Infinity.

So that could make our computers FSM based. But there is no computation successfully performed by Turing Machine that cannot be performed by our computers. So this makes it TM based too.

We know that Turing Machine is way more powerful than FSM because FSM can easily fall on a non-ending state or can catch up on a loop hole and it has no memory.

There are practical limitations but still computers can run any Turing program.  

FSM and TM both helped us a lot in developing different programs.  



References

1 - https://en.wikipedia.org/wiki/Finite-state_machine

2 - https://www.reddit.com/r/learnpython/comments/1z4jjk/finite_state_machines/

3- http://www.programmingbasics.org/en/beginner/fsm.html


Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

See, you have started gaining people's attention! This is a wonderful article! Good job, @event-horizon

Thankyou.

  ·  7 years ago (edited)

I've tried doing some game developing and tried coding some NPCs, but found FSM method of AI programming to be limiting and results in boring NPC behavior, e.g. you have an enemy soldier who after seeing you goes "I am a hostile, I am attacking you! I am 100% bent on attacking you" who then switches in an instant to "I am now running away! I am 100% bent on running away" after some predetermined number of hitpoints have been lost. If I want to code a character that acts like a human, then this decision wouldn't be a sudden switch, but a constant careful examination of ones situation, which in turn would affect his behavior - not as a jump but in a more seamless way. A soldier could attack you in a cowardly way and is ready to skedaddle as things get a bit hairier. Or be emboldened by his buddies showing up.

Doing this behavior in FSM is difficult because a machine can be in only one state at a time. You'd have to previously code a bunch of states of different behavior. a state for attack with 100% determination. Another state for attack with 90% determination and 10% cowardice. Another one for 80% and 20% etc, leading to a bunch of states. Really inefficient.

I'd like to have the different states in competition with each other and each state applying an effect dependent on influences that apply to that particular state and have the behavior emerge dynamically. I wonder if there's a name for this design pattern.

You are right finite state machine has its limitations. I don't know how you implemented but as you explained, I think you should check behavior trees. I haven't worked with them but as per my knowledge those are used for complex AI, where there are too many states.