Finite State Machines, Flow Charts, and State Tables

Let's Make Robots Tutorials
1

State_Machine_1_-_Command_Based_Motion_Control.jpg
State_Machine_1_-_Command_Based_Motion_Control.jpg777×752 48.1 KB

My friend Jon Hylands had asked a simple question the other day as to whether I used Finite State Machines in my code. 

 

 I quipped back "Of course! Is there any other way?" 

 

But that got me to thinking... Was this always the case?  And where did trial and error coding end and planned FSM begin?  In discussions with a few other Hobby Roboticists, it became evident that the concept of a "Finite State Machine" was not fully clear.

 

The Academics in the group (who probably wouldn't read my tripe anyway) would tell you that a Finite State machine is " a mathematical model of computation used to design both computer programs and sequential logic circuits. It is conce......"   blah blah blah......

 

 

 Flow chart and a set of tables!    A finite state machine is simply a flow chart that follows a table of possible states that something can be in, provided the appropriate inputs.

 

I know many of us, myself included start off small projects just stringing pieces of code together to "get a result".  But very soon into the project you realize that you need to define the parameters of operation. 

 

For instance, in a very simple "Object Avoidance Robot"  that just wanders around and makes sure it doesn't hit things, there is still a State Machine to follow. 

 

 

Following the above routine, you should be able to wander until your battery dies...  Not very smart, not very useful, but predictable.

 

Even if you have a "Fully Manual Control" Robot, ie: you have some means of providing motion commands and expect it to react in kind,  you likely still have some kind of logic flow (State Machine) running to manage this motion.

 

For  instance something as "Simple" as a "Move Forward to position X,Y" command might *really* look like this:

 

 

When you start drawing out the various "states" of your Robot:

  • Stopped
  • moving forward - forward path clear - left side clear - right side clear
  • moving forward - obstacle in distance - left side clear - right side clear
  • moving forward - obstacle in near - left side clear - right side clear
  • moving forward - forward path clear - left side blocked - right side clear
  • moving forward - obstacle in distance - left side blocked - right side clear
  • moving forward - obstacle in near - left side blocked - right side clear
  • etc...

You will realize just how convoluted this can get... This is where a "State Table" comes in handy.

 

Turn each question into a Yes or No, True or False.  Don't ask "how far is it to the obstacle?"  but rather "Is there an obstacle within 12cm?" 

 


In this table, we are simply looking forward, not side to side.  Is our path clear, or is there an object present, distant or near, and is our compass heading on target or drifting Clockwise or Counter Clockwise.

The answers to these Boolean states will drive the left and right wheel Direction and Speed.

 

Creating State Tables for your various routines will help you better understand the expected outcomes based on inputs.  You may suddenly understand why your Robot keeps getting trapped in that corner!

 

 

 

References:

http://playground.arduino.cc/Code/FiniteStateMachine

http://en.wikipedia.org/wiki/Finite-state_machine

 

2

And guess what im learning

And guess what im learning about in my Embedded system course at the moment … FSM (Finite State Machines) and my next lab test will be based on the  implementation and use of this … have to admit takes a bit of understanding but im generally slow at picking things up but hopefully going over and over the material again and again it will sink in.

3

Best of luck!

I think what I was trying to get at most in the article was that Planning, even a quick worflow on a napkin will help you in the long run have a goal and direction for your code.  As opposed to merely coding routines until something works.

 

Lay out what you want the bot to do in different scenarios, and then define what inputs are required to cause those actions. 

 

 

4

in my old time, I am not so

in my old time, I am not so young anymore, we called that process synopsis diagram or process flow, its waht I did on the beginning of thinking my robot, before buy or build something, just like you say “on the napkin”

5

If you want to see a very

If you want to see a very simple FSM-based robot controller that I am currently working on (written in Python), you can look here:

https://github.com/JonHylands/uCee-py/blob/master/memzip_files/src/uCee.py

This includes the implementation for the Finite State Machine itself, which is a port of one I found for Arduino a while back. The actual “moving the robot” state machine is only two states, although I could break it up into a few more simpler states if I wanted to.

The key to using a FSM to control a robot is the main loop is running all the time. My FSM update function gets called (on this robot) 10x per second. All the sensors get read 10x per second. There are absolutely no delays that would slow down the main loop below that 10Hz cycle.

6

I ws SO hoping you would weigh in on this one.

You didn’t let me down.   Thank you.

 

(Mind you, you beat me to the punch, as my next update was going to talk about using timers or interrupts to initiate activities such as the motor PID loop, Serial Communications,  or Sensor Reading and putting a complete ban on the use of delay() )

edit:   Holy cr@p Jon!  This is the cleanest python code I’ve ever read!   Top to bottom, I just get it.  Dude… you humble me.