18-649 Project 4
Time-Triggered Design Using Statecharts
Check the course webpage
for due dates
Please submit all project-related correspondence to --
- 9/26/2011 - Clarified that elevator must be fully designed by
this project handin. "NOTE"s added in Assignment section.
This semester, your group will specify, design, and build an
elevator control system and use it to control a simulated
elevator. You will learn of and deal with many of the details of
building a distributed, real-time, embedded system.
In project 3, your project matured from concept to specification
when you wrote the event-triggered behaviors for some of the
controllers. In this project, you and your group will design the
time-triggered behavioral requirements for those controllers.
Then, you will express each controller using a state chart.
You will transform your requirements specification from an
event-triggered system to a time-triggered one, and complete a
detailed design document. No longer are there discrete events that
cause information processing and state changes in your
controllers. In your time-triggered system, once during each cycle
(we use cycle here as some unit of time determined by processing
and control needs) a time triggered machine looks at the
information it has available to it, possibly calculates some
internal variables, and decides whether it should transition to a
new state. For each non-environmental object, you will complete a
detailed design using UML state charts as described in the
PLEASE KNOW THAT CODE AND DESIGN ARE DIFFERENT THINGS.
Code should be well designed, but there should be no actual code
in your design. If there is code, it is not a design, and so it
will be graded as code and not a design---which means you will
earn no points for that submission item. Pseudo code is acceptable
for expressing guard conditions, state outputs, and so on, but you
should use it as little as possible. This applies to requirements
as well as statechart actions and trigger conditions.
The procedure for this assignment is:
- Rewrite your event-triggered behavioral requirements to be
time-triggered. This means that instead of acting on events
(like receiving a message), the controller modifies its outputs
based on the current value of state variables. When you found
yourselves doing tricky state variable manipulation to get a
correct event-triggered behavior, you will find that
time-triggered requirements make your design much simpler.
- You can assume that each controller maintains a copy of the
system state that consists of the most recent message values for
all messages the controller receives. For simplicity, you
should continue to use the mMessage notation (e.g.
mHallCall[f,b,d]) to refer to these state variables.
- Make sure that you have a complete set of time-triggered
requirements. It is up to you whether you leave your
event-triggered requirements in place or remove them and replace
them with time-triggered requirements. If you choose not
to remove the event triggered requirements, make sure that you
us a different numbering scheme for the two sets so that there
is no ambiguity..
- You will need to update your requirements-to-sequence-diagrams
and requirements-to-constraints traceability to reflect the new
requirements you have written. Since only the
time-triggered requirements will be used as you go forward, it
is acceptable to trace only the time-triggered requirements
(i.e. in the traceability, you can let the TT requirements
replace the ET ones).
- NOTE: The format for
time-triggered requirements is slightly different from those
presented in the lecture, and this assignment supercedes what
was presented in the lectures. Read the
discussion below on Time-Triggered
Design for more guidelines.
- Keep track of changes to your design using the issue
log. If you make any substantive changes to your
behavioral requirements (such that an outside observer would
notice a different behavior), you must document those changes in
the issue log which is included with the project portfolio
template. If, in the course of writing requirements
or statecharts, you find that you must add or modify your
scenarios and sequence diagrams, you must document these changes
in the issue log as well.
- In the course of rewriting your event-triggered requirements
as time-triggered, you only need to log changes if you change
the behavior of the system. If the new requirements have
the same function as the old requirements, no log entry is
- Design a state chart for each non-environmental control
The state charts shall be time-triggered with guard
conditions, not event-triggered. Although you may not
agree with this design choice, you are required to design a pure
time-triggered system. Time triggered design is a often a
good choice for reliable, distributed systems, and our goal is
to teach you this technique. For detailed information
about time-triggered design, see the following section of this
writeup on Time-Triggered
Design and the course lecture notes.
NOTE: The statecharts should fully describe your working
elevator. You should have a complete Sabbath elevator design
by the end of this week. This may require you to create more
use cases or scenarios than what we originally gave you.
- Ensure backward and forward traceability by documenting the
relationships between each behavior requirement and each state
chart transition arc or state. Only trace the time-triggered
In order to do forward and backward traceability in one table,
construct a table with the requirement numbers across the first
row and the states and transitions down the first column.
Put an X in the appropriate cells to indicate that a
state/transition supports a requirement. See the example. A correct
design will have at least one state or transition for each
requirement and at least one requirement for each state or
transition. So, every row and every column should have at least
one X in it.
- Forward traceability means directly relating each
requirement in the specification to one or more states
- Backward traceability means directly relating each state
or transition to one or more requirements.
NOTE: For this project, nothing should trace to future
expansion except network messages that are transmitted but
- Perform a peer review of your statecharts. You must
complete a peer review checklist for each statechart ie. one
peer review per object. Record the results in a peer
also complete a log entry into peer review log. Recording
defects on the peer review sheet does NOT result in point
deductions. Be honest.
- Turn in your complete team design package.
Time-Triggered Design Overview
Follow these guidelines when doing your time-triggered
design. These guidelines are very strict, but are intended
to guide you down the path to a time-triggered design. In
some cases, these requirements are more restrictive than other
guidelines (such as some UML techniques which we specifically
prohibit). These restrictions are in place to prevent you
from making design choices that will make your life more difficult
In this project phase, you may not change the input or output
interfaces for any of the control objects.
Time Triggered Requirements
Time triggered requirements:
- DO have the form IF <condition> then <state variable
or output> shall be set to <value>.
- <condition> is a compound logical statement composed of
zero or more tests of state variables and zero or more tests of
message values combined with boolean AND and OR operators.
- <output> can be a message value that is in the output
interface for that controller or state variable.
- DO have one number per verb. If a condition results in
two outputs being set, then you can subnumber them, as in:
12.1 If CONDITION A,
12.1a B shall be set to TRUE
12.1b C shall be set to FALSE
As with the previous projects, you should always trace to the
the sub-numbered requirements.
- DO set outputs based on the current state of the system (not
how you arrived at the current state).
- DO NOT contain phrases like "message received" or references
to other events in the system.
Time Triggered Statecharts
Time triggered statecharts DO:
- Set every output (in the controllers output interface) in
- Make decisions based ONLY on the current state of the system.
- Have mutually excluding transitions. This means that no
combination of state variable values can result in a TRUE
condition for more than one arc that originates from a single
- Only list transitions and state actions in one place (in the
diagram or in a separate table, but not both).
- Describe the controller in a way that is easy to read.
- Make sure all text is clearly legible.
- Make sure it is clear which transition the labels correspond
Time triggered statecharts DO NOT:
- Have actions on arcs (even though this is allowed by UML).
- Make decisions based on how the current state was reached
(this is basically an action on an arc).
- Have entry actions (* notation) -- every action performed in a
state must be performed every time the statechart executes.
- Have branches in transitions (even though this is allowed by
UML). Just make two separate transitions.
- Use a state variable as a substitute for a state. If you
have two sets of transitions out of a state that are
distinguished by a boolean state variable, you have likely
collapsed the two states into one state. For example, a
"DoorIsClosed" state variable might be used to collapse a
"DoorOpen" state and a "Door Closed" state into a "Door Motor
Commanded to Stop" state.
UML has a very rich syntax for defining nested statecharts.
We advise you to avoid nested states as much as possible.
However, if you choose to use nested states, observe these
- The separate substates of an AND state (concurrency) may not
modify the same state variables or outputs. Transition
conditions in one portion of the AND state may be based on the
output of the other portion, but watch out for race
- If you use nested states, no transition may cross the boundary
of a super state. This means that all transitions MUST be
between states at the same level in the state hierarchy.
In addition, each level of the state hierarchy must have its own
initialization conditions. The figure below shows an
example of a transition that crosses a superstate boundary.
Note that transition actions and entry actions are specifically
prohibited. These are very tricky to get right in
implementation, and can easily lead to deadlock or other race
conditions. In general, if you think you cannot avoid these, then
you can implement them in a strict time-triggered way using
intermediate states. However, we urge you to avoid this
approach. Intermediate states add latency and
complexity. If you choose to use intermediate states in your
design, note that they must follow all the guidelines for normal
states (like setting all outputs). In the implementation
phase, you will not be allowed to make more than one transition in
a single execution of the controller
For an example of time-triggered requirements, statecharts, and
traceability, you may refer back to the TestLight example from Project 1.
You may notice that the passenger object specification has
actions on transitions. This is because the passenger is
inherently event driven. For this reason, you should not
base your design on the passenger specification.
For the first half of the course we are suggesting you design a
really simple dispatcher while you learn the system, design
techniques, and other aspects of the project. If you really want
to have a more complex dispatcher you are welcome to do so. But,
whaver you decided to design has to be working for the
mid-semester hand-in, so don't be too aggressive. In the second
half of the course we will require you to improve your dispatcher.
If you find any problems or "bugs" with the assignment, please
let us know immediately so we can fix it. While we'll do
everything we can to give you a quick response, there are
reasonable limits to our availability. If we have to make a change
we'll announce the change on blackboard. In the unlikely event we
make a major and/or urgent change, an email from the course staff
will accompany any announcement on blackboard.
Team Design Portfolio
The portfolio you submit should contain the most up-to-date
design package for your elevator system organized into the
following directories. You are
going to update your portfolio every week, so be sure to keep an
up to date working copy.
Files that you should update for this week are:
- Portfolio Table of Contents (as needed)
- Scenarios and Sequence Diagrams
- Improvements Log
- Requirements II - time-triggered requirements, statecharts,
and requirements-to-statecharts traceability.
- Sequence Diagrams to Requirements Traceability
- Requirements to Constraints Traceability
- Issue Log
- Peer review log
Handing In Results
Each team shall submit exactly one copy of the
Follow the handin instructions detailed in the
Project FAQ to submit
your portfolio into the afs handin directory. Be sure you follow the required
format for the directory structure of the portfolio and its
location in the handin directories.
Be sure to follow ALL
the portfolio guidelines detailed in the Portfolio Layout
Any submission that contains files with modification dates
after the project deadline will be considered late and subject
to a grade deduction (see course
page for more information).
If you don't already have an ECE account send e-mail to
email@example.com and Cc to requesting a course account for 18-649.
This is probably a new experience for most of you. We don't
expect perfection. We expect an honest, good-faith attempt to
complete the assignment, getting as much help as is appropriate
from your classmates and lab partners. We suggest you leave at
least a week of time to think about the requirements. There is not
too much writing for this project, but quite a lot of thinking.
If you stumble we'll make sure you get fixed up before the next
project segment. You'll be allowed to change the behaviors in
later labs for optimization and debugging, but you should give
this your best shot. (In particular, we expect that people will
take several project phases to create a good dispatcher, as some
things just can't be specified well without a lot of
Grading (110 points total):
Here's the minimum requirement
Grading will be based on providing a complete state chart design
for each control object for which you are responsible, and
documented traceability between the state chart transition arcs
and states and your group's requirements specification.
Consistency and coherence (your design must match your
requirements) are the two criteria we're looking for. We
will not be grading your new requirements specifications beyond
making sure that they match your state charts and are
time-triggered, but keep in mind that effort spent now in
producing a good design is likely to reduce the amount of time you
will spend during unit and integration testing. So, it's a good
idea to make updates as you go.
This assignment counts as one team grade.
The grading rubric for this assignment is available here. Please
note that the grading rubric is only a general guideline and that
you are still responsible for all the details in the
writeup. If the grading rubric and the project writeup
conflict, the project writeup takes precedence. If you find
a conflict, please let us know by sending mail to the staff list.
Grading will be as follows:
- 15 points for requirements
- These points are awarded if your requirements are
- 35 points for statecharts. There are seven control
objects, so each state chart is worth 1/7 of these points. Each
member must do at least one statechart.
- 35 points for traceability. Each control object is
worth 1/7 of these points. For each control object, half of its
points are for complete forward traceability (Requirements to
States/Transitions), and the other half are for complete
backward traceability (States/Transitions to
Requirements). Each member must do at least one object
worth of traceability.
- 5 points for including a list of which points
corresponding to which tasks were primarily completed by each
team member (every point must be assigned to a specific team
member). AND, an entry in the Improvements
Log that tells us what can be improved about this
project. If you encountered any minor bugs that we haven't
already addressed, please mention them so we can fix them. If
you have no suggestions, say so in your entry for this project.
- 20 points for completing a peer
all 7 state charts . Each
member must do at least one review on a different state
Each team member must satisfy the minimum stated per-member
requirements. Team members who omit any required per-member
activity will receive a zero contribution grade.
Course home page