Table of Contents
- 1 Challenge
- 2 The ME480 Disciplined Process
- 3 System Model Development
- 4 System Model Validation
- 5 Controller Design
- 6 Controller Validation
- 7 Exercise 1 - DUE by the beginning of class on Wednesday, 9/1/2021
- 7.1 Challenge: Zumo Intersection
- 7.2 Controller Design: Fixed assumptions
- 7.3 Model Development: Your Gate System
- 7.4 Controller Design: Your State Transition Diagram
- 7.5 Controller Design: Your State Transition Table
- 7.6 Controller Design: Your Model Development
- 7.7 Controller Validation: Zumo Intersection
- 7.8 Synchronous FSMs
IMPORTANT!! Before reading a Jupyter notebook assignment, navigate to Cell->Run All from the menu. If you do not do this, important content such as videos and simulations may not show up!
Challenge¶
Robots, factories, AI characters in a video game, traffic lights, microwaves and digital watches all require a control system to "decide" what the machine/software/system is doing at any moment.
In this class you will need to control electromechanical systems, including a small tracked "zumo" robot, so you will need to learn how to implement "decision-making" for this kind of system. This will mean controlling when to move, when to stop and when to turn, for example.
The video below is an example of the kind of control you will learn. To render it, make sure you have selected Cell->Run All from the menu bar!
(Amazon News. "Amazon’s newest robots mean new jobs." Online video clip. YouTube. Youtube, 5 June 2019.)
Although this factory system is very complex, you are capable STARTING to design such a control system RIGHT NOW! As a first step you will need to design one part of a large factory robot control system. This first assignment, due by the beginning of class on Wednesday, is to attempt to control the flow of factory robots. In this case the factory uses modified Zumo robots as well as floor sensors and gates. 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.
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.
As a way to get familiar with this process we'll consider what it will take to make a device that acts like something familiar. For this example we'll use the brain!
System Model Development¶
To design a controller we need a model of the system we need to control. This lets us predict the effectiveness of our controller without the cost of fabrication or the risk of a live experiment.
This means we need to make a "model" of your brain. We really aren't sure at this early stage of the disciplined process what kind of model we'll use, so we'll begin by thinking about what a brain does based on our experiences and see if that can get us started. If you start to think about what the brain does... it turns out it does a lot!
However, at this point we are NOT trying to make the best model of a brain, we are just trying to come up with any reasonable model. So lets begin with the simplest model we can come up with and then we can increase the complexity later if needed.
That means we MUST make assumptions about how much of the complexity of the real system we'll capture in our model. As engineers we need to do this in ALL situations and ALL times. We will never model a real system EXACTLY. A model will always be some kind of approximation and that is ok if it captures behaviors we care about, and is predictive of the system's behavior within the bounds we wish to model. This ethos is captured well the following 1991 paper by philosopher Daniel Dennett called "Real Patterns.". Dennett casts the problem of simplification of actual phenomena in terms of pattern recognition, but the idea is the same: simplified engineering models of dynamic systems are valuable if they are predictive over the range of inputs we suspect the system will see.
To get started we'll need to think about a very basic behavior of the brain. Even then there are A LOT of choices, but we will assume that the brain moves between only two "situations": Being awake and being asleep. Like your experience modeling systems in ME352, we need to have some idea of how the system dynamically moves between these two situations. We probably don't have a lot of knowledge about the physiology of the brain, but we do have some common system modeling experience. Using that we could propose the following brain response behavior:
System Model Validation¶
With a model in hand, is there any way we can assess its validity? Do we have data or theory to "test" it? Sometimes we might have previous experience and/or data we can draw on, but in this case we would likely need to seek out new knowledge. A brief search of articles identified this article as a potential resource.
The authors looked at the ability of participants to perform a task (lifting their finger when a "target tone" was heard) as they fell asleep. The data for the participants' ability to do this is shown in the figure below, which was pulled from the paper text.
This is interesting, and it does appear that as time goes on and brainwave activity indicates the participants are falling into sleep, their ability to respond to the task follows a curve that looks (roughly, if you squint) like our model!
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.
What do these mean for the brain model? It means that if we were to develop a Finite State Machine (FSM) model of your brain, we would be asserting that your brain cannot be both asleep and awake at the same time. It would be reasonable to say that a brain model needs more than two states, but this is only a model. If more complex behavior is revealed to be important as you validate your controller design, than more states can always be added to the model.
Controller Design¶
Now that we know how your system behaves, we need to design a controller that will allow us to dictate when and how it does those things.
To begin developing tools for the design of Finite State Machines, we can create a State Transition Diagram.
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!
The details of how to set up a state transition diagram are best learned by example, so let's continue with the Sleeping/Awake model of the brain.
Here each Boolean state of our brain model is shown as its own bubble as seen below.
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.
The diagram below indicates how the arrow and transition condition indicates what happens if the brain is the Sleeping state AND the "alarm goes off" transition condition occurs. The brain will change to the Awake state. EVERYTHING shown in the diagram is needed to define a State Transition.
On a State Transition Diagram,the arrow from one state to another is a State Transitions. These arrows describe how the FSM changes states. The Transition Conditions represent the inputs or internal stimuli are needed to cause the states to transition. In this case it is the "Alarm Goes Off".
To better understand the difference between a Transition Condition and a State Transition, consider what would happen if the "Alarm Goes Off" when the brain is in the Awake state. Will it cause the brain to transition states again?
Thinking through the scenario, the alarm will not cause a state transition if already in the Awake Boolean state so we would NOT show an arrow from Awake to Sleeping for that conditoin.
It will quickly become difficult to fit all of the transition conditions as complete labels on our state transition diagram, so we will use shorthand labels to make the diagrams easier to read. Below is the complete state transition diagram for our brain model.
We'll use a State Transition Table to clearly define the state transitions and the transition conditions shown in the diagram.
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: Latches¶
Consider our brain example. What happens when you are Awake and it is not bedtime?
You may think it's obvious that the brain should remain in the "Awake" Boolean state, but that possibility is not accounted for yet in our diagram and table. For an FSM design to be complete, all logical possibilities must be accounted for in the state transition diagram. This means that we have to be very explicit about when we stay in the "Awake" state and when we stay in the "Sleeping" state.
To keep an FSM in a Boolean state, you need to use a transition from a state back to itself. These state transitions are called Latches. They are a very special transitions that can make or break your FSM design!
We can draw a latch state transition on our diagram the same way as any state transition arrow with the current Boolean state (at the beginning of the arrow) and the new state (at the point of the arrow) being the same!
In the diagram above, we added state transitions "C" and "D", which are based on the logical statements in the table below. Note that the order in which you label the transitions, latches, and conditions is not important, but it helps to organize them for yourself so the table is easy to read and is quickly referenced.
| Transition | Starting State | Condition | Ending State |
|---|---|---|---|
| A | Sleeping | Alarm rings | Awake |
| B | Awake | Bedtime and I'm tired | Sleeping |
| C | Sleeping | The alarm has not rung | Sleeping |
| D | Awake | It is not bedtime and I'm not tired | Awake |
Notice that transitions B and C both result in the machine ending up in the "Sleeping" state. This can be read as "The brain will be in 'sleeping' if A is true or if C is true."
It's important to note that the latch condition for each state covers all possibilities that the transition conditions out of that state did not. This is because each time we "make a decision" about which state to be in, we have to end up in one of our Boolean states! For this simple two state model, it is possible to see by inspection we have covered all possibilities for all of the inputs and states of our state machine.
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?
We could assume that our brain model's only output is either open or closed eyes. So the eyes would be "open" in the awake state and they would be "closed" when in the asleep state.
Outputs are not explicitly shown in a state transition diagram, so you will need to keep track of which outputs belong to each state in your FSM model by writing them down separately.
If you wanted to make our brain model more realistic, you could add more outputs! You could add outputs based on each of the states (heart rate 70 when awake vs. heart rate 45 when asleep, etc.) without changing the design of the FSM as shown in the state transition diagram and table.
FSM Designs are NOT unique!
FSM designs offer the designer a lot of freedom. Your choice of states is just that-- a choice. As you move through the semester, you'll be asked to design FSMs to control the high-level operation of your robot, of laboratory experiments, or of the control systems you'll design and analyze on homework assignments and exams. You may not always choose a "friendly" set of states, but don't despair! Practice will make you more and more adept at choosing a design that's simple but effective.
Controller Validation¶
At this point its time to validate your controller design by implementing it and seeing if it behaves as you expect. The implmentation of the controller design could take many forms. It could be the system you ultimately control is entirely within a computer program. Or maybe it is a very simple physical system that uses 2 LEDs for "eyes".
Or maybe this is the first step in developing a humanoid robot
Creepy? Maybe. This paper is an interesting read about robot eyes.
Whatever the implementation, the validation would come from observing what the implemented controller does. Do the eyes open when an alarm goes off? Do they close when enough time has passed that your brain should be "tired"? From observation you would assess if your controller and system meets your expecatations. What if it doesn't work? The disciplined process shows you would start revisiting previous steps, look for the issue, and try again!
Exercise 1 - DUE by the beginning of class on Wednesday, 9/1/2021¶
Challenge: Zumo Intersection¶
Your first assignment is to develop a state transition diagram and table for the finite state machine model of the robot intersection shown below. The assignment is to be submitted by Wednesday, Sept 1 by the start of class.
You have only learned how to design finite state machines, not how to implement and test them. So there is no expectation you can evaluate your design! The assignment is to simply use the tools and knowledge presented in this notebook as best you understand them and submit a design.
However, this does identify a need to learn how to implement your design to see if it will work! Stay tuned!
Controller Design: Fixed assumptions¶
The list below is a set of assumptions that you will incorporate into your system model and controller design. Because they are assumptions they technically could be changed. However, to keep the designs consistent we will consider these FIXED ASSUMPTIONS unchangable for this challenge.
System Model
- 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.
Controller Design
- 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.
- Only 1 robot will be in the intersection at a time.
- All gates will be closed if no robot is present at the intersection.
- When a robot approaching the intersection activates sensor 1, gate 1 and gate 2 will open. The robot will automatically proceed straight ahead and the gates will close when the robot has passed beyond sensor 2.
- When a robot approaching the intersection activates sensor 2, gate 2 and gate 1 will open. The robot will automatically proceed straight ahead and the gates will close when the robot has passed beyond sensor 1.
- When a robot approaching the intersection activates sensor 3, gate 3 and gate 2 will open. The robot will automatically turn right and then proceed ahead. The gates will close when the robot has passed sensor 2.
Model Development: Your Gate System¶
Although simplistic, explain your "model" for the gate system you're controlling. Describe the relationships between inputs and outputs that you're assuming apply to each of the gate system's componenents. At this point in the semester, these could be very simple, but you need to have expectations for how each of the components will work! It is likely you'll revist this answer several times in the process as you better understand what kind of model is needed to implement your controller design.
YOUR ANSWER HERE
Controller Design: Your State Transition Diagram¶
Create your diagram using draw.io. Here is a very short video to get you started quickly. When you have completed the diagram, cut and paste the image of your work into the cell below.
YOUR ANSWER HERE
Controller Design: Your State Transition Table¶
Double click on this cell to copy/paste a basic table into the cell below. Add rows and fill it out as needed.
| Transition | Starting State | Condition | Ending State |
|---|---|---|---|
| A | State x | Description of condition | State y |
YOUR ANSWER HERE
Controller Design: Your Model Development¶
Explain the model you used for your controller and what assumptions you made (beyond the fixed assumptions)
YOUR ANSWER HERE
Controller Validation: Zumo Intersection¶
Normally you would validate your model of the controller you designed, but for now you don't have any way to evaluate it. That means that after you've applied the disciplined process as best you understand it, you are done... for now! That means we know what the next step will be... learn HOW to validate our model of our controller design!
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.