Table of Contents
- 1 ME480
- 2 FSM
- 2.1 Controller Design: Boolean Algebra
- 2.2 Controller Design: The Four-Block Structure
- 2.3 Controller Design: The challenge of the first loop. How do you get in to the starting state?
- 3 Dynamic Modeling
- 4 Feedback Control
ME480¶
The ME480 Disciplined Process¶
You'll need to use a process to help guide decisions about what is needed and what might not be working to develop a controller for a system. The process can be extended from your system modeling experience in ME352. For both system modeling and controller design you need to develop an expectation of what will happen and then compare that to what does happen.
FSM¶
Finite State Machine (FSM) Model¶
However, to keep this model as simple as possible we could say "we assume the time it takes to transition between sleeping and awake is short enough that we aren't interested in the details of the transition". This means that we would only practically be interested in whether the brain was "sleeping" or "awake" as the transition would be so short it wouldn't be of interest.
This type of model is very common and allows you to represent different "situations" as Boolean States. A FINITE STATE MACHINE is a model that is always in a defined Boolean State and the time to transition between the states is neglected. While not everything can be accurately represented by a Finite State Machine model, they are very common in robotics and industrial control systems.
Each of the "Boolean States" in a finite state machine can take only one of two values:
- True (the machine is in this state)
- False (the machine is not in this state)
If you use a finite state machine to model your system then two assumptions are required
- The number of Boolean states is finite, meaning that you can count them.
- A Finite State Machine can be only be allowed to be in one Boolean state at a time.
Note that we are using the term "Boolean State" to distinguish from the "state" you're familiar with from system dynamics used in "state space" models.
FSM State Transition Diagrams¶
A state transition diagram is a design tool for FSMs that allows you to organize how your system will move from one state to another. It consists of bubbles representing each Boolean state, and arrows that show how the system is permitted to move between those Boolean states. A generic example is shown below-- note that it is not possible for the system to move from state 3 to state 1!
FSM - INPUTS, STIMULI (CONDITIONS) and TRANSITIONS¶
In general, it takes some kind of "stimulus" to cause a state machine to leave one Boolean state and go to the other. In our brain model the stimulus that brings you from "Sleeping" to "Awake" might be an alarm going off for your 8AM class. The transition from "Awake" to "Asleep" might be described by the condition that "you're tired and it's past your bedtime."
There are two types of stimuli that we will deal with in ME480:
- Inputs (stimuli from the user/outside world)
- Internal Stimuli (e.g. a timer internal to the controller)
Inputs are often things like switches, buttons, and control panels on a robot or machine. "Timers" in an FSM program keep track of how long it's been since some event has occurred, and "Counters" keep track of how many times something has happened. You'll learn about those in upcoming notebooks.
FSM: State Transition Tables¶
State transition tables are like a "key" that is used to read a state transition diagram. Each row represents a transition on the state transition diagram.
| Transition | Starting State | Condition | Ending State |
|---|---|---|---|
| A | Sleeping | Alarm rings | Awake |
| B | Awake | Bedtime and I'm tired | Sleeping |
Once this table is constructed, you can describe each entire transition from one state to another by reading across the table. For example, for transition B, we have:
"Transition B occurs when the state is 'Awake' and 'Bedtime and I'm tired' occurs."
Note that state transition tables are typically written using mathematical shorthand rather than full sentences. We will learn how to do this in a subsequent notebook.
FSM: OUTPUTS¶
In a FSM, what is considered an "output" is up to the engineer. Usually, an output is something that the machine uses to interact with its environment or its user... something observable to the outside world. Examples could be lights that indicate machine operation, signals that power motors or pumps, or text displayed on a user interface. One way to think about states is that they are "unique collections of system outputs."
What would the outputs be in our brain model?
The tools you need to design the gate-intersection system are same ones needed to control robots, AI characters in a video game, traffic lights, microwaves, digital watches, etc. Each of these machines and systems share the need to have a control system that makes a "decision" about how it will behave.
Synchronous FSMs¶
In this course, we will generally consider synchronous state machines, which basically means that their operation is governed by a clock signal executing one command after the other at a specified time. Generally, a synchronous state machine implemented in software consists of an "infinite" program loop that runs over and over. In each "loop" of the program, inputs are measured, logical conditions are evaluated to determine what state the machine should be in based on the user inputs and the machine's prior state. Then, at the end of each loop, outputs are written (think motors, lights, buzzers, etc.) based on what state the machine is in.
There are other types of state machines! For more information on types of state machine (this will not be on a test!) you can refer to this link or this one.
Because the state machines we will be implementing in this course are synchronous and running on an infinite loop, they need to make a decision about which state to be in every time through the loop. The decision has to be made regardless of whether anything of note has happened, and the software we write to implement a FSM must set each boolean state variable to either true or false on each pass through the loop.
Controller Design: Boolean Algebra¶
Boolean Variables: two possibilities¶
It's possible to intuit the concept of a Boolean variable. Here are some example manifestations:
| False | True |
|---|---|
| 0 | 1 |
| low | high |
| energized | de-energized |
| open | closed |
All of these words are equivalent. In some programming languages (like Arduino), you can use "0" or "false" or "LOW" interchangeably to represent "false," and "1," "true," or "HIGH" to represent true. Many languages, however, are more restrictive. MATLAB (or its open-source equivalent, Octave), for instance, insists that Boolean variables are assigned a value of either "true" or "false" or "1" or "0," respectively.
Operations on Boolean Variables¶
The building blocks of "Boolean Expressions" are the basic logical operators "OR" "AND" and "NOT." A Boolean expression can be thought of as a statement of equivalence comprised of Boolean (true/false) variables,
OR¶
The "or" operator is often written as a "+" sign. Example: "C is true if A or B is true" can be written:
\begin{equation} C = A+B \end{equation}In ME480 our simulators and programming languages use "||" to represent "or" so the expression above would be coded as:
C = A||B;
AND¶
The "and" operator is often written as a dot, $\cdot$, or ommitted entirely. Example: "C is true if A and B are true" can be written:
\begin{equation} C=A\cdot B \end{equation}In some circles (including this class), the $\cdot$ AND symbol can be omitted so the expression $Y=A\cdot B$ is the same as the expression $Y=AB$.
ME480 simulators and the programming languages used in the course use "&&" to represent "and" so the expression above would be coded as:
C = A&&B;
NOT¶
The "not" operator is often written as a bar over an existing variable, e.g. $\overline{A}$. For example, the statement: "C is true if A is not true" can be written:
\begin{equation} C=\overline{A} \end{equation}However, most programming languages do not allow you to use a $\overline{}$ sign to represent "not." In ME480, our simulators and hardware use languages that represent the "not" operator with a ! character. MATLAB (and Octave) are a bit different-- they represent "not" by either a tilde (~) or the word "not()." In an Arduino or ME480 simulator program, however, defining the Boolean variable "C" to be true if "A" is false, and false if A is true, we could write the following line of code:
ME480 simulators and Arduino use "!()" to represent "not" so the expression above would be coded as:
C = !(A);
MATLAB and Octive use "~" to represent "not" so the expression above would be coded as:
C = ~A;Common Symbols for Boolean Operations¶
The table below shows a summary of characters used for Boolean operators in different programming languages. It also includes the symbols use in other disciplines like philosophy.
Note that for "NOT," we include a "." to show that we are negating something. The "." is not part of the symbol(s).
| Language | OR | AND | NOT(.) | |
|---|---|---|---|---|
| ME480 | $+$ | $\cdot$ | $\overline{.}$ | |
| MATLAB | $ | $ | $\&$ | ~.,"not(.)" |
| Python | $|$, "and" | $\&\&$, "or" | ~., "not" . | |
| C,C++,Java,Arduino | $|$ | $\&\&$ | !. | |
| Philosophy, Logic | $\lor$ | $\land$ | $\neg .$ |
Order of Operations¶
Formally, the order of operations for Boolean Algebra is:
- NOT
- AND
- OR
Note: The "NOT" operator, denoted by the overline $\overline{.}$, has implied parentheses that span its length. Parentheses are used to group terms the same way as an overbar can be used, so parentheses and the "NOT" operator have equal precedence.
Much the same as it is in arithmetic and/or algebra. the "AND" ($\cdot$) operator takes precedent over the "OR" ($+$) operator, and parentheses can be used to group portions of an expression.
Truth Tables¶
When we evaluate a Boolean expression, it's often necessary to look at all possible combination of inputs (variables on the RHS of the expression) and evaluate their corresponding output (assigned variable on the LHS of the equation) to understand the implications of subjecting the expression to all possible combinations of inputs. To do this, we use a tool called the Truth Table. For example, the truth table for the expression $C=A\cdot B$ is given below:
| $$A$$ | $$B$$ | $$C=A\cdot B$$ |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 1 | 1 | 1 |
Note that I needed to exhaust all possible combinations of the inputs in order to construct the table. As the number of inputs grows, so does the number of combinations you must test! In fact, there are $2^n$ combinations, where $n$ is the number of inputs in the expression!
Even with this complexity, truth tables are useful for testing more complex expressions "brute force." A good first example of this is the "XOR" or "exclusive OR" operator (shown as $\oplus$). This is like an "OR" operator but returns false if both A and B are true. By definition, the "XOR" operator is defined according to the following statement:
$$A\oplus B = \left(A+B \right)\cdot\overline{A\cdot B} $$The procedure for constructing a truth table is simple. Create a column for each variable in the Boolean expression, and then create columns for intermediate steps in computing the expression according to the order of operations. Make certain that you exhaust all possibilities for combinations of inputs, or else the truth table will not be "complete."
| $A$ | $B$ | $A \oplus B$ | $A+B$ | $AB$ | $\overline{AB}$ | $\left(A\right. + \left.B \right) \cdot \overline{A\cdot B}$ |
|---|---|---|---|---|---|---|
| 0 (false) | 0 (false) | 0 (false) | 0 (false) | 0 (false) | 1 (true) | 0 (false) |
| 1 (true) | 0 (false) | 1 (true) | 1 (true) | 0 (false) | 1 (true) | 1 (true) |
| 0 (false) | 1 (true) | 1 (true) | 1 (true) | 0 (false) | 1 (true) | 1 (true) |
| 1 (true) | 1 (true) | 0 (false) | 1 (true) | 1 (true) | 0 (false) | 0 (false) |
| ............... | ............... | ............... | ............... | ............... | ............... | ................................... |
The intermediate columns in the table above make evaluating the expression easier by grouping terms.
Properties of Boolean Expressions¶
It is possible to evaluate any Boolean expression using a truth table, but it is long and tedious! Using a few simplification rules presented below make the job becomes much easier.
Commutative Property¶
\begin{equation} A\cdot B = B\cdot A \end{equation}\begin{equation} A+B=B+A \end{equation}Associative Property¶
\begin{equation} \left(A\cdot B\right)\cdot C = A\cdot \left(B \cdot C\right) \end{equation}\begin{equation} \left(A+B\right)+C = A+\left(B+C\right) \end{equation}Distributive Property¶
The AND operator can be distributed into an OR expression (just like multiplication into addition!)
\begin{equation} A\cdot \left(B+C\right)=\left(A\cdot B\right)+\left(A\cdot C\right) \end{equation}Simplifying expressions: DeMorgan's Laws¶
DeMorgan's Laws, or the Laws of Negation, can be used to simplify long, complex Boolean expressions. It would be good practice to prove these using hand-written truth tables! Committing these to memory is actually quite usefule as they show up a lot in practical expressions common in logic-based programming and control (e.g. FSM design/implementation).
The first of DeMorgan's laws is one we like to call "neither!" It explains how to say that "neither A nor B can be true." \begin{equation} \overline{A+B}=\overline{A}\cdot \overline{B} \end{equation}
The second of DeMorgan's laws is one we like to call "Not this, or not that." It describes how to say that an expression is true if either A is false, or if B is false. Note that this is different than the case above, which says that neither A nor B can be true if the expression is to return true.
\begin{equation} \overline{A\cdot B} = \overline{A}+\overline{B} \end{equation}Example: Boolean Algebra Expression Simplification¶
Making use of these rules can help you simplify complex logic. Consider the following Boolean algebra expression.
\begin{equation} Y=A\left(\overline{A+B}\cdot B\right)+B \end{equation}The truth table for this would be epic. However, if we make the simplification for $\overline{A+B}$, we see that we get:
\begin{equation} Y=A\left(\overline{A}\cdot\overline{B}\cdot B\right)+B \end{equation}$B$ and $\overline{B}$ can never return true (B cannot be both true and false at the same time) so the whole parenthetical expression disappears, leaving us with $Y=B$.
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.
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.
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 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.
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.
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.