What is a "state machine"?

[Caretaker.CCI]

The term "state machine" has popped up in several places throughout this website. I'm not sure that I understand what this is referring to.

What follows is information that I found using a "Google" search. If it is not appropriate for me to post this here please feel free to delete this (I'm not sure of the proper etiquette for posting other people's information from the Internet). The information was found at the website list here:

http://searchcio-midmarket.techtarget.com/sDefinition/0,,sid183_gci214244,00.html

To summarize it, a state machine can be described as:
•   An initial state or record of something stored someplace
•   A set of possible input events
•   A set of new states that may result from the input
•   A set of possible actions or output events that result from a new state

In their book Real-time Object-oriented Modeling, Bran Selic & Garth Gullekson view a state machine as:
•   A set of input events
•   A set of output events
•   A set of states
•   A function that maps states and input to output
•   A function that maps states and inputs to states (which is called a state transition function)
•   A description of the initial state

This definition seems pretty clear to me. Does this suffice as a starting point for this discussion? If so... how are we using it here, in the context of a PBASIC program?

Greg

[JonnyMac]

In point of fact, PBASIC has an element that we don't use too often, BRANCH, that facilitates state-machine type programs.  Here's what the "good stuff" looks like in code:

Main:
  ' do important stuff

  BRANCH state, (State_0, State_1, State_2)
  state = 0

State_0:
  ' do state 0 stuff
  state = 1
  GOTO Main

State_1:
  ' do state 1 stuff
  state = 2
  GOTO Main

State_2:
  ' do state 2 stuff
  state = 0
  GOTO Main

In this case we're using a general state-machine for the program.  The way this sorts out, the program runs like this:

important stuff
State_0
important stuff
State_1
important stuff
State_2

.. and repeats.  Some could argue that you could do that with a linear program but the beauty of a state machine is that any state can set the next state, hence alter the flow of the program.  And remember, a state can be held until some requirement is met.  Let's say you wanted to manage two servos with the Prop-1 and debounce an input.  You might do something like this:

Main:
  PULSOUT Servo1, pos1
  PULSOUT Servo2, pos2
  PAUSE 17

  BRANCH state, (Get_Trigger, Start_Up, Wind_Down)
  state = Get_Trigger

Get_Trigger:
  timer = timer + 20 * Trigger
  IF timer < 200 THEN Main
    state = 1
    GOTO Main

Start_Up:
  GOTO Main

Wind_Down:
  GOTO Main

With the servo updates and required PAUSE we're going to assume a 20 millisecond (roughly) loop time, hence this is what we use in the debounce state.  Once that condition is met the state is advanced and the program can move to the state that cause BRANCH to land on Start_Up.

The key to this structure is that you can do something active (e.g., refreshing servos) while waiting for another condition to become true or false -- whatever is required to make the transition to the next state.

[steveo]

Jon,
Thats very cool (well to me at least).

I'm waiting on delivery of a Ping))) sensor right now, and will be writing a program that requires the sensor to be checked and then trigger events based on the output of the sensor. I thought that I would need to get into an SX, so I could multi-task and have the Ping))) always outputting a value so the program could trigger events in "real time" as the output met certain conditions.

Could the branch command do this, albeit in a limited sense?

As usual, qualify my question under the condition that I rarely know what the heck I'm talking about.

[JonnyMac]

Yes, put the Ping processing in section above BRANCH so that it happens between every task.  Just remember that the farther the object is, the longer the Prng will take to respond, so this will cause a bit of timing variability.

[hatallica]

Great question.  I have not used a state machine in 15 years, but came up with a great reason to use one this year.

I am using 4 passive infrared (PIR) sensors to control the haunt action in my garage. 
If someone proceeds through the garage as expected, then the status of the PIR sensors changes from 0000 to 0001 to 0010 to 0100 to 1000, and finally back to 0000 when the garage is vacated. 
If there are multiple people, then the status may change from 0000 to 0001 to 0011 to 0110, and so on.

If someone moves backwards through the garage, then I do not want the props to react the same way.  So, what happens when the PIRs = 0100 depends on the previous status  If it was 1000, then I know somebody is proceeding in reverse.  If it was 0010, then I  know somebody is proceeding forwards.  The lighting, sounds, and animation will be triggered accordingly.

To draw a "finite state machine", I started with a circle that is simply called "start".  I assumed that there are only two valid possibilities from here - either someone is proceeding from the exit or the entrance.  So, I have a fork in the road.  Two arrows are drawn out of my "start" circle.  One is labeled "1000" and the other is labeled "0001".  They both terminate in circles that I will label "Reverse step 1" and "Forward step 1".  I will then define what should happen at this state, such as prop triggers.

From the "Forward step 1" circle, there is another possible fork in the road.  If the next sampling of the PIRs = 0000, the the person may have been scared and run away.  If the PIRs = 0010 or 0011, then one or more people are proceeding forward.  Each of those possibilities may constitute another state (circle) and trigger new actions.

As you can see, even four simple binary inputs can create a large numbe of possible states.  I had to simplify things by only considering a limited number of defined states, and then a default state for anything unexpected.

Each year, my party-goers get more sophisticated, so this is a powerful tool to keep a step ahead of them.

Have fun!
pH