Learning objective: hands-on experience with statecharts; experience
responding to a requirements change with a statechart change; get an idea what
design drawing tools are available; low-stakes chance to find out if you'll
have troubles with your project statechart. This homework is intended to be
done BEFORE the project to get you started in the right direction.
Create a statechart for a maze-solving robot with the below properties. Be
sure that your statechart has an initialization arc, a number of states, an
action for each state, and guard conditions on each transition.
Consider a maze-solving robot that uses the left-hand-rule approach to
solving a maze. A person using this rule would extend their left hand and walk
while keep it touching the wall at all times, turning as required to follow the
wall.
However, our turtle-bot doesn't have a "left hand," and instead
only has a front bumper. We assume that the front bumper can detect the wall
without the need for the turtle bot to actually move (for example, it is a
single forward-facing ultrasonic distance sensor with a range of less than one
square size). Thus, implementing a left-hand-rule approach requires a step of
turning left to see if the wall is there, and then either proceding or turning
again depending upon whether the wall was sensed.
The turtle bot has the following movement capabilities. These are the ONLY
permitted actuator outputs that can be set by states in the statechart. The
system can only perform one action per time step, and can only be in one state
per time step. (This is a fully synchronous state machine, with the time step
equalling the time taken by the robot to turn or move, which we assume is the
same for each possible action.)
LEFT: Turn left 90 degrees
RIGHT: Turn right 90 degrees
MOVE: Move forward one square in a maze grid
STOP: Stay still
The turtle bot has the following input sensing capabilities:
BUMP: Detect whether a wall is immediately in front of the turtle.
Possible values: {true, false}. It is preferable to assume that the BUMP sensor
is measured after any turn or movement has been performed in that
movement cycle.
GOAL: Detect whether the turtle is in the goal square (i.e., maze
goal has been reached): Possible values: {true, false}
This means that one turtle time step includes the following:
After performing the move action, read the BUMP sensor.
After performing the move action, read the GOAL sensor.
Solving a maze is subject to the following constraints:
The maze is an NxM size rectangular grid, for example a standard chess
board would be an 8x8 grid (64 squares, with walls at some square boundaries
but not others).
You have no information as to where in the grid the turtle starts, and
where in the grid the goal square is. (This means you have to book-keep
movement and you can't exploit any knowledge about where the rest of the maze
might be.)
Each statechart transition takes one time step, including same-state
default transitions.
The turtle is only permitted to make exactly ONE of its listed movement
capabilities at each time step. It should correctly process both input sources
at each time step. (We stress this because some prior-year projects tried to
rotate 360 degrees and sample all four walls in a single time step. The default
code lets you do this, but later on this constraint will be actively enforced
as we improve the simulation framework's representation of real world
constraints.)
Maze walls are between squares. This implies that each square is surrounded
by 0, 1, 2, 3, or 4 walls. (If trapped inside 4 walls, movement is not
possible.)
The turtle displays movements in keeping with the left-hand-rule or
right-hand-rule approach to maze solving. (This will change for future
projects, but do this for now to keep it simple.)
The turtle must stay still once it has reached the goal square (i.e., it
must execute only STOP move actions when on the goal square).
The output of this exercise should be a well formed statechart. Do NOT write
code to implement the statechart. Paste the statchart onto a slide using the
usual naming convention.
It is OK to take a photo of a hand-written or other diagram and paste it
into the statechart for in-class exercises. Drawing tools are highly
recommended, and in some cases required, for homeworks and project work. For
now, don't spend a lot of time worrying about tools if you don't already have a
favorite tool.
Here's a video showing how the turtle should move. (View directly on YouTube
here: https://youtu.be/xifVOQs9ZEc )
Follow these rules for your statechart:
Give every state a number/identifier (S1, S2, etc.) and a name (IDLE,
etc.). For example: "S1. IDLE"
List side effects for every state. Side effects such as output values and
changes to state variables are unconditional.
That means each state has the same side effect all the time rather than a
side effect based on some condition. (If you have a conditional assignment, you
need to add more states to get rid of the condition.)
It's OK to have unconditional algorithmic side effects. That means
"add one minute to alarm time" is OK, but "add one minute to
alarm time if button is depressed" is not OK, because the "if"
makes it conditional. If you want a conditional effect you need to break the
true/false conditions into two different states.
You can have either comparisons or a "true" guard for arcs, but
no side effects on arcs. (i.e., it's a
Moore state machine).
Note that if an exit arc has a "true" guard condition the system
will remain in the originating state for exactly one periodic cycle, and exit
for the next cycle.
You can omit "stays in same state" arcs if they are uninteresting
since the default is to stay in the same state.
Here are some style rules to keep everyone on the right path:
You may NOT add additional 1-bit or boolean state variables. We want you to
make one big statechart so you can get the hang of working with medium-large
statechart, even though in practice you might break this into parallel
statecharts.
This applies to later assignments when you are writing code rather than
this homework, but keep this rule in mind starting with this exercise: You may
NOT use an enum or equivalent for encoding state information EXCEPT for state
information explicitly represented in the statechart. (i.e., the enum should
correspond to the states you're drawing in the diagram -- no hidden, undrawn
states buried in an enum).
It is OK to test for equality/inequality of state variables that have more
than 1 bit of value.
If you need to create a holding variable for a more or less continuous
value of state value (e.g. X or Y position in the maze) that's OK. But do this
to support computations, not hide states from the statechart.
13-1. Create two variants: one with a left-hand-rule and one with a
right-hand-rule maze solving heuristic.
13-1a. Find a statechart software drawing tool to use for this homework
question and tell us which one you used. There are a number of web-based tools.
(See supplemental reading section.) Hand-drawn statecharts and freehand paint
programs are NOT acceptable. While you can use powerpoint, we suggest trying to
find something that is smarter about manipulating boxes, arrows, and so on.
(The point of this question is for you to get some familiarity with available
tools, even though we realize that the tool learning curve might take more time
than drawing by hand.)
13-1b. Define and draw the states for the robot. Hint: start with a
"goal" state, add a "move" state, and go from there. Add
additional states that might be needed to keep track of history. Draw a state
diagram with each state causing a particular robot behavior to be performed for
one time unit/one "step" of robot movement.
13-1c. Add arcs to your statechart to fully define left-hand-rule behavior.
Each arc guard shall be specified, and should be either "true"
(always executed) or based on the state of one of the sensor inputs (e.g.,
bump). Partial credit will be awarded at TA discretion. Make this drawing of
both states + arcs separate from the answer to the previous question part (on a
separate slide) for grading purposes, even though it will be the same states.
13-1d. Re-draw the statechart for right-hand rule behavior. This means
you'll have three slides in a sequence: just the states; left-hand-rule; right
hand rule, and they should differ ONLY in the arcs. (There are other changes
you might make instead, but we want you to change arcs to see how that works
out.)
13-1e. How many arcs did you have to change for right-hand rule behavior?
How do you think this experience compares with changing the project code (or
will compare, depending upon whether you've made that change to the project
code)?
RUBRIC:
Answers for questions 13-1, five slides, one per question part.
(there are many others, so do a web search and pick one you like
Many campus cluster machines have Visio if you prefer that tool. Stay away
from the evil UML templates -- just use it for boxes and arrows. (If someone
finds a great tool we'll list it here for next time the class is taught.)
If you want a good example of a flowchart design that should be a
statechart design (i.e., why flowcharts can be a REALLY bad idea), look at
figures 9-12B (figure sheets 6-9) of:
https://www.google.com/patents/US4715786