Search This Blog

Wednesday, 26 February 2014

Of Finite State Machines and Robotics...

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