State Machines

LoopyByteloose

Quite often we see 'state machines' mentioned in documentaton about robots and even about more complicated chips.

I started to do a bit of research and suddenly found that there are several different kinds of 'state machines'.
I am not sure about what information is truly useful and what information is just academic.

Does anyone know how to get started with designing programs from a 'state machine' point of view?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"When all think alike, no one is thinking very much.' - Walter Lippmann (1889-1974)

······································································ Warm regards,····· G. Herzog [noparse][[/noparse]·黃鶴 ]·in Taiwan

Jon Williams

I'm not formally schooled in this stuff, so I don't know if this qualifies.... I design many of my BASIC Stamp programs like this:

task··· VAR··· Nib

Main:
· DO
··· GOSUB Critical_Task
··· ON task GOSUB Task0, Task1, Task2, Task3
· LOOP

Critical_Task:
··' task code
· RETURN

Task0:
· ' task code
· IF (condition) THEN
··· ' set new task (state)
· ELSE
··· task = task + 1 // MaxTask
· ENDIF
· RETURN

This design does a couple things: it interleaves the Critical_Task code between everything else (like a soft interrupt) and allows each task (state) to determine what happens next.· Normally, it would simply point to the next task, but each task can have a check that lets the program be redirected if necessary.· Also, each task is setup as s subroutine so that it can be called from any point in the program, even another task.


▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Jon Williams
Applications Engineer, Parallax

Post Edited (Jon Williams (Parallax)) : 12/17/2005 3:22:54 PM GMT

Bruce Bates

George -

Thanks go to Dr. Tracey Allen for this excellent discussion and tutorial on the use of Finite State Machines with the PBASIC Stamp:
http://www.emesystems.com/BS2fsm.htm

Regards,

Bruce Bates

Paul Baker

There are basically 2 types Moore and Mealy, Moore is the most used. A Moore machine updates its outputs upon state transition (in the picture below, outputs are inside the state), a Mealy machine updates its outputs according to the inputs (in the picture below an output would be on a transition, this means·outputs can change more than once while in a particular state and therefore has assynchronous outputs, but it is not shown below because the·picture is of a Moore machine). A state machine is defined by its inputs and outputs, and is formalized as a state diagram, like this oversimplified one for an elevator door:



The transition indicates state change when the transition condition (input to the state machine) is valid, and the next state machine update occurs (ie a clock), Opened and Closed are called the state names and 1 and 2 are called the states. E: is the entry action which is the output of the state machine, which becomes true upon entering a state and stays true until leaving the state.

Once you have the state diagram defined, you can create a state transition table which has the current state along the X axis, and possible input conditions on the Y axis, the grid is filled with the next state given the current state and the input value, like this:


You'll note that not all entries are filled, because you dont nessesarily have acesses to every other state when in a particular state. Also the total number of input conditions is typically layed out in 2^{(# inputs)}, because a state transition can be defined by a compound argument of the inputs (ie transition if only input A and input B are true). So for a state machine having 2 inputs, you will have 4 entries (00,01,10,11) on the Y axis. Once you have the state transition table you can use Tracy Allen's page on how to define the state machine within a BS. For a more formal discussion you can read the Wikipedia entry.


▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10

Post Edited (Paul Baker) : 12/17/2005 4:00:03 PM GMT

daniel

George,

I'd recommend Miro Samek's "Practical Statecharts in C/C++" as a sound
introduction to application of statemachines/statecharts. Definately not
Stamp oriented, but his framework is applied to embedded work in general.
Samek's website is http://www.quantum-leaps.com/; the book is available
there or on Amazon, et.al.

I've been programming for 25 years; this book changed how I program.


Daniel

Paul Baker

Oh the fun of designing state machines out of 74HC series logic, using grey codes for states and mixed mode logic to reduce transition logic, I spent many sleepless nights huddled over a breadboard rewiring incorrect transition logic :P

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10

Kevin Wood

The Applied Robotics with the SumoBot manual has an introduction to state machines.

Tracy Allen

Hi there, I hope your weekend is going well.

A computer is ipso facto a finite state machine. So any program you write is also one, but that is not saying much.

The finite state machine philosophy will try to work as many tasks as possible in parallel without entering modes. Or at least have the appearance of working in parallel. Thus you have a real time operating system (RTOS) that Jon promotes, or the virtual peripherals of the SX chip, those are making highly efficient use of the computer to run many virtual machines in parallel. The RTOS has internal "state variables" such as the current task and the priorities that operate at the highest level of the virtual machine. The word "state variable" is a givaway that a project is implemented with finite state philosophy. A "mode" is a situation where the program is locked in doing one task to the exclusion of all others.

Quite often the virtual machines need to communicate with one another and that is done by sending "messages", which are additional state variables or flags. In contrast, a program might be a spagetti plate of GOTOs and little "modal" routines that have trouble keeping up with more than one task at a time.

Individual problems can be framed in terms of state machines. For example, the task of debouncing a pushbutton might naively be coded in a way that goes into a little loop that monitors the one button for multiple occurances of the up or down state. But while it is monitoring that one button, other inputs and outputs are not being tended and and extra code may have to be written to prevent the program from becoming stuck in a mode. In contrast, the state machine approach would hold the state of that button in a state variable and go around and around a loop tending to other tasks, and the debouncing and state decoding would be done in by logic on the state variables associated with that button, and the decoded states would be passed as messages to other tasks.

In some cases the logic of the state variables can be highly parallel. For example, the debouncing of multiple buttons can on a keypad be done in parallel using word-wide state variables, and computations that figure out the transitions of all the buttons in parallel with one operation. Mathematically, the inputs and outputs and state variables are n-tuples.

The above is the standpoint of synthesis, where you are building a machine to accomplish tasks. From the standpoint of analysis, you might be observing someone elses robot and trying to figure out "how they did it" or you might be an ethologist, trying to figure out the rules that an ant colony uses to build its nest. A system is viewed as an a sets of input states, output states and internal states, and rules of computation. The internal states and the rules of computatioon may be "hidden", while the inputs and the outputs are "observeable". In analysis, you are trying to figure out what interenal states and computations are necessary to account for the observables.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

LoopyByteloose

It took a while to get back here.· I am particularly interested the PBasic and State machine web site.

I see the·quotes from Wikipedia [noparse][[/noparse]where I began my query]

I just wanted to say thanks, I need to do more reading to fully grasp their use in planning software.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"When all think alike, no one is thinking very much.' - Walter Lippmann (1889-1974)

······································································ Warm regards,····· G. Herzog [noparse][[/noparse]·黃鶴 ]·in Taiwan

LoopyByteloose

Well, I have been exploring and State Machines apply to just about anything that is systematic and dynamic.

That means that they apply to both computer hardware and computer software.· It is a great tool to get a vision of where you want to go with a project.

ALL of the above reading material is quite useful.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"When all think alike, no one is thinking very much.' - Walter Lippmann (1889-1974)

······································································ Warm regards,····· G. Herzog [noparse][[/noparse]·黃鶴 ]·in Taiwan