### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# Finite State Machine

Introduction to Finite State Machines; Maze-solving algorithms
by

## Amer Abbas

on 26 October 2014

Report abuse

#### Transcript of Finite State Machine

FSE
A four-way intersection has red/green traffic lights that are controlled with timers.

Behavior:
Traffic can only move in one direction at a time: NS or EW.
http://www.mountvernonnews.com/local/11/05/14/image-gallery
What We're Learning Today
1 To know what a Finite State Machine

2 What is the purpose of a Finite State Machine

3 How a Finite State Machine can be represented
Know what Transitions & States are
EW
green
NS
red
EW
red
NS
green
Timer Expired
Timer Expired
Traffic Light Controller
We can represent the system graphically by using a
state transition diagram
.
Nodes = States
Edges = Input
Finite State Machine
A model of the discrete dynamics of a system that has a finite number of discrete states.
Transitions between states are caused by events, such as:
The expiration of a timer
A change in a sensor
State Table
Online: Right-Hand Rule
Online: Tremaux's algorithm
Current State
Event
Next State
EW
green
/NS
red
EW
red
/NS
green
Timer Expired
Timer Expired
EW
green
/NS
red
EW
red
/NS
green
Q7 A Garage Door
Opening System
If the door is closed and I press the button, the door begins to move up.

When it reaches the top, the door activates a limit switch and stops.

If the door is open and I press the button, the door begins to move down.

When it reaches the bottom, the door activates a limit switch and stops.
States:
Door closed
Door opening
Door open
Door closing
Events:
Button pressed
Limit switch tripped
Implementing a Finite-State Machine
while (true)
event = GetEvent()
if (state == closed AND event == button_press)
open_door()
state = opening
else
if (state == opening AND event == limit_switch)
stop_door()
state = open
else
if (state == open AND event == button_press)
close_door()
state = closing
else
if (state == closing AND event == limit_switch)
stop_door()
state = closed
This is pseudocode, a mix of natural language and typical programming language constructs without the details of language-specific syntax.
The Maze Project
autonomously
traverse the maze

Use an
online
algorithm for the solution

Points will be given based on maze completion
Starting from the entrance reach the end of the maze and return to start

Extra credit will be provided for fastest times among those who fully complete the maze

More details to come in Lab 10
Our Autonomous Robot
Offline:
All data must be gathered/entered before the start of algorithmic processing

Online:
Data will continue to be added as algorithmic execution progresses (this will be used in the maze)
Offline vs Online Algorithms
Offline vs Online Algorithms
FSM: Right-Then-Left Algorithm
Right-Then-Left VPL
FSM: Wall Following algorithm
Forward
???
???
Bump
detected
action
complete
wall too far
action complete
Our Autonomous Robot
DistanceMeasured < rightDistance
DistanceMeasured >= rightDistance
Since you now have this code, you can't use this algorithm for your project...
Finite State Machine
A finite state machine is a
Low Level
Logical System
which performs a specific job

Traffic Light System
A search function
Spell Checkers
Grammar Check
Automatic Door
Finite State Machine
is represented by a Diagram
Writing

which explains what is happening
Arrows which
An example of a FSM Diagram
States
Transition
There are 4 states
>Current State
>Input
>Next State
>Action/Output
Door Closing
Door Open
Limit Tripped
Button Pressed
Door Closed
Door Opening
Button Pressed
Limit Tripped
States:
Door closed
Door opening
Door open
Door closing
Events:
Button pressed
Limit switch tripped
the transitions are events

like triggers

eg if button x is pressed
if button y is pressed