None W01B_FSM_Boolean

Table of Contents

Challenge

The challenge associated with today's assignment is to complete the challenge presented in the last notebook. As a reminder, you will attempt to control the flow of factory robots. In this case the factory uses modified Zumo robots as well as floor sensors and gates. For this application, another team has developed the robot controllers and you are only responsible for the sequencing of the gates. The video below shows you the operation you will need to achieve.

In the last assignment, you were tasked with representing the gate system as a finite state machine, and creating a state transition diagram to govern the state machine's behavior.

While this is an important design and planning step, it does not allow you to directly implement your design in software or hardware. To do this, you need a few new tools to expand the disciplined process of FSM design. The sections in this notebook present a basic set of these tools. In today's assignment, you will actually code your first state machine using a built-in simulator of the gate system shown in the video!

Controller Design: Boolean Algebra

In ME480, each "state" in your finite state machine will be represented in software by a Boolean variable. A boolean variable is either true or false. Therefore, the job of a FSM computer program is to make sure that when the one (and only one) variable that represents a state in your state transition diagram is true all others are false.

For example, let's consider the design of a NHTSA Level 2 automation system in a car, similar to what is available on a Tesla Roadster. Say that you've designed the state machine governing whether the vehicle should maintain its lane, or change lanes to pass. Perhaps your diagram looks like the one below:

image.png

To implement this design, you would use a Boolean variable in your code to represent the truth value of each state. Maybe your variables are initialized as "LK," "LCL," and "LCR," to represent the three states in the diagram. The program's "main loop" will need to set just one of those variables true on each pass through the code, and make sure the others are false, in order to satisfy the fundamental assumption that a FSM can only be in one state at a time.

To make this actionable, we need to spend a little bit of time talking about how to create, evaluate, and code expressions using Boolean variables. In life, few things are "Black & White" or "True or False," but in the design of machines, two-state thinking is common. In the context of designing finite state machines, we use boolean algebra to write Boolean Expressions to represent whether a machine is in a particular state, and to represent the truth value of conditions, transitions, and latches.

This allows us to go from a design for a FSM in the form of a state transition diagram with transitions expressed in English to an actual computer program that keeps track of what state our FSM is in.

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.

See the code cell below for an example.

In [2]:
a = true
b = false

not(a)

a = 1
b = 0
ans = 0

But really, most things are not strictly off or on.

How do we deal with the ambiguity of "real life?" Mostly, we set "thresholds" for continuous variables that we wish to characterize with a Boolean "True" or "False." In digital circuits, such as the ones that make up your computer, logical "True" or "False" values like those that make up the bits of a binary number, are represented by voltages.

As you know from System Dynamics and/or Instrumentation, voltage is a continuous quantity. Logic circuits deal with this by setting "thresholds" for what they consider a "False" voltage (close to 0), or a True voltage (close to 3.3V, 5V, 12V, etc. depending on the operating voltage of the circuit). Your house's thermostat also uses this concept. If you set your thermostat to 68 degrees Fahrenheit, your house's temperature control system will consider anything below 68 degrees to be "cold," and anything above 68 degrees to be "hot," even though as humans we have a much more nuanced outlook on temperature.

So although real-life is continuous, there is value in modeling these systems with Boolean behavior.

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:

  1. NOT
  2. AND
  3. 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$.

Exercise 1: Boolean Algebra Practice-- Due by the beginning of class on Friday, Sept 3.

You will be programming your first state machine in the very next exercise using a simulator. The simulator will be able to help you evaluate whether your design and implmementation is correct, but it will generally not tell you exactly why your machine does not work. The Boolean Algebra rules and truth tables discussed above are supposed to act as evaluative tools during the disciplined process of state machine design. Therefore, let's get some practice using these for debugging so you'll be able to use them when you need them!

Consider the state transition diagram for the Tesla roadster at the beginning of this reading. The relevant state transitions of this diagram along with a picture of the obstacle sensors on the vehicle are shown below:

image.png

On this vehicle, each of the sensors $S_l,S_r,S_b,S_f$ provides a Boolean "true" to your state machine program when there is something in the way, and "false" otherwise.

Let's consider only the transition from "Lake Keeping" to "Lane Change Left" in the diagram above. The desired behavior here is that:

"The vehicle should enter state Lane Change Left (LCL) if it is currently in state Lane Keeping (LK), and if no car is behind us, no car is to our left, and there is a car in front of us."

In attempting to program your finite state machine, you defined the following row in your state transition table:

Transition Starting State Transition Condition Ending State
A Lane Keeping (LK) $\overline{(S_l\cdot S_b)}\cdot S_f$ Lane Change Left (LCL)

The corresponding line of code in your logic program is:

A = LK&&!(Sl&&Sb)&&Sf;

Unfortunately, your logic for transition "A" is wrong. It is not true when you expect and therefore the Lane Change Left state will not be true when needed. Your task is to use the Boolean Algebra simplification rules and a truth table to determine why the logic in the table (which matches the logic in the line of code that sets variable A to either true or false) does not produce the desired behavior.

Use the markdown cell below to:

  1. Show a truth table identifying the problem
  2. Include a short explanation
  3. Show a corrected line of code defining transition A to meet the specifications described above

YOUR ANSWER HERE

Exercise 2 - DUE by the beginning of class on Friday, Sept 3.

Now that you have the ability to represent transitions between states as codeable boolean algebra, you can use this to validate a controller design. Noting that you have only a few days to complete this assignment, it is possible that you may not get the controller to meet every requirement. Perfect execution is not the expectation here. However, it is extremely important you make an earnest effort. It is in these attempts that you will both better understand the Boolean algebra explained above and be ready for the next step in controller design we'll discuss on Friday.

Controller Validation: One-Zumo Intersection

Now it is time to program your first ever FSM! This FSM will be the realization of the challenge at the top of this notebook. You must program the gates of an intersection to produce the behavior shown in the animation at the top of this assignment.

To get started, look back on the Week 1 Monday assignment.

Paste your state transition diagram and table in the answer cell below as it was submitted on Monday. This portion of the assignment is graded on completion.

YOUR ANSWER HERE

Now, use this diagram to generate code that operates the three intersection gates. Do not modify your diagram! Just make a first attempt at generating code from the diagram you submitted on Monday. Once you have generated your code in Arduino/Javascript format (same as the example above), paste it into the Zumo intersection simulator and observe its operation.

IMPORTANT: You will need to "save" your code by pasting it in the markdown cell above the simulator cell. The simulator itself will not save your code once you close this notebook or reload your page!

Double click the cell and add your code. Use the "back quote" to mark the block of code so Jupyter will render and highlight the code properly.

```javascript

```

You can find the ` character on the upper left key on the keyboard

An example code is provided below to get you started, which opens gates 1 and 2 if a zumo approaches the straight section of road from either side. Note that in this example, "V1" might represent a state called "zumo go straight." Y1 being true lifts gate 1, and Y2 being true lifts gate 2. Therefore, in this simple case, because I want both Y1 and Y2 to lift if "let zumo go straight" is true, I can simply set each gate's truth value be equal to the truth value of the state "let zumo go straight." If you'd like to try the starter code in the simulator, copy and paste it in, and then hit the update button on the simulator.

paste your initial code below. This portion of the assignment is graded on completion

YOUR ANSWER HERE

//See the simulator for notes on what each variable means

//variable V1 represents the state "north/south travel"

V1 = X1||X4||X2;

Y1 = V1;
Y2 = V1;

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

Did your solution work? If not, rework your state transition diagram and transition conditions, modifying your code as necessary. Paste your work, including any tables, diagrams, and code that you come up with, into the markdown cells below. If you need to add more cells, do so using the "insert->cell" command from the Jupyter toolbar, and then change the cell type to "markdown" using the "cell->cell type" option in the Jupyter toolbar.

Because the simulator allows you to self-assess, and because you now have tools to debug your work, this portion of the assignment will be graded on correctness. Your instructor will run your code as submitted to determine your score.

Updated State Transition Diagram and table goes here:

YOUR ANSWER HERE

Updated Code Goes here. Use three back quotes above and below your code as in the example above to format it properly.

```javascript

```

YOUR ANSWER HERE

This is an extra cell for your work if needed (pictures, etc.)

This is an extra cell for your work if needed (pictures, etc.)