Help with finite state machine please

[Voltarin]

Hi folks

I am new to picaxe and having a lot of fun to boot!

I have two inputs into a picaxe that give me four different states. How do I program the checking of the states simply and elegantly?

The states are as follows:

Inp 1 Low & Inp 2 Low - cycle and look for changes in state
Inp 1 High & Inp 2 Low - Action 1
Inp 1 High & Inp 2 High - Action 2
Inp 1 Low & Inp 2 High - Action 3

Any help appreciated.

Voltarin

 

[premelec]

Welcome to this forum... elegance and simplicity are in the eye of the programmer - consider DO If a AND B THEN GOSUB AB or convert A&B into 0,1,2,3 and use CASE statement - read the manuals - try things in the editor simulator and you are on your way... Submit some code if you aren't getting any results and we can make more specific suggestions... Try stuff it's easy and syntax checks will help you see if your code will run. There are so many ways to do something and in large part we learn by doing as well as getting suggestions... and reading examples... have fun! What PICAXE chip do you have? Have you downloaded editor and manuals 1,2,3?

 

[Dartmoor]

What you are asking is ideal for programming with the flowchart (which is easy for us beginners!).
If you really want it in basic, you can convert the flowchart to basic. It will look messy but works, you can then tidy it up to look pretty!

Play!!

 

[eggdweather]

I would implement your state machine like this:

main:
GOSUB process_states
GOTO main

process_states:
IF pin1=0 AND pin2 = 0 GOSUB state0
IF pin1=0 AND pin2 = 1 GOSUB state1
IF pin1=1 AND pin2 = 0 GOSUB state2
IF pin1=1 AND pin2 = 1 GOSUB state3
RETURN

state0:
rem do something
RETURN

state1:
do something
RETURN

state2:
do something
RETURN

state3:
do something
RETURN

Vary the pin-number to suit your connections e.g. pin5 or pin0 or whatever, but grouped into two logical pairs to get the binary sequences correct:
00
01
10
11

 

[MartinM57]

The offerings above would seem to provide the functionality requested but I'm not convinced that they are FSM implementations as the OP seems to suggest is the requirement - http://en.wikipedia.org/wiki/Finite-state_machine ...
... It is conceived as an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition; this is called a transition. A particular FSM is defined by a list of its states, and the triggering condition for each transition.


To implement a FSM (is this an exam question?) you probably need to start with a piece of paper:
- each state and any associated action named in a "bubble"
- the valid state transitions as directional lines between the bubbles
- the condition that causes the transitions as labels for the lines
...then the exercise is to work out the code that implements the bubbles and lines.

I guess it's a bit of an academic discussion whether the codes being offered above are actually a FSM implementation, but I'm sure there's someone here with an A-level in FSMs that can put us right

 

[eggdweather]

I think a PICAXE programmed to react to input stimuli fits the description of state machine quite well:

'A state is a description of the status of a system that is waiting to execute a transition.' - if its checking inputs, then meets that criteria
'A transition is a set of actions to be executed when a condition is fulfilled or when an event is received' - if it acts on the input states and reacts with an action, say illuminates an LED, then that meets the criteria

I suppose in a purist sense it needs to react externally to an input that then creates a corresponding (external) output. Yes it feels like an exam question - the candidate should discuss

 

[Pongo]

I think the concept is to detect and act upon a change in state of the inputs. So rather than loop continually decoding the inputs it feels more correct to me to store the state of the inputs, decode them and take the corresponding action. Then start looping comparing the inputs to the stored value, and when a change is detected store the new state, decode it and take the corresponding action, and go back to the comparison loop.

 

[premelec]

Probably some mechanical switches would do...

 

[geoff07]

For suitable applications (generally, doing something in response to an occasional stimulation where the response depends on what has gone before), finite-state-machines are very effective. If you want to see how someone else has done it, take a look at the simple FSM code structure in my blog. The parts are:

- event_monitor, a subroutine that continually scans inputs, timers, etc, and generates an event and exits when one is found
- a loop that calls event monitor and when it returns, calls the subroutine to process the event that was found
- a subroutine for every event, which does whatever is appropriate for the state it is currently in
- hardware subroutines to interface to the world

It is very simple but can be used generically, I have several household systems running for several years using this code, for various tasks. Using it means that the application code does not have to worry about how control is handled, it 'just' has to decide what the states, events, and transitions should be. It means that a new system can be up and running very quickly, will work immediately, and can be extended easily without messing with the core code.

A good way to draw up your FSM system is to use QFSM. It is well worth drawing it before starting any coding.

It doesn't make for so-called efficient code. For that, use assembler. But it does make the development and maintenance cycle much easier and even a complex system won't stretch the boundaries of a Picaxe.

 

[hippy]

The offerings above would seem to provide the functionality requested but I'm not convinced that they are FSM implementations as the OP seems to suggest is the requirement

I would agree. Though it may be what the OP wants or needs, to me that is simply a single state machine with four input handlers which then return to the original state. Though labelled "State1" through "State4" they are not strictly FSM states as such.

Part of the natural confusion is that there are two distinct things called "state"; inputs, ie, "what is the state of the input pins", and what the program is doing, "which FSM state is the program now in". What the program does may reflect input state, but that doesn't, of itself, make for different FSM states.

The best way to recognise the difference is if "Action 1" in the spec is an "increment counter" action. In eggdweather's code, when the input pins indicate "Action 1" the counter will repeatedly increment, rather than increment then stay in an incremented FSM state until the input pins become something else.

It is possible to alter the code to check the input pins, compare to previous input pin value, and only trigger the action on changes, that is an FSM where the state is indicated by the value of the variable which stores the input pin values. That easily works here because it is a very simple FSM.

To my mind, a true FSM has its FSM state indicated implicitly, by which section of the code is currently executing, so doesn't require any stored knowledge of what the input pins were previously.

That would fit the traditional drawing of states as circles with event arrows between them and action dots on those arrows which are passed through as FSM state changes..

However, when it comes to turn an FSM into a practical program both would deliver the same result, and both would probably pass muster as FSM.

The question then comes down to; what type of FSM is desired or required? One which stores state in variables or one which does not.

 

[geoff07]

You do need to know the current state, so you know which events are valid and should be acted upon. But you don't need to store the conditions of inputs, as they are implicit in how you got to the current state, and you now only need to know what the next event is. Digital input transitions can be detected with an interrupt without storing anything, though ADC or timer changes might require you to store a 'previous value' for testing. Because the history is almost entirely embodied in the current state, that helps keep FSM code simple: do/wait for valid event/process event/loop. Storing any history adds complexity and becomes a nightmare if you want to manage several FSM threads in one program, which is quite simple if you don't.

For me, eddgweather's states are in fact events, and there is only one state, so all the transitions ('do something') return to the same state. For it to be a multi-state FSM it would need each transition to specify which initial state it applied to (some transitions would only apply to some states), and would then specify which state it was in after the transition. You could say that, leaving aside the terminology, it is still an FSM, just there is only one state. One is still finite so it could be called a minimal FSM.

 

[techElder]

To me FSM and other "high brow" methods are really just that; methods to visualize a program. I see the advantage, but I also see that the intended audience and the one to benefit the most is the designer ... not necessarily the programmer. (Although "we" are all really both.)

The designer isn't always encumbered with the nuts and bolts of programming, so a high level of visualization is a benefit.

A programmer starts implementing FSM and starts saying, "Why am I jumping through this hoop, when I can just GOSUB to here and back?"

We're victims of our own experience.

I'm only saying this to explain why something like FSM is often difficult to grasp unless one practices the process.

 

[hippy]

The designer isn't always encumbered with the nuts and bolts of programming, so a high level of visualization is a benefit.

A programmer starts implementing FSM and starts saying, "Why am I jumping through this hoop, when I can just GOSUB to here and back?"

I would say the answer to that is, if you have an FSM design which has been assessed to work, then implementing that design as an FSM will work as designed. So at that level it simplifies the process; just implement what has been designed, no more, no less.

That's not to say the implementation has to be the exact same as the design but, if it is different, it can be harder to correlate the two and you lose the guarantee that what is implemented matches the design.

 

[Voltarin]

Hi Guys,

Sorry about the delayed reply, but living in sunny SA at the moment gets a bit hairy powerwise. Had no power the whole weekend, due to a council local sub-station blowing itself to kingdom come because of the national supplier's "Load Shedding" schedule - or so the official line goes. Nonetheless, still here, still alive, and TG still struggling with my new project.
I have gone the If X And Y route, and it seems to work, but am definitely going to try the code suggestion from eggdweather. I have also learnt a lot from the very academic discussion here regarding FSMs. Thank you all for your help and education.

Regards
Voltarin

 

[popchops]

To implement a FSM (is this an exam question?) you probably need to start with a piece of paper:
- each state and any associated action named in a "bubble"
- the valid state transitions as directional lines between the bubbles
- the condition that causes the transitions as labels for the lines
...then the exercise is to work out the code that implements the bubbles and lines.

I guess it's a bit of an academic discussion whether the codes being offered above are actually a FSM implementation, but I'm sure there's someone here with an A-level in FSMs that can put us right

I agree. An FSM action depends not only on the pin inputs but also the current STATE. I hit this thread because I am also interested in the most efficient method/ BASIC commands to use in coding a finite state machine. I don't want any time to be wasted considering states other than the current state, and I would like actions and transitions to be as quick as possible to minimise loop time. I expect the OP has similar interests.

Pops

 

[popchops]

As a novice programmer, I use a lot of If...Then...Else to consider combinations of state variables AND pin inputs but the code becomes horrendous to navigate and the IF condition seems quite inflexible. I know that switch case command is common in C for state machine implementations - I think the equivalent in BASIC is select case \ case \ else \ endselect. Is it more efficient than If...Then...Else?
What about Goto, Gosub etc... what's the best way?
Typically - some actions and code are repeated in multiple states. Is it more efficient in processing time to simply duplicate the code, or to define a subroutine/function? (I have plenty of Picaxe memory so code size is not a constraint).

Thanks! Pops.

 

[papaof2]

I seem to remember someone doing comparison testing of the time to do several GOSUBs versus having repeating inline code and the inline code was slightly faster - time saved by not doing the configuration for the GOSUB and the RETURN. I have an appointment with a surgeon within the hour so I won't be researching that now.

 

[oracacle]

I would be tempted to read the pins into bits 0 and 1, then read the value of B0. You could use just about any number of ways to get to the sections of coffee you wanted to execute from there.

You could also read the entire port into a variable, mask off the bits you don't want leaving just the pins in that variable instead of 2 separate pin reads. Depending on things are connected bit shifting may be needed.

Also what reviving a thread from 8 years ago?

 

[Buzby]

This is how I would build a FSM.

A state machine executes very quickly, because only the code in the active state is being run. It's also easier to debug, for the same reason.

( This code can be improved by moving the 'do' instructions to just before the 'if' statements, but I left it like this as it's clearer to follow when simulating. )

#picaxe 28X2

symbol pb0 = pina.0
symbol pb1 = pina.1
symbol pb2 = pina.2
symbol pb3 = pina.3

symbol lamp0 = b.6
symbol lamp1 = b.5
symbol lamp2 = b.4
symbol lamp3 = b.3

State0: 
do
      high lamp0
      low lamp1
      low lamp2
      low lamp3
      if pb1 = 1 then goto State1
      if pb2 = 1 then goto State2
loop

State1:
do
      low lamp0
      high lamp1  
      low lamp2
      low lamp3
      if pb3 = 1 then goto State3
      if pb0 = 1 then goto State0
loop

State2:
do
      low lamp0
      low lamp1
      high lamp2
      low lamp3
      if pb3 = 1 then goto State3
      if pb0 = 1 then goto State0
loop

State3:
do
      low lamp0
      low lamp1
      low lamp2
      high lamp3
      if pb0 = 1 then goto State0
      if pb1 = 1 then goto State1
loop

 

[hippy]

I know that switch case command is common in C for state machine implementations - I think the equivalent in BASIC is select case \ case \ else \ endselect. Is it more efficient than If...Then...Else?

A SELECT-CASE should be no more or less efficient than a sequence of IF-THEN-ELSE but can be a lot easier to comprehend and find where one will be within such a command structure for a particular condition value..

What about Goto, Gosub etc... what's the best way?

There's no simple answer to that. It depends on what you are doing but GOTO can make a program harder to follow than GOSUB. With a GOSUB you know execution should eventually continue after the GOSUB but with GOTO you cannot be sure where it then goes without looking deeper into the code.

 

[popchops]

This is how I would build a FSM.

A state machine executes very quickly, because only the code in the active state is being run. It's also easier to debug, for the same reason.

I like it. Problem is - there is typically other stuff that needs to be run each iteration, whilst also maintaining the finite state machine. So what about this: nested select case commands allow evaluation of the transition request in each possible state. If the input in any given state triggers a transition, the requisite actions are performed and finally the 'current state' variable is updated:

select case active_channel
  case 1
    select case channel_request      
      ;case 1 - do nothing
      case 2
        low b.1
        high b.2
        active_channel = 2
      case 3
        low b.1
        high b.3
        active_channel = 3
      else
        ;invalid request - do nothing
    endselect
  case 2
    select case channel_request  
      case 1
        low b.2
        high b.1
        active_channel = 1
      ;case 2 - do nothing
      case 3
        low b.2
        high b.3
        active_channel = 3
      else
        ;invalid request - do nothing
    endselect
  case 3
    select case channel_request  
      case 1
        low b.3
        high b.1
        active_channel = 1
      case 2
        low b.3
        high b.2
        active_channel = 2
      ;case 3 - do nothing
      else
        ;invalid request - do nothing
    endselect
  else
    ;invalid state - how did you get here?
endselect

 

[Goeytex]

I asked ChatGPT to provide example code in BASIC that demonstrates a Finite State machine. Here it is

' Finite State Machine Example in BASIC

' Define state constants
Const STATE_A = 1
Const STATE_B = 2
Const STATE_C = 3

' Initialize current state variable
Dim currentState As Byte
currentState = STATE_A

' Loop forever
Do

    ' Check current state and perform actions accordingly
    Select Case currentState
  
        Case STATE_A
            ' Do something in state A
            ' Transition to state B if condition is met
            If someCondition Then
                currentState = STATE_B
            End If
          
        Case STATE_B
            ' Do something in state B
            ' Transition to state C if condition is met
            If someOtherCondition Then
                currentState = STATE_C
            End If
          
        Case STATE_C
            ' Do something in state C
            ' Transition back to state A if condition is met
            If yetAnotherCondition Then
                currentState = STATE_A
            End If
          
    End Select
  
    ' Wait a short period of time before repeating loop
    DelayMS 100

Loop

'In this example, we define three state constants (STATE_A, STATE_B, and STATE_C) and initialize
' a variable called currentState to the initial state 'STATE_A.

'The program then enters an infinite loop, in which it checks the current state using a Select Case
'statement. Depending on the current state, the 'program performs certain actions and checks
'conditions to determine whether to transition to a different state.

'After performing the necessary actions and transitioning to a new state (if applicable), the
' program waits for a short period of time before 'repeating the loop. This delay is accomplished using
' the DelayMS function, which pauses execution for a specified number of milliseconds.

Might be a good template for a simple FSM in Picaxe Basic.

What stands out to me is there are no gosubs or gotos.


Goey

 

[hippy]

The typical State will do something on entry, support transitioning to another state, and do something on exit when it transitions,

I would be tempted to code those as three separate routines, some of which may be 'do nothing' dummies for some states, so it's easy to have them separately in code and not deeply embedded in any sort of conditional structure ...

Do
  If wantedState <> state Then
    Gosub State_Exit
    state = wantedState
    Gosub State_Enter
  End If
  Gosub State_Run
Loop

State_Enter : On state Goto State0_Enter, State1_Enter, ...
State_Run   : On state Goto State0_Run,   State1_Run,   ...
State_Exit  : On state Goto State0_Exit,  State1_Exit,  ...

; === STATE 0 ===

State0_Enter:
  High LED0
  Return

State0_Run:
  wantedState = 1
  Return

State0_Exit:
  Low LED0
  return

; === STATE 1 ===

There are quite a few different ways to implement FSM. I believe the best ways are when it's easy to confirm each state is doing what it's supposed to be doing and the above suits that. But it isn't the fastest nor most responsive. What one chooses may need some compromise between clarity, ease of changing, adding or removing states, speed, and memory use.

I always favour simple and clear, prefer to only sacrifice those when absolutely necessary.

 

[Buzby]

There are two basic methods of implementing FSM.

In the the method I posted the only code running is the code in the current state.
All the actions and transition conditions are held in one 'block'.
This is how most commercial FSM packages 'display' a state, but it is unlikely that their implementation actually follows this form.

The other methods use lists of pointers and an index to the current state, or, like the chatGPT code, a state variable and a CASE structure.
The programme in this case is jumping between execution of a state and determining which state to execute.

There are pros and cons to both methods.

In the real world FSM programming is similar to Sequential Flow Chart (SFC), and is one of the five standard languages in IEC 61131-3.
SFC is very good for problems that have a sequential solution, like a recipe for baking a cake.
It is not very good for things that can happen in any order, or interact with each other.
This is why it is important to choose the programming tool most suitable for the task in hand.

In PICAXE we have BASIC, BLOCKLY, and FLOWCHART tools.
The first two are just different representations of normal BASIC, but FLOWCHART is very close to generating 'real' FSM code.

This extract shows some cells from a PICAXE flowchart ...

Cell_7_4:
    if pinC.3=1 then
        goto Cell_7_5
    end if
    goto Cell_7_4

Cell_7_5:
    readadc C.1, varA
    if varA < 128 then
        goto Cell_7_7
    end if
    play 1, 3
    goto Cell_7_4

Cell_7_7:
    play 0, 3
    goto Cell_7_4

You can see that the cells represent states, with both actions and transitions in the same cell.

As hippy suggested, most commercial implementations of FSM / SFC have entry and exit phases associated with each state. They also have minimum and/or maximum execution times, latching or non-latching actions, override, interlock and reset conditions, and lots of other features to make them more suitable to real world applications.

I don't think the OP actually needed an FSM, but we've had a good time thrashing it about !.

Cheers,

Buzby

 

[oracacle]

Hippy that is the sort of thing i was thinkning about, just slightly harder to write out on my phone. The biggest issue of the state machines is getting it a point that the state can be easily identified.
I actually use that exact setup of a multi page menu and user interface on various projects. The nice thing is it doesn't execute unless that is a change.

This is some what close to what have i would have used for the original 2015 question

symbol reading = b0
symbol store = b1

main:
    bit0 = pinc.1
    bit1 = pinc.2
    if reading <> store then
        'do your if statements case select based on the value of reading varaible
        'even better if this can be called as an interrupt on either of the inputs
        'you would have a short execution time in terms of main loop
        'as it stands this about as fast as it gets without interrupts
        select case reading
        case 0
            'do for case 0
        case 1
            'do for case 1
        case 2
            'do for case 2
        case 3
            'do for case 3
        else
            'cover your backside if something outside the planned sates crops up
        endselect
        
        
        store =  reading
    end if
    
    pause 100            'hold here for simulation
    
    goto main

However, you using the very nice lookdown comand you can get just about anything you want with next to no effort. This command does not exist in C (at least as far as I know ATM) and would have to be done with a loop looking through an array. Either way its very flexible in what the value could be. But you ca not mix interger and asscii in the same lookdown so some conversion maybe needed if you plan on mixing them

symbol reading    = b0    'whatever state has jut been read
symbol store    = b1    'hold the previous value that was executed
symbol index    = b2    'holds the index of the value you are looking for

main:
    lookdown reading,("abcd"), index
    
    if reading <> store then
        select case index
        case 0
            'do for case a
        case 1
            'do for case b
        case 2
            'do for case c
        case 3
            'do for case d
            
            'continue to cover all states
            
        else
            'cover your backside if something outside the planned states crops up
        endselect
        
        store =  reading
    end if
    
    pause 100            'hold here for simulation
    
    goto main

The other thing I would implore anyone who is coding any sort of state machine is to assign something human memorable to each of the states.
Honestly i would be this as one of the most underated pieces of code advice i ahve read, it made my life so much easier when adopting it as my standard for just about anything.
for example

symbol button_pressed  = 0
symbol ir_beam_broken = 1
    'do your code

select case reading
  case button_press
     'do button pressed code
  case ir_beam_broken
     'do ir beam code
....

here are some actual refrences that i have used in my last project

#define main_menu 0               //this is used to select the main menu/title
#define duration_title 1          //how long?
#define colour_title 2            //what colour are the Leds
#define led_direction_title 3     //which way are the LEDs going
#define type_title 4              //timer disobgplay type, is it continuous, time then off or time then stay on?
#define trigger_title 5           //what trigger are we going to use?
#define alarm_title 6             //ar we going have an alarm sound?
#define direction_title 7         //still experimental to detect dirction of beam break

#define button 0                  //start/stop button
#define beam_break 1              //look for beam break
#define beam_make 2               //look got beam make
#define break_then_make 3         //trigger if the beam is broken and then remade
#define make_then_make 4          //trigger of the beam is made and then broken

The other nice thing about this is they also reference the postions within array that are used to write data to the display. It all just work when you have the same reference for the same things instead of remembering numbers

doing this will make your life easier when you are trying to fault find more complex state machines that deal with more than a handful of states.
It's a really small thing but can an absolutely massive difference when it doesn't work as expected.

Ive been finding recently that I have been leaning towards making responsive code, using the conditional entry into the case select and storing the last reading for the condtion mean that the code isn't executed unless it needs to be. As an idea I have a project that runs on a different MCU system it runs an graphical LED display, programmable LEDs and keeps track of elecpsed time between certian events while allowing the user to interact in a resonably complex menu without any noticable lag to whomever is using it. It makes use of similar state machine as i have outline here and multiple if/else statement for smaller 2 or three state, state machine. Some of these are simple overflow/underflow detection and correction, and I am not sure if you could define them as finite, but they are definetly state machines of some sort