None W1C_FSM_FourBlock

Table of Contents

Challenge

In the last assignment, you were tasked with implementing your first finite state machine. Perhaps after that experience you would be able to recognize the steps listed below as similar to your process:

  1. Choose states
  2. Draw a state transition diagram, mapping out all paths from state to state and all latches
  3. Construct a state transition table using Boolean algebra, simplifying where possible
  4. Choose and document (using comments in code) variable names to represent each input, output, state and/or state transition in your design.
  5. Draft a "Boolean Algebra Program" that will run as an infinite loop on your microprocessor, simulator, or programmable logic controller
  6. Test and refine your design

You will find that these are necessary steps in all of the FSM designs we will ask you to complete this semester. However, you may have noticed that implementing a state machine can get complicated fairly quickly and these steps DO NOT provide guidance on how to reliabily implement a FSM design.

Consider the challenge for this the need to have your intersection system handle two zumo robots in the factory rather than just one! In today's assignment, you will implement a finite state machine in a simulator that achieves the behavior shown in the video below:

As you might imagine, dealing with the possibility that more than one robot is waiting its turn at the intersection adds a substantial amount of complexity to the requirements that the control system make sure that no conflicts occur in the intersection!

This complexity motivates a need for a disciplined process that will help us manage the implementation of an FSM that may have many states. In developing a consistent approach to programming our FSMs, we can mitigate the risks associated with our controller's complexity.

Controller Design: Jobs of a State Machine program

Based on your experience in the last challenge, you now know what a state machine is supposed to do conceptually: move a system from condition to condition (state to state) based on user inputs, sensors, and internal variables. Each state in our design, represented by a Boolean variable, must be set to either true or false in each program loop.

Based on its current state, the machine will also need to take some action. The action could be to illuminate lights on a display panel, activate motion of motors/pumps/solenoids, trigger some controlled subprocess in a robot like a "collision avoidance" strategy, or generate sound in the form of bells, whistles, or alarms. In this week's challenges, the "action" that the machine must take is to raise or lower a set of gates.

Embedded in these various requirements is the reality that the program implementing the state machine has to do more than just evaluate logical statements for state transitions. While the simulators we will provide you with in this course do some of these things for you, it is true that in general, a complete program needs to:

  • Handle/react to user inputs and sensors (read "pins" on an arduino for instance)
  • Update any internal variables (counters, timers) used in the state transition logic
  • Evaluate state transition logic to determine which of the transitions/latches in your state transition table is active (there must always be exactly one true state at the end of each loop).
  • Update the machine's state based on the active transition or latch
  • Use the current machine state to activate the appropriate outputs
  • Store any variables from the "current" loop as "old" copies if they are needed in the next loop

THAT'S A LOT OF STUFF TO PLAN AND KEEP TRACK OF!. Additionally, the order in which we perform these sub-tasks matters... a lot. To make the planning/execution of complex state machine designs tractable, we will introduce a Four-block Structure we'd like you to follow when writing Boolean Algebra programs (state machine programs that operate using Boolean Logic statements). Following this structure is not strictly necessary to make your state machine program work, but it will help you avoid some common traps and make your code interpretable by anyone familiar with this framework. THEREFORE, THIS FOUR-BLOCK STRUCTURE WILL BE REQUIRED FOR ALL OF YOUR FSMs FROM NOW ON.

Controller Design: The Four-Block Structure

One possible way to organize a FSM implementation (and the way that is required in ME480) is by separating the code into four blocks, which are given below. Using this structure makes it very straightforward to turn your state transition diagram into a functioning FSM implementation. The structure is given below.

image.png

Block 1: Process User Inputs & Sensors

Robots, factory assembly lines, CNC machines, handheld electronic games, HVAC systems, aircraft cockpits, and other automatic control systems whose operation can be supervised by a state machine usually have some way to interact with a human operator. Types of input devices are widely varied, but momentary switches and "latching" switches (toggle or locking switches like a light switch) are most common. In your laboratory assignment this week you have seen (or will see) that a switch can be used to generate a "high" voltage or "low" voltage. The outputs of these switches are the most basic type of Boolean input for a state machine design.

Block 1 is also where the program needs to take any "raw" inputs from the user and process/translate them for use in the state transition logic. For example, if your design requires you to hold a button for 2 seconds, you may need to write some logic that uses a "timer" (which we will cover later) to check how long a certain momentary button has been held.

Example - Unique Press

A common task that needs to go into this portion of your program is that of detecting a unique press on a momentary switch or button. Look at the time history of a momentary button press below:

image-6.png

Each drawing of the button represents one pass or "loop" through the program logic. A Boolean Algebra Program implemented on a microprocessor often runs hundreds or thousands of times each second, so when a user presses a button just once, as shown in the figure above, the button's boolean state may read "TRUE" for more than one loop of the program, even though we humans can interpret the behavior shown as only a single unique button press. If your state transition logic depends on unique button presses, but your logic merely uses the Boolean variable "BUTTON_STATE," you may get unexpected behavior!

So how do we fix this problem? In the figure above, we see that the rising edge on the red "Button_State" trace is what is unique about the button press. In words, we can read a rising edge as follows:

"The button is pressed now, but it was not pressed the last time I looked at it."

As a logical statement, this would read something like:

$$BTN\_PRESS = Button\_State \cdot \overline{OLD\_Button\_State}$$

where OLD_Button_State is a stored value of what Button_State was in the LAST LOOP through the Boolean Algebra Program. Implemented as shown in this equation, the variable "BTN_PRESS" would have the time history shown in purple in the figure above. Note that it will only return "true" for one loop of the program even if the button is pressed, held, and released. In Arduino code, this might look like:

BTN_PRESS = Button_State && !OLD_Button_State;

Of course, this is just one example of what "Block 1" of your program should contain. In summary, it needs to update the value of anything that will be used to evaluate the state transition logic in the next block.

Block 2: Evaluate State Transition Logic

This portion of the program is the most critical to implement correctly, but can be the easiest to implement if you have carefully considered the design of your state transition diagram.

To write the code for block 2, simply write a single line of code representing to the boolean expression for each transition in your state transition table without including the ending state. This means that in block 2, you should have as many lines of code as there are transitions in your state transition table. This is a simple but extremely powerful way to make a quick self-assessment of the reasonableness of your block 2 code.

Block 2 Example

Let's consider a simple state machine that illuminates either a red light or a green light. If the machine is currently illuminating the green light, it will be in state "S1." If it is illuminating the red light, it will be in "S2." The machine will stay in its current state until the user registers a unique press on a momentary switch. When a unique press occurs, the machine will switch which light is illuminated. The state transition diagram for this machine is given below:

image.png

The state transition table for this machine is as follows:

Transition Starting State Transition Condition Ending State
1: A S1: Green State $SW1\_PRESS$ S2:Red State
2: B S1: Green State $\overline{SW1\_PRESS}$ S1:Green State
3: C S2: Red State $SW1\_PRESS$ S1:Green State
4: D S2: Red State $\overline{SW1\_PRESS}$ S2:Red State

To implement block 2 for this finite state machine, we simply write a single line of code for each of the four rows in the state transition table. Remember that to do this, we read the table left to right, but we do not include the ending state in the expression. We set a variable representing the transition to either true or false, but we do not set the ending state to true or false just yet!

A=S1&&SW1_PRESS;
B=S1&&!SW1_PRESS;
C=S2&&SW1_PRESS;
D=S2&&!SW1_PRESS;

These four lines together complete "Block 2" of our Boolean Algebra state machine program.

There are a few things that are important to notice about the logic above:

  1. We do not actually set the truth value of any states in block 2. All we are doing is determining which transition in our design is true. Because of this, variables representing a state SHOULD NEVER be on the left hand side of the equals sign in block 2.
  2. Exactly one of these expressions must evaluate to true during one program loop! If none do, we will end up in no state at all, and if multiple transitions evaluate to true, we will end up in more than one state!
  3. The transition conditions are redundant (2 are SW1_PRESS and 2 are !SW1_PRESS) but the state transitions themselves are unique, because they contain information about the current (starting) state.

While items 2 and 3 are fairly self explanatory, number 1 in the list above bears some extra explanation, so let's consider a counterexample.

Imagine that I tried to directly set the ending states in block 2. Perhaps I thought to myself "why not cut out the extra steps? The table tells me where I'm supposed to end up. That should work!"

This attempt might look like the following:

S2=S1&&SW1_PRESS;
S1=S1&&!SW1_PRESS;
S1=S2&&SW1_PRESS;
S2=S2&&!SW1_PRESS;

Look carefully at this block of code, and imagine the following scenario: I'm in state 1 and push the button to get into state 2. Evaluating the first line of the program, I see that because S1=true and SW1_PRESS=true:

S2=S1&&SW1_PRESS; evaluates to TRUE

But then when I evaluate line 3, and I see that because S2 is now true, and because SW1_PRESS is still true:

S1=S2&&SW1_PRESS; evaluates to TRUE

so the machine "instantaneously" switches back into state 1, where I started!

This is called "falling through" the logic, and it's exactly why we only set the truth values of intermediate variables that represent the state transitions in Block 2 rather than setting the truth value of the states just yet. As a reminder, the correct block 2 for our design is given by:

A=S1&&SW1_PRESS;
B=S1&&!SW1_PRESS;
C=S2&&SW1_PRESS;
D=S2&&!SW1_PRESS;

Because we are using the "extra" variables to represent the state transitions The order of the individual lines of code in block 2 is unimportant!

In the correct implementation, we aren't prematurely setting S1 to true before we finish evaluating the transition logic. You can think of these "transition variables" as "queuing up" the move from one state to another, but deferring the actual move until all transition possibilities are evaluated.

Combining the "block 1" example above with our correct block 2, we currently have a Boolean Algebra Program that looks like this:

//block 1
SW1_PRESS = SW1&&!SW1_OLD;
//block 2
A=S1&&SW1_PRESS;
B=S1&&!SW1_PRESS;
C=S2&&SW1_PRESS;
D=S2&&!SW1_PRESS;

This procedure, if followed rigorously, will eliminate almost all of the frustration and heartache that can accompany state machine programming. You can follow the same procedure outlined here for any arbitrarily complex state machine, and it will still work.

Let's move on to a talk about Block 3, which takes our transition variables and uses them to set the proper state for the state machine.

Block 3: Set States

This section of code will finally "decide" which of our states will be true for this loop of the program. We look to the diagram to determine how to use the state transitions to set our current state. Specifically, we look at each state in our diagram and count the number of arrow heads pointing at it. Each arrow, as we know, represents one of the transition variables we defined in block 2. So all that is required now is to write the logic to say that a state is true if any of the state transitions ending in that state are true.

Functionally, this might manifest for a single state as:

State_x = T1||T2||T3;

where T1, T2, and T3 are the all state transition variables with an ending state of State_x. Let's write block 4 for our two-state program example.

Example

For the same program we were working on above, the Block 3 logic would look like this:

S1=B||C;
S2=A||D;

Notes:

  1. All of the rows of the table are used in block 3. This is the same as the number of arrows on your state transition diagram.
  2. Block 3 has as many lines of code as there are states in your diagram.
  3. Because our state transition diagram and table cover all logical possibilities for the state machine, our machine will end up in either the red or the green state after each loop. So far, then, our complete Boolean Algebra Program is given by the following:
//block 1
SW1_PRESS = SW1&&!SW1_OLD;
//block 2
A=S1&&SW1_PRESS;
B=S1&&!SW1_PRESS;
C=S2&&SW1_PRESS;
D=S2&&!SW1_PRESS;
//block 3
S1=B||C;
S2=A||D;

Now that the variables S1 and S2 are properly updated for this loop of our program, we will move on to Block 4, which uses the current (updated) state to activate any appropriate outputs.

Block 4: Activate Outputs For Current State and Update Variables

This (final) part of your Boolean Algebra program is fairly self-explanatory. Now that I know which state my machine is in, I'll use that information to activate any outputs (lights, sounds, motors, pumps) that are associated with this state. Because I'm "finished" with all of the program's tasks, I'll store the current state of relevant variables in an "OLD" variable so I will be able to access in the next loop of the program after inputs have been updated. In this case, we just need to store the "OLD" value of SW1 so that we can detect unique presses.

Example

For the two state example we've been working in this notebook, the outputs are a red light and a green light. Let's assume that setting the variable "Y1" to true makes the green light turn on, and setting "Y2" to true makes the red light turn on. This yields the following (almost) complete Boolean algebra program for our example:

//block 1
SW1_PRESS = SW1&&!SW1_OLD;
//block 2
A=S1&&SW1_PRESS;
B=S1&&!SW1_PRESS;
C=S2&&SW1_PRESS;
D=S2&&!SW1_PRESS;
//block 3
S1=B||C;
S2=A||D;
//block 4
Y1=S1;
Y2=S2;
SW1_OLD=SW1;

Controller Design: Explaining Variable Names

To make your code readable to another engineer, it is important that you create a "key" or list of all of your variable names, and explain what each one does. This can be in a spreadsheet, or just expressed as a simple list.

Why is this required?

If you are implementing your state machine on a microprocessor like the Zumo or a plain old Arduino, you'll need to declare any variables you use to represent inputs, states, internal conditions, or outputs as well; this must happen before your program kicks into its "infinite loop" to ensure that the variables are scoped properly for use in later iterations of a program loop. If you're implementing your state machine on a Programmable Logic Controller (PLC), as we'll be doing soon, you'll have to follow the proper procedures for defining variables there as well.

Depending on what type of machine you're implementing your FSM/Boolean Algebra Program on, you may or may not be able to name all of your variables descriptively. In the Javascript simulators you'll be using for this class to practice writing FSMs, and in the Programmable Logic Controllers (PLCs) we'll be using in lab this semester, you don't have much choice in variable names (variables are already pre-declared in these scenarios as well). Therefore, It's important to describe what each of your variables is in your code so that it is readable by another engineer.

For instance, if we were to implement our two-state program on a simulator that only allows us to use variables named X1-X1, Y1-Y6, and V1-V21, we would need to explain what each of these things represents physically and/or in terms of our FSM design. We ask that you do this in comments in your code. For our two-state program example, this would mean adding the following comment lines above your program. Note that the variable names have been modified. It would be very difficult to read this version of the code without a key, since the variable names are no longer descriptive!!

//V10 represents transition from State 1 to State 2 (A)
//V11 represents latch on State 1 (B)
//V12 represents transition State 2 to State 1 (C)
//V13 represents latch on State 2 (D)
//V1 represents State 1 in the diagram
//V2 represents State 2 in the diagram

//X1 represents SW1's state
//V3 represents SW1's "old" state
//V4 represents a unique press on SW1

//Y1 represents the green light
//Y3 represents the red light

//block 1
V4 = X1&&!V3;
//block 2
V10=V1&&V4;
V11=V1&&!V4;
V12=V2&&V4;
V13=V2&&!V4;
//block 3
V1=V11||V12;
V2=V10||V13;
//block 4
Y1=V1;
Y3=V2;
V3=X1;

Controller Design: The challenge of the first loop. How do you get in to the starting state?

In a properly coded FSM, it is necessary to somehow initialize one of the design's states to true when the program first starts up. This is vital because all of the transitions in a state transition diagram depend on the context of the machine already being in a particular state.

If you're programming your state machine in Arduino, MATLAB, etc., this is easy. Just set whichever state the machine is supposed to start in to "true" at the top of our program, before beginning our infinite loop. On the simulator or on a PLC, however, the situation is a little trickier. PLCs (and our simulator below) often have a special variable that's set to true only on the very first loop of the program. In the simulator, this variable is called "SP0." To make sure our program gets into the correct state on the first run through the logic, we simply add an "OR" to the line in block 3 for that state. Let's assume the machine is supposed to start in S1. Then, the updated state transition chart and complete program look like the following: 

//V10 represents transition from State 1 to State 2 (A)
//V11 represents latch on State 1 (B)
//V12 represents transition State 2 to State 1 (C)
//V13 represents latch on State 2 (D)
//V1 represents State 1 in the diagram
//V2 represents State 2 in the diagram

//X1 represents SW1's state
//V3 represents SW1's "old" state
//V4 represents a unique press on SW1

//Y1 represents the green light
//Y3 represents the red light

//block 1
V4 = X1&&!V3;
//block 2
V10=V1&&V4;
V11=V1&&!V4;
V12=V2&&V4;
V13=V2&&!V4;
//block 3
V1=V11||V12||SP0;
V2=V10||V13;
//block 4
Y1=V1;
Y3=V2;
V3=X1;

We have included a Boolean Algebra Program Simulator below you can use to test your codes. Paste this code into the simulator in the cell below to watch it work! Make sure to Run the cell below so that the simulator shows up before trying to run the code. Use the UPDATE button to load your code and run the simulator.

See the Pen p5.js Boolean Algebra Program Simulator w/Timers, Counters and touch scaled by Alexander Brown (@brownaa) on CodePen.

Exercise 1: Two-Robot Intersection - Due by the beginning of class on Wednesday, September 8, 2021

Your task is to design a program that replicates the behavior in the animation at the top of this notebook.

Fixed Assumptions

  • At most, there will be 2 robots in the intersection at one time.
  • There are inductive vehicle sensors under the path of the robots. Each is "active" or "true" when a robot is positioned over it, and "false" otherwise.
  • The gates will not activate until 2 robots have activated any combination of sensors 1,2, and 3.
  • All gates will be closed if no robot is present at the intersection.
  • The robots have been programmed by another team to proceed along the first available path that is not blocked by a gate. They will stop if all paths are blocked.
  • When robots activate sensors 1 and 2 (regardless of order of arrival):
    • gate 2 and 3 will open to allow the zumo coming from the south road to pass sensor 3
    • then gate 2 will close and gate 1 will open to allow the zumo coming from the north road to pass sensor 3
    • then gates 1 and 3 will close
  • When robots activate sensors 2 and 3 (regardless of order of arrival):
    • gate 1 and 2 will open to allow the zumo coming from the south road to pass sensor 1
    • then gate 1 will close and gate 3 will open to allow the zumo coming from the west road to pass sensor 2
    • then gates 2 and 3 will close
  • When robots activate sensors 1 and 3 (regardless of order of arrival):
    • gate 1 and 2 will open to allow the zumo coming from the north road to pass sensor 2
    • then gate 2 will close and gate 3 will open to allow the zumo coming from the west road to pass sensor 1
    • then gates 1 and 3 will close

Deliverables

  1. Draw a state transition diagram and paste it in the first answer cell below
  2. Create a state transition table in the second answer cell below.
  3. Draft your Boolean Algebra program in the third answer cell, using variables available in the simulator
  4. Test your program in the simulator and refine your answers as needed. Ensure that your submitted State Transition Diagram and Table are consistent with the final version of your Boolean Algebra Program.

Model Developement

Identify in the Mardown cell below the modeling assumptions you will use in your controller design regarding the behavior of the system elements.

YOUR ANSWER HERE

Controller Design: State Transition Diagram

YOUR ANSWER HERE

Controller Design: State Transition Table

YOUR ANSWER HERE

Controller Validation: Draft Boolean Algebra Program

Write code in Javascript by using the codeblock syntax in markdown. Enclose your code in backticks so that it formats nicely. Double-click this cell to see how:

//your code here. Comments are begun with a double slash. && is AND, || is OR, !() is NOT.`

YOUR ANSWER HERE

Controller Validation: Test and refine your program in the simulator

See the Pen p5.js Fill Station Simulator by Alexander Brown (@brownaa) on CodePen.

In [ ]: